Skip to content
กลับไปยังผลการค้นหา

การปรับให้เหมาะสมด้วยวิธีฝูงมดแบบเอเจนต์ — ปัญญาฝูงสำหรับการแก้ปัญหาเชิงการจัดหมู่และการจำลอง

ผู้เสนอ
Dorigo, M. and colleagues; agent-based framing developed in swarm intelligence community
ปี
1992-2004
ประเภท
Metaheuristic optimization — agent-based swarm simulation
กลุ่มวิธี
Simulation / optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การปรับให้เหมาะสมด้วยวิธีฝูงมดแบบเอเจนต์ (AB-ACO) จำลองมดแต่ละตัวเป็นเอเจนต์อิสระที่สร้างคำตอบอย่างน่าจะเป็นไปได้โดยการติดตามและทิ้งรอยฟีโรโมนบนกราฟการค้นหา ด้วยการเชื่อมโยงกฎพฤติกรรมระดับเอเจนต์เข้ากับสภาพแวดล้อมฟีโรโมนที่ใช้ร่วมกัน ระบบโดยรวมจะลู่เข้าสู่คำตอบคุณภาพสูงสำหรับปัญหาการจัดหมู่ที่ยากและปัญหาการปรับให้เหมาะสมที่ฝังอยู่ในการจำลอง โดยไม่ต้องมีการประสานงานจากส่วนกลาง

แนวคิดเบื้องหลังวิธีการ

อาณานิคมมดจริงจะค้นหาเส้นทางที่สั้นที่สุดไปยังอาหารโดยการเสริมสร้างเส้นทางที่ประสบความสำเร็จด้วยฟีโรโมน — เส้นทางที่ไม่ดีจะระเหยไปในขณะที่เส้นทางที่ดีจะดึงดูดมดมากขึ้น AB-ACO สะท้อนสิ่งนี้: มดเอเจนต์แต่ละตัวจะสำรวจพื้นที่คำตอบอย่างอิสระ โดยทิ้งฟีโรโมนที่เข้มข้นขึ้นเมื่อพบคำตอบที่ดีกว่า ตลอดการวนซ้ำหลายครั้ง ข้อมูลป้อนกลับแบบ stigmergic แบบกระจายจะรวมศูนย์การค้นหาของอาณานิคมรอบ ๆ พื้นที่ที่มีแนวโน้มดี เนื่องจากมดแต่ละตัวเป็นเอเจนต์ชั้นหนึ่งที่มีสถานะและกฎการตัดสินใจของตัวเอง กรอบการทำงานนี้จึงขยายไปสู่เอเจนต์ที่แตกต่างกัน สภาพแวดล้อมแบบไดนามิก และแบบจำลองการจำลองที่ภูมิทัศน์ความเหมาะสมเปลี่ยนแปลงไปตามกาลเวลาได้อย่างเป็นธรรมชาติ

ประวัติศาสตร์

การปรับให้เหมาะสมด้วยวิธีฝูงมด (Ant Colony Optimization) ได้รับการแนะนำโดย Marco Dorigo ในวิทยานิพนธ์ปริญญาเอกของเขาในปี 1992 และได้รับการจัดรูปแบบอย่างเป็นทางการร่วมกับ Stutzle ในปี 2004 มุมมองแบบเอเจนต์เกิดขึ้นจากกรอบการทำงานปัญญาฝูง (swarm intelligence) ที่กว้างขึ้น (Bonabeau, Dorigo, Theraulaz 1999) ซึ่งวางตำแหน่งมดเป็นเอเจนต์อิสระที่แสดงการประสานงานแบบ stigmergic การเชื่อมโยง ACO เข้ากับสภาพแวดล้อมการจำลองแบบเอเจนต์กลายเป็นที่โดดเด่นในการวิจัยด้านโลจิสติกส์ ห่วงโซ่อุปทาน และระบบหลายเอเจนต์ตลอดช่วงทศวรรษ 2000 และ 2010

ควรใช้เมื่อใด

