Ant Colony optimization


Ant colony optimization

ACO เป็นขั้นตอนวิธีที่ได้แนวคิดมาจากพฤติกรรมการหาอาหารของมด ซึ่ง Deneuborg et al. (1990) ได้อธิบายไว้ว่ามดจะค้นหาเส้นทางสั้นที่สุดระหว่างแหล่งอาหารกับรังของมัน ระหว่างที่เดินทางไปกลับระหว่างแหล่งอาหารและรัง มดจะทิ้งหลักฐานที่เรียกว่า ฟีโรโมน (Pheromone) ไว้บนพื้น เมื่อจะตัดสินใจเลือกทางเดินก็จะเลือกเส้นทางที่มี ฟีโรโมน หนาแน่นมากกว่า การทำงานของขั้นตอนวิธี ACO มีองค์ประกอบที่สำคัญอย่างหนึ่งของการทำงาน คือการกำหนดปัญหาให้อยู่ในรูปแบบ construction graph เนื่องจากเส้นทางที่เดินผ่านกราฟอย่างสมบูรณ์จะแทนผลเฉลยของปัญหา (Socha et al., 2003)

             ขั้นตอนวิธี ACO ที่ได้นำเสนอครั้งแรก (Dorigo, Maniezzo & Colorni, 1996) เรียกว่า Ant System (AS) ซึ่งการทำงานโดยทั่วไป คือ ถ้ากำหนดให้ A แทนเซตของมดทุกตัวและ Sa แทนผลเฉลยที่ถูกสร้างโดยมด a Î A เริ่มตนการทำงานจะมีการกำหนดค่าระดับ pheromone ให้เท่ากันทุกเส้นทางที่ค่าต่ำ ๆ ค่าหนึ่ง (ph > 0) มดทุกตัวจะสร้างผลเฉลยโดยการเพิ่มส่วนประกอบเข้าไปทีละส่วนในรูปแบบของการเดินทางผ่านไปตามเส้นเชื่อมต่อระหว่างโนดของ construction graph ส่วนประกอบถัดไปที่จะถูกเพิ่มเข้าไปเป็นส่วนหนึ่งของผลเฉลยใน AS จะใช้ state transition rule ซึ่งจะมีพารามิเตอร์สำคัญที่ต้องใช้ร่วมในการพิจารณาคือ ค่า pheromone และ heuristic information เช่น ในกรณีการแก้ปัญหาการเดินทางของพนักงานขาย (Traveling Salesman Problem : TSP) ค่า ฟีโรโมน ก็จะเป็นระดับ ฟีโรโมน ระหว่างเมือง 2 เมือง (ซึ่งได้มาจากการปรับปรุงค่าจากการทำงานในรอบที่ผ่านมา) ส่วน heuristic information ก็คือระยะทางระหว่างเมือง 2 เมือง และเมื่อมดทุกตัวได้สร้างผลเฉลยเสร็จสมบูรณ์แล้วก็จะมีการปรับปรุงค่า ฟีโรโมน โดยมีวัตถุประสงค์เพื่อเพิ่มค่า ฟีโรโมน ให้กับส่วนประกอบของผลเฉลยที่พบว่ามีคุณภาพดี (Blum & Roli, 2003) จากนั้นก็จะมีการวนรอบการทำงานซ้ำจนกระทั่งเงื่อนไขที่กำหนดให้หยุด เช่น เวลาที่กำหนดไว้สูงสุด จำนวนรอบสูงสุด หรือเมื่อผลเฉลยไม่มีการเปลี่ยนแปลง

            มีตัวอย่างของงานวิจัยที่มีการประยุกต์ใช้ ACO (Socha et al., 2003; Dorigo  Gambardella, 1997) คือ Socha et al. (2003) นำ MAX-MIN Ant System (MMAS) ซึ่งเป็นขั้นตอนวิธีที่ปรับปรุงจาก ACO โดย Stutzle and Hoos (2000) ในการแก้ปัญหาการจัดตารางสอนซึ่ง Socha al. (2003) ก็ได้นำเสนอ construction graph และรูปแบบ pheromone ที่เหมาะสมเพื่อนำไปใช้ในการแก้ปัญหา ขณะที่ Dorigo and Gambardella (1997) ใช้ Ant Colony System (ACS) ซึ่งเป็นขั้นตอนวิธีที่ปรับปรุงจาก ACO ในการแก้ปัญหาการเดินทางของพนักงานขาย โดยเปรียบเทียบการทำงานกับขั้นตอนวิธีที่มีการเลียนแบบธรรมชาติอื่นๆ พบว่าส่วนใหญ่แล้ว ACS ให้ผลการทำงานที่ดีกว่า

