蟻群算法中改進的螞蟻選擇城市概率公式

曹嚴清， 王 濤

（長春工業大學 計算機科學與工程學院，吉林 長春 130012）

0 引 言

20世紀50年代中期創立了仿生學，人們從生物進化的機理中受到啟發，提出了解決復雜問題的優化方法，如遺傳算法、免疫算法等。遺傳算法是一種群體智能算法，其本身具有并行性和分布式特點。該算法是模擬螞蟻尋找食物的過程，由意大利學者A.Colomi和M.Dorigo等人于1992年首先提出來的。TSP問題中的概率選擇公式是螞蟻選擇下一城市的參考標準，標準蟻群算法中包含信息素和相鄰城市間距離兩個因素。標準蟻群算法由于信息素的積累，容易出現早熟停滯現象。文中針對早熟和停滯現象，在概率選擇公式中加入了以歷代最優解作為參考的啟發式信息，削弱信息素在螞蟻選擇路徑時的影響，擴展解空間，避免過早陷入局部最優。運用TSP問題，對改進蟻群算法與標準蟻群算法做對比，驗證了算法的有效性［1－3］。

1 經典的蟻群算法

個體螞蟻之間是通過信息素來傳遞信息的，進而相互合作來完成復雜的任務。螞蟻在移動時能夠留下信息素，并且螞蟻在運動過程中能夠感受到這種物質的強弱，以此作為引導自己運動的方向，螞蟻會朝著這種物質濃度高的地方運動。大量螞蟻的集體行為就表現為一種信息正反饋，某條路徑走的螞蟻越多，這條路徑上的信息素濃度就越大，這條路徑被別的螞蟻選擇的可能性就越大。螞蟻個體就是靠這種簡單的信息交流找到蟻穴與食物之間的最短路徑，此過程沒有總體指揮。蟻群算法通常用于TSP問題。

用蟻群算法處理TSP問題，有m只螞蟻在圖的相鄰節點之間移動，通過合作來得到問題的解，每只螞蟻在選擇下一個節點時，由通向下一個節點的弧上的兩類信息決定：其一是這條弧上的信息素濃度；其二是這條弧的長度。信息素有兩種更新方式：一種是所有路徑上的信息素都會以某種比例減少；另一種是被螞蟻走過的某條邊上的信息素濃度會增加。最初螞蟻只是隨機地選擇路徑，隨著多代多只螞蟻的探索，就會積累具有局部優勢的啟發式信息，根據啟發式信息逐步達到最優解［4］。

建立禁忌表可以讓螞蟻不再訪問走過的節點，螞蟻通過信息素進行選擇，當某些路徑上的螞蟻越多，路徑上就會留下更多的信息素，螞蟻選擇這條路徑的概率就會增加，就會進一步增加這條路徑上的信息素濃度，路徑上沒有螞蟻通過或只有較少的螞蟻通過，路徑上的信息素會因為蒸發而顯得相對較少。螞蟻的信息素更新，有從一個節點移動到另一個節點就更新信息素，也有一代螞蟻構建出一條路徑后才更新信息素的。

模擬螞蟻的行為，引入以下記號：

m——螞蟻的數量；

n——TSP問題中城市的數量；

dij——城市i和j之間的距離；

ηij——一邊（i，j）的啟發信息，反映由城市i到城市j的距離信息，在TSP中ηij＝1／dij；

τij——一邊（i，j）上的信息素量；

個體螞蟻的行為特征：

1）螞蟻完成一次循環后，螞蟻會在走過的路徑上留下信息素。

2）螞蟻選擇城市，是根據路徑上信息素濃度和城市間距離。

3）完成一次循環之前，螞蟻不允許訪問已被訪問過的城市。

系統過程如下：

m只螞蟻隨機被分配到m個城市。各個路徑上設置相等的初始信息素濃度值，設τij（0）＝τ0，τ0是信息素濃度初始值，可設為τ0＝m／cmn，m為螞蟻數量，如果τ0太小，搜索將陷入較差的局部空間，τ0太大只有信息素蒸發到足夠小時，螞蟻釋放的信息素才會發揮指引作用。

螞蟻是隨機選擇下一個城市的，位于i城市的螞蟻選擇j城市依據如下概率公式

式中：τij——路徑（i，j）的信息素濃度；

ηij——城 市 間 距 離 的 啟 發 式 信 息，ηij＝1／dij；

α，β——兩個啟發式信息的參數，決定啟發式信息對螞蟻選擇城市影響的程度；

allow——螞蟻未訪問城市的集合。

以上是個體螞蟻的行為特征，要想得到局部最優解，需要多只螞蟻多代尋找路徑，一旦發現新的最短路徑，就將此路徑記錄下來。

2 經典蟻群算法的不足之處

在標準蟻群算法中，由于信息素的積累，在算法初期就會得到局部最優解，在最優路徑上的信息素濃度高于其他路徑上的信息素濃度，螞蟻選擇路徑時以此作為參考，就失去了探索解空間的能力，將會導致算法陷入局部最優［5］。此后的大部分時間都是對局部最優解的重復搜索。針對這些不足，學者們提出了一些改進算法。Stutzle和Hoos提出最大最小螞蟻系統（MMAS）［6］，設置信息素的上下限，避免過早停滯［7］；最優最差蟻群系統（BWAS）對最優解增強，最差解減弱；基于排序的螞蟻系統，對螞蟻所走路徑大小進行排序，并對路徑賦予權重，路徑長度較小的權重較大；還有通過增加路線來改善一些算法的不足，如：K－opt、Or－opt節線交換法［8］；引入變異機制；自適應改變信息素的揮發，自適應改變路徑上的信息素［9］；相遇算法提高了螞蟻遍歷的質量。文中加入以歷代最優解作為參考的啟發式，可以拓展解空間，因為歷代最優解的各條弧并不一定在此代信息素濃度高的路徑上，削弱了信息素的影響，如果選擇了信息素濃度不高的弧，較標準蟻群算法就擴展了解空間，避免過早的陷入局部最優［10－11］。

