蟻群算法
 |
蟻群算法（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.