ตารางที่ 2 การพัฒนาการของ ACO และ ผู้คิดค้น (Aderak, 2008)

วิธีการ

ผู้คิดค้น

Ant system (AS)

Dorigo, Maniezzo and Colonies(1991)

Elitist ant system (EAS)

Dorigo, Maniezzo and Colonies(1992)

Rank – Based ant system (AS-rank)

Bullnheimer,Harlt and Strauss(1997)

Max-Min ant system (MMAS)

Stutzle and Hoos(1997)

Ant colony system (ACS)

Dorigo and Gambardella(1997)

1 . Ant system

ได้ถูกนำเสนอเป็นครั้งแรกในปี ค.ศ. 1991 โดยได้ถูกคิดค้นและพัฒนาขึ้นโดย Marco Dorigo และคณะ ซึ่งที่จริงแล้ว ระบบมดเดิมได้มีอยู่ 3 แบบด้วยกันคือ Ant - density, Ant - quantity และ Ant - cycle (Dorigo et al., 1991; Dorigo and Stutzle, 2004) ระบบ Ant - density และระบบ Ant - quantity นั้นจะมีการอัพเดทสารฟีโรโมนทันทีขณะที่เดินทางจากโหนดหรือเมือง (Node  or city)  ไปยังเมือง  ขณะที่ระบบ Ant - cycle นั้นจะอัพเดทสารฟีโรโมนหลังจากที่มดเดินทางครบทุกเมืองแล้ว โดยที่ปริมาณของสารฟีโรโมนที่จะอัพเดทนั้นขึ้นอยู่กับอัตราส่วนระหว่างค่าคงที่ต่อระยะทางหรือคุณภาพของผลเฉลยที่ได้ ท้ายที่สุดแล้วระบบ Ant - density และระบบ Ant - quantity ก็ไม่ได้รับการปรับปรุงและพัฒนาต่อไปอีก เนื่องจากมีประสิทธิภาพในการหาผลเฉลยหรือเส้นทางที่น้อยมากเมื่อเทียบกับระบบ  Ant - cycle ดังนั้นในปัจจุบัน เมื่อกล่าวถึงระบบมด ก็คือระบบ Ant - cycle นั่นเอง (Dorigo and Stutzle, 2004)

2. Elitist ant system

 Elitist ant system เกิดจากการพัฒนา Ant system ให้มีประสิทธิภาพดีขึ้น โดยเรียกการพัฒนานี้ว่า Elitist strategy โดยนำเสนอเป็นครั้งแรกในปี 1992 โดย Dorigo โดยที่ส่วนการทำงานเริ่มต้นจะเหมือนกับ Ant system แต่จะเพิ่มในส่วนของการเก็บค่าดีที่สุดของแต่ละรอบการคำนวณ (Best so far tour) เพื่อการเพิ่มร่องรอยฟีโรโมน (Update pheromone trail) โดยจะเก็บค่าที่ดีที่สุดของรอบการคำนวณที่หนึ่งแล้ว Update pheromone ซึ่งเส้นทางที่เป็น Best so far tour จะมีพจน์ที่เพิ่มขึ้นมาเพื่อทำให้เส้นทางที่เป็น Best so far tour จะมีปริมาณฟีโรโมนมากกว่าเส้นทางที่มดผ่านปกติทั่วไป (โดยที่เส้นทางที่มดผ่านตัวอื่นจะใช้สมการ ant system)

3. Max-min ant system

