蟻群算法的參數分析

文/譚慧莉

蟻群算法的參數分析

文/譚慧莉

在詳細分析了蟻群算法的數學模型及綜述當前國內外蟻群算法研究現狀的基礎上，文章重點對狀態轉移概率和信息素更新機制進行改進，并以旅行商問題(TSP)為例進行仿真實驗，有效地避免了蟻群算法出現早熟和停滯的問題，驗證了改進的合理性和有效性。

蟻群算法 TSP問題 狀態轉移概率信息素

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

1 蟻群算法的數學模型

蟻群算法最初用于解決旅行商問題(TSP)。旅行商問題是一個經典的組合優化問題，是驗證求解組合優化問題有效性的一個間接標準。

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

m—蟻群螞蟻的數量

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

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

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

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

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

算法步驟：

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

（5）螞蟻個體根據狀態轉移概率公式（1）計算的概率選擇城市j并前進，

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

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

2 國內外的研究現狀及分析

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

2.1 對蟻群內部分工協作的模擬

真實的蟻群社會中，不同螞蟻分工不同，相互協作共同完成任務。對此進行模擬的多態蟻群算法中，引入多種螞蟻群，不同螞蟻群的信息素調控不同，在螞蟻搜索過程中，針對各具體路徑選擇合適的信息素的濃度，加快尋優收斂速度。

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

L.M.Gambardella提出了一種修正的蟻群算法—蟻群系統，對螞蟻尋路的規則進行了一定的調整；張軍[7]等人對蟻群算法中的參數進行分析得到了較好的改進。

3 對蟻群算法參數的改進思路

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

3.1 對狀態轉移概率的改進

修改公式（1）為

3.2 對信息素的改進

即蟻群創建的第一條路徑時要參考城市之間的距離信息，導致蟻群留下的信息可能不準確，阻礙以后的螞蟻發現更好的全局最優解。改進對策：

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

定義初始時刻信息素值

q為權值，0和1之間取值，將距離當前城市較遠的初始信息素值設為較近城市的q倍。

4 實驗結果與分析數據

選用TSPLIB基準庫中的Oliver30問題進行試驗，已知的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。

由于算法中的參數選取對實驗結果影響很大，采用了多組參數對實驗結果進行分析，令Q=100，m=20，迭代200次的最優路徑值為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 結論語

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

[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]鮑文杰.朱信忠.趙建民.徐慧英.加權值.多態蟻群算法[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問題的并行化研究與實現[J].計算機技術與發展,2011(05)：72-74.

[8]全 惠 云,文 高 進.求 解TSP的 子空間遺傳算法[J].數學理論與應用,2002,22(01)：36-39.

作者單位 哈爾濱商業大學 黑龍江省哈爾濱市 150028

譚慧莉（1979-），女，理學碩士。哈爾濱商業大學講師。研究方向為優化理論。