การหาค่าเหมาะที่สุดด้วยอาณานิคมมดแบบหลายวัตถุประสงค์ (Multi-Objective Ant Colony Optimization: MOACO)
- ผู้เสนอ
- Gambardella, Taillard & Agazzi; Dorigo & Stützle
- ปี
- 1999
- ประเภท
- Population-based metaheuristic
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Multi-Objective Ant Colony Optimization (MOACO) คือ อัลกอริทึมเมตาฮิวริสติก (metaheuristic) แบบปัญญาฝูง (swarm-intelligence) ที่ขยายกรอบการทำงานของ Ant Colony Optimization แบบดั้งเดิม เพื่อหาค่าเหมาะที่สุดของวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองวัตถุประสงค์ขึ้นไปพร้อมกัน มดเทียมจะสร้างคำตอบที่เป็นไปได้ โดยมีเส้นทางฟีโรโมนและข้อมูลฮิวริสติก (heuristic information) เป็นแนวทาง ค่อยๆ สร้างคลังสะสมคำตอบที่เหมาะสมแบบพาเรโต (Pareto-optimal solutions) แทนที่จะลู่เข้าสู่คำตอบที่ดีที่สุดเพียงคำตอบเดียว
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงอาณานิคมมดที่กำลังหาอาหารในภูมิประเทศที่ไม่มีเส้นทางที่ดีที่สุดเพียงเส้นทางเดียว แต่เส้นทางต่างๆ จะมีการแลกเปลี่ยนระหว่างระยะทางกับความปลอดภัย หรือความเร็วกับพลังงาน มดแต่ละตัวจะปล่อยฟีโรโมนตามสัดส่วนคุณภาพของเส้นทางในหลายเกณฑ์พร้อมกัน เมื่อเวลาผ่านไปหลายชั่วอายุ อาณานิคมจะร่วมกันสร้างแผนที่ขอบเขตการแลกเปลี่ยน (trade-off frontier) หรือหน้าพาเรโต (Pareto front) โดยไม่ต้องบังคับการกำหนดน้ำหนักของวัตถุประสงค์ล่วงหน้า แนวคิดหลักคือ สติ๊กเมอร์จี (stigmergy) หรือการสื่อสารทางอ้อมผ่านฟีโรโมน สามารถเข้ารหัสข้อมูลคุณภาพแบบหลายวัตถุประสงค์ ทำให้สามารถประมาณพื้นผิวการแลกเปลี่ยนที่สมบูรณ์ได้อย่างเกิดขึ้นเอง (emergent approximation)
ประวัติศาสตร์
Ant Colony Optimization ถูกนำเสนอโดย Marco Dorigo ในวิทยานิพนธ์ปริญญาเอกปี 1992 และกำหนดเป็นทางการร่วมกับ Maniezzo และ Colorni การขยายผลแบบหลายวัตถุประสงค์เริ่มปรากฏในช่วงปลายทศวรรษ 1990 MACS-VRPTW ของ Gambardella, Taillard, และ Agazzi (1999) แสดงให้เห็นถึงอาณานิคมมดหลายอาณานิคมที่มุ่งเป้าไปที่วัตถุประสงค์ที่แตกต่างกัน กรอบการทำงานต่อมาโดย Doerner, Hartl และคนอื่นๆ ได้จัด MOACO เป็นกลุ่มวิธีอย่างเป็นทางการ และตำราปี 2004 ของ Dorigo และ Stützle ได้อธิบายเชิงอัลกอริทึมไว้เป็นมาตรฐาน MOACO ยังคงเป็นสาขาวิจัยที่ยังคงเคลื่อนไหว โดยมีการประยุกต์ใช้ในการจัดเส้นทางเครือข่าย ชีวสารสนเทศศาสตร์ และโลจิสติกส์ที่ยั่งยืน
ควรใช้เมื่อใด
ใช้ MOACO เมื่อปัญหามีวัตถุประสงค์ที่ขัดแย้งกันตั้งแต่สองวัตถุประสงค์ขึ้นไป มีปริภูมิคำตอบแบบผสม (combinatorial) หรือแบบไม่ต่อเนื่อง (discrete) (เช่น การจัดเส้นทาง การจัดตารางเวลา การออกแบบเครือข่าย) และไม่มีความชอบล่วงหน้าต่อวัตถุประสงค์ที่ชัดเจนซึ่งจะทำให้ต้องแปลงเป็นค่าสเกลาร์ อัลกอริทึมนี้มีความโดดเด่นในปัญหาด้านโลจิสติกส์ ห่วงโซ่อุปทาน และการจัดตารางการทำงาน (workflow scheduling) ที่ ACO ทำงานได้ดีกับวัตถุประสงค์เดียว หลีกเลี่ยง MOACO เมื่อปัญหาเป็นแบบต่อเนื่อง (continuous) และวิธีหาค่าเหมาะที่สุดแบบหลายวัตถุประสงค์ที่ใช้เกรเดียนต์ (gradient-based multi-objective methods) (เช่น NSGA-II ที่มีการเข้ารหัสแบบจริง หรือ Bayesian optimization) มีประสิทธิภาพมากกว่า เมื่อมีงบประมาณในการคำนวณจำกัดอย่างมาก เนื่องจาก MOACO ต้องการการประเมินจำนวนมาก หรือเมื่อต้องการหน้าพาเรโตที่แม่นยำสำหรับปัญหาที่การโปรแกรมแบบหลายวัตถุประสงค์ที่แม่นยำ (เช่น multi-objective MILP) สามารถแก้ไขได้
ข้อจำกัดและข้อควรพิจารณา
- ต้องมีการปรับแต่งไฮเปอร์พารามิเตอร์หลายตัวอย่างรอบคอบ (α, β, ρ, ขนาดอาณานิคม, ความจุคลัง) และความไวต่อการตั้งค่าเหล่านี้อาจสูง
- การลู่เข้าช้ากว่าตัวแก้ปัญหาแบบแม่นตรง (exact solver)สำหรับปัญหาขนาดเล็กที่มีโครงสร้างดี ซึ่งวิธีการโปรแกรมจำนวนเต็ม (integer programming) หรือการโปรแกรมพลวัต (dynamic programming) สามารถแก้ไขได้
- คุณภาพของการประมาณและระดับความหลากหลายของหน้าพาเรโตไม่ได้รับการรับประกัน ผลลัพธ์อาจแตกต่างกันไปในแต่ละครั้งที่ทำงาน เนื่องจากการสร้างคำตอบแบบสุ่ม
- การขยายใช้กับปริภูมิวัตถุประสงค์ที่มีมิติสูง (>3 วัตถุประสงค์) เป็นเรื่องยาก และอาจต้องใช้กลยุทธ์การแยกส่วน (decomposition strategies) แบบพิเศษ
- ไม่มีการพิสูจน์การลู่เข้าสำหรับกรณีปัญหาทั่วไป การรับประกันทางทฤษฎีมีจำกัดเมื่อเทียบกับการโปรแกรมเชิงคณิตศาสตร์
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จัดการกับปริภูมิคำตอบแบบผสมและแบบเรียงสับเปลี่ยน (permutation-based) ได้ตามธรรมชาติ ซึ่งวิธีการแบบไล่ระดับไม่สามารถทำได้
- สร้างหน้าพาเรโตโดยประมาณที่สมบูรณ์ในการทำงานครั้งเดียว ทำให้ผู้ตัดสินใจได้รับข้อมูลการแลกเปลี่ยนที่ชัดเจน
- ความหลากหลายของฝูงป้องกันการลู่เข้าก่อนกำหนดและสนับสนุนการสำรวจบริเวณพาเรโตที่ไม่เชื่อมต่อกัน
- หน่วยความจำฟีโรโมนให้การเรียนรู้โดยปริยายข้ามรอบการทำงาน ช่วยให้ใช้ประโยชน์ (exploitation) จากคำตอบดีๆ โดยไม่ละทิ้งการสำรวจ
- สามารถขนาน (parallelized) ได้ง่าย: อาณานิคมมดหลายอาณานิคม หรืออาณานิคมเฉพาะวัตถุประสงค์สามารถทำงานพร้อมกันได้
- ทนทานต่อลักษณะของปัญหา เช่น จุดเหมาะสมที่สุดเฉพาะที่ (local optima) หลายจุด
การประยุกต์ใช้
- การจัดเส้นทางยานพาหนะแบบหลายวัตถุประสงค์และการจัดตารางโลจิสติกส์พร้อมข้อจำกัดด้านเวลาและปริมาณบรรทุก
- การออกแบบโทโพโลยีเครือข่ายที่หาค่าเหมาะที่สุดของต้นทุน ความหน่วง และความน่าเชื่อถือพร้อมกัน
- การจัดตารางงานแบบยืดหยุ่น (flexible job-shop scheduling) ที่สมดุลระหว่างเวลาผลิตทั้งหมด (makespan) การใช้พลังงาน และการใช้เครื่องจักร
- ชีวสารสนเทศศาสตร์: การทำนายโครงสร้างโปรตีนและการเลือกคุณลักษณะสำหรับการจำแนกประเภทหลายป้าย (multi-label classification)
- การออกแบบห่วงโซ่อุปทานที่ยั่งยืน โดยหาค่าเหมาะที่สุดของต้นทุนทางเศรษฐกิจ การปล่อยคาร์บอน และเกณฑ์ทางสังคม
- การจัดตารางการทำงาน (workflow scheduling) แบบหลายวัตถุประสงค์ในสภาพแวดล้อมคลาวด์คอมพิวติ้ง
วิธีการทำงาน
วิธีการทำงาน
เริ่มต้นเมทริกซ์ฟีโรโมน (เมทริกซ์เดียวต่อหนึ่งวัตถุประสงค์ หรือเมทริกซ์ถ่วงน้ำหนักที่ใช้ร่วมกัน) ด้วยค่าคงที่ กำหนดข้อมูลฮิวริสติก η สำหรับแต่ละส่วนประกอบของคำตอบ สร้างคลังพาเรโตที่ว่างเปล่าเพื่อจัดเก็บคำตอบที่ไม่ถูกครอบงำ (non-dominated solutions) ที่พบระหว่างการค้นหา
มดแต่ละตัวสร้างคำตอบที่สมบูรณ์ทีละขั้นตอน โดยการเลือกส่วนประกอบของคำตอบตามความน่าจะเป็น ความน่าจะเป็นในการเปลี่ยนสถานะใช้ความเข้มข้นของฟีโรโมน τ และความน่าสนใจเชิงฮิวริสติก (heuristic desirability) η ที่ยกกำลังด้วยเลขชี้กำลัง α และ β สำหรับการปรับแต่ง รูปแบบ MOACO ที่แตกต่างกันจะกำหนดเมทริกซ์ฟีโรโมนต่อวัตถุประสงค์ หรือใช้น้ำหนักการแปลงเป็นสเกลาร์ (scalarization weights) ที่เปลี่ยนแปลงไปตามมดแต่ละตัว
สูตร
p_{ij}^k = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in \mathcal{N}_i^k} [\tau_{il}]^\alpha \cdot [\eta_{il}]^\beta}ประเมินคำตอบที่สร้างขึ้นแต่ละคำตอบด้วยฟังก์ชันวัตถุประสงค์ทั้งหมดพร้อมกัน ระบุความสัมพันธ์การครอบงำ (dominance relationship) กับสมาชิกในคลังที่มีอยู่: คำตอบหนึ่งจะครอบงำอีกคำตอบหนึ่ง หากคำตอบนั้นดีอย่างน้อยเท่ากันในทุกวัตถุประสงค์ และดีกว่าอย่างน้อยหนึ่งวัตถุประสงค์
อัปเดตคลังพาเรโตโดยการเพิ่มคำตอบที่ไม่ถูกครอบงำ และลบสมาชิกในคลังที่ถูกครอบงำโดยคำตอบใหม่ ใช้กลไกการรักษาความหลากหลาย (เช่น ระยะห่างความแออัด (crowding distance) หรือการแบ่งกลุ่มตามตาราง (grid-based density)) เพื่อป้องกันไม่ให้คลังมีความเข้มข้นมากเกินไปในบางบริเวณของปริภูมิวัตถุประสงค์
ลดการระเหยของเส้นทางฟีโรโมนทั้งหมดด้วยปัจจัย (1 − ρ) เพื่อให้ข้อมูลเก่าจางหายไป ฝากฟีโรโมนใหม่บนส่วนประกอบของคำตอบที่เป็นของคำตอบในคลัง (elite solutions) ปริมาณการฝาก Δτ สะท้อนถึงคุณภาพเฉพาะวัตถุประสงค์ หรืออันดับตามความแออัด เสริมสร้างส่วนประกอบที่เกี่ยวข้องกับคำตอบที่เหมาะสมแบบพาเรโตที่กระจายตัวได้ดี
สูตร
\tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij} + \sum_{k: s^k \in \mathcal{A}} \Delta\tau_{ij}^kทำซ้ำการสร้างคำตอบผ่านการอัปเดตฟีโรโมน สำหรับจำนวนรอบที่กำหนด หรือจนกว่าจะถึงเกณฑ์การลู่เข้า ส่งคืนคลังพาเรโตสุดท้ายเป็นหน้าพาเรโตโดยประมาณ ซึ่งแสดงถึงช่วงของการแลกเปลี่ยนที่เหมาะสมที่สุดสำหรับผู้ตัดสินใจในการเลือก
ข้อผิดพลาดที่พบบ่อย
- การใช้เมทริกซ์ฟีโรโมนเดียวที่ใช้ร่วมกันโดยไม่มีการแยกแยะเฉพาะวัตถุประสงค์ มักจะสร้างหน้าพาเรโตที่เอนเอียงและกระจายตัวได้ไม่ดี
- การละเลยการจัดการความหลากหลายของคลังส่งผลให้หน้าพาเรโตมีความหนาแน่นในบริเวณหนึ่งและมีช่องว่างขนาดใหญ่ในบริเวณอื่น ทำให้เกิดภาพการแลกเปลี่ยนที่ทำให้เข้าใจผิด
- การตั้งค่าอัตราการระเหย ρ สูงเกินไปทำให้ฟีโรโมนจางหายและสูญเสียการเรียนรู้ที่สะสมไว้; ต่ำเกินไปจะทำให้ติดอยู่กับคำตอบที่ไม่เหมาะสมที่สุด
- การเปรียบเทียบผลลัพธ์ MOACO ระหว่างการทำงานต่างๆ โดยไม่มีการทำซ้ำทางสถิติ (multiple seeds, hypervolume indicator) จะทำให้การประเมินคุณภาพคลาดเคลื่อน
- การลืมปรับค่าวัตถุประสงค์ให้เป็นมาตรฐาน (normalize) ก่อนการคำนวณการครอบงำหรือการฝากฟีโรโมน จะทำให้การค้นหาบิดเบือนเมื่อวัตถุประสงค์มีสเกลที่แตกต่างกันมาก
คำถามที่พบบ่อย
MOACO แตกต่างจากการรัน ACO แบบวัตถุประสงค์เดียวหลายครั้งด้วยการผสมผสานน้ำหนักที่แตกต่างกันอย่างไร?
การรัน ACO แบบวัตถุประสงค์เดียวแบบถ่วงน้ำหนักจำเป็นต้องระบุค่าน้ำหนักล่วงหน้า และแต่ละครั้งจะประมาณจุดที่เหมาะสมที่สุดแบบพาเรโตเพียงจุดเดียว MOACO สร้างคลังคำตอบที่ไม่ถูกครอบงำทั่วทั้งพื้นผิวการแลกเปลี่ยนในการทำงานครั้งเดียว และการอัปเดตฟีโรโมนจะเสริมสร้างคำตอบคุณภาพสูงที่หลากหลาย แทนที่จะเป็นค่าเหมาะสมที่สุดแบบสเกลาร์เพียงค่าเดียว
ควรใช้ MOACO รูปแบบใดสำหรับปัญหาใหม่?
หากวัตถุประสงค์สามารถแยกออกจากกันได้และแต่ละวัตถุประสงค์มีข้อมูลฮิวริสติกตามธรรมชาติ แนวทางอาณานิคมหลายอาณานิคม (หนึ่งอาณานิคมต่อวัตถุประสงค์ที่ใช้คลังพาเรโตที่ใช้ร่วมกัน) เป็นจุดเริ่มต้นที่ดี หากวัตถุประสงค์มีความเชื่อมโยงกันอย่างใกล้ชิด อาณานิคมเดียวที่มีการแปลงเป็นสเกลาร์แบบแยกส่วน (เช่น รูปแบบ MOACO/D) มักจะลู่เข้าได้อย่างมีประสิทธิภาพมากขึ้น โปรดตรวจสอบงานวิจัยที่ตีพิมพ์สำหรับโดเมนปัญหาเฉพาะของคุณก่อน
โดยทั่วไปต้องใช้มดกี่ตัวและกี่รอบ?
ไม่มีคำตอบที่เป็นสากล แต่การกำหนดค่าเริ่มต้นทั่วไปคือ 20–100 ตัวต่ออาณานิคม และ 500–2000 รอบ สำหรับปัญหาแบบผสมขนาดปานกลาง ปริภูมิคำตอบที่ใหญ่ขึ้นและวัตถุประสงค์ที่มากขึ้นต้องการรอบการทำงานที่มากขึ้น ควรทำการทดลองซ้ำหลายครั้งโดยอิสระ และรายงานตัวบ่งชี้ hypervolume หรือ IGD ที่หาค่าเฉลี่ยจากหลาย seed
MOACO สามารถจัดการกับปัญหาการหาค่าเหมาะที่สุดแบบต่อเนื่อง (continuous optimization problems) ได้หรือไม่?
ACO แบบมาตรฐานออกแบบมาสำหรับปริภูมิที่ไม่ต่อเนื่อง มีรูปแบบ MOACO แบบต่อเนื่อง (เช่น ที่อิงตาม ACOR) แต่โดยทั่วไปแล้วมีประสิทธิภาพด้อยกว่า NSGA-II หรือ MOEA/D ในปัญหาแบบต่อเนื่อง สงวน MOACO ไว้สำหรับปัญหาแบบผสมหรือแบบจำนวนเต็ม ซึ่งการสร้างคำตอบแบบอิงกราฟให้ข้อได้เปรียบตามธรรมชาติ
ควรตั้งค่าขนาดคลังพาเรโตอย่างไร?
ขนาดคลังจำกัดจำนวนคำตอบชั้นยอดที่ใช้สำหรับการฝากฟีโรโมน คลังที่มีขนาดเล็กเกินไปจะสูญเสียความหลากหลาย คลังที่มีขนาดใหญ่เกินไปจะทำให้การเสริมสร้างฟีโรโมนช้าลง ค่าทั่วไปอยู่ในช่วง 10 ถึง 100 คำตอบ ใช้กลยุทธ์ crowding-distance หรือ grid-based เพื่อรักษาคลังที่กระจายตัวได้ดีโดยไม่คำนึงถึงขนาด
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo, & F. Glover (Eds.), New Ideas in Optimization (pp. 63–76). McGraw-Hill.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วDorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
ISBN: 9780262042192คัดลอกแล้ว