Max-Min Ant System ถูกนำเสนอเป็นครั้งแรกในปี 1997 โดย Stutzle กับ Hoos โดยที่ทั้งสองคนได้พัฒนา Max-Min Ant System มาจาก Ant System โดยได้พัฒนาจาก Ant System 4 อย่างด้วยกัน ดังนี้

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

อย่างที่สอง คือการกำหนดช่วงของฟีโรโมนให้อยู่ในช่วงที่สมการกำหนด เพื่อที่เราจะได้จำกัดขอบเขตของเส้นทางที่ดีที่สุดเพียงหนึ่งช่วงเท่านั่น ทำให้หาเส้นทางที่ดีที่สุดได้อย่างรวดเร็ว

อย่างที่สาม คือ ค่าฟีโรโมนเริ่มต้นจะมีค่าตัวแปรการระเหยของปริมาณฟีโรโมนไว้ในตอนแรกเลย ซึ่งตรงจุดนี้ก็เป็นอีกจุดหนึ่งที่ Max-Min Ant System ต่างจาก Ant System

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

4. Rank-base ant system

 เป็นอีกตัวหนึ่งที่พัฒนามาจาก Ant system โดยถูกนำเสนอครั้งแรกโดย Bullnheimer ในปี 1999 โดยที่ AS-Rank จะวางจำนวนฟีโรโมนลดลงตามลำดับเส้นทางที่มดเดินผ่าน เช่น เส้นทางที่ดีที่สุดจะมีพจน์ที่เพิ่มขึ้นในสมการมีค่ามากที่สุด เพื่อให้เกิดฟีโรโมนของรอบใหม่มากที่สุดใส่ลำดับกันลงมาซึ่งจะแตกต่างจาก Elitist ant system ที่ จะมีพจน์ที่เพิ่มค่า Best so far tour เพียงค่าเดียว ซึ่งขั้นตอนต่างๆ นอกเหนือจากนี้จะเหมือนกับ Ant system กับ Elitist ant system ส่วนที่เพิ่มขึ้นมา  โดยที่ตัวแปร w จะเป็นค่าที่จัดเก็บลำดับ โดยส่วนใหญ่จะมีค่า w = 6 และค่า r เป็นค่า Rank ของมด โดยถ้า Rank ของมดมากจะทำให้ปริมาณฟีโรโมนลดลงตามลำดับ

5. Ant colony system

ACS ถูกสร้างขึ้นมาเพื่อปรับปรุงประสิทธิภาพของ Ant System โดยการปรับปรุงครั้งนี้ต่างจากทุกครั้งที่ผ่านมากล่าวคือ การปรับปรุงครั้งนี้ไม่ได้อยู่บนพื้นฐานของ Ant System อีกต่อไป โดยสร้างกลไกการทำงานใหม่เพื่อเพิ่มประสิทธิภาพการทำงาน   ACS ถูกนำเสนอครั้งแรกในปี 1997 โดย Dorigo และ Gambardella โดยที่มีความต่างจาก Ant System สามหลักการใหญ่ๆ คือ 

            1 ACS จะพัฒนาในส่วนของการจำเส้นทางในการเดินของมด โดยจะทำให้มดมีประสบการณ์ในการจำเส้นทางมากขึ้นและจะมีผลต่อการตัดสินใจในการเลือกเส้นทางมากขึ้นด้วย

            2 การระเหยฟีโรโมนและการวางฟีโรโมนจะทำในส่วนที่เป็นเส้นทางที่ดีที่สุดเท่านั้น

            3 ในแต่ละเส้นทางที่มดเดินผ่านไปนั่น มดจะเอาฟีโรโมนออก เพื่อที่จะทำให้เกิดการเพิ่มเส้นทางหรือโอกาสในการเลือกเส้นทางอื่น

สรุป กระบวนการ Ant Colony optimization