3 改進的蟻群算法

以上是經典的蟻群算法的個體螞蟻選擇城市的概率公式，為了兼顧歷代最短路徑搜索結果，將結果信息納入啟發式信息，歷代結果中弧出現的次數作為啟發式信息［12］。在傳統的概率選擇公式上加了一個啟發式信息ωij，ωij（用公式編輯器）是在歷代最短路徑中（i，j）弧出現的次數，弧出現的次數多，對螞蟻的選擇有正向影響，在程序中用minTourRec［］［］這樣的二維數組存儲。新的概率選擇公式如下：

除了ωij，其余符號的意義均與上述標準蟻群算法符號的意義相同。

改進算法中的信息素增加，使用的是和標準蟻群算法一樣的全局調整，公式如下：

Lk在本次循環中第k只螞蟻所經過路徑總長度，即完成一次循環后，才進行信息素的全局調整，Q為常數。

4 性能分析

從TSPLIB中選取TSP問題，用Java語言進行編程，對標準蟻群算法和改進的蟻群算法進行了大量的實驗。實驗中所用到的參數為α＝1.0，β＝2.0，τ0＝9.1，ρ＝0.5，Q＝1，迭代次數為2 000。

經典的蟻群算法與改進的蟻群算法，使用48個城市的att48的TSP問題做了5組對比，見表1。

表1 標準蟻群算法與文中改進蟻群算法5組實驗對比

每組兩種算法各連續運行30次。在總共300次運行中，最優解是由第5組改進算法得到的，如圖1～圖5所示。

改進算法加入的啟發式擴展了解空間，緩解了過早陷入局部最優，在第1組和第4組中，改進算法的一些解會明顯地在傳統算法主體解趨勢之下（見圖1和圖4）。

在上述實驗的基礎上，又對不同的TSP問題對標準蟻群算法和改進蟻群算法進行了實驗對比。選取了Berlin52，Eil51，Eil76，St70這4個TSP問題。4種TSP問題的算法中所用到的參數均為α＝1.0，β＝2.0，τ0＝9.1，ρ＝0.5，Q＝1。

圖1 第1組標準算法與改進算法各連續運行3 0次解的折線圖

圖2 第2組標準算法與改進算法各連續運行3 0次解的折線圖

圖3 第3組標準算法與改進算法各連續運行3 0次解的折線圖

圖4 第4組標準算法與改進算法各連續運行3 0次解的折線圖

圖5 第5組標準算法與改進算法各連續運行3 0次解的折線圖

Berlin52，迭代次數均為2 000，Eil51的螞蟻數量為50，標準和改進算法各連續運行30次。Eil76的螞蟻數量為76，St70的螞蟻數量為70，標準和改進各連續運行15次。實驗結果見表2。

從表2中可以看出，改進蟻群算法的最優解均小于標準蟻群算法的最優解。Berlin52，Eil51，Eil76改進算法的平均解均小于標準算法的平均解，說明了改進算法的有效性。

5 結 語

提出了對蟻群算法的改進，把螞蟻將要選擇的下一節點與當前節點之間弧在歷代最短路徑中出現的次數作為螞蟻選擇下一節點的正向影響因素。避免螞蟻過早的陷入局部最優解。

各種TSP問題實驗結果表明了該方法的有效性。隨著蟻群算法研究的深入，這種仿生算法將會得到更廣泛的應用。

表2 標準蟻群算法與改進蟻群算法針對不同TSP問題的實驗對比

［1］ M Dorigo，L M Gambardella.Ant colony system：a cooperative learning approach to the traveling salesman problem［J］.IEEE Transactions on Evolutionary Computation，1997，1（1）：53－66.

［2］ M Dorigo，G L M DiCaro.Gambardella Ant algorithms for discrete optimization［J］.Artificial Life，1999，80：130－172.

［3］ G DiCaro，M Dorigo.AntNet：Distributed stigmergetic control for communications networks［J］.Journal of Artifical Intelligence Research（JAIR），1998，102：312－365.

［4］ G DiCaro，F Ducatelle，L M Gambardella.AntHocNet：an ant－based hybrid routing algorithm for mobile ad hoc networks［C］／／Proceedings of Parallel Problem Solving from Nature（PPSN VIII），2004：143－150.

［5］ M Dorigo，T Stutzle.Ant colony optimization［M］.USA：MIT Press，2004.

［6］ S Thomas，H H Holger.MAX－MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889－914.

［7］ D Merkle，M Middendorf，Schmeck H.Ant colony optimization for resource－constrained project scheduling［J］.IEEE TransEvol Computer，2002，6（4）：333.

［8］ 夏亞梅，程渤，陳俊亮，等.基于改進蟻群算法的服務組合優化［J］.計算機學報，2012，35（2）：271－281.

［9］ 陳崚，章春芳.并行蟻群算法中的自適應交流策略［J］.軟件學報，2007，18（3）：617－624.

［10］ 鄭嘯，羅軍舟，宋愛波.基于Agent和蟻群算法的分布式服務發現［M］.軟件學報，2010，21（8）：1795－1809.

［11］ 郭禾，程童，陳鑫，等.一種使用視覺反饋與行為記憶的蟻群優化算法［M］.軟件學報，2011，22（9）：1994－2005.

［12］ 張良.約束滿足問題求解啟發式研究［D］：長春：吉林大學，2014.