蟻群算法的參數(shù)分析

文/譚慧莉

蟻群算法的參數(shù)分析

文/譚慧莉

在詳細(xì)分析了蟻群算法的數(shù)學(xué)模型及綜述當(dāng)前國內(nèi)外蟻群算法研究現(xiàn)狀的基礎(chǔ)上，文章重點(diǎn)對狀態(tài)轉(zhuǎn)移概率和信息素更新機(jī)制進(jìn)行改進(jìn)，并以旅行商問題(TSP)為例進(jìn)行仿真實驗，有效地避免了蟻群算法出現(xiàn)早熟和停滯的問題，驗證了改進(jìn)的合理性和有效性。

蟻群算法 TSP問題 狀態(tài)轉(zhuǎn)移概率信息素

當(dāng)今社會已高速發(fā)展，各領(lǐng)域內(nèi)不斷的涌現(xiàn)出超大規(guī)模、隨機(jī)性的復(fù)雜問題，傳統(tǒng)的計算方法難于解決這些復(fù)雜問題。蟻群算法(ACA)是近年提出的解決這類復(fù)雜問題的一種模擬進(jìn)化算法。最早，由意大利學(xué)者M(jìn).Dorigo等人于1991年在首屆歐洲人工生命會議上提出。從此，蟻群算法逐漸引起了許多國家研究者的關(guān)注，大量有價值的研究成果陸續(xù)發(fā)表。

1 蟻群算法的數(shù)學(xué)模型

蟻群算法最初用于解決旅行商問題(TSP)。旅行商問題是一個經(jīng)典的組合優(yōu)化問題，是驗證求解組合優(yōu)化問題有效性的一個間接標(biāo)準(zhǔn)。

在自然界中，螞蟻個體從蟻巢出發(fā)尋找食物源，會在所經(jīng)過的路徑上留下一種稱為“信息素”的物質(zhì)，后面螞蟻在運(yùn)動的過程中，能夠感知這種物質(zhì)的存在和強(qiáng)度，最終，找出蟻巢和食物源之間的最短距離。受蟻群覓食行為的啟發(fā)，M.Dorigo等人提出了蟻群算法的基本思想，以n個城市的TSP問題(1,2,…,n分別表示城市的編號)為例，算法的數(shù)學(xué)模型是：

m—蟻群螞蟻的數(shù)量

dij—城市i與j之間的距離(假定dij=dji)，i,j=1,2,…,n

bi(t)—t時刻位于城市i的螞蟻的數(shù)量

ηij(t)—t時刻所能提供的某種啟發(fā)式信息，

τij(t)—t時刻螞蟻群在路徑(i,j)上的信息素

其中α為信息啟發(fā)式因子，β為期望啟發(fā)式因子，tabuk是螞蟻k已走過的城市，表示t時刻螞蟻k的禁忌表。

算法步驟：

（3）螞蟻的禁忌表索引號k=1

（5）螞蟻個體根據(jù)狀態(tài)轉(zhuǎn)移概率公式（1）計算的概率選擇城市j并前進(jìn)，

（6）修改禁忌表指針，即螞蟻k移動到新的城市，并把該城市加到螞蟻k的禁忌表中

（8）根據(jù)式(2)和(3)更新每條路徑上的信息量

2 國內(nèi)外的研究現(xiàn)狀及分析

蟻群算法作為一種新型的模擬進(jìn)化算法，具有正反饋機(jī)制，分布式計算，易與其他方法結(jié)合等很多優(yōu)點(diǎn)。但是，蟻群算法也存在一些不足和缺陷，收斂速度慢、易于停滯等問題是目前重點(diǎn)解決的問題，針對以上缺陷，蟻群算法的主要研究內(nèi)容集中在以下幾個方面：

2.1 對蟻群內(nèi)部分工協(xié)作的模擬

真實的蟻群社會中，不同螞蟻分工不同，相互協(xié)作共同完成任務(wù)。對此進(jìn)行模擬的多態(tài)蟻群算法中，引入多種螞蟻群，不同螞蟻群的信息素調(diào)控不同，在螞蟻搜索過程中，針對各具體路徑選擇合適的信息素的濃度，加快尋優(yōu)收斂速度。

2.2 縮短蟻群算法的搜索時間

