อัลกอริทึมการเพิ่มประสิทธิภาพอาณานิคมมด

ในวิทยาการคอมพิวเตอร์และการวิจัยปฏิบัติการอัลกอริทึมการเพิ่มประสิทธิภาพอาณานิคมมด ( ACO ) เป็น เทคนิค เชิงความน่าจะเป็นสำหรับการแก้ปัญหาการคำนวณที่สามารถลดทอนลงเหลือการค้นหาเส้นทางที่ดีผ่านกราฟมดเทียมแสดงถึง วิธีการ หลายตัวแทนที่ได้รับแรงบันดาลใจจากพฤติกรรมของมด จริง การสื่อสารโดยใช้ฟีโรโมนของมดทางชีววิทยาเป็นกระบวนทัศน์หลักที่ใช้^{[ 2 ]}การผสมผสานระหว่างมดเทียมและ อัลกอริทึม การค้นหาแบบโลคอลได้ กลายเป็นวิธีการที่นิยมสำหรับงานเพิ่มประสิทธิภาพจำนวนมากที่เกี่ยวข้องกับ กราฟบางประเภทเช่นการกำหนดเส้นทางยานพาหนะและการกำหนดเส้นทางอินเทอร์เน็ต

ตัวอย่างเช่น การเพิ่มประสิทธิภาพอาณานิคมมด^{[ 3 ]}เป็นกลุ่มของ อัลกอริ ธึมการเพิ่มประสิทธิภาพ ที่จำลองมาจากพฤติกรรมของอาณานิคมมด^{[ 4 ]} 'มด' เทียม (เช่น ตัวแทนจำลอง) ค้นหาโซลูชันที่เหมาะสมที่สุดโดยการเคลื่อนที่ผ่านพื้นที่พารามิเตอร์ที่แสดงถึงโซลูชันที่เป็นไปได้ทั้งหมด มดจริงจะปล่อยฟีโรโมนเพื่อนำทางกันและกันไปยังทรัพยากรในขณะที่สำรวจสภาพแวดล้อม 'มด' จำลองก็เช่นกัน จะบันทึกตำแหน่งและคุณภาพของโซลูชันของตน เพื่อให้ในการจำลองซ้ำในภายหลัง มดจำนวนมากขึ้นจะค้นหาโซลูชันที่ดีกว่า^{[ 5 ]}รูปแบบหนึ่งของแนวทางนี้คืออัลกอริธึมผึ้งซึ่งคล้ายคลึงกับรูปแบบการหาอาหารของผึ้งน้ำผึ้งซึ่งเป็นแมลงสังคมอีกชนิดหนึ่ง

อัลกอริทึมนี้เป็นสมาชิกของตระกูลอัลกอริทึมอาณานิคมมดใน วิธี การปัญญาแบบฝูงและประกอบด้วย การเพิ่มประสิทธิภาพ เมตาฮิวริสติก บางอย่าง เดิมทีเสนอโดยMarco Dorigoในปี 1992 ในวิทยานิพนธ์ปริญญาเอกของเขา^{[ 6 ] [ 7 ]}อัลกอริทึมแรกมีเป้าหมายเพื่อค้นหาเส้นทางที่เหมาะสมที่สุดในกราฟ โดยอิงจากพฤติกรรมของมดที่ค้นหาเส้นทางระหว่างอาณานิคม ของพวกมัน กับแหล่งอาหาร แนวคิดดั้งเดิมได้แตกแขนงออกไปเพื่อแก้ปัญหาเชิงตัวเลขที่กว้างขึ้น และเป็นผลให้เกิดปัญหาหลายอย่างขึ้น โดยดึงเอาแง่มุมต่างๆ ของพฤติกรรมของมดมาใช้ จากมุมมองที่กว้างขึ้น ACO ดำเนินการค้นหาตามแบบจำลอง^{[ 8 ]}และมีความคล้ายคลึงกับอัลกอริทึมการประมาณการกระจาย

ในโลกธรรมชาติ มดบางชนิด (ในตอนแรก) จะเดินเตร่ไปมาอย่างสุ่มๆและเมื่อพบอาหารก็จะกลับไปยังรังของพวกมันพร้อมกับทิ้ง ร่องรอย ฟีโรโมนไว้ หากมดตัวอื่นๆ พบเส้นทางดังกล่าว พวกมันมักจะหยุดเดินทางแบบสุ่มและหันมาเดินตามเส้นทางนั้นแทน โดยจะกลับมาและเสริมความแข็งแกร่งให้กับเส้นทางนั้นหากพวกมันพบอาหารในที่สุด (ดูการสื่อสารของมด ) ^{[ 9 ]}

อย่างไรก็ตาม เมื่อเวลาผ่านไป ร่องรอยฟีโรโมนจะเริ่มระเหย ทำให้ความดึงดูดลดลง ยิ่งใช้เวลานานเท่าใดที่มดจะเดินทางไปตามเส้นทางและกลับมา ฟีโรโมนก็จะมีเวลาระเหยมากขึ้นเท่านั้น ในทางกลับกัน เส้นทางสั้นๆ จะถูกมดเดินผ่านบ่อยกว่า ดังนั้นความหนาแน่นของฟีโรโมนจึงสูงกว่าในเส้นทางที่สั้นกว่าเส้นทางที่ยาวกว่า การระเหยของฟีโรโมนยังมีข้อดีคือช่วยหลีกเลี่ยงการบรรจบกันที่คำตอบที่เหมาะสมที่สุดในระดับท้องถิ่น หากไม่มีการระเหยเลย เส้นทางที่มดตัวแรกเลือกจะดึงดูดมดตัวต่อๆ ไปมากเกินไป ในกรณีนั้น การสำรวจพื้นที่คำตอบจะถูกจำกัด อิทธิพลของการระเหยของฟีโรโมนในระบบมดจริงยังไม่ชัดเจน แต่มีความสำคัญมากในระบบเทียม^{[ 10 ]}

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

เนื่องจาก "สติปัญญา" ไม่ได้กระจุกตัวอยู่เพียงจุดเดียวอีกต่อไป แต่สามารถพบได้ในวัตถุขนาดเล็กทุกชนิด จึงจำเป็นต้องมีแนวคิดใหม่ๆ แนวคิดที่ยึดมนุษย์เป็นศูนย์กลางนั้นนำไปสู่การสร้างระบบไอทีที่การประมวลผลข้อมูล หน่วยควบคุม และพลังการคำนวณรวมศูนย์อยู่ หน่วยรวมศูนย์เหล่านี้ได้เพิ่มประสิทธิภาพอย่างต่อเนื่องและสามารถเปรียบเทียบได้กับสมองของมนุษย์ แบบจำลองของสมองจึงกลายเป็นวิสัยทัศน์สูงสุดของคอมพิวเตอร์ แต่เครือข่ายของวัตถุอัจฉริยะ และในไม่ช้า ระบบสารสนเทศรุ่นใหม่ที่มีการกระจายตัวมากขึ้นและใช้เทคโนโลยีนาโน จะเปลี่ยนแปลงแนวคิดนี้อย่างลึกซึ้ง อุปกรณ์ขนาดเล็กที่เปรียบเทียบได้กับแมลงนั้นไม่ได้มีสติปัญญาสูงด้วยตัวของมันเอง อันที่จริง สติปัญญาของพวกมันจัดอยู่ในระดับค่อนข้างจำกัด ตัวอย่างเช่น เป็นไปไม่ได้ที่จะรวมเครื่องคิดเลขประสิทธิภาพสูงที่มีพลังในการแก้ปัญหาทางคณิตศาสตร์ทุกประเภทลงในไบโอชิปที่ฝังอยู่ในร่างกายมนุษย์ หรือรวมเข้ากับแท็กอัจฉริยะที่ออกแบบมาเพื่อติดตามสินค้า อย่างไรก็ตาม เมื่อวัตถุเหล่านั้นเชื่อมต่อกัน พวกมันจะพัฒนาสติปัญญาในรูปแบบที่สามารถเปรียบเทียบได้กับฝูงมดหรือผึ้ง ในกรณีของปัญหาบางอย่าง สติปัญญาประเภทนี้อาจเหนือกว่าการใช้เหตุผลของระบบส่วนกลางที่คล้ายกับสมอง^{[ 11 ]}

