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

Ant Colony Optimization — Swarm-Based Combinatorial Optimisation

ปี
1992 (foundational thesis); 1997 (Ant Colony System formalization)
ประเภท
Metaheuristic — swarm intelligence

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

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

ใช้ทำอะไร?

Ant Colony Optimization (ACO) เป็นอัลกอริทึมเมตาฮิวริสติกที่ Marco Dorigo และคณะได้นำเสนอในช่วงต้นทศวรรษ 1990 ซึ่งแก้ปัญหาการหาค่าเหมาะที่สุดเชิงการจัดหมู่ (combinatorial optimisation problems) โดยการจำลองพฤติกรรมการหาอาหารแบบรวมกลุ่มของมด มดจริงจะทิ้งรอยฟีโรโมนไว้ตามเส้นทางและเลือกเดินตามเส้นทางที่เข้มข้นกว่าเป็นพิเศษ ACO นำกลไกการตอบรับเชิงบวกนี้มาใช้เป็นกระบวนการค้นหาที่ให้ผลลัพธ์คุณภาพสูงสำหรับปัญหาที่มีโครงสร้างแบบกราฟ เช่น ปัญหาการเดินทางของพนักงานขาย (Travelling Salesman Problem), การจัดเส้นทางการเดินรถ, และการจัดตารางเวลา

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

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

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

กรอบการทำงาน Ant Colony Optimization ถูกนำเสนอโดย Marco Dorigo ในวิทยานิพนธ์ปริญญาเอกของเขาในปี 1992 โดยอิงจากการสังเกตการณ์ว่าอาณานิคมมดจริงหาเส้นทางที่สั้นที่สุดได้อย่างไรผ่านการสื่อสารแบบ stigmergic ด้วยฟีโรโมน อัลกอริทึมที่เป็นรูปธรรมแรกคือ Ant System (AS) ซึ่งตีพิมพ์ร่วมกับ Maniezzo และ Colorni ในปี 1996 ในปี 1997 Dorigo และ Gambardella ได้ตีพิมพ์ Ant Colony System (ACS) ซึ่งนำเสนอการอัปเดตฟีโรโมนเฉพาะที่และกฎการใช้ประโยชน์ที่ก้าวร้าวมากขึ้น ซึ่งช่วยปรับปรุงประสิทธิภาพอย่างมากในปัญหาการเดินทางของพนักงานขาย ในปี 2004 Dorigo และ Stützle ได้รวบรวมกรอบการทำงาน ACO ในหนังสือของ MIT Press และจัดตั้งให้เป็นสาขาหลักของ swarm intelligence ตั้งแต่นั้นมา ACO ได้ถูกขยายไปยังโดเมนแบบต่อเนื่อง (ACOR), ปัญหาหลายวัตถุประสงค์ (MOACO), และกราฟแบบไดนามิก

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

ACO เหมาะสำหรับปัญหาการหาค่าเหมาะที่สุดเชิงการจัดหมู่ที่สามารถแสดงเป็นงานการหาเส้นทางหรือการมอบหมายบนกราฟ — ตัวอย่างคลาสสิก ได้แก่ ปัญหาการเดินทางของพนักงานขาย, การจัดเส้นทางการเดินรถ, การจัดตารางงานในโรงงาน (job-shop scheduling), และการจัดเส้นทางเครือข่าย มันยอมรับทั้งตัวแปรตัดสินใจแบบต่อเนื่องและแบบจำแนกประเภทเมื่อปัญหาถูกเข้ารหัสอย่างเหมาะสม ไม่จำเป็นต้องมีข้อสมมติฐานเรื่องการแจกแจงปกติ และไม่มีข้อจำกัดเรื่องขนาดตัวอย่างขั้นต่ำ; ข้อมูลนำเข้าที่เกี่ยวข้องคือโครงสร้างกราฟที่กำหนดไว้อย่างดีและงบประมาณรอบที่เพียงพอ (โดยทั่วไปคือหลายร้อยถึงหลายพันรอบ) ACO มีความสามารถในการแข่งขันสูงโดยเฉพาะเมื่อมีฮิวริสติกเฉพาะทางเพื่อนำทางมด หากสามารถจัดสรรรอบได้น้อยกว่าประมาณ 100–200 รอบ Tabu Search จะเป็นทางเลือกที่ดีกว่า

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

  • ต้องการงบประมาณรอบที่เพียงพอ; หากมีรอบน้อยเกินไป รอยฟีโรโมนจะไม่น่าเชื่อถือและคุณภาพของคำตอบจะเสื่อมลง
  • ต้องปรับพารามิเตอร์หลักสามค่า — α, β, และ ρ; ค่าที่ไม่เหมาะสมอาจทำให้เกิดการลู่เข้าก่อนเวลาอันควรหรือการหยุดนิ่ง
  • การลู่เข้าอาจช้าบนกราฟขนาดใหญ่มาก เนื่องจากสัญญาณฟีโรโมนเจือจางไปตามเส้นเชื่อมจำนวนมาก
  • ไม่เหมาะโดยธรรมชาติกับปัญหาการหาค่าเหมาะที่สุดแบบต่อเนื่องหากไม่มีการเข้ารหัสแบบกราฟ

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