เราสามารถสรุปได้ว่า ACO ทุกตัวพัฒนามาจาก Ant System ทั้งหมด ซึ่งจะเป็นการปรับปรุงและพัฒนา Ant System ให้มีประสิทธิภาพการทำงานดีขึ้น หาคำตอบได้ดีขึ้นหรือลดเวลาการหาคำตอบที่ดีที่สุดลง ซึ่งตัวที่ปรับปรุงปรับเปลี่ยนจาก Ant System มากที่สุดคือ Ant Colony System ซึ่งจะว่าไปก็เป็นการเปลี่ยนหลักการทำงานของ Ant System เลยก็ว่าได้ ส่วนตัวอื่นจะมีการปรับปรุงตรงค่าการปรับปรุงปริมาณฟีโรโมน (Update Pheromone Trail) ซึ่งตัวอย่างของ ACO ที่กล่าวมาทั้งหมดนั้นเป็นตัวอย่างของการปัญหาพนักงานขาย (Traveling Saleman Problem) ซึ่งเป็นปัญหาพื้นฐานในการประยุกต์ใช้ ACO จากการอธิบายเกี่ยวกับ Ant Colony Optimization ทั้ง 5 ตัวนั้นซึ่งประกอบไปด้วย AS, EAS AS-Rank, MMASและ ACS สามารถสรุปการใช้ ACO กับรูปแบบลักษณะของปัญหา เช่น Quadratic Assignment Problem, Scheduling Problem,  Vehicle Routing Problem และ Timetabling Problem ซึ่งสามารถสรุปเป็นตารางได้ดังนี้

ตารางที่ 3 การประยุกต์ใช้ ACO และวิธีการแก้ปัญหา (Aderak, 2008)

ปัญหา

นักวิจัย

วิธีการ

Traveling Salesman Problem

Dorigo et al. (1991)

Colorni et al. (1994)

Dorigo and Gamardella (1997)

Bullnheimer et al. (1997)

Stutzle and Hoos (2000)

AS

AS

ACS

AS-Rank

MMAS

Quadratic Assignment Problem

Gambardella et al (1999)

Stutzle and Hoos (2000)

Solimanpur et al. (2004)

AS

MMAS

ACO

Scheduling Problem

Colorni et al (1994)

Stutzle (1997)

McMullen (2001)

Gravel et al. (2002)

Ying and Liao (2004)

Shyu et al. (2004)

AS

AS

ACO

ACO

ACS

ACO

Vehicle Routing Problem

Bullnheimer et al. (1999)

Bell and McMullen (2004)

AS

ACO

Timetabling Problem

Socha et al.(2003)

MMAS

 

 

หมายเลขบันทึก: 99496เขียนเมื่อ 29 พฤษภาคม 2007 21:42 น. ()แก้ไขเมื่อ 6 กันยายน 2013 18:02 น. ()สัญญาอนุญาต: สงวนสิทธิ์ทุกประการจำนวนที่อ่านจำนวนที่อ่าน:


ความเห็น (4)

อยากได้เนื้อหาหนังสือ Ant Colony Optimization ที่เป็นภาษาไทยอ่านครับ ตอนนี้จะทำงานวิจัยเกี่ยวกับเรื่องนี้แหละรบกวนแนะนำหน่อยน่ะครับ

ขอบคุณมากสำหรับความรู้ที่เอามาแบ่งปันค่ะ กำลังสนใจเรื่องนี้มากๆ

ซื้อ textbook เรื่องนี้มาอ่าน แต่ยังอ่านไม่จบเลยค่ะ ถ้ามีข้อมูลหรือความรู้

ด้าน ACO , PSO , GA และ finding path รบกวนขอความกรุณาเอามาแบ่งปัน

เพื่อให้ความรู้อีกนะคะ

ขอบคุณมากค่ะ

ขอบคุณมากมากค่ะเป็นประโยชน์มากมากเลย

มาแบ่งปันความรู้อีกนะคะ

พบปัญหาการใช้งานกรุณาแจ้ง LINE ID @gotoknow
ClassStart
ระบบจัดการการเรียนการสอนผ่านอินเทอร์เน็ต
ทั้งเว็บทั้งแอปใช้งานฟรี
ClassStart Books
โครงการหนังสือจากคลาสสตาร์ท