蟻群演算法
 |
蟻群演算法（Ant Colony Optimization，ACO），又稱螞蟻演算法，是一種用來在圖中尋找最佳化路徑的機率型演算法。它由Marco Dorigo於1992年在他的博士論文「Ant system: optimization by a colony of cooperating agents」中提出，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種類比進化演算法，初步的研究表明該演算法具有許多優良的性質。針對PID控制器參數最佳化設計問題，將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較，數值仿真結果表明，蟻群演算法具有一種新的類比進化最佳化方法的有效性和應用價值。
常見的擴充[編輯]
下面是一些最常用的變異蟻群演算法：
精英螞蟻系統[編輯]
全域最佳解決方案在每個迭代以及其他所有的螞蟻的沉積資訊素。
最大最小螞蟻系統（MMAS）[編輯]
添加的最大和最小的資訊素量[ τmax，τmin ]，只有全域最佳或迭代最好的巡邏沉積的資訊素。所有的邊緣都被初始化為τmax並且當接近停滯時重新初始化為τmax。
蟻群系統[編輯]
蟻群系統已被提出。
基於排序的螞蟻系統（ASrank）[編輯]
所有解決方案都根據其長度排名。然後為每個解決方案衡量資訊素的沉積量，最短路徑相比較長路徑的解沉積了更多的資訊素。
連續正交蟻群（COAC）[編輯]
COAC的資訊素沉積機制能使螞蟻協同運作而有效地尋解。利用正交設計方法，在可行域的螞蟻可以使用增大的全域搜尋能力和精度，快速、高效地探索他們選擇的區域。 正交設計方法和自適應半徑調整方法也可推廣到其他最佳化演算法中，在解決實際問題施展更大的威力。
收斂[編輯]
一些版本的演算法可以被證明是收斂的（即它能夠在有限時間找到全域最佳解）。第一個蟻群演算法收斂的證據製作於2000年，建立了基於圖像的蟻群演算法，繼而是ACS和MMAS的演算法。像大多數元啟發式方法一樣，估計理論收斂速度是很難的。在2004年，Zlochin和他的同事們表明，COA-type演算法在分布演算法的叉熵和估計方面能被隨機梯度下降法吸收。他們建議這些元啟發式方法作為一個「研究性模式」。
應用[編輯]
蟻群最佳化演算法已應用於許多組合最佳化問題，包括蛋白質摺疊或路由車輛的二次分配問題，很多衍生的方法已經應用於實變數動力學問題，隨機問題，多目標並列的實現。它也被用旅行推銷員問題的擬最佳解。在圖表動態變化的情況下解決相似問題時，他們相比類比退火演算法和遺傳演算法方法有優勢；蟻群演算法可以連續執行並適應即時變化。這在網路路由和城市交通系統中是有利的。
第一蟻群最佳化演算法被稱為「螞蟻系統」，它旨在解決推銷員問題，其目標是要找到一系列城市的最短遍歷路線。總體演算法相對簡單，它基於一組螞蟻，每隻完成一次城市間的遍歷。在每個階段，螞蟻根據一些規則選擇從一個城市移動到另一個：它必須訪問每個城市一次;一個越遠的城市被選中的機會越少（能見度更低）;在兩個城市邊際的一邊形成的資訊素越濃烈，這邊被選擇的概率越大;如果路程短的話，已經完成旅程的螞蟻會在所有走過的路徑上沉積更多資訊素，每次迭代後，資訊素軌跡揮發。
排程問題[編輯]
車間作業排程問題（JSP）
開放式車間排程問題（OSP）
排列流水車間問題（PFSP）
單機總延遲時間問題（SMTTP）
單機總加權延遲問題（SMTWTP）
資源受限專案排程問題（RCPSP）
車間組排程問題（GSP）
附帶依賴安裝時間順序的單機總延遲問題（SMTTPDST）
附帶順序相依設定/轉換時間的多階段流水車間排程問題（MFSP）
車輛路徑問題[編輯]
限量車輛路徑問題（CVRP）
多站車輛路徑問題（MDVRP）
周期車輛路徑問題（PVRP）
分批配送車輛路徑問題（SDVRP）
隨機車輛路徑問題（SVRP）
裝貨配送的車輛路徑問題（VRPPD）
帶有時間窗的車輛路徑問題（VRPTW）
依賴時間的時間窗車輛路徑問題（TDVRPTW）
帶時間窗和複合服務員工的車輛路徑問題（VRPTWMS）
分配問題[編輯]
二次分配問題（QAP）
廣義分配問題（GAP）
頻率分配問題（FAP）
冗餘分配問題（RAP）
設定問題[編輯]
覆蓋設定問題（SCP）
分割區設定問題（SPP）
約束重量的樹圖劃分問題（WCGTPP）
加權弧L-基數樹問題（AWlCTP）
多背包問題（MKP）
最大獨立集問題（MIS）
其他[編輯]
面向關係的網路路由
無連接網路路由
資料探勘
專案排程中的貼現現金流
分散式資訊檢索
網格工作流排程問題
圖像處理
系統辨識
蛋白質摺疊
電子電路設計
相關的方法[編輯]
遺傳演算法（GA）支援一系列的解決方案。解的合併或突變增加了解集，其中品質低劣的解被丟棄，尋找進階解決方案的過程模仿了這一演變。
類比退火（SA）是一個全域最佳化相關的通過產生當前解的相鄰解來遍歷搜尋空間的技術。進階的相鄰解總是可接受的。低階的相鄰解可能會根據基於品質和溫度參數的差異的概率被接受。溫度參數隨著演算法的行程被修改以改變搜尋的性質。
反作用搜尋最佳化的重點在於將機器學習與最佳化的結合，加入內部回饋迴路以根據問題、根據實例、根據當前解的附近情況的特點自動調整演算法的自由參數。
禁忌搜尋（TS）類似於類比退火，他們都是通過測試獨立解的突變來遍歷解空間的。而類比退火演算法對於一個獨立解只生成一個突變，禁忌搜尋會產生許多變異解並且移動到產生的解中的符合度最低的一個。為了防止迴圈並且促進在解空間中的更大進展，由部分或完整的解組建維繫了一個禁忌列表。移動到元素包含于禁忌列表的解是禁止，禁忌列表隨著解遍歷解空間的過程而不斷更新。
人工免疫系統（AIS）演算法仿照了脊椎動物的免疫系統。
粒子群最佳化（PSO），群智慧型方法。
引力搜尋演算法（GSA），群智慧型方法。
蟻群聚類別方法（ACCM中），這個方法利用了聚類別方法擴充了蟻群最佳化。
隨機傳播搜尋（SDS），基於代理的概率全域搜尋和最佳化技術，最適合於將目標函式分解成多個獨立的分布函式的最佳化問題。
歷史[編輯]
蟻群最佳化演算法的年表：
1959年，Pierre-Paul Grassé發明了Stigmergy理論來解釋白蟻建設巢的行為。
1983年，Deneubourg和他的同事們研究了螞蟻的集體行為。
1988年，Moyson Manderick寫了一篇螞蟻自組織的文章。
1989年，Goss, Aron, Deneubourg和Pasteels關於阿根廷螞蟻的集體行為的研究，給蟻群最佳化演算法的思想提供了靈感。
1989年，Ebling和他的同事落實了覓食行為的模型。
1991年，M. Dorigo在他的博士論文中提出了螞蟻系統（文章於1992年發表）。一份從論文中提取的技術報告五年後出版，由V. Maniezzo和A.Colorni合著。
1996年，螞蟻系統的文章出版。
1996年，Hoos與Stützle發明了最大最小螞蟻系統。
1997年，Dorigo和Gambardella發布了蟻群系統。
1997年，Schoonderwoerd和他的同事們開發了對電信網路的首次應用。
1998年，Dorigo發起了第一次蟻群演算法的專題會議。
1998年，Stützle提出初步的並列實現。
1999年，Bonabeau, Dorigo和Theraulaz的出版了一本書，主要關於人工螞蟻。
2000年，未來電腦系統雜誌上發表了螞蟻演算法特刊。
2000年，排程的最早期的應用程式，排程了序列和約束的滿意度。
2000年，Gutjahr提供了一個蟻群演算法收斂的第一個證據。
2001年，COA演算法首次被使用（Eurobios和AntOptima）。
2001年，IREDA和他的同事們發表了第一個多對象演算法。
2002年，排程設計的首次應用，貝葉斯網路。
2002年，比安奇和她的同事提出了隨機問題的最早演算法。
2004年，Zlochin和Dorigo表明，有些演算法等價於隨機梯度下降法，交叉熵最佳化法和估計分布演算法。[1]
2005年，首次在蛋白質摺疊問題上的應用。
- ^ M. Zlochin, M. Birattari, N. Meuleau, et M. Dorigo, Model-based search for combinatorial optimization: A critical survey, Annals of Operations Research, vol. 131, pp. 373-395, 2004.