ธรรมชาติมีตัวอย่างมากมายที่แสดงให้เห็นว่าสิ่งมีชีวิตขนาดเล็ก หากพวกมันปฏิบัติตามกฎพื้นฐานเดียวกันทั้งหมด สามารถสร้างสติปัญญารวมหมู่ในระดับมหภาคได้อย่างไร อาณานิคมของแมลงสังคมเป็นตัวอย่างที่สมบูรณ์แบบของแบบจำลองนี้ ซึ่งแตกต่างจากสังคมมนุษย์อย่างมาก แบบจำลองนี้ตั้งอยู่บนความร่วมมือของหน่วยอิสระที่มีพฤติกรรมที่เรียบง่ายและคาดเดาไม่ได้^{[ 12 ]}พวกมันเคลื่อนที่ไปทั่วบริเวณโดยรอบเพื่อทำงานบางอย่าง และมีข้อมูลเพียงเล็กน้อยเท่านั้นที่จะทำเช่นนั้นได้ ตัวอย่างเช่น อาณานิคมของมดแสดงให้เห็นถึงคุณสมบัติมากมายที่สามารถนำไปใช้กับเครือข่ายของวัตถุแวดล้อมได้ อาณานิคมของมดมีความสามารถสูงมากในการปรับตัวให้เข้ากับการเปลี่ยนแปลงของสิ่งแวดล้อม รวมถึงความแข็งแกร่งในการจัดการกับสถานการณ์ที่มดตัวใดตัวหนึ่งไม่สามารถทำงานที่กำหนดได้ ความยืดหยุ่นแบบนี้จะมีประโยชน์มากสำหรับเครือข่ายเคลื่อนที่ของวัตถุที่กำลังพัฒนาอย่างต่อเนื่อง ข้อมูลที่เคลื่อนที่จากคอมพิวเตอร์ไปยังวัตถุดิจิทัลมีพฤติกรรมเช่นเดียวกับที่มดจะทำ พวกเขาเคลื่อนที่ผ่านเครือข่ายและผ่านจากโหนดหนึ่งไปยังอีกโหนดหนึ่งโดยมีเป้าหมายที่จะไปถึงจุดหมายปลายทางสุดท้ายให้เร็วที่สุด^{[ 13 ]}

การสื่อสารโดยใช้ฟีโรโมนเป็นหนึ่งในวิธีการสื่อสารที่มีประสิทธิภาพมากที่สุด ซึ่งพบเห็นได้ทั่วไปในธรรมชาติ ฟีโรโมนถูกใช้โดยแมลงสังคม เช่น ผึ้ง มด และปลวก ทั้งสำหรับการสื่อสารระหว่างตัวแทนและระหว่างตัวแทนกับฝูง เนื่องจากความเป็นไปได้ ฟีโรโมนสังเคราะห์จึงถูกนำมาใช้ในระบบหุ่นยนต์หลายตัวและระบบหุ่นยนต์แบบฝูง การสื่อสารโดยใช้ฟีโรโมนถูกนำไปใช้ด้วยวิธีการต่างๆ เช่น ทางเคมี^{[ 14 ] [ 15 ] [ 16 ]}หรือทางกายภาพ (แท็ก RFID ^{[ 17 ]}แสง^{[ 18 ] [ 19 ] [ 20 ] [ 21 ]}เสียง^{[ 22 ]} ) อย่างไรก็ตาม การนำไปใช้เหล่านั้นไม่สามารถจำลองทุกแง่มุมของฟีโรโมนได้เหมือนที่พบในธรรมชาติ

การใช้แสงที่ฉายออกมาได้รับการนำเสนอในเอกสาร IEEE ปี 2007 โดย Garnier, Simon และคณะ ในฐานะการตั้งค่าการทดลองเพื่อศึกษาการสื่อสารโดยใช้ฟีโรโมนกับหุ่นยนต์อัตโนมัติขนาดเล็ก^{[ 23 ]}การศึกษาอีกชิ้นหนึ่งนำเสนอระบบที่ใช้ฟีโรโมนผ่านหน้าจอ LCD แนวนอนที่หุ่นยนต์เคลื่อนที่ โดยหุ่นยนต์มีเซ็นเซอร์แสงที่หันลงด้านล่างเพื่อบันทึกรูปแบบที่อยู่ด้านล่าง^{[ 24 ] [ 25 ]}

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

ขั้นตอน ACO_MetaHeuristic จะทำงานในขณะที่ยังไม่สิ้นสุด generateSolutions() การกระทำของเดมอน() pheromoneUpdate() ทำซ้ำขั้นตอนสุดท้าย

มดแต่ละตัวจำเป็นต้องสร้างวิธีแก้ปัญหาเพื่อเคลื่อนที่ผ่านกราฟ ในการเลือกขอบถัดไปในการเดินทาง มดจะพิจารณาความยาวของแต่ละขอบที่มีอยู่จากตำแหน่งปัจจุบันของมัน รวมถึงระดับฟีโรโมนที่สอดคล้องกัน ในแต่ละขั้นตอนของอัลกอริทึม มดแต่ละตัวจะเคลื่อนที่จากสถานะหนึ่งไปยังอีกสถานะหนึ่งซึ่งสอดคล้องกับวิธีแก้ปัญหาขั้นกลางที่สมบูรณ์ยิ่งขึ้น ดังนั้น มดแต่ละตัวจะคำนวณชุดของการขยายที่เป็นไปได้ไปยังสถานะปัจจุบันของมันในแต่ละรอบ และเคลื่อนที่ไปยังหนึ่งในนั้นตามความน่าจะเป็น สำหรับมดตัวที่ 1 ความน่าจะเป็นของการเคลื่อนที่จากสถานะหนึ่งไปยังอีกสถานะหนึ่งขึ้นอยู่กับการรวมกันของสองค่า คือความน่าสนใจของการเคลื่อนที่ ซึ่งคำนวณโดยฮิวริสติกบางอย่างที่บ่งชี้ถึง ความน่าปรารถนา เบื้องต้นของการเคลื่อนที่นั้น และระดับเส้นทางของการเคลื่อนที่ ซึ่งบ่งชี้ว่ามันมีความเชี่ยวชาญมากแค่ไหนในอดีตในการเคลื่อนที่นั้นระดับเส้นทางแสดงถึงการบ่งชี้ภายหลังถึงความน่าปรารถนาของการเคลื่อนที่นั้น ${\displaystyle x}$${\displaystyle y}$${\displaystyle k}$${\displaystyle A_{k}(x)}$${\displaystyle k}$${\displaystyle p_{xy}^{k}}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \eta _{xy}}$${\displaystyle \tau _{xy}}$

โดยทั่วไปมดตัวที่ th จะเคลื่อนที่จากสถานะหนึ่งไปยังอีกสถานะหนึ่งด้วยความน่าจะเป็น ${\displaystyle k}$${\displaystyle x}$${\displaystyle y}$

