吳詩娟　李旭偉

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

[關(guān)鍵詞]蟻群算法模擬進化組合優(yōu)化

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

一、蚊群算法基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

三、蟻群算法的應(yīng)用研究

蟻群算法應(yīng)用研究及適用范圍主要歸結(jié)為兩大領(lǐng)域：

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

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

四、蚊群算法的前景展望

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

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

算法的性能也有待進一步提高，如路徑選擇概率的適應(yīng)性調(diào)整，信息素的動態(tài)更新，算法參數(shù)的優(yōu)化，信息素揮發(fā)系數(shù)優(yōu)化等方向。

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

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

對于以上問題的研究必將使蟻群算法展現(xiàn)更加廣闊的發(fā)展前景。

作者簡介：

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