蟻群算法理論及應用研究

吳詩娟　李旭偉

[摘要]首先簡述蟻群算法的基本原理和特點，然后介紹具有代表性的改進算法和蟻群算法的應用領域，最后對蟻群算法未來的研究方向和發展趨勢進行展望。

[關鍵詞]蟻群算法模擬進化組合優化

中圖分類號：029文獻標識碼：A文章編號：1671－7597(2009)0210050－01

一、蚊群算法基本原理

蟻群算法的基本思想是模仿螞蟻間通過在路徑上釋放信息素進行交流，并根據累積的信息素不斷搜索較優路徑，并最終找到全局最佳路徑。

Dorigo等于1991年提出了第一個蟻群算法的模型(As)[1]，并成功用于求解旅行商問題(TSP)等復雜的組合優化問題。

(一)蟻群算法的數學模型。將m只螞蟻隨機放到n個全連通的城市上，并使各路徑上信息素濃度相等。t時刻位于城市i的螞蟻k傾向于選擇那些長度較短且信息素強度較高的路徑，并在某一時間更新路徑上的信息素濃度。當所有螞蟻都遍歷完n個城市以后，計算出此次遍歷的最短路徑。此后算法迭代至滿足終止條件后結束，找到遍歷整個城市的最短路徑。

(二)基本蟻群算法的優缺點。AS算法具有天然的隨機性，自適應性，分布式計算，無中心控制和個體間異步間接協作的優點，具有良好的并行處理和全局優化能力。但也存在一些缺陷：

1、求解速度慢。算法時間復雜度為O(n³)，當問題規模(n)增大時，算法時間將以三次冪的速度增長。

2、算法執行過程中容易出現停滯。當搜索進行到一定程度后，被信息素更新算法選中的路徑和未被選中的路徑間的差異會越來越大，會使解趨于一致，不利于發現更好的解。

二、蚊群算法的理論研究與改進

(一)改進的蟻群算法。針對蟻群算法的不足很多學者圍繞著改進蟻群算法，提高算法的性能做了大量工作。

Dorigo等隨后提出蟻群系統(ACS)[2]。改進了螞蟻選擇城市的狀態轉移規則；只允許當前找到最優路徑的螞蟻在遍歷后釋放信息素；在轉移過程中，減少路徑上的信息素濃度，有效避免過早的收斂到同一路徑。

Stutzle[3]等提出MMAS算法，將路徑上信息素的濃度限制在[T min。Tmax]范圍內；各路徑上信息素的初始值設為t max，p取較小值，可在初始階段搜索到更多可行解。此算法是目前求解TSP等離散優化問題最好的算法模型之一。Gambardella等提出混合蟻群算法，Taillard等提出了快速螞蟻系統，都盡可能提高蟻群算法在一定空間復雜度下的尋優能力，并拓寬蟻群算法的應用領域。

(二)參數設置研究。在蟻群算法實現過程中。ρ α β等參數的值決定了搜索速度與收斂速度的平衡。Dorigo等通過實驗得出當a＝1，β＝5，ρ＝0.5時為AS算法的最佳參數設置，而在ACS算法中α＝0.9，β＝2，ρ＝0.1。蔣玲艷等分析了α β ρ對算法性能的影響，并利用大量數據指出，當α∈[0.1，0.3], β∈[3,6]，ρ∈[0.1，0.3]時算法有較好的性能。

(三)收斂性研究。Gutjahr等首先對基于圖的蟻群算法(GBAS)及其后改進的GBAS/tdev和GBAS/tdlb算法的收斂性進行了證明，Stuezle和Dorigo證明了一類蟻群算法當迭代次數趨于無窮時，算法可以保證找到全局最優解。黃翰等結合ACS對蟻群算法的收斂速度進行了分析。孫燾等對一類簡單蟻群算法的收斂性做了初步研究。

(四)與遺傳算法融合。Abbattista等利用遺傳算法尋找最優的α βq參數設置。丁建立等利用遺傳算法產生較好的信息素初始分布，再利用螞蟻算法求精確解。這樣可以把蟻群算法的協作效應與遺傳算法的進化效應進行優勢互補，獲得優化和時間上的雙贏。

三、蟻群算法的應用研究

蟻群算法應用研究及適用范圍主要歸結為兩大領域：

(一)離散組合優化問題。除TSP問題外，蟻群算法早已應用到其他典型的優化離散組合優化問題中；指派問題，二次規劃，job—shop，圖著色，通訊網絡路由選擇，電力系統故障檢測，圖像處理，參數辨識等。

(二)連續空間優化問題。蟻群算法在連續優化問題中的應用剛剛起步。高瑋等提出的免疫連續蟻群算法應用到了巖土工程分析中，并通過簡單的算例驗證了算法的有效性及卓越的計算效率。Ho等提出的求解連續優化問題的蟻群算法，并運用在電磁裝置的優化設計上，取得了良好的效果。

四、蚊群算法的前景展望

蟻群算法在求解優化組合問題中有著明顯的優越性和廣闊的應用前景，未來還可以在以下幾方面深入研究：

1、算法理論分析的完善和改進。對蟻群算法有效性進行嚴格的數學解釋，算法的收斂性分析與證明及算法通用的模型有待進一步研究。

算法的性能也有待進一步提高，如路徑選擇概率的適應性調整，信息素的動態更新，算法參數的優化，信息素揮發系數優化等方向。

2、與其他優化算法融合。蟻群算法與其他算法融合研究仍處于初級階段，探討新的融合策略來進一步改善蟻群算法的性能，并將其應用于實際問題中，都是很有意義的研究方向。

3、實際工程中的應用擴展。現階段蟻群算法大部分應用仍停留在小規模的仿真階段，還需要使蟻群算法的求解更接近工程實際，并對更復雜的問題進行深入討論，對算法的可靠性進行深入分析，其蟻群算法的應用領域也有待進一步擴展。

對于以上問題的研究必將使蟻群算法展現更加廣闊的發展前景。

作者簡介：

吳詩娟，女，四川成都人，碩士研究生，主要研究方向：計算機網絡與信息系統；李旭偉，男，浙江長興人，副教授，碩士，主要研究方向：計算機網絡與信息系統。