${\displaystyle p_{xy}^{k}={\frac {(\tau _{xy}^{\alpha })(\eta _{xy}^{\beta })}{\sum _{z\in \mathrm {allowed} _{y}}(\tau _{xz}^{\alpha })(\eta _{xz}^{\beta })}}}$

โดยที่คือปริมาณฟีโรโมนที่สะสมไว้สำหรับการเปลี่ยนสถานะจากสถานะหนึ่งไปยังอีก สถานะ หนึ่ง≥ 0 คือพารามิเตอร์ที่ใช้ควบคุมอิทธิพลของคือความน่าสนใจของการเปลี่ยนสถานะ( ความรู้เบื้องต้น โดยทั่วไปคือ โดยที่คือระยะทาง) และ≥ 1 คือพารามิเตอร์ที่ใช้ควบคุมอิทธิพลของและ แทนระดับเส้นทาง และความน่าดึงดูดใจสำหรับการเปลี่ยนสถานะอื่นๆ ที่เป็นไปได้ ${\displaystyle \tau _{xy}}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \alpha }$${\displaystyle \tau _{xy}}$${\displaystyle \eta _{xy}}$${\displaystyle xy}$${\displaystyle 1/d_{xy}}$${\displaystyle d}$${\displaystyle \beta }$${\displaystyle \eta _{xy}}$${\displaystyle \tau _{xz}}$${\displaystyle \eta _{xz}}$

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

${\displaystyle \tau _{xy}\leftarrow (1-\rho )\tau _{xy}+\sum _{k}^{m}\Delta \tau _{xy}^{k}}$

โดยที่คือปริมาณฟีโรโมนที่ถูกปล่อยออกมาสำหรับการเปลี่ยนสถานะคือสัมประสิทธิ์การระเหยของฟีโรโมนคือจำนวนมด และคือปริมาณฟีโรโมนที่ปล่อยออกมาโดยมดตัวที่ ซึ่งโดยทั่วไปจะกำหนดไว้สำหรับ ปัญหา TSP (โดยการเคลื่อนที่สอดคล้องกับส่วนโค้งของกราฟ) โดย ${\displaystyle \tau _{xy}}$${\displaystyle xy}$${\displaystyle \rho }$${\displaystyle m}$${\displaystyle \Delta \tau _{xy}^{k}}$${\displaystyle k}$

${\displaystyle \Delta \tau _{xy}^{k}={\begin{cases}Q/L_{k}&{\mbox{if ant }}k{\mbox{ uses curve }}xy{\mbox{ in its tour}}\\0&{\mbox{otherwise}}\end{cases}}}$

โดยที่คือค่าใช้จ่ายในการเดินทางของสัตว์ตัวที่ th (โดยทั่วไปคือระยะทาง) และคือค่าคงที่ ${\displaystyle L_{k}}$${\displaystyle k}$${\displaystyle Q}$

ต่อไปนี้คือตัวอย่างอัลกอริทึม ACO ที่ได้รับความนิยมมากที่สุดบางส่วน

ระบบมดเป็นอัลกอริทึม ACO ตัวแรก อัลกอริทึมนี้สอดคล้องกับอัลกอริทึมที่นำเสนอข้างต้น พัฒนาโดย Dorigo ^{[ 26 ]}

ในอัลกอริทึมระบบอาณานิคมมด ระบบมดดั้งเดิมได้รับการปรับเปลี่ยนในสามด้านดังนี้:

1. การเลือกขอบนั้นเอนเอียงไปทางด้านการหาประโยชน์ (กล่าวคือ ให้ความสำคัญกับโอกาสในการเลือกขอบที่สั้นที่สุดซึ่งมีฟีโรโมนจำนวนมาก)
2. ในระหว่างการสร้างวิธีแก้ปัญหา มดจะเปลี่ยนแปลงระดับฟีโรโมนของขอบที่พวกมันเลือกโดยใช้กฎการปรับปรุงฟีโรโมนเฉพาะที่
3. เมื่อสิ้นสุดการวนซ้ำแต่ละครั้ง มดที่ดีที่สุดเท่านั้นที่จะได้รับอนุญาตให้อัปเดตเส้นทางโดยใช้กฎการอัปเดตฟีโรโมนทั่วโลกที่แก้ไขแล้ว^{[ 27 ]}

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

อัลกอริทึมนี้ควบคุมปริมาณฟีโรโมนสูงสุดและต่ำสุดในแต่ละเส้นทาง เฉพาะเส้นทางที่ดีที่สุดโดยรวมหรือเส้นทางที่ดีที่สุดของการวนซ้ำเท่านั้นที่ได้รับอนุญาตให้เพิ่มฟีโรโมนลงในเส้นทาง เพื่อหลีกเลี่ยงภาวะชะงักงันของอัลกอริทึมการค้นหา ช่วงของปริมาณฟีโรโมนที่เป็นไปได้ในแต่ละเส้นทางจะถูกจำกัดไว้ที่ช่วง [τ _max ,τ _min ] ขอบทั้งหมดจะถูกกำหนดค่าเริ่มต้นเป็น τ _maxเพื่อบังคับให้มีการสำรวจโซลูชันที่สูงขึ้น เส้นทางจะถูกกำหนดค่าเริ่มต้นใหม่เป็น τ _maxเมื่อใกล้ถึงภาวะชะงักงัน^{[ 28 ]}

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

ระบบอาณานิคมมด (ACS) ที่มีกลยุทธ์การสื่อสารได้รับการพัฒนาขึ้น มดเทียมถูกแบ่งออกเป็นหลายกลุ่ม มีการเสนอวิธีการสื่อสารเจ็ดวิธีสำหรับการอัปเดตระดับฟีโรโมนระหว่างกลุ่มใน ACS และใช้งานได้กับปัญหาพนักงานขายเดินทาง ^{[ 29 ]}

กลไกการฝากฟีโรโมนของ COAC ช่วยให้มดสามารถค้นหาวิธีแก้ปัญหาร่วมกันได้อย่างมีประสิทธิภาพ โดยใช้วิธีการออกแบบเชิงตั้งฉาก มดในโดเมนที่เป็นไปได้สามารถสำรวจพื้นที่ที่เลือกได้อย่างรวดเร็วและมีประสิทธิภาพ พร้อมความสามารถในการค้นหาทั่วโลกและความแม่นยำที่เพิ่มขึ้น วิธีการออกแบบเชิงตั้งฉากและวิธีการปรับรัศมีแบบปรับได้ยังสามารถขยายไปยังอัลกอริธึมการเพิ่มประสิทธิภาพอื่นๆ เพื่อให้ได้ข้อได้เปรียบที่กว้างขึ้นในการแก้ปัญหาในทางปฏิบัติ^{[ 30 ]}

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

