蟻群算法理論及應(yīng)用研究

吳詩(shī)娟　李旭偉

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

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

中圖分類號(hào)：029文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1671－7597(2009)0210050－01

一、蚊群算法基本原理

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

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

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

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

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

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

二、蚊群算法的理論研究與改進(jìn)

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

Dorigo等隨后提出蟻群系統(tǒng)(ACS)[2]。改進(jìn)了螞蟻選擇城市的狀態(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è)置研究。在蟻群算法實(shí)現(xiàn)過程中。ρ α β等參數(shù)的值決定了搜索速度與收斂速度的平衡。Dorigo等通過實(shí)驗(yàn)得出當(dāng)a＝1，β＝5，ρ＝0.5時(shí)為AS算法的最佳參數(shù)設(shè)置，而在ACS算法中α＝0.9，β＝2，ρ＝0.1。蔣玲艷等分析了α β ρ對(duì)算法性能的影響，并利用大量數(shù)據(jù)指出，當(dāng)α∈[0.1，0.3], β∈[3,6]，ρ∈[0.1，0.3]時(shí)算法有較好的性能。

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

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

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

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

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

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

四、蚊群算法的前景展望

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

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

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

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

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

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

作者簡(jiǎn)介：

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