ใช้ AB-ACO เมื่อเผชิญกับปัญหาการปรับให้เหมาะสมเชิงการจัดหมู่ (การกำหนดเส้นทาง การจัดตารางเวลา การมอบหมาย การออกแบบเครือข่าย) ที่พื้นที่การค้นหามีขนาดใหญ่เกินไปสำหรับวิธีการที่แม่นยำ และการค้นหาเชิงสุ่มแบบประชากรมีความเหมาะสม วิธีนี้จะโดดเด่นเมื่อปัญหาสามารถกำหนดเป็นกราฟการเดินทาง และเมื่อการประสานงานแบบกระจายและแบบเกิดใหม่เป็นที่ต้องการมากกว่าการควบคุมจากส่วนกลาง เหมาะอย่างยิ่งสำหรับปัญหาแบบไดนามิกหรือปัญหาที่ฝังอยู่ในการจำลองที่การประเมินความเหมาะสมเกี่ยวข้องกับการเรียกใช้การจำลองแบบเอเจนต์ หลีกเลี่ยงวิธีนี้สำหรับภูมิทัศน์การปรับให้เหมาะสมแบบต่อเนื่องที่ราบรื่น (วิธีการเกรเดียนต์จะเหนือกว่า) สำหรับปัญหาขนาดเล็กมาก (ตัวแก้ปัญหาที่แม่นยำเพียงพอ) หรือเมื่อไม่มีงบประมาณในการปรับพารามิเตอร์ฟีโรโมน — การปรับ alpha/beta/rho ที่ไม่ดีอาจนำไปสู่การลู่เข้าก่อนกำหนด

ข้อจำกัดและข้อควรพิจารณา

  • ประสิทธิภาพมีความไวต่อการเลือก alpha, beta และ rho; มักจะต้องมีการปรับพารามิเตอร์อย่างละเอียดหรือการปรับให้เหมาะสมแบบเมตา
  • ความเร็วในการลู่เข้าโดยทั่วไปจะช้ากว่าวิธีการแก้ปัญหาเดียว (เช่น tabu search) ในปัญหาแบบคงที่ที่มีโครงสร้างที่ชัดเจน
  • การหยุดนิ่งของฟีโรโมน — ที่เอเจนต์ทั้งหมดตามรอยที่ไม่เหมาะสมเดียวกัน — อาจเกิดขึ้นได้หากการระเหยช้าเกินไปหรือประชากรมีขนาดเล็กเกินไป
  • การรับประกันการลู่เข้าเชิงทฤษฎีมีอยู่ภายใต้เงื่อนไขที่จำกัดเท่านั้น; โดยทั่วไปจำเป็นต้องมีการตรวจสอบเชิงประจักษ์
  • หน่วยความจำและค่าใช้จ่ายในการสื่อสารของการรักษามีเมทริกซ์ฟีโรโมนทั่วโลกเพิ่มขึ้นตามจำนวนองค์ประกอบของคำตอบ

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • จัดการกับพื้นที่การค้นหาแบบไม่ต่อเนื่องและเชิงการจัดหมู่ได้อย่างเป็นธรรมชาติโดยไม่ต้องใช้ข้อมูลเกรเดียนต์
  • กรอบการทำงานแบบเอเจนต์ช่วยให้สามารถรวมเข้ากับแบบจำลองการจำลองได้โดยตรง โดยที่ความเหมาะสมของมดแต่ละตัวจะถูกประเมินโดยการเรียกใช้ตอนการจำลอง
  • การตอบรับเชิงบวกผ่านการเสริมสร้างฟีโรโมนช่วยให้เกิดการเพิ่มความเข้มข้นอย่างรวดเร็วรอบ ๆ คำตอบที่มีแนวโน้มดีเมื่อถูกค้นพบ
  • ประชากรของเอเจนต์ให้การขนานกันโดยนัยและความทนทานต่อค่าเหมาะสมที่สุดเฉพาะที่ผ่านการสำรวจพร้อมกันที่หลากหลาย
  • ปรับขนาดได้อย่างราบรื่นสำหรับปัญหาแบบไดนามิก: การระเหยของฟีโรโมนช่วยให้อาณานิคมสามารถปรับตัวได้เมื่อภูมิทัศน์ความเหมาะสมเปลี่ยนแปลงไป

การประยุกต์ใช้

  • การกำหนดเส้นทางยานพาหนะและการวางแผนโลจิสติกส์ที่มดเอเจนต์ค้นพบตารางการจัดส่งที่มีประสิทธิภาพ
  • โปรโตคอลการกำหนดเส้นทางเครือข่ายในการสื่อสารโทรคมนาคมที่มดสำรวจเส้นทางและทิ้งฟีโรโมนการกำหนดเส้นทาง
  • การปรับให้เหมาะสมห่วงโซ่อุปทานโดยการรวม AB-ACO เข้ากับแบบจำลองการจำลองเหตุการณ์ไม่ต่อเนื่องหรือแบบเอเจนต์
  • การจัดตารางเวลาการผลิตแบบ Job-shop และแบบยืดหยุ่นที่เอเจนต์แสดงถึงเครื่องจักรหรืองาน
  • ปัญหาการพับโปรตีนและการจัดเรียงลำดับชีวสารสนเทศที่กำหนดเป็นกราฟการเดินทาง
  • การวางแผนเส้นทางอพยพในการจำลองเมืองแบบเอเจนต์พร้อมการสร้างแบบจำลองฝูงชนแบบไดนามิก