สำหรับอัลกอริทึมบางเวอร์ชัน สามารถพิสูจน์ได้ว่ามีการลู่เข้า (กล่าวคือ สามารถหาค่าเหมาะสมที่สุดทั่วโลกได้ในเวลาจำกัด) หลักฐานแรกของการลู่เข้าสำหรับอัลกอริทึมอาณานิคมมดเกิดขึ้นในปี 2000 คืออัลกอริทึมระบบมดแบบกราฟ และต่อมาสำหรับอัลกอริทึม ACS และ MMAS เช่นเดียวกับเมตาฮิวริสติก ส่วนใหญ่ เป็นเรื่องยากมากที่จะประเมินความเร็วการลู่เข้าทางทฤษฎี การวิเคราะห์ประสิทธิภาพของอัลกอริทึมอาณานิคมมดแบบต่อเนื่องโดยพิจารณาจากพารามิเตอร์ต่างๆ (กลยุทธ์การเลือกขอบ เมตริกการวัดระยะทาง และอัตราการระเหยของฟีโรโมน) แสดงให้เห็นว่าประสิทธิภาพและอัตราการลู่เข้ามีความไวต่อค่าพารามิเตอร์ที่เลือก โดยเฉพาะอย่างยิ่งค่าของอัตราการระเหยของฟีโรโมน^{[ 33 ]}ในปี 2004 Zlochin และเพื่อนร่วมงานของเขา^{[ 8 ]}แสดงให้เห็นว่าอัลกอริทึมประเภท ACO มีความเกี่ยวข้องอย่างใกล้ชิดกับการลดระดับความชันแบบสุ่มวิธีเอนโทรปีแบบไขว้และอัลกอริทึมการประมาณการกระจาย พวกเขาเสนอคำศัพท์รวมว่า "การค้นหาตามแบบจำลอง" เพื่อใช้อธิบายเม ตา ฮิวริสติกประเภทนี้

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

อัลกอริทึม ACO ตัวแรกเรียกว่าระบบมด^{[ 26 ]}และมีจุดมุ่งหมายเพื่อแก้ปัญหาพนักงานขายเดินทาง ซึ่งเป้าหมายคือการหาเส้นทางไป-กลับที่สั้นที่สุดเพื่อเชื่อมโยงเมืองต่างๆ เข้าด้วยกัน อัลกอริทึมโดยทั่วไปค่อนข้างเรียบง่ายและอิงตามชุดของมด โดยแต่ละตัวจะทำการเดินทางไป-กลับที่เป็นไปได้หนึ่งเส้นทางตามเมืองต่างๆ ในแต่ละขั้นตอน มดจะเลือกที่จะย้ายจากเมืองหนึ่งไปยังอีกเมืองหนึ่งตามกฎบางประการ:

1. ต้องเดินทางไปเยือนแต่ละเมืองเพียงครั้งเดียวเท่านั้น
2. เมืองที่อยู่ห่างไกลมีโอกาสน้อยกว่าที่จะถูกเลือก (เนื่องจากมองเห็นได้ชัดเจน)
3. ยิ่งร่องรอยฟีโรโมนที่ทิ้งไว้ตามแนวเขตแดนระหว่างสองเมืองมีความเข้มข้นมากเท่าไร โอกาสที่แนวเขตแดนนั้นจะถูกเลือกก็จะยิ่งมากขึ้นเท่านั้น
4. เมื่อเดินทางเสร็จสิ้น มดจะปล่อยฟีโรโมนเพิ่มเติมตามขอบทางที่มันเดินทางผ่าน หากการเดินทางนั้นสั้น
5. หลังจากแต่ละรอบ ร่องรอยของฟีโรโมนจะระเหยหายไป

• ปัญหาการเรียงลำดับตามลำดับ (SOP) ^{[ 34 ]}
• ปัญหา การจัดตารางงาน (JSP) ^{[ 35 ]}
• ปัญหาการจัดตารางเวลาร้านค้าเปิด (OSP) ^{[ 36 ] [ 37 ]}
• ปัญหาการเรียงลำดับการไหลของร้านค้า (PFSP) ^{[ 38 ]}
• ปัญหาความล่าช้ารวมของเครื่องจักรเครื่องเดียว (SMTTP) ^{[ 39 ]}
• ปัญหาความล่าช้ารวมถ่วงน้ำหนักของเครื่องจักรเครื่องเดียว (SMTWTP) ^{[ 40 ] [ 41 ] [ 42 ]}
• ปัญหาการจัดตารางเวลาโครงการที่มีข้อจำกัดด้านทรัพยากร (RCPSP) ^{[ 43 ]}
• ปัญหาการจัดตารางเวลาร้านค้ากลุ่ม (GSP) ^{[ 44 ]}
• ปัญหาความล่าช้ารวมของเครื่องจักรเครื่องเดียวที่มีเวลาการตั้งค่าขึ้นอยู่กับลำดับ (SMTTPDST) ^{[ 45 ]}
• ปัญหาการจัดตารางเวลาการผลิตแบบหลายขั้นตอน (MFSP) ที่มีเวลาการตั้งค่า/การเปลี่ยนขึ้นอยู่กับลำดับ^{[ 46 ]}
• ปัญหาการวางแผนลำดับการประกอบ (ASP) ^{[ 47 ]}

• ปัญหาการกำหนดเส้นทางยานพาหนะที่มีความจุ (CVRP) ^{[ 48 ] [ 49 ] [ 50 ]}
• ปัญหาการกำหนดเส้นทางยานพาหนะหลายคลังสินค้า (MDVRP) ^{[ 51 ]}
• ปัญหาการกำหนดเส้นทางยานพาหนะตามช่วงเวลา (PVRP) ^{[ 52 ]}
• ปัญหาการกำหนดเส้นทางยานพาหนะจัดส่งแยก (SDVRP) ^{[ 53 ]}
• ปัญหาการกำหนดเส้นทางยานพาหนะแบบสุ่ม (SVRP) ^{[ 54 ]}
• ปัญหาการกำหนดเส้นทางยานพาหนะสำหรับการรับและส่งมอบ (VRPPD) ^{[ 55 ] [ 56 ]}
• ปัญหาการกำหนดเส้นทางยานพาหนะด้วยช่วงเวลา (VRPTW) ^{[ 57 ] [ 58 ] [ 59 ] [ 60 ]}
• ปัญหาการกำหนดเส้นทางยานพาหนะที่ขึ้นอยู่กับเวลาพร้อมหน้าต่างเวลา (TDVRPTW) ^{[ 61 ]}
• ปัญหาการจัดเส้นทางยานพาหนะที่มีช่วงเวลาและเจ้าหน้าที่บริการหลายคน (VRPTWMS)

• ปัญหาการจัดสรรกำลังสอง (QAP) ^{[ 62 ]}
• ปัญหาการมอบหมายทั่วไป (GAP) ^{[ 63 ] [ 64 ]}
• ปัญหาการจัดสรรความถี่ (FAP) ^{[ 65 ]}
• ปัญหาการจัดสรรส่วนเกิน (RAP) ^{[ 66 ]}

• ปัญหาชุดปกคลุม (SCP) ^{[ 67 ] [ 68 ]}
• ปัญหาการแบ่งส่วน (SPP) ^{[ 69 ]}
• ปัญหาการแบ่งต้นไม้กราฟที่มีข้อจำกัดน้ำหนัก (WCGTPP) ^{[ 70 ]}
• ปัญหาต้นไม้ l-cardinality ที่ถ่วงน้ำหนักส่วนโค้ง (AWlCTP) ^{[ 71 ]}
• ปัญหากระเป๋าหลายใบ (MKP) ^{[ 72 ]}
• ปัญหาชุดอิสระสูงสุด (MIS) ^{[ 73 ]}

• การเพิ่มประสิทธิภาพวงจรขยายสัญญาณ CMOS ขนาด 45 นาโนเมตรโดยใช้การปรับปรุงด้วยอัลกอริทึม Ant colony optimization (ACO) สามารถบรรลุโซลูชันที่เหมาะสมที่สุดได้ในเวลาที่น้อยมาก^{[ 74 ]}
• การสังเคราะห์วงจรย้อนกลับโดยใช้การปรับปรุงประสิทธิภาพของอาณานิคมมด (ACO) สามารถปรับปรุงประสิทธิภาพได้อย่างมีนัยสำคัญ^{[ 75 ]}

