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

การหาค่าเหมาะที่สุดด้วยอาณานิคมมดแบบหลายวัตถุประสงค์ (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) แบบหลายวัตถุประสงค์ในสภาพแวดล้อมคลาวด์คอมพิวติ้ง

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

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

1

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

2

มดแต่ละตัวสร้างคำตอบที่สมบูรณ์ทีละขั้นตอน โดยการเลือกส่วนประกอบของคำตอบตามความน่าจะเป็น ความน่าจะเป็นในการเปลี่ยนสถานะใช้ความเข้มข้นของฟีโรโมน τ และความน่าสนใจเชิงฮิวริสติก (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}
3

ประเมินคำตอบที่สร้างขึ้นแต่ละคำตอบด้วยฟังก์ชันวัตถุประสงค์ทั้งหมดพร้อมกัน ระบุความสัมพันธ์การครอบงำ (dominance relationship) กับสมาชิกในคลังที่มีอยู่: คำตอบหนึ่งจะครอบงำอีกคำตอบหนึ่ง หากคำตอบนั้นดีอย่างน้อยเท่ากันในทุกวัตถุประสงค์ และดีกว่าอย่างน้อยหนึ่งวัตถุประสงค์

4

อัปเดตคลังพาเรโตโดยการเพิ่มคำตอบที่ไม่ถูกครอบงำ และลบสมาชิกในคลังที่ถูกครอบงำโดยคำตอบใหม่ ใช้กลไกการรักษาความหลากหลาย (เช่น ระยะห่างความแออัด (crowding distance) หรือการแบ่งกลุ่มตามตาราง (grid-based density)) เพื่อป้องกันไม่ให้คลังมีความเข้มข้นมากเกินไปในบางบริเวณของปริภูมิวัตถุประสงค์

5

ลดการระเหยของเส้นทางฟีโรโมนทั้งหมดด้วยปัจจัย (1 − ρ) เพื่อให้ข้อมูลเก่าจางหายไป ฝากฟีโรโมนใหม่บนส่วนประกอบของคำตอบที่เป็นของคำตอบในคลัง (elite solutions) ปริมาณการฝาก Δτ สะท้อนถึงคุณภาพเฉพาะวัตถุประสงค์ หรืออันดับตามความแออัด เสริมสร้างส่วนประกอบที่เกี่ยวข้องกับคำตอบที่เหมาะสมแบบพาเรโตที่กระจายตัวได้ดี

สูตร
\tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij} + \sum_{k: s^k \in \mathcal{A}} \Delta\tau_{ij}^k
6

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

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

  • การใช้เมทริกซ์ฟีโรโมนเดียวที่ใช้ร่วมกันโดยไม่มีการแยกแยะเฉพาะวัตถุประสงค์ มักจะสร้างหน้าพาเรโตที่เอนเอียงและกระจายตัวได้ไม่ดี
  • การละเลยการจัดการความหลากหลายของคลังส่งผลให้หน้าพาเรโตมีความหนาแน่นในบริเวณหนึ่งและมีช่องว่างขนาดใหญ่ในบริเวณอื่น ทำให้เกิดภาพการแลกเปลี่ยนที่ทำให้เข้าใจผิด
  • การตั้งค่าอัตราการระเหย ρ สูงเกินไปทำให้ฟีโรโมนจางหายและสูญเสียการเรียนรู้ที่สะสมไว้; ต่ำเกินไปจะทำให้ติดอยู่กับคำตอบที่ไม่เหมาะสมที่สุด
  • การเปรียบเทียบผลลัพธ์ 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 เพื่อรักษาคลังที่กระจายตัวได้ดีโดยไม่คำนึงถึงขนาด

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

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

  1. 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.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.

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