วิธีการทำงาน

วิธีการทำงาน

1

กำหนดปัญหาการปรับให้เหมาะสมเป็นกราฟการสร้าง โดยที่โหนดแสดงถึงองค์ประกอบของคำตอบ และขอบมีระดับฟีโรโมนและค่าความน่าปรารถนาเชิงฮิวริสติก ระบุจำนวนเอเจนต์ m, อัตราการระเหย rho, พารามิเตอร์อิทธิพล alpha (ฟีโรโมน) และ beta (ฮิวริสติก) และเกณฑ์การหยุด

2

วางเอเจนต์มด m ตัวที่โหนดเริ่มต้นที่สุ่มเลือกหรือเลือกตามหลักฮิวริสติก กำหนดค่าเริ่มต้นของรอยฟีโรโมน tau_ij ทั้งหมดให้เป็นค่าคงที่เล็ก ๆ tau_0 เพื่อป้องกันอคติก่อนกำหนด เอเจนต์แต่ละตัวจะรักษารายการต้องห้าม (tabu list) หรือคำตอบที่กำลังสร้างของตนเอง

3

เอเจนต์แต่ละตัวจะวนซ้ำผ่านกราฟ โดยเลือกองค์ประกอบถัดไป j จากย่านใกล้เคียงที่เป็นไปได้ N_i^k ด้วยความน่าจะเป็น p_ij ที่เป็นสัดส่วนกับ tau_ij^alpha * eta_ij^beta ฮิวริสติก eta_ij เข้ารหัสคำแนะนำเฉพาะปัญหา (เช่น ระยะทางผกผัน) กฎเชิงสุ่มนี้จะสร้างสมดุลระหว่างการสำรวจกับการใช้ประโยชน์จากเกรเดียนต์ฟีโรโมนที่เรียนรู้

สูตร
p_{ij}^k = \frac{[\tau_{ij}]^\alpha [\eta_{ij}]^\beta}{\sum_{l \in N_i^k} [\tau_{il}]^\alpha [\eta_{il}]^\beta}
4

หลังจากที่เอเจนต์ทั้งหมดสร้างคำตอบเสร็จสิ้น ให้ประเมินความเหมาะสมของคำตอบแต่ละรายการ อัปเดตฟีโรโมน: ระเหยรอยทั้งหมดด้วยปัจจัย (1-rho) จากนั้นเสริมสร้างขอบที่ใช้โดยคำตอบที่ดีด้วย Delta_tau_ij^k ที่เป็นสัดส่วนกับคุณภาพของคำตอบ อาจใช้การดำเนินการของ daemon เช่น การเสริมสร้างค่าที่ดีที่สุดทั่วโลก

สูตร
\tau_{ij} \leftarrow (1-\rho)\tau_{ij} + \sum_{k=1}^{m} \Delta\tau_{ij}^k
5

ทำซ้ำรอบการสร้างและอัปเดตจนกว่าจะถึงเกณฑ์การหยุด (จำนวนการวนซ้ำสูงสุด การตรวจจับการหยุดนิ่ง หรือคุณภาพเป้าหมาย) ส่งคืนคำตอบที่ดีที่สุดที่พบในทุกเอเจนต์และทุกการวนซ้ำ

ข้อผิดพลาดที่พบบ่อย

  • การตั้งค่า rho ต่ำเกินไปทำให้เกิดการสะสมของฟีโรโมนที่ทำให้อาณานิคมติดอยู่ในค่าเหมาะสมที่สุดเฉพาะที่ตั้งแต่ต้นการทำงาน
  • การละเว้นองค์ประกอบฮิวริสติก (eta = 1) ทำให้เสียความรู้เฉพาะโดเมนและทำให้การลู่เข้าช้าลงในปัญหาที่มีโครงสร้าง เช่น TSP
  • การใช้เอเจนต์น้อยเกินไปจะลดความหลากหลาย; การใช้มากเกินไปจะเพิ่มต้นทุนการประเมินโดยไม่ได้รับคุณภาพที่เพิ่มขึ้นตามสัดส่วน — ปรับเทียบ m เทียบกับขนาดปัญหา
  • การสับสน AB-ACO กับ ACO มาตรฐาน: หากเอเจนต์ขาดสถานะส่วนบุคคล หน่วยความจำ หรือความแตกต่างทางพฤติกรรม แบบจำลองจะลดลงเหลือเพียง ACO ธรรมดา และกรอบการทำงานแบบเอเจนต์ก็ไม่เพิ่มมูลค่าใด ๆ
  • การประยุกต์ใช้ AB-ACO กับพื้นที่ต่อเนื่องโดยไม่มีการทำให้เป็นดิสครีตหรือขั้นตอนการฝังกราฟจะนำไปสู่ประสิทธิภาพที่ไม่ดี; ให้ใช้ตัวแปร ACO แบบต่อเนื่องแทน