เพื่อเพิ่มประสิทธิภาพรูปแบบของเสาอากาศ สามารถใช้อัลกอริธึมอาณานิคมมดได้ ตัวอย่างเช่น สามารถพิจารณาเสาอากาศ RFID-tag ที่ใช้อัลกอริธึมอาณานิคมมด (ACO) ^{[ 77 ]}ตัวสั่นแบบวนกลับและไม่วนกลับ 10×10 ^{[ 76 ]}

อัลกอริทึม ACO ใช้ในการประมวลผลภาพสำหรับการตรวจจับขอบ ภาพ และการเชื่อมโยงขอบ ภาพ ^{[ 78 ] [ 79 ]}

• การตรวจจับขอบ:

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

ขั้นตอนต่อไปนี้เกี่ยวข้องกับการตรวจจับขอบโดยใช้ ACO: ^{[ 80 ] [ 81 ] [ 82 ]}

ขั้นตอนที่ 1: การกำหนดค่าเริ่มต้นวางมดแบบสุ่มบนภาพโดย กำหนดค่าเริ่มต้นให้กับ เมทริกซ์ฟีโรโมนด้วยค่าสุ่ม ความท้าทายหลักในกระบวนการกำหนดค่าเริ่มต้นคือการกำหนดเมทริกซ์ฮิวริสติก ${\displaystyle K}$${\displaystyle I_{M_{1}M_{2}}}$${\displaystyle K=(M_{1}*M_{2})^{\tfrac {1}{2}}}$${\displaystyle \tau _{(i,j)}}$

มีหลายวิธีในการกำหนดเมทริกซ์ฮิวริสติก สำหรับตัวอย่างด้านล่างนี้ เมทริกซ์ฮิวริสติกคำนวณจากสถิติเฉพาะที่: สถิติเฉพาะที่ตำแหน่งพิกเซล ${\displaystyle (i,j)}$

${\displaystyle \eta _{(i,j)}={\tfrac {1}{Z}}*Vc*I_{(i,j)},}$

รูปภาพขนาดนี้อยู่ ที่ไหน${\displaystyle I}$${\displaystyle M_{1}*M_{2}}$

${\displaystyle Z=\sum _{i=1:M_{1}}\sum _{j=1:M_{2}}Vc(I_{i,j})}$

เป็นปัจจัยการปรับค่ามาตรฐาน และ

${\displaystyle {\begin{aligned}Vc(I_{i,j})=&f\left(\left\vert I_{(i-2,j-1)}-I_{(i+2,j+1)}\right\vert +\left\vert I_{(i-2,j+1)}-I_{(i+2,j-1)}\right\vert \right.\\&+\left\vert I_{(i-1,j-2)}-I_{(i+1,j+2)}\right\vert +\left\vert I_{(i-1,j-1)}-I_{(i+1,j+1)}\right\vert \\&+\left\vert I_{(i-1,j)}-I_{(i+1,j)}\right\vert +\left\vert I_{(i-1,j+1)}-I_{(i-1,j-1)}\right\vert \\&+\left.\left\vert I_{(i-1,j+2)}-I_{(i-1,j-2)}\right\vert +\left\vert I_{(i,j-1)}-I_{(i,j+1)}\right\vert \right)\end{aligned}}}$

${\displaystyle f(\cdot )}$สามารถคำนวณได้โดยใช้ฟังก์ชันต่อไปนี้:

${\displaystyle f(x)=\lambda x,\quad {\text{for x ≥ 0; (1)}}}$

${\displaystyle f(x)=\lambda x^{2},\quad {\text{for x ≥ 0; (2)}}}$

${\displaystyle f(x)={\begin{cases}\sin({\frac {\pi x}{2\lambda }}),&{\text{for 0 ≤ x ≤}}\lambda {\text{; (3)}}\\0,&{\text{else}}\end{cases}}}$

${\displaystyle f(x)={\begin{cases}\pi x\sin({\frac {\pi x}{2\lambda }}),&{\text{for 0 ≤ x ≤}}\lambda {\text{; (4)}}\\0,&{\text{else}}\end{cases}}}$

พารามิเตอร์ในแต่ละฟังก์ชันข้างต้นจะปรับรูปร่างของฟังก์ชันนั้นๆ ${\displaystyle \lambda }$

ขั้นตอนที่ 2: กระบวนการสร้างการเคลื่อนที่ของมดขึ้นอยู่กับพิกเซลที่เชื่อมต่อกัน 4 จุด หรือ8 จุดความน่าจะเป็นที่มดจะเคลื่อนที่นั้นกำหนดโดยสมการความน่าจะเป็น${\displaystyle P_{x,y}}$

ขั้นตอนที่ 3 และขั้นตอนที่ 5: กระบวนการอัปเดต เมทริกซ์ฟีโรโมนจะได้รับการอัปเดตสองครั้ง ในขั้นตอนที่ 3 เส้นทางของมด (กำหนดโดย) จะได้รับการอัปเดต ในขณะที่ในขั้นตอนที่ 5 อัตราการระเหยของเส้นทางจะได้รับการอัปเดต ซึ่งกำหนดโดย: ${\displaystyle \tau _{(x,y)}}$

${\displaystyle \tau _{new}\leftarrow (1-\psi )\tau _{old}+\psi \tau _{0}}$,

ค่าสัมประสิทธิ์การสลายตัวของฟีโรโมนอยู่ที่ไหน${\displaystyle \psi }$${\displaystyle 0<\tau <1}$

ขั้นตอนที่ 7: กระบวนการตัดสินใจเมื่อมด K ตัวเคลื่อนที่ไปเป็นระยะทางคงที่ L เป็นจำนวน N รอบ การตัดสินใจว่าจะเป็นขอบหรือไม่นั้นขึ้นอยู่กับค่าเกณฑ์ T บนเมทริกซ์ฟีโรโมน τ ค่าเกณฑ์สำหรับตัวอย่างด้านล่างคำนวณโดยใช้วิธีของ Otsu

ตรวจจับขอบภาพโดยใช้ ACO: ภาพด้านล่างสร้างขึ้นโดยใช้ฟังก์ชันต่าง ๆ ที่กำหนดโดยสมการ (1) ถึง (4) ^{[ 83 ]}

• การเชื่อมโยงขอบ: ^{[ 84 ]} ACO ยังพิสูจน์แล้วว่ามีประสิทธิภาพในอัลกอริทึมการเชื่อมโยงขอบ

• การคาดการณ์การล้มละลาย^{[ 85 ]}
• การจำแนกประเภท^{[ 35 ]}
• การวางแผนการผลิตระยะยาวของเหมืองเปิด^{[ 86 ]}
• การกำหนดเส้นทางเครือข่ายแบบเน้นการเชื่อมต่อ^{[ 87 ]}
• การกำหนดเส้นทางเครือข่ายแบบไร้การเชื่อมต่อ^{[ 88 ] [ 89 ]}
• การขุดข้อมูล^{[ 35 ] [ 90 ] [ 91 ] [ 92 ]}
• กระแสเงินสดที่คิดลดในการกำหนดตารางเวลาโครงการ^{[ 93 ]}
• การดึงข้อมูลแบบกระจาย^{[ 94 ] [ 95 ]}
• การออกแบบเครือข่ายพลังงานและไฟฟ้า^{[ 96 ]}
• ปัญหาการจัดกำหนดการเวิร์กโฟลว์กริด^{[ 97 ]}
• การออกแบบเปปไทด์ยับยั้งสำหรับปฏิสัมพันธ์ระหว่างโปรตีน^{[ 98 ]}
• ระบบทดสอบอัจฉริยะ^{[ 99 ]}
• การออกแบบวงจรอิเล็กทรอนิกส์กำลัง^{[ 100 ]}
• การพับโปรตีน^{[ 101 ] [ 102 ] [ 103 ]}
• การระบุระบบ^{[ 104 ] [ 105 ]}

