曹嚴清， 王 濤

（長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院，吉林 長春 130012）

0 引 言

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

1 經(jīng)典的蟻群算法

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

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

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

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

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

n——TSP問題中城市的數(shù)量；

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

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

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

個體螞蟻的行為特征：

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

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

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

系統(tǒng)過程如下：

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

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

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

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

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

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

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

2 經(jīng)典蟻群算法的不足之處

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

3 改進的蟻群算法

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

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

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

Lk在本次循環(huán)中第k只螞蟻所經(jīng)過路徑總長度，即完成一次循環(huán)后，才進行信息素的全局調(diào)整，Q為常數(shù)。

4 性能分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

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

表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(xiàn) 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］ 夏亞梅，程渤，陳俊亮，等.基于改進蟻群算法的服務(wù)組合優(yōu)化［J］.計算機學(xué)報，2012，35（2）：271－281.

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

［10］ 鄭嘯，羅軍舟，宋愛波.基于Agent和蟻群算法的分布式服務(wù)發(fā)現(xiàn)［M］.軟件學(xué)報，2010，21（8）：1795－1809.

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

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