คำถามที่พบบ่อย

AB-ACO แตกต่างจาก ACO มาตรฐานอย่างไร?

ACO มาตรฐานถือว่ามดเป็นตัวสร้างคำตอบเชิงสุ่มที่สามารถใช้แทนกันได้ซึ่งใช้เมทริกซ์ฟีโรโมนร่วมกัน AB-ACO จำลองมดแต่ละตัวอย่างชัดเจนว่าเป็นเอเจนต์อิสระที่มีสถานะพร้อมกฎพฤติกรรมส่วนบุคคล บทบาทที่อาจแตกต่างกัน และความสามารถในการโต้ตอบกับสภาพแวดล้อมการจำลอง — ทำให้กรอบการทำงานนี้มีความสมบูรณ์ยิ่งขึ้นสำหรับบริบทปัญหาแบบไดนามิกหรือแบบหลายเอเจนต์

โดยทั่วไปต้องใช้การวนซ้ำและเอเจนต์กี่ครั้ง?

ไม่มีคำตอบที่เป็นสากล จุดเริ่มต้นทั่วไปคือ m = 10-50 เอเจนต์ และ 100-500 การวนซ้ำสำหรับปัญหาขนาดกลาง ภูมิทัศน์ที่ใหญ่ขึ้นและซับซ้อนขึ้นต้องใช้มากขึ้น ควรตรวจสอบพล็อตการลู่เข้า (คำตอบที่ดีที่สุดเทียบกับการวนซ้ำ) เสมอเพื่อยืนยันการสำรวจที่เพียงพอ

AB-ACO สามารถจัดการกับปัญหาหลายวัตถุประสงค์ได้หรือไม่?

ได้ ส่วนขยายหลายวัตถุประสงค์ (เช่น MOPACO, Pareto-ACO) จะรักษาเมทริกซ์ฟีโรโมนแยกต่างหากสำหรับแต่ละวัตถุประสงค์ หรือใช้ Pareto dominance เพื่อนำทางการอัปเดต การกำหนดสูตรแบบเอเจนต์ยังสามารถติดตามวัตถุประสงค์ส่วนบุคคลของเอเจนต์และโปรไฟล์ความชอบได้อีกด้วย

การระเหยของฟีโรโมนคืออะไรและทำไมจึงสำคัญ?

การระเหยจะลดระดับฟีโรโมนทั้งหมดลงด้วยปัจจัย (1-rho) ในแต่ละการวนซ้ำ เพื่อให้แน่ใจว่าข้อมูลเก่าจะเสื่อมสลายและอาณานิคมสามารถปรับตัวได้ หากไม่มีการระเหย ฟีโรโมนจะสะสมอย่างไม่มีกำหนด ทำให้เกิดการลู่เข้าก่อนกำหนด อัตรา rho เป็นหนึ่งในพารามิเตอร์ที่สำคัญที่สุดในการปรับแต่ง

AB-ACO เหมาะสำหรับการปรับให้เหมาะสมแบบเรียลไทม์หรือแบบออนไลน์หรือไม่?

ด้วยความระมัดระวัง ก็ได้ เนื่องจากฟีโรโมนเข้ารหัสคุณภาพของคำตอบที่เรียนรู้ อาณานิคมจึงสามารถดำเนินการต่อจากเมทริกซ์ฟีโรโมนที่เริ่มต้นแบบ warm-started เมื่อปัญหาเปลี่ยนแปลงแบบไดนามิก ทำให้ปรับตัวได้ดีกว่าวิธีการที่อิงการเริ่มต้นใหม่ อย่างไรก็ตาม ความเร็วในการประเมินต่อมดต้องเร็วพอที่จะดำเนินการวนซ้ำให้เสร็จสิ้นภายในงบประมาณเวลาตอบสนอง

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Dorigo, M., Stutzle, T. (2004). Ant Colony Optimization. MIT Press, Cambridge, MA.

    ISBN: 9780262042192
    คัดลอกแล้ว
  2. Bonabeau, E., Dorigo, M., Theraulaz, G. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York.

    ISBN: 9780195131581
    คัดลอกแล้ว