ด้วยอัลกอริทึม ACO เส้นทางที่สั้นที่สุดในกราฟระหว่างจุด A และ B จะถูกสร้างขึ้นจากการรวมกันของเส้นทางหลายเส้นทาง^{[ 106 ]}การให้คำจำกัดความที่แม่นยำว่าอัลกอริทึมใดเป็นหรือไม่ใช่อัลกอริทึมอาณานิคมมดนั้นไม่ใช่เรื่องง่าย เพราะคำจำกัดความอาจแตกต่างกันไปตามผู้เขียนและการใช้งาน โดยทั่วไปแล้ว อัลกอริทึมอาณานิคมมดถือเป็นเมตาฮิวริสติกที่มีประชากร โดยแต่ละวิธีแก้ปัญหาแทนด้วยมดที่เคลื่อนที่ในพื้นที่การค้นหา^{[ 107 ]}มดจะทำเครื่องหมายวิธีแก้ปัญหาที่ดีที่สุดและคำนึงถึงเครื่องหมายก่อนหน้าเพื่อเพิ่มประสิทธิภาพการค้นหาของพวกมัน พวกมันสามารถมองได้ว่าเป็นอัลก อริทึม หลายเอเจน ต์เชิงความน่าจะเป็นโดย ใช้การกระจายความน่าจะ เป็น เพื่อทำการเปลี่ยนผ่านระหว่างการวนซ้ำ แต่ละครั้ง ^{[ 108 ]}ในเวอร์ชันสำหรับปัญหาเชิงการจัดเรียง พวกมันใช้การสร้างวิธีแก้ปัญหาแบบวนซ้ำ[ ^{109 ] ตาม}ที่ผู้เขียนบางคนกล่าว สิ่งที่ทำให้ ACO แตกต่างจากญาติอื่นๆ (เช่น อัลกอริทึมในการประมาณการการกระจายหรือการเพิ่มประสิทธิภาพฝูงอนุภาค) ก็คือลักษณะการสร้างของมันนั่นเอง ในปัญหาเชิงการจัดเรียง เป็นไปได้ว่าในที่สุดจะพบวิธีแก้ปัญหาที่ดีที่สุด แม้ว่าจะไม่มีมดตัวใดพิสูจน์ได้ว่ามีประสิทธิภาพก็ตาม ดังนั้น ในตัวอย่างของปัญหาพนักงานขายเดินทาง ไม่จำเป็นว่ามดจะต้องเดินทางตามเส้นทางที่สั้นที่สุดเสมอไป เส้นทางที่สั้นที่สุดสามารถสร้างขึ้นจากส่วนที่แข็งแกร่งที่สุดของวิธีแก้ปัญหาที่ดีที่สุดได้ อย่างไรก็ตาม คำจำกัดความนี้อาจมีปัญหาในกรณีของปัญหาในตัวแปรจริง ซึ่งไม่มีโครงสร้างของ 'เพื่อนบ้าน' อยู่ พฤติกรรมโดยรวมของแมลงสังคมยังคงเป็นแหล่งแรงบันดาลใจสำหรับนักวิจัย ความหลากหลายของอัลกอริธึม (สำหรับการเพิ่มประสิทธิภาพหรือไม่) ที่แสวงหาการจัดระเบียบตนเองในระบบชีวภาพได้นำไปสู่แนวคิดของ " ปัญญาฝูง " ^{[ 11 ]}ซึ่งเป็นกรอบงานทั่วไปมากที่อัลกอริธึมอาณานิคมมดเหมาะสม

ในทางปฏิบัติมีอัลกอริทึมจำนวนมากที่อ้างว่าเป็น "อาณานิคมมด" โดยที่ไม่ได้ใช้กรอบการทำงานทั่วไปของการเพิ่มประสิทธิภาพโดยอาณานิคมมดแบบมาตรฐานเสมอไป^{[ 110 ]}ในทางปฏิบัติ การใช้การแลกเปลี่ยนข้อมูลระหว่างมดผ่านสิ่งแวดล้อม (หลักการที่เรียกว่า " stigmergy ") ถือว่าเพียงพอแล้วสำหรับอัลกอริทึมที่จะอยู่ในกลุ่มของอัลกอริทึมอาณานิคมมด หลักการนี้ทำให้ผู้เขียนบางคนสร้างคำว่า "ค่า" ขึ้นมาเพื่อจัดระเบียบวิธีการและพฤติกรรมโดยอิงจากการค้นหาอาหาร การคัดแยกตัวอ่อน การแบ่งงาน และการขนส่งแบบร่วมมือ^{[ 111 ]}

อัลกอริทึมทางพันธุกรรม (GA)

วิธีการเหล่านี้ช่วยรักษากลุ่มของวิธีแก้ปัญหาไว้ได้ แทนที่จะมีเพียงวิธีเดียว กระบวนการค้นหาวิธีแก้ปัญหาที่เหนือกว่านั้นเลียนแบบกระบวนการวิวัฒนาการ โดยวิธีแก้ปัญหาต่างๆ จะถูกนำมาผสมผสานหรือกลายพันธุ์เพื่อเปลี่ยนแปลงกลุ่มของวิธีแก้ปัญหา และวิธีแก้ปัญหาที่มีคุณภาพต่ำกว่าจะถูกกำจัดทิ้งไป

อัลกอริทึมการประมาณการกระจาย (EDA)

อัลกอริทึมวิวัฒนาการที่แทนที่ตัวดำเนินการสืบพันธุ์แบบดั้งเดิมด้วยตัวดำเนินการนำทางแบบจำลอง แบบจำลองดังกล่าวเรียนรู้จากประชากรโดยใช้เทคนิคการเรียนรู้ของเครื่องและแสดงเป็นแบบจำลองกราฟิกความน่าจะเป็น ซึ่งสามารถสุ่มตัวอย่างโซลูชันใหม่ได้^{[ 112 ] [ 113 ]}หรือสร้างขึ้นจากการผสมข้ามแบบมีคำแนะนำ^{[ 114 ] [ 115 ]}

การอบชุบแบบจำลอง (SA)

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

การเพิ่มประสิทธิภาพการค้นหาแบบตอบสนอง

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

การค้นหาต้องห้าม (TS)

วิธีการนี้คล้ายคลึงกับการจำลองการอบชุบ (simulated annealing) ตรงที่ทั้งสองวิธีสำรวจพื้นที่คำตอบโดยการทดสอบการกลายพันธุ์ของคำตอบแต่ละคำตอบ แต่การจำลองการอบชุบจะสร้างคำตอบที่กลายพันธุ์เพียงหนึ่งเดียว ในขณะที่การค้นหาแบบแทบู (tabu search) จะสร้างคำตอบที่กลายพันธุ์หลายคำตอบและจะย้ายไปยังคำตอบที่มีค่าความเหมาะสม (fitness) ต่ำที่สุดในบรรดาคำตอบที่สร้างขึ้น เพื่อป้องกันการวนซ้ำและส่งเสริมการเคลื่อนที่ผ่านพื้นที่คำตอบมากขึ้น จึงมีการเก็บรักษาลิสต์แทบู (tabu list) ซึ่งประกอบด้วยคำตอบบางส่วนหรือคำตอบทั้งหมด ห้ามย้ายไปยังคำตอบที่มีองค์ประกอบอยู่ในลิสต์แทบู ซึ่งจะได้รับการอัปเดตเมื่อคำตอบสำรวจพื้นที่คำตอบ

