การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์โดยใช้เอเจนต์ (Agent-Based Multi-Objective Optimization) — การค้นหาแบบกระจายศูนย์ผ่านวัตถุประสงค์ที่แข่งขันกัน
- ผู้เสนอ
- Bonabeau, Dorigo, Theraulaz; Coello Coello et al.
- ปี
- 1990s–2000s
- ประเภท
- Simulation-driven multi-objective search
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์โดยใช้เอเจนต์ (Agent-based multi-objective optimization, ABMOO) เป็นการฝังเอเจนต์อิสระ (autonomous agents) ไว้ในสภาพแวดล้อมจำลอง และพัฒนาพฤติกรรมหรือพารามิเตอร์ของเอเจนต์เหล่านั้นเพื่อหาค่าที่เหมาะสมที่สุดสำหรับสองวัตถุประสงค์ที่ขัดแย้งกันหรือมากกว่านั้นไปพร้อมๆ กัน ซึ่งจะให้ผลลัพธ์เป็นแนวหน้าของพาเรโต (Pareto-efficient frontier) แทนที่จะเป็นค่าที่เหมาะสมที่สุดเพียงค่าเดียว วิธีนี้เหมาะสมกับระบบปรับตัวที่ซับซ้อน (complex adaptive systems) ซึ่งวัตถุประสงค์เกิดขึ้นจากปฏิสัมพันธ์ในระดับจุลภาค (micro-level interactions) มากกว่าที่จะมาจากสมการรูปแบบปิด (closed-form equations)
แนวคิดเบื้องหลังวิธีการ
แทนที่จะเขียนฟังก์ชันวัตถุประสงค์ส่วนกลางเพียงฟังก์ชันเดียว ABMOO ช่วยให้กลุ่มของเอเจนต์ที่ปฏิสัมพันธ์กันสำรวจปริภูมิคำตอบ (solution space) ผ่านกฎเกณฑ์ระดับท้องถิ่น (local rules) และพฤติกรรมที่เกิดขึ้นเอง (emergent behavior) เอเจนต์แต่ละตัวแทนคำตอบที่เป็นไปได้หรือผู้มีอำนาจตัดสินใจ ระบบจะถูกรันไปข้างหน้าในการจำลอง ผลลัพธ์จะถูกวัดในแต่ละวัตถุประสงค์ และกลไกการคัดเลือกแบบพาเรโตจะรักษาคำตอบที่ไม่ถูกครอบงำ (non-dominated solutions) ให้คงอยู่ข้ามรุ่น เนื่องจากภูมิทัศน์ความเหมาะสม (fitness landscape) ถูกประเมินผ่านการจำลอง ABMOO จึงสามารถจัดการกับฟังก์ชันวัตถุประสงค์ที่ไม่เป็นเชิงเส้น (non-linear) สุ่ม (stochastic) และขึ้นอยู่กับเส้นทาง (path-dependent) ซึ่งยากต่อการวิเคราะห์ ผลลัพธ์ที่ได้คือแนวหน้าพาเรโตที่หลากหลาย ซึ่งแสดงให้เห็นโครงสร้างการแลกเปลี่ยน (trade-off structure) ที่สมบูรณ์ระหว่างเป้าหมายที่แข่งขันกัน
ประวัติศาสตร์
การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์โดยใช้เอเจนต์ (ABMOO) เกิดขึ้นในช่วงปลายทศวรรษ 1990 และต้นทศวรรษ 2000 เมื่อนักวิจัยได้รวมกรอบการสร้างแบบจำลองโดยใช้เอเจนต์ (Agent-based modeling frameworks) (เช่น NetLogo, Repast, MASON) เข้ากับอัลกอริทึมวิวัฒนาการหลายวัตถุประสงค์ งานพื้นฐานโดย Bonabeau, Dorigo, และ Theraulaz เกี่ยวกับปัญญาฝูง (swarm intelligence) และโดย Coello Coello et al. เกี่ยวกับการหาค่าเหมาะสมที่สุดหลายวัตถุประสงค์แบบวิวัฒนาการ (evolutionary multi-objective optimization) ได้วางรากฐานทางทฤษฎีที่ถูกนำมารวมกันใน ABMOO แนวทางนี้ได้รับความนิยมในวิทยาศาสตร์ระบบที่ซับซ้อน การวางผังเมือง และการจัดการระบบนิเวศตลอดช่วงทศวรรษ 2000 และ 2010
ควรใช้เมื่อใด
ใช้ ABMOO เมื่อพฤติกรรมของระบบเกิดขึ้นจากปฏิสัมพันธ์ของเอเจนต์และไม่สามารถจับต้องได้ด้วยสมการรูปแบบปิด เมื่อวัตถุประสงค์สองข้อขึ้นไปขัดแย้งกันและผู้มีอำนาจตัดสินใจต้องการแนวหน้าการแลกเปลี่ยนที่สมบูรณ์ และเมื่อความสุ่มหรือการขึ้นอยู่กับเส้นทางทำให้การหาค่าที่เหมาะสมที่สุดเชิงวิเคราะห์เป็นไปไม่ได้ เหมาะสำหรับการออกแบบนโยบายในระบบสังคม นิเวศ หรือห่วงโซ่อุปทาน อย่าใช้เมื่อวัตถุประสงค์เดียวเพียงพอ เมื่อมีตัวแก้ปัญหาเชิงวิเคราะห์ที่ใช้เกรเดียนต์ (gradient-based solver) ที่รวดเร็ว เมื่อมีข้อจำกัดด้านงบประมาณการคำนวณอย่างรุนแรง (การประเมินการจำลองมีค่าใช้จ่ายสูง) หรือเมื่อวัตถุประสงค์สามารถรวมเป็นฟังก์ชันอรรถประโยชน์เชิงสเกลาร์ได้โดยไม่สูญเสียความเข้าใจ
ข้อจำกัดและข้อควรพิจารณา
- มีค่าใช้จ่ายในการคำนวณสูง: การประเมินความเหมาะสมแต่ละครั้งต้องรันการจำลองโดยใช้เอเจนต์เต็มรูปแบบ ทำให้ต้นทุนเพิ่มขึ้นตามขนาดประชากรและจำนวนรุ่น
- ผลลัพธ์มีความสุ่ม แนวหน้าพาเรโตอาจเปลี่ยนแปลงไปในแต่ละครั้งที่รัน จำเป็นต้องรันหลายครั้งอย่างอิสระและรวมผลลัพธ์ทางสถิติ
- ความถูกต้องของแบบจำลองขึ้นอยู่กับความสมจริงของกฎเอเจนต์และสภาพแวดล้อมการจำลองอย่างมาก ข้อมูลเข้าที่ผิดพลาดจะนำไปสู่แนวหน้าพาเรโตที่ทำให้เข้าใจผิด
- การปรับพารามิเตอร์ (ขนาดประชากร, อัตราการผสมข้าม, ความยาวการจำลอง) ไม่ใช่เรื่องง่ายและขึ้นอยู่กับปัญหาเฉพาะ
- การตีความและดำเนินการกับแนวหน้าพาเรโตที่มีมิติสูงยังคงเป็นความท้าทายหากไม่มีเครื่องมือสนับสนุนการตัดสินใจเพิ่มเติม
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จัดการกับภูมิทัศน์วัตถุประสงค์ที่ไม่เป็นเชิงเส้น เกิดขึ้นเอง และขึ้นอยู่กับเส้นทาง ซึ่งต่อต้านการกำหนดรูปแบบด้วยสมการปิด
- ให้ผลลัพธ์เป็นแนวหน้าพาเรโตที่สมบูรณ์ ทำให้ผู้มีอำนาจตัดสินใจมองเห็นการแลกเปลี่ยนได้อย่างชัดเจน แทนที่จะเป็นจุดเดียว
- รองรับความสุ่มได้อย่างเป็นธรรมชาติโดยการหาค่าเฉลี่ยของการจำลองซ้ำภายในขั้นตอนการประเมินความเหมาะสม
- ปรับขนาดให้รองรับประชากรเอเจนต์ที่หลากหลายซึ่งมีกฎพฤติกรรมและโทโพโลยีการโต้ตอบที่แตกต่างกัน
- เข้ากันได้กับอัลกอริทึมหลายวัตถุประสงค์ที่จัดตั้งขึ้น (NSGA-II, MOEA/D, MOPSO) ในฐานะตัวขับเคลื่อนการหาค่าเหมาะสมที่สุด
การประยุกต์ใช้
- การวางผังเมืองจราจรและการใช้ที่ดิน ซึ่งการแลกเปลี่ยนการลงทุนโครงสร้างพื้นฐาน (ต้นทุนเทียบกับความแออัดเทียบกับมลพิษ) เกิดขึ้นจากการตัดสินใจของเอเจนต์ผู้อยู่อาศัย
- การหาค่าเหมาะสมที่สุดของความยืดหยุ่นของห่วงโซ่อุปทาน (supply chain resilience) โดยการสร้างสมดุลระหว่างต้นทุน เวลานำ และความเสี่ยงจากการหยุดชะงักระหว่างเอเจนต์ซัพพลายเออร์ที่เชื่อมโยงกัน
- การจัดการระบบนิเวศเพื่อค้นหานโยบายการเก็บเกี่ยวหรือการอนุรักษ์ที่เหมาะสมที่สุดแบบพาเรโต ซึ่งสร้างสมดุลระหว่างผลผลิตทางเศรษฐกิจและวัตถุประสงค์ด้านความหลากหลายทางชีวภาพ
- การออกแบบมาตรการแทรกแซงโรคระบาด โดยการหาค่าที่เหมาะสมที่สุดของการแลกเปลี่ยนระหว่างความครอบคลุมของการฉีดวัคซีนกับกิจกรรมทางเศรษฐกิจ ผ่านการจำลองเอเจนต์ประชากร
- การจัดการโครงข่ายพลังงาน โดยการประสานงานเอเจนต์ผู้ผลิต-ผู้บริโภค (prosumer agents) เพื่อลดต้นทุน การปล่อยคาร์บอน และความไม่เสถียรของโครงข่ายไปพร้อมๆ กัน
- การประเมินนโยบายทางสังคม โดยการระบุชุดพารามิเตอร์นโยบายที่ปรับปรุงผลลัพธ์ด้านความเท่าเทียมและประสิทธิภาพร่วมกันในแบบจำลองสังคมโดยใช้เอเจนต์
วิธีการทำงาน
วิธีการทำงาน
ระบุวัตถุประสงค์ m ข้อ f_1, ..., f_m (ทั้งหมดต้องถูกทำให้มีค่าน้อยที่สุดหรือมากที่สุด) และตัวแปรตัดสินใจที่เข้ารหัสอยู่ในจีโนม (genome) หรือชุดกฎของเอเจนต์แต่ละตัว กำหนดข้อจำกัดและสภาพแวดล้อมการจำลองที่แปลงการตัดสินใจของเอเจนต์ให้เป็นผลลัพธ์ที่สังเกตได้
เริ่มต้นประชากรเอเจนต์ N ตัว ด้วยจีโนมที่สุ่มหรือตั้งต้นด้วยฮิวริสติก จีโนมของเอเจนต์แต่ละตัวเข้ารหัสพารามิเตอร์หรือกฎพฤติกรรมที่การหาค่าเหมาะสมที่สุดจะปรับแต่งข้ามรุ่น
รันการจำลองโดยใช้เอเจนต์ไปข้างหน้าเป็นเวลา T ขั้นตอน เมื่อสิ้นสุดการรันแต่ละครั้ง ให้อ่านค่าวัตถุประสงค์ f_1(x), ..., f_m(x) สำหรับเอเจนต์แต่ละตัวหรือสำหรับระบบโดยรวม อาจมีการทำซ้ำหลายครั้งและหาค่าเฉลี่ยเพื่อจัดการกับสัญญาณรบกวนแบบสุ่ม
ใช้การจัดอันดับแบบไม่ถูกครอบงำ (non-dominated sorting): จัดอันดับเอเจนต์ตามการครอบงำแบบพาเรโต เอเจนต์ x ครอบงำ y หาก x ไม่แย่กว่าในทุกวัตถุประสงค์ และดีกว่าอย่างน้อยหนึ่งวัตถุประสงค์ รักษาแนวหน้าที่ไม่ถูกครอบงำ (แนวหน้าพาเรโต) และใช้ระยะห่างความแออัด (crowding distance) หรือการมีส่วนร่วมของปริมาตร (hypervolume contribution) เพื่อรักษาความหลากหลาย
ใช้ตัวดำเนินการทางพันธุกรรม (การผสมข้าม, การกลายพันธุ์) หรือการอัปเดตความเร็วแบบฝูง (swarm-style velocity updates) กับประชากรที่รอดชีวิต เอเจนต์ผู้สมัครใหม่จะสืบทอด ผสม หรือรบกวนจีโนมของสมาชิกในแนวหน้าพาเรโต จากนั้นจึงกลับเข้าสู่การจำลองเพื่อประเมินผล
หลังจากถึงเกณฑ์การหยุด (งบประมาณรุ่น, การลู่เข้าของปริมาตร, หรือขีดจำกัดเวลาจริง) ให้ส่งคืนแนวหน้าพาเรโตสุดท้ายเป็นชุดคำตอบ แสดงภาพการแลกเปลี่ยนโดยใช้แผนภาพกระจายในปริภูมิวัตถุประสงค์ (objective-space scatter plots) หรือแผนภาพพิกัดขนาน (parallel-coordinate diagrams) เพื่อให้ผู้มีอำนาจตัดสินใจตีความ
ข้อผิดพลาดที่พบบ่อย
- การรันการจำลองซ้ำน้อยเกินไปต่อการประเมินเอเจนต์หนึ่งครั้งจะเพิ่มสัญญาณรบกวนและทำให้การจัดอันดับแบบพาเรโตเสียหาย — ควรทดสอบความเพียงพอของการจำลองซ้ำก่อนเสมอ
- การลู่เข้าก่อนเวลาอันควรสู่บริเวณที่แคบของแนวหน้าพาเรโตเนื่องจากกลไกความหลากหลายไม่เพียงพอ ให้ใช้การจัดอันดับระยะห่างความแออัดหรือการเลือกตามปริมาตรอย่างชัดเจน
- การปะปนวัตถุประสงค์ของการหาค่าเหมาะสมที่สุดกับแบบจำลองการจำลองเอง ตรวจสอบให้แน่ใจว่ากฎของเอเจนต์แสดงถึงระบบจริง ไม่ใช่ผลลัพธ์ที่ต้องการ
- การละเลยข้อจำกัดด้านงบประมาณการคำนวณและการระบุขนาดประชากรหรือจำนวนรุ่นที่ไม่สามารถทำได้สำหรับเวลาการรันการจำลอง
- การนำเสนอแนวหน้าพาเรโตดิบแก่ผู้มีอำนาจตัดสินใจโดยไม่มีการกรองหรือการแสดงภาพสนับสนุนการตัดสินใจ ซึ่งนำไปสู่ภาวะวิกฤตในการวิเคราะห์
คำถามที่พบบ่อย
ABMOO แตกต่างจากอัลกอริทึมพันธุกรรมหลายวัตถุประสงค์มาตรฐาน (standard multi-objective genetic algorithm) อย่างไร
ใน MOEA มาตรฐาน การคำนวณความเหมาะสมจะทำเชิงวิเคราะห์หรือผ่านฟังก์ชันที่รวดเร็ว ใน ABMOO การคำนวณความเหมาะสมทำได้โดยการรันการจำลองโดยใช้เอเจนต์เต็มรูปแบบ ทำให้การประเมินแต่ละครั้งมีค่าใช้จ่ายสูงกว่ามาก แต่ช่วยให้สามารถจัดการกับภูมิทัศน์วัตถุประสงค์ที่ขึ้นอยู่กับพลวัตที่เกิดขึ้นเอง การโต้ตอบ และความสุ่ม
อัลกอริทึมหลายวัตถุประสงค์ใดที่ทำงานได้ดีที่สุดในฐานะตัวปรับค่าเหมาะสมที่สุดใน ABMOO
NSGA-II เป็นที่นิยมใช้มากที่สุดเนื่องจากการจัดอันดับแบบไม่ถูกครอบงำและระยะห่างความแออัด MOEA/D และ MOPSO ก็เป็นที่นิยมเช่นกัน การเลือกขึ้นอยู่กับรูปร่างและมิติของแนวหน้าพาเรโต ไม่มีตัวเลือกที่ดีที่สุดสากล — ควรทดสอบกับชุดข้อมูลขนาดเล็กก่อน
ฉันควรรันการจำลองซ้ำกี่ครั้งต่อการประเมินเอเจนต์หนึ่งครั้ง
เพียงพอที่จะลดสัญญาณรบกวนเพื่อให้การเปรียบเทียบการครอบงำแบบพาเรโตเชื่อถือได้ สูตรสำเร็จที่ใช้กันทั่วไปคือรันจนกว่าสัมประสิทธิ์ของการแปรผัน (coefficient of variation) ของแต่ละวัตถุประสงค์จะต่ำกว่า 5–10% ซึ่งอาจต้องใช้การจำลองซ้ำ 10–50 ครั้ง ขึ้นอยู่กับความสุ่มของระบบ
ABMOO สามารถจัดการกับวัตถุประสงค์มากกว่าสองข้อได้หรือไม่
ได้ แต่ประสิทธิภาพจะลดลงเมื่อจำนวนวัตถุประสงค์เพิ่มขึ้น (ปัญหาของมิติในเรื่องการครอบงำแบบพาเรโต) หากมีวัตถุประสงค์มากกว่าสามข้อ ให้พิจารณาอัลกอริทึมสำหรับวัตถุประสงค์จำนวนมาก (many-objective algorithms) เช่น NSGA-III หรือ MOEA/D และใช้เทคนิคการแสดงภาพลดมิติ (dimensionality-reduction visualization techniques) สำหรับแนวหน้าผลลัพธ์
เมื่อใดที่ฉันควรเลือกการหาค่าที่เหมาะสมที่สุดแบบทนทาน (robust optimization) แทน ABMOO มาตรฐาน
เมื่อสภาพแวดล้อมการจำลองเองมีความไม่แน่นอน (ความไม่แน่นอนของพารามิเตอร์, ความไม่แน่นอนของโครงสร้าง) ให้ใช้รูปแบบที่ทนทานซึ่งประเมินเอเจนต์ภายใต้สถานการณ์แวดล้อมหลายแบบ และหาค่าที่เหมาะสมที่สุดสำหรับกรณีที่แย่ที่สุด (worst-case) หรือประสิทธิภาพพาเรโตที่คาดหวัง (expected Pareto performance) แทนที่จะเป็นแนวหน้าแบบกำหนดค่าเดียว
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Bonabeau, E., Dorigo, M., & Theraulaz, G. (2002). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.
ISBN: 9780195131598คัดลอกแล้วCoello Coello, C. A., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems (2nd ed.). Springer.
ISBN: 9780387332543คัดลอกแล้ว