การปรับให้เหมาะสมด้วยวิธีฝูงมดแบบเอเจนต์ — ปัญญาฝูงสำหรับการแก้ปัญหาเชิงการจัดหมู่และการจำลอง
- ผู้เสนอ
- 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 และแบบยืดหยุ่นที่เอเจนต์แสดงถึงเครื่องจักรหรืองาน
- ปัญหาการพับโปรตีนและการจัดเรียงลำดับชีวสารสนเทศที่กำหนดเป็นกราฟการเดินทาง
- การวางแผนเส้นทางอพยพในการจำลองเมืองแบบเอเจนต์พร้อมการสร้างแบบจำลองฝูงชนแบบไดนามิก
วิธีการทำงาน
วิธีการทำงาน
กำหนดปัญหาการปรับให้เหมาะสมเป็นกราฟการสร้าง โดยที่โหนดแสดงถึงองค์ประกอบของคำตอบ และขอบมีระดับฟีโรโมนและค่าความน่าปรารถนาเชิงฮิวริสติก ระบุจำนวนเอเจนต์ m, อัตราการระเหย rho, พารามิเตอร์อิทธิพล alpha (ฟีโรโมน) และ beta (ฮิวริสติก) และเกณฑ์การหยุด
วางเอเจนต์มด m ตัวที่โหนดเริ่มต้นที่สุ่มเลือกหรือเลือกตามหลักฮิวริสติก กำหนดค่าเริ่มต้นของรอยฟีโรโมน tau_ij ทั้งหมดให้เป็นค่าคงที่เล็ก ๆ tau_0 เพื่อป้องกันอคติก่อนกำหนด เอเจนต์แต่ละตัวจะรักษารายการต้องห้าม (tabu list) หรือคำตอบที่กำลังสร้างของตนเอง
เอเจนต์แต่ละตัวจะวนซ้ำผ่านกราฟ โดยเลือกองค์ประกอบถัดไป 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}หลังจากที่เอเจนต์ทั้งหมดสร้างคำตอบเสร็จสิ้น ให้ประเมินความเหมาะสมของคำตอบแต่ละรายการ อัปเดตฟีโรโมน: ระเหยรอยทั้งหมดด้วยปัจจัย (1-rho) จากนั้นเสริมสร้างขอบที่ใช้โดยคำตอบที่ดีด้วย Delta_tau_ij^k ที่เป็นสัดส่วนกับคุณภาพของคำตอบ อาจใช้การดำเนินการของ daemon เช่น การเสริมสร้างค่าที่ดีที่สุดทั่วโลก
สูตร
\tau_{ij} \leftarrow (1-\rho)\tau_{ij} + \sum_{k=1}^{m} \Delta\tau_{ij}^kทำซ้ำรอบการสร้างและอัปเดตจนกว่าจะถึงเกณฑ์การหยุด (จำนวนการวนซ้ำสูงสุด การตรวจจับการหยุดนิ่ง หรือคุณภาพเป้าหมาย) ส่งคืนคำตอบที่ดีที่สุดที่พบในทุกเอเจนต์และทุกการวนซ้ำ
ข้อผิดพลาดที่พบบ่อย
- การตั้งค่า 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 เมื่อปัญหาเปลี่ยนแปลงแบบไดนามิก ทำให้ปรับตัวได้ดีกว่าวิธีการที่อิงการเริ่มต้นใหม่ อย่างไรก็ตาม ความเร็วในการประเมินต่อมดต้องเร็วพอที่จะดำเนินการวนซ้ำให้เสร็จสิ้นภายในงบประมาณเวลาตอบสนอง
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Dorigo, M., Stutzle, T. (2004). Ant Colony Optimization. MIT Press, Cambridge, MA.
ISBN: 9780262042192คัดลอกแล้วBonabeau, E., Dorigo, M., Theraulaz, G. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York.
ISBN: 9780195131581คัดลอกแล้ว