ระบบภูมิคุ้มกันเทียม (AIS)

จำลองมาจากระบบภูมิคุ้มกันของสัตว์มีกระดูกสันหลัง

การเพิ่มประสิทธิภาพฝูงอนุภาค (PSO)

วิธีการปัญญาประดิษฐ์แบบกลุ่ม (Swarm Intelligence )

หยดน้ำอัจฉริยะ (IWD)

อัลกอริทึมการเพิ่มประสิทธิภาพแบบกลุ่มที่อิงตามการไหลของหยดน้ำตามธรรมชาติในแม่น้ำ

อัลกอริทึมการค้นหาตามแรงโน้มถ่วง (GSA)

วิธีการปัญญาประดิษฐ์แบบกลุ่ม (Swarm Intelligence )

วิธีการจัดกลุ่มแบบอาณานิคมมด (ACCM)

วิธีการที่ใช้แนวทางการจัดกลุ่ม (clustering) ซึ่งเป็นการต่อยอดจาก ACO (Absolute Concentration of Coefficient of Coefficient)

การค้นหาแบบแพร่กระจายสุ่ม (SDS)

เทคนิคการค้นหาและเพิ่มประสิทธิภาพระดับโลกเชิงความน่าจะเป็นแบบอิงตัวแทน เหมาะที่สุดสำหรับปัญหาที่ฟังก์ชันเป้าหมายสามารถแยกย่อยออกเป็นฟังก์ชันย่อยอิสระหลายฟังก์ชันได้

ลำดับเหตุการณ์ของอัลกอริทึม ACO

ลำดับเหตุการณ์ของอัลกอริทึมการเพิ่มประสิทธิภาพโดยใช้ฝูงมด

• ^ในปี พ.ศ. 2492 ปิแอร์-ปอล กราสเซ่ได้คิดค้นทฤษฎีสติ๊กเมอร์จีเพื่ออธิบายพฤติกรรมการสร้างรังของปลวก [ ^{116 ]}
• ^{ใน ปี}พ.ศ. 2526 Deneubourg และเพื่อนร่วมงานของเขาได้ศึกษาพฤติกรรมรวมหมู่ของมด [ ^{117 ]}
• 1988 และ Moyson Manderick มีบทความเกี่ยวกับการจัดระเบียบตนเองในหมู่มด^{[ 118 ]}
• ในปี พ.ศ. 2532 ผลงานของ Goss, Aron, Deneubourg และ Pasteels เกี่ยวกับพฤติกรรมรวมหมู่ของมดอาร์เจนตินาซึ่งก่อให้เกิดแนวคิดเกี่ยวกับอัลกอริธึมการเพิ่มประสิทธิภาพอาณานิคมมด^{[ 119 ]}
• พ.ศ. 2532 การนำแบบจำลองพฤติกรรมด้านอาหารมาใช้โดย Ebling และเพื่อนร่วมงานของเขา^{[ 120 ]}
• ในปี พ.ศ. 2534 M. Dorigo ได้เสนอระบบมดในวิทยานิพนธ์ปริญญาเอกของเขา (ซึ่งได้รับการตีพิมพ์ในปี พ.ศ. 2535 ^{[ 7 ]} ) รายงานทางเทคนิคที่ดึงมาจากวิทยานิพนธ์และร่วมเขียนโดย V. Maniezzo และ A. Colorni ^{[ 121 ]}ได้รับการตีพิมพ์ห้าปีต่อมา^{[ 26 ]}
• 1994 Appleby และ Steward จาก British Telecommunications Plc ได้เผยแพร่แอปพลิเคชันแรกสำหรับเครือข่ายโทรคมนาคม^{[ 122 ]}
• ในปี พ.ศ. 2538 Gambardella และ Dorigo ได้เสนอant-q [ ^{123 ] ซึ่ง}เป็นเวอร์ชันเบื้องต้นของระบบอาณานิคมมดในฐานะส่วนขยายแรกของระบบมด^{[ 26 ]}
• 1996 Gambardella และ Dorigo เสนอระบบอาณานิคมมด^{[ 124 ]}
• พ.ศ. 2539 การตีพิมพ์บทความเกี่ยวกับระบบมด^{[ 26 ]}
• 1997 Dorigo และ Gambardella เสนอระบบอาณานิคมมดแบบผสมผสานกับการค้นหาในพื้นที่^{[ 27 ]}
• ในปี พ.ศ. 2540 Schoonderwoerd และเพื่อนร่วมงานของเขาได้เผยแพร่แอปพลิเคชันที่ได้รับการปรับปรุงสำหรับเครือข่ายโทรคมนาคม^{[ 125 ]}
• 1998 Dorigo เปิดตัวการประชุมครั้งแรกที่อุทิศให้กับอัลกอริทึม ACO; ^{[ 126 ]}
• พ.ศ. 2541 Stützle เสนอการใช้งานแบบขนาน^{เบื้องต้น} [ ^{127 ]}
• ในปี พ.ศ. 2542 Gambardella, Taillard และ Agazzi ได้เสนอmacs-vrptwซึ่งเป็นระบบอาณานิคมมดหลายตัวระบบแรกที่นำมาใช้กับปัญหาการกำหนดเส้นทางยานพาหนะที่มีช่วงเวลา^{[ 57 ]}
• ในปี พ.ศ. 2542 Bonabeau, Dorigo และ Theraulaz ได้ตีพิมพ์หนังสือที่กล่าวถึงมดเทียมเป็นหลัก^{[ 128 ]}
• 2000 ฉบับพิเศษของวารสาร Future Generation Computer Systems เกี่ยวกับอัลกอริทึมมด^{[ 129 ]}
• ในปี พ.ศ. 2543 Hoos และ Stützle ได้คิดค้นระบบมด max-min ขึ้น มา^{[ 28 ]}
• ปี 2000 มีการประยุกต์ใช้ครั้งแรกในการจัดตารางเวลา ลำดับการจัดตารางเวลา และการปฏิบัติตามข้อจำกัดต่างๆ
• ในปี พ.ศ. 2543 Gutjahr ได้ให้หลักฐานแรกของการบรรจบกันของอัลกอริทึมของอาณานิคมมด^{[ 130 ]}
• ปี 2001 บริษัทต่างๆ เริ่มนำอัลกอริทึม COA มาใช้เป็นครั้งแรก ( EurobiosและAntOptima )
• ในปี พ.ศ. 2544 Iredi และเพื่อนร่วมงานของเขาได้ตีพิมพ์อัลกอริทึมแบบหลายวัตถุประสงค์ ตัวแรก ^{[ 131 ]}
• ปี 2002 มีการนำเครือข่ายเบย์เซียนมาประยุกต์ใช้ครั้งแรกในการออกแบบตารางเวลา
• ในปี พ.ศ. 2545 Bianchi และเพื่อนร่วมงานของเธอได้เสนออัลกอริทึมแรกสำหรับปัญหาเชิงสุ่ม^{[ 132 ]}
• 2004 Dorigo และ Stützle ตีพิมพ์หนังสือ Ant Colony Optimization กับสำนักพิมพ์ MIT Press ^{[ 133 ]}
• ในปี 2547 Zlochin และ Dorigo แสดงให้เห็นว่าอัลกอริทึมบางอย่างเทียบเท่ากับการลดระดับความชันแบบสุ่มวิธีเอนโทรปีแบบไขว้และอัลกอริทึมในการประมาณการกระจาย^{[ 8 ]}
• ปี 2005 มีการประยุกต์ใช้ครั้งแรกในการแก้ปัญหาการพับตัวของโปรตีน
• ในปี 2012 Prabhakar และเพื่อนร่วมงานได้ตีพิมพ์งานวิจัยที่เกี่ยวข้องกับการทำงานของมดแต่ละตัวที่สื่อสารกันโดยไม่ใช้ฟีโรโมน ซึ่งสะท้อนหลักการของการจัดการเครือข่ายคอมพิวเตอร์ รูปแบบการสื่อสารนี้ได้รับการเปรียบเทียบกับโปรโตคอลควบคุมการส่งข้อมูล^{[ 134 ]}
• 2016 การประยุกต์ใช้ครั้งแรกในการออกแบบลำดับเปปไทด์^{[ 98 ]}
• ในปี 2017 ได้มีการบูรณาการวิธีการตัดสินใจแบบหลายเกณฑ์ PROMETHEE เข้ากับอัลกอริทึม ACO ( อัลกอริทึม HUMANT ) สำเร็จ ^{[ 135 ]}