L.M.Gambardella提出了一種修正的蟻群算法—蟻群系統(tǒng)，對螞蟻尋路的規(guī)則進(jìn)行了一定的調(diào)整；張軍[7]等人對蟻群算法中的參數(shù)進(jìn)行分析得到了較好的改進(jìn)。

3 對蟻群算法參數(shù)的改進(jìn)思路

針對蟻群算法容易出現(xiàn)局部最優(yōu)解和停滯的的缺點(diǎn)，通過對文獻(xiàn)[3,5,6,7]的深入研究，d對蟻群算法在以下兩方面做出改進(jìn)：

3.1 對狀態(tài)轉(zhuǎn)移概率的改進(jìn)

修改公式（1）為

3.2 對信息素的改進(jìn)

即蟻群創(chuàng)建的第一條路徑時要參考城市之間的距離信息，導(dǎo)致蟻群留下的信息可能不準(zhǔn)確，阻礙以后的螞蟻發(fā)現(xiàn)更好的全局最優(yōu)解。改進(jìn)對策：

借鑒文獻(xiàn)[8]中對最大可選城市數(shù)的分析：以城市i為中心，作半徑為R的圓PCi，R從0不斷擴(kuò)大，直至取得i的臨近城市為止時記錄下圓內(nèi)的城市數(shù)

定義初始時刻信息素值

q為權(quán)值，0和1之間取值，將距離當(dāng)前城市較遠(yuǎn)的初始信息素值設(shè)為較近城市的q倍。

4 實驗結(jié)果與分析數(shù)據(jù)

選用TSPLIB基準(zhǔn)庫中的Oliver30問題進(jìn)行試驗，已知的Oliver30問題的最短路徑長度為423.740 601，路徑中螞蟻的行走路線為：1—2—3—4—6—5—7—8—9—10—11—12—13—14—15—16—17—19—18—20—21—22—23—24—25—28—26—27—29—30。

由于算法中的參數(shù)選取對實驗結(jié)果影響很大，采用了多組參數(shù)對實驗結(jié)果進(jìn)行分析，令Q=100，m=20，迭代200次的最優(yōu)路徑值為424.4611，螞蟻的行走路線為：6—10—9—8—7—4—3—2—1—30—29—28—26—27—25—24—23—22—21—20—18—19—17—16—15—14—13—12—11—5。

5 結(jié)論語

本文在充分研究了蟻群算法在狀態(tài)轉(zhuǎn)移概率和信息素更新方面的缺陷的基礎(chǔ)上，對蟻群算法進(jìn)行改進(jìn)，并通過TSP問題的仿真實驗進(jìn)行數(shù)據(jù)分析和比較驗證了改進(jìn)的有效性。

[1]M.Dorigo,C.Blum.Ant Colony Optimization Theory：ASurvey. Theoretical Computer Science,2005,344(2-3)：243-278.

[2]M.Birattari,P.Pellegrini,M. Dorigo.On the Invariance of Ant Colony Optimization.IEEE Transactions on Evolutionary Computation.2007,11(06)：732-742

[3]徐宗本.計算智能[M].北京：高等教育出版社,2004：111-123.

[4]M.Dorigo,L.M.Gambardella.Ant Colonies for the Traveling Salesman Problem. Bio-System,1997,43：73-81.

[5]鮑文杰.朱信忠.趙建民.徐慧英.加權(quán)值.多態(tài)蟻群算法[J].軟件工程,2016(04)：1-4.

[6]L.M.Gambardella,M.Dorigo.Solving Symmetric and a Symmetric TSPs by Ant Colonies.Proceedings of the IEEE Conference on Evolutionary Computation,1996：622-627.

[7]張軍,劉羽,程樊啟.蟻群算法解決TSP問題的并行化研究與實現(xiàn)[J].計算機(jī)技術(shù)與發(fā)展,2011(05)：72-74.

[8]全 惠 云,文 高 進(jìn).求 解TSP的 子空間遺傳算法[J].數(shù)學(xué)理論與應(yīng)用,2002,22(01)：36-39.

作者單位 哈爾濱商業(yè)大學(xué) 黑龍江省哈爾濱市 150028

譚慧莉（1979-），女，理學(xué)碩士。哈爾濱商業(yè)大學(xué)講師。研究方向為優(yōu)化理論。