จุดแข็ง

  • จัดการกับปริภูมิการค้นหาเชิงการจัดหมู่หมู่ขนาดใหญ่และไม่ต่อเนื่องที่วิธีการที่แม่นยำไม่สามารถจัดการได้
  • การค้นหาแบบกลุ่ม (Population-based search) ช่วยให้สามารถประมวลผลแบบขนานโดยปริยาย — สำรวจคำตอบที่เป็นไปได้หลายคำตอบพร้อมกัน
  • สามารถนำความรู้เฉพาะทาง (ฮิวริสติก η) มาใช้โดยตรงในกฎการเปลี่ยนสถานะเพื่อเร่งการลู่เข้า
  • กลไกฟีโรโมนแบบตอบรับเชิงบวกมุ่งเน้นการค้นหาไปยังบริเวณที่มีแนวโน้มดีโดยธรรมชาติเมื่อเวลาผ่านไป
  • ทนทานต่อการปรับโครงสร้างปัญหา: การเพิ่มหรือลบโหนด/เส้นเชื่อมในกราฟไม่จำเป็นต้องมีการคำนวณอัลกอริทึมใหม่

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

  • ปัญหาการเดินทางของพนักงานขาย (TSP) และการจัดเส้นทางการเดินรถ — การหาเส้นทางต้นทุนต่ำสุดข้ามเมืองหรือจุดส่งของ
  • การจัดตารางงานในโรงงานและแบบเปิด (Job-shop and open-shop scheduling) — การมอบหมายการดำเนินการให้กับเครื่องจักรเพื่อลดเวลาผลิตรวม (makespan) หรือความล่าช้า
  • การจัดเส้นทางเครือข่ายในการสื่อสารโทรคมนาคม — การปรับเส้นทางแพ็กเก็ตแบบไดนามิกเพื่อลดความแออัด
  • การหาค่าเหมาะที่สุดของห่วงโซ่อุปทานและโลจิสติกส์ — การมอบหมายคลังสินค้า, การจัดลำดับการจัดส่งในระยะสุดท้าย (last-mile delivery)
  • การออกแบบทางวิศวกรรม — ปัญหาการเลือกพารามิเตอร์และการจัดวางส่วนประกอบที่เข้ารหัสเป็นปริภูมิการค้นหาแบบไม่ต่อเนื่อง

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

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

1

ปัญหาการหาค่าเหมาะที่สุดจะถูกเข้ารหัสเป็นกราฟ: โหนด (nodes) แทนจุดตัดสินใจ (เช่น เมือง, งาน, การดำเนินการ) และเส้นเชื่อม (edges) มีน้ำหนักสองค่า — ระดับฟีโรโมน τ ที่จะได้รับการปรับปรุงทุกรอบ และค่าฮิวริสติก η ที่ได้จากความรู้เฉพาะทาง (เช่น ส่วนกลับของระยะทาง) กราฟนี้คือสภาพแวดล้อมร่วมที่มดทุกตัวสื่อสารกันโดยอ้อม

