曹嚴(yán)清， 王 濤

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

0 引 言

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

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

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

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

建立禁忌表可以讓螞蟻不再訪問(wèn)走過(guò)的節(jié)點(diǎn)，螞蟻通過(guò)信息素進(jìn)行選擇，當(dāng)某些路徑上的螞蟻越多，路徑上就會(huì)留下更多的信息素，螞蟻選擇這條路徑的概率就會(huì)增加，就會(huì)進(jìn)一步增加這條路徑上的信息素濃度，路徑上沒(méi)有螞蟻通過(guò)或只有較少的螞蟻通過(guò)，路徑上的信息素會(huì)因?yàn)檎舭l(fā)而顯得相對(duì)較少。螞蟻的信息素更新，有從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)就更新信息素，也有一代螞蟻構(gòu)建出一條路徑后才更新信息素的。

模擬螞蟻的行為，引入以下記號(hào)：

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

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

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

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

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

個(gè)體螞蟻的行為特征：

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

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

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

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

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

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

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

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

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

allow——螞蟻未訪問(wèn)城市的集合。

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

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

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

3 改進(jìn)的蟻群算法

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

除了ωij，其余符號(hào)的意義均與上述標(biāo)準(zhǔn)蟻群算法符號(hào)的意義相同。

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

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

4 性能分析

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

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

表1 標(biāo)準(zhǔn)蟻群算法與文中改進(jìn)蟻群算法5組實(shí)驗(yàn)對(duì)比

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

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

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

圖1 第1組標(biāo)準(zhǔn)算法與改進(jìn)算法各連續(xù)運(yùn)行3 0次解的折線圖

圖2 第2組標(biāo)準(zhǔn)算法與改進(jìn)算法各連續(xù)運(yùn)行3 0次解的折線圖

圖3 第3組標(biāo)準(zhǔn)算法與改進(jìn)算法各連續(xù)運(yùn)行3 0次解的折線圖

圖4 第4組標(biāo)準(zhǔn)算法與改進(jìn)算法各連續(xù)運(yùn)行3 0次解的折線圖

圖5 第5組標(biāo)準(zhǔn)算法與改進(jìn)算法各連續(xù)運(yùn)行3 0次解的折線圖

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

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

5 結(jié) 語(yǔ)

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

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

表2 標(biāo)準(zhǔn)蟻群算法與改進(jìn)蟻群算法針對(duì)不同TSP問(wèn)題的實(shí)驗(yàn)對(duì)比

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

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

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

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

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