• M. Dorigo , 1992. การเพิ่มประสิทธิภาพ การเรียนรู้ และอัลกอริทึมธรรมชาติ , วิทยานิพนธ์ปริญญาเอก, มหาวิทยาลัยโพลีเทคนิคแห่งมิลาน, อิตาลี
• M. Dorigo, V. Maniezzo & A. Colorni, 1996. " ระบบมด: การเพิ่มประสิทธิภาพโดยอาณานิคมของตัวแทนที่ร่วมมือกัน ", IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26 (1): 29–41
• M. Dorigo & LM Gambardella , 1997. " ระบบอาณานิคมมด: แนวทางการเรียนรู้แบบร่วมมือสำหรับปัญหาพนักงานขายเดินทาง " IEEE Transactions on Evolutionary Computation, 1 (1): 53–66.
• M. Dorigo, G. Di Caro & LM Gambardella, 1999. " อัลกอริทึมมดสำหรับการเพิ่มประสิทธิภาพแบบไม่ต่อเนื่องเก็บถาวรเมื่อ 2018-10-06 ที่Wayback Machine ". Artificial Life, 5 (2): 137–172.
• E. Bonabeau, M. Dorigo และ G. Theraulaz, 1999. ปัญญาแบบฝูง: จากระบบธรรมชาติสู่ระบบเทียม , สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด. ISBN 0-19-513159-2
• M. Dorigo และ T. Stützle, 2004. การเพิ่มประสิทธิภาพด้วยอัลกอริทึม Ant Colony Optimization , สำนักพิมพ์ MIT Press. ISBN 0-262-04219-3
• M. Dorigo, 2007. "การปรับปรุงประสิทธิภาพของอาณานิคมมด" . Scholarpedia.
• C. Blum, 2005 " การปรับปรุงประสิทธิภาพของอาณานิคมมด: บทนำและแนวโน้มล่าสุด " วารสารฟิสิกส์แห่งชีวิต, 2: 353-373
• M. Dorigo, M. Birattari และ T. Stützle, 2006 การเพิ่มประสิทธิภาพด้วยฝูงมด: มดเทียมในฐานะเทคนิคปัญญาประดิษฐ์เชิงคำนวณ TR/IRIDIA/2006-023
• Mohd Murtadha Mohamad, "การ วางแผนการเคลื่อนที่ของหุ่นยนต์ข้อต่อโดยใช้กลยุทธ์มดหาอาหาร", วารสารเทคโนโลยีสารสนเทศ - ฉบับพิเศษด้านปัญญาประดิษฐ์, เล่มที่ 20, ฉบับที่ 4 หน้า 163–181, ธันวาคม 2551, ISSN 0128-3790 
• N. Monmarché, F. Guinand & P. ​​Siarry (บรรณาธิการ), "Artificial Ants", สิงหาคม 2010 ปกแข็ง 576 หน้า  ISBN 978-1-84821-194-0.
• A. Kazharov, V. Kureichik, 2010. " อัลกอริทึมการเพิ่มประสิทธิภาพด้วยฝูงมดสำหรับการแก้ปัญหาการขนส่ง " วารสารวิทยาศาสตร์คอมพิวเตอร์และระบบนานาชาติ เล่มที่ 49 ฉบับที่ 1 หน้า 30–43
• CM. Pintea, 2014, ความก้าวหน้าในการคำนวณที่ได้รับแรงบันดาลใจจากชีววิทยาสำหรับปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัดเรียง , Springer ISBN 978-3-642-40178-7
• K. Saleem, N. Fisal, MA Baharudin, AA Ahmed, S. Hafizah และ S. Kamilah, "โปรโตคอลการกำหนดเส้นทางที่ปรับให้เหมาะสมด้วยตนเองโดยได้รับแรงบันดาลใจจากอาณานิคมมดบนพื้นฐานของสถาปัตยกรรมแบบครอสเลเยอร์สำหรับเครือข่ายเซ็นเซอร์ไร้สาย", WSEAS Trans. Commun., เล่ม 9, ฉบับที่ 10, หน้า 669–678, 2010. ISBN 978-960-474-200-4
• K. Saleem และ N. Fisal, "อัลกอริทึม Ant Colony ที่ได้รับการปรับปรุงเพื่อการกำหนดเส้นทางข้อมูลที่มั่นใจได้ด้วยตนเองในเครือข่ายเซ็นเซอร์ไร้สาย", การประชุมนานาชาติ IEEE ครั้งที่ 18 ด้านเครือข่าย (ICON) ปี 2012, หน้า 422–427. ISBN 978-1-4673-4523-1
• Abolmaali S, Roodposhti FR. การเพิ่มประสิทธิภาพพอร์ตโฟลิโอโดยใช้วิธีอาณานิคมมด กรณีศึกษาตลาดหลักทรัพย์เตหะรานวารสารการบัญชี มีนาคม 2561;8(1).

• หน้าการเพิ่มประสิทธิภาพอาณานิคมมดของ Scholarpedia
• หน้าหลักของการเพิ่มประสิทธิภาพด้วยอัลกอริทึม Ant Colony Optimization
• "การปรับปรุงประสิทธิภาพของอาณานิคมมด" - ชุมชนวิทยาศาสตร์และการวิจัยของรัสเซีย
• AntSim - การจำลองอัลกอริทึมของ Ant Colony
• MIDACO-Solverเป็นซอฟต์แวร์เพิ่มประสิทธิภาพอเนกประสงค์ที่ใช้หลักการเพิ่มประสิทธิภาพด้วยอัลกอริทึมมด (Matlab, Excel, VBA, C/C++, R, C#, Java, Fortran และ Python)
• มหาวิทยาลัยไคเซอร์สเลาเทิร์น ประเทศเยอรมนี, AG Wehn: แอปเพล็ตการเพิ่มประสิทธิภาพด้วยฝูงมดการแสดงภาพการแก้ปัญหาพนักงานขายเดินทางด้วยระบบฝูงมด พร้อมตัวเลือกและพารามิเตอร์มากมาย (แอปเพล็ต Java)
• การจำลองอัลกอริทึมมด (แอปเพล็ต Java)
• เฟรมเวิร์กระบบอาณานิคมมด Java
• การนำอัลกอริทึมการปรับปรุงประสิทธิภาพด้วยฝูงมดมาใช้ (Python Notebook)