2

มดเทียมแต่ละตัวจะสร้างคำตอบที่สมบูรณ์โดยการเดินทางผ่านกราฟ ที่ทุกโหนด มันจะเลือกเส้นเชื่อมถัดไปตามกฎการเปลี่ยนสถานะ (transition rule) ที่ถ่วงดุลระหว่างระดับฟีโรโมน (ยกกำลัง α) และความน่าสนใจเชิงฮิวริสติก (ยกกำลัง β) ค่า α ที่สูงขึ้นจะส่งเสริมการใช้ประโยชน์จากเส้นทางที่ดีที่ทราบแล้ว; ค่า β ที่สูงขึ้นจะเพิ่มการพึ่งพาความรู้เฉพาะทางของปัญหา ผลลัพธ์คือกลุ่มของคำตอบที่เป็นไปได้ที่สร้างขึ้นพร้อมกันในแต่ละรอบ

3

หลังจากมดทุกตัวเดินทางเสร็จสิ้น ระดับฟีโรโมนจะถูกปรับในสองขั้นตอน ขั้นแรก การระเหยจะลดฟีโรโมนของทุกเส้นเชื่อมด้วยปัจจัย (1 − ρ) เพื่อป้องกันการสะสมอย่างไม่จำกัดและป้องกันไม่ให้การค้นหาติดขัดก่อนเวลาอันควร ขั้นที่สอง มดจะสะสมฟีโรโมนบนเส้นเชื่อมที่พวกมันใช้; คำตอบที่ดีกว่าจะสะสมมากกว่า เป็นการเสริมแรงเส้นทางที่สั้นกว่าหรือมีคุณภาพสูงกว่า รูปแบบ Ant Colony System (ACS) ยังมีการปรับปรุงฟีโรโมนเฉพาะที่ (local pheromone update) ในระหว่างการสร้างเพื่อเพิ่มความหลากหลายในการค้นหา

4

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

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

  • การรันรอบน้อยเกินไป (หลักการทั่วไปคืออย่างน้อยหลายร้อยรอบ) — อาณานิคมไม่สามารถสร้างรอยฟีโรโมนที่เสถียรได้ ทำให้ได้คำตอบที่ใกล้เคียงกับการสุ่ม; เปลี่ยนไปใช้ Tabu Search หากงบประมาณมีจำกัดมาก
  • การตั้งค่าอัตราการระเหย ρ ต่ำเกินไป — ฟีโรโมนเก่าสะสม, อาณานิคมยึดติดกับเส้นทางที่ไม่เหมาะสมตั้งแต่เนิ่นๆ และความหลากหลายลดลง; เพิ่ม ρ หรือใช้กลไกการรีเซ็ตฟีโรโมน
  • การละเลยข้อมูลฮิวริสติก (β = 0) — อัลกอริทึมจะขับเคลื่อนด้วยฟีโรโมนเพียงอย่างเดียว ซึ่งช้าและไม่น่าเชื่อถือในช่วงเริ่มต้นเมื่อเส้นทางยังไม่มีข้อมูล
  • การนำ ACO ไปใช้กับปัญหาแบบต่อเนื่องโดยไม่มีการเข้ารหัสแบบกราฟที่เหมาะสม — กฎการเปลี่ยนสถานะตามความน่าจะเป็นอาศัยกราฟแบบไม่ต่อเนื่อง; การจับคู่ตัวแปรค่าจริงโดยตรงโดยไม่มีการแบ่งกลุ่ม (discretisation) หรือรูปแบบ ACO ที่เหมาะสม (เช่น ACOR) จะนำไปสู่ผลลัพธ์ที่ไม่ดี
  • การไม่ติดตามคำตอบที่ดีที่สุดทั่วโลกตลอดทุกรอบ — การอัปเดตฟีโรโมนโดยอิงจากมดที่ดีที่สุดในรอบปัจจุบันเท่านั้นจะทำให้สูญเสียคำตอบที่ดีที่สุดที่เคยพบ

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

ACO แตกต่างจาก Genetic Algorithms อย่างไร?

ทั้งสองเป็นเมตาฮิวริสติกแบบกลุ่ม (population-based metaheuristics) แต่แตกต่างกันในวิธีการที่คำตอบมีการวิวัฒนาการ Genetic Algorithms จะรักษาประชากรของคำตอบที่สมบูรณ์และใช้ตัวดำเนินการ crossover และ mutation เพื่อสร้างลูกหลาน ACO จะรักษาเมทริกซ์ฟีโรโมน — หน่วยความจำร่วม — และมดแต่ละตัวจะสร้างคำตอบใหม่ตั้งแต่ต้นโดยอาศัยหน่วยความจำนั้น ACO โดยทั่วไปจะเหมาะสมกว่าสำหรับปัญหาการหาเส้นทางและการจัดลำดับ ในขณะที่ Genetic Algorithms สามารถนำไปใช้กับปัญหาการหาค่าเหมาะที่สุดแบบค่าจริง (real-coded) และแบบไบนารีได้อย่างกว้างขวาง

ควรใช้ค่าใดสำหรับ α, β, และ ρ?

การทดสอบมาตรฐานบน TSP แนะนำค่า α ≈ 1, β ≈ 2–5, และ ρ ≈ 0.02–0.1 เป็นจุดเริ่มต้นที่สมเหตุสมผล (Dorigo & Stützle, 2004) ค่า β ที่สูงขึ้นจะเพิ่มอิทธิพลของฮิวริสติก (มีประโยชน์เมื่อความรู้เฉพาะทางน่าเชื่อถือ); ค่า ρ ที่สูงขึ้นจะเพิ่มการระเหยและความหลากหลาย แต่อาจทำให้การลู่เข้าช้าลง พารามิเตอร์เหล่านี้ขึ้นอยู่กับปัญหาและควรได้รับการปรับอย่างเป็นระบบ เช่น ด้วยการค้นหาแบบกริด (grid search) ขนาดเล็ก หรือ Bayesian optimisation

ACO สามารถแก้ปัญหาการหาค่าเหมาะที่สุดแบบต่อเนื่องได้หรือไม่?

ACO มาตรฐานถูกออกแบบมาสำหรับปริภูมิการค้นหาแบบไม่ต่อเนื่องที่มีโครงสร้างแบบกราฟ ปัญหาแบบต่อเนื่องสามารถแก้ไขได้ด้วย ACOR (Ant Colony Optimization for Continuous Domains) ซึ่งแทนที่เมทริกซ์ฟีโรโมนด้วยที่เก็บคำตอบ (solution archive) และฟังก์ชันความหนาแน่นของความน่าจะเป็น (probability density function) สำหรับปัญหาแบบต่อเนื่องล้วนๆ ที่ไม่มีการเข้ารหัสแบบกราฟตามธรรมชาติ ทางเลือกอื่น เช่น Particle Swarm Optimization หรือ Differential Evolution อาจง่ายกว่าในการนำไปใช้

โดยทั่วไปต้องการมดและรอบจำนวนเท่าใด?

ไม่มีคำตอบสากล แต่จุดเริ่มต้นที่ใช้งานได้คือการตั้งค่าจำนวนมดให้เท่ากับจำนวนโหนดในกราฟและรันเป็นเวลาหลายร้อยรอบ การตรวจจับการหยุดนิ่ง — หยุดเมื่อคำตอบที่ดีที่สุดไม่ได้รับการปรับปรุงในช่วงจำนวนรอบที่กำหนด — สามารถประหยัดการคำนวณได้ หากมีงบประมาณจำกัดน้อยกว่าประมาณ 100–200 รอบ ACO ไม่น่าจะให้ผลลัพธ์ที่น่าเชื่อถือ; Tabu Search เป็นตัวเลือกที่ดีกว่าในสภาวะดังกล่าว

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

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

  1. Dorigo, M. & Gambardella, L.M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.

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

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