易正俊，李勇霞，易校石

(1.重慶大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，重慶 401331;2.重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，重慶 401131)

自適應(yīng)蟻群算法求解最短路徑和TSP問題

易正俊1，李勇霞1，易校石2

(1.重慶大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，重慶 401331;2.重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，重慶 401131)

對傳統(tǒng)蟻群算法的初始化信息素濃度加入方向引導(dǎo)，避免蟻群在初始階段盲目地隨機搜索浪費較多的時間；在全局信息素更新過程中加入雙曲正切函數(shù)作為動態(tài)因子，自適應(yīng)地更新每次迭代較優(yōu)解路徑的信息素濃度，增大算法獲取全局最優(yōu)解的可能性。兩個算例采用改進(jìn)的蟻群算法進(jìn)行優(yōu)化，優(yōu)化的結(jié)果與實際情形具有良好的一致性，說明了改進(jìn)算法的有效性和實用性。

蟻群算法；最短路徑；方向引導(dǎo)；動態(tài)因子：旅行商問題

0 引 言

蟻群算法(Ant Colony System,ACS)是由意大利學(xué)者Dorigo等于20世紀(jì)90年代初期提出的一種基于種群的啟發(fā)式隨機搜索算法[1-4]。蟻群算法具有正反饋、魯棒性、并行性等優(yōu)點,有很多文獻(xiàn)采用蟻群算法計算最短路徑的問題。最短路徑問題在交通運輸、物流配送、網(wǎng)絡(luò)分析、管道鋪設(shè)、廠區(qū)選取等領(lǐng)域有廣泛的應(yīng)用。如交通運輸往往需要盡可能降低運輸成本,等價于搜索運輸網(wǎng)中兩節(jié)點的最短路徑；但傳統(tǒng)的蟻群算法在計算較復(fù)雜的網(wǎng)絡(luò)圖中兩節(jié)點間的最短距離時容易陷入局部最優(yōu)，且隨著網(wǎng)絡(luò)圖的復(fù)雜程度的增加其收斂速度慢,還有可能出現(xiàn)停滯現(xiàn)象[5-6]。針對這些問題，有學(xué)者對傳統(tǒng)的蟻群算法做了一些相應(yīng)改進(jìn)。有的將信息素濃度控制在一定范圍內(nèi)變化，避免螞蟻都選擇同一條路徑，避免算法中的停滯現(xiàn)象。Stuzle等[7]提出“最大最小蟻群系統(tǒng)”(Max-Min Ant System);Clornei等[8]將蟻群算法和遺傳算法相結(jié)合,增強了算法的尋優(yōu)能力；鄭衛(wèi)國等[9]提出帶獎罰的蟻群算法，對較優(yōu)信息素濃度進(jìn)行獎勵，對較差信息素濃度進(jìn)行懲罰。這些改進(jìn)的蟻群算法雖然獲得了較好的最優(yōu)解，但初始搜索時間較長，全局更新規(guī)則中沒有考慮較優(yōu)解。

文中對初始信息素濃度進(jìn)行方向的改進(jìn)：距離目標(biāo)方向越近的路徑，就提高此路徑上信息素濃度比例，這樣就會促進(jìn)螞蟻在尋找食物源時以最大概率沿著信息素濃度高的路徑，用最短時間接近最優(yōu)食物源的快速通道，避免初始搜索時間較長的缺陷；由于傳統(tǒng)蟻群算法的動態(tài)因子在調(diào)節(jié)全局信息素濃度時不具有自適應(yīng)性，因此引入雙曲線正切函數(shù)在全局的信息素濃度更新中作為其自適應(yīng)動態(tài)因子，每次迭代最優(yōu)解路徑的信息素濃度時具有一定的自適應(yīng)性，使最優(yōu)路徑的信息素增大，從而增大了算法獲取最優(yōu)解的可能性，縮短了算法的收斂時間。

1 最短路徑問題的描述

設(shè)一個帶權(quán)重的有向圖G=(V,{L}),其中V是含有n個節(jié)點的集合，L是邊的集合，每條邊(i,j)∈L都賦予一個非負(fù)權(quán)重dij，表示節(jié)點i到節(jié)點j間的距離大小，i,j∈V。設(shè)B，E分別為V中的任意兩點，最優(yōu)路徑問題就是在帶有權(quán)重的有向圖中，尋找從點B到E的一條具有最小權(quán)重總和的路徑。

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

一種仿生算法—蟻群算法，是模擬自然界螞蟻尋找食物過程而得出。在此過程中，它們總能找到從巢穴到食物源之間的一條最短路徑。其原因在于螞蟻在路徑上會釋放一種信息激素(pheromone)進(jìn)行信息傳遞，螞蟻在運動過程中能夠感知這種物質(zhì)，由它來指導(dǎo)運動方向。當(dāng)它們碰到一個陌生路口時，就會隨機地選出一條路徑進(jìn)行前行，同時螞蟻會在這條路徑上釋放一定量的信息素，此時路徑上的信息素濃度增大，后來的螞蟻再次碰到這個路口時，就會選擇信息素濃度高的路徑,這樣就形成一種正反饋。最優(yōu)路徑上的激素濃度越來越大，最終整個蟻群就會搜索出一條最短路徑。

2.1 算法初始時刻濃度改進(jìn)

傳統(tǒng)的蟻群算法在初始迭代時給每條路徑上的濃度是一個常數(shù)，那時螞蟻不知道每條路徑的長度，它只能隨機選擇，產(chǎn)生了大量無關(guān)緊要的路徑，阻礙最優(yōu)路徑搜索過程，同時對信息素濃度局部更新也會產(chǎn)生影響。但在求最短路徑時，節(jié)點與節(jié)點之間的距離是已知的，因此在用蟻群算法求最短路徑時，沒有必要進(jìn)行盲目選擇，可以對迭代開始時的初始濃度進(jìn)行精確賦值。

設(shè)在網(wǎng)絡(luò)圖中需要求出從點B到E的一條最短路徑。其中節(jié)點i和節(jié)點j之間路徑上的初始信息素濃度為τij(0)，反映靠近最短距離的程度,越靠近最短距離,濃度應(yīng)該越大。用dBE表示起點B到終點E的直線距離,dBj表示節(jié)點B與節(jié)點j的直線距離，djE表示節(jié)點j到終點E的直線距離,dBj+djE表示B→j→E的曲線距離,dBE/(dBj+djE)中dBj+djE越趨向于dBE，dBE/(dBj+djE)越接近于1,此條路徑上的濃度越大,螞蟻就越偏向選擇這些節(jié)點作為移動方向。因此節(jié)點i和節(jié)點j之間路徑上的初始信息素濃度為τij(0)定義為:

(1)

算法的這種改進(jìn)使得螞蟻在搜索過程產(chǎn)生了比較合理的方向引導(dǎo)，進(jìn)而對無關(guān)路徑起到抑制作用，避免螞蟻的盲目搜索,提高了搜索全局最優(yōu)解的速率。

2.2 全局更新規(guī)則的改進(jìn)

傳統(tǒng)蟻群算法在全局更新規(guī)則中只更新每次迭代的最優(yōu)路徑上的信息素濃度。這樣就導(dǎo)致某些較短路徑信息素濃度過分增加，全局最優(yōu)路徑與單次迭代的最優(yōu)路徑相關(guān)性較大[10-12]，易陷入局部最優(yōu)。在全局更新規(guī)則中，引入自適應(yīng)動態(tài)因子σ(σ∈(0,1))，這樣不僅可以實時動態(tài)更新每次迭代最優(yōu)路徑的全局信息素濃度，而且也要動態(tài)更新較優(yōu)的局部最優(yōu)解。經(jīng)過自適應(yīng)控制單次迭代最優(yōu)解的信息素濃度在當(dāng)前最優(yōu)解中的比重，從而較優(yōu)路徑信息素濃度發(fā)揮了更大的作用，更好地反映了路徑信息，最優(yōu)解逐漸凸現(xiàn)，加快了全局最優(yōu)解的收斂速度。

τij(t+1)=τij(t)+σμΔτij

(2)

(3)

對于自適應(yīng)因子σ，當(dāng)Llocalmin越大，即搜索路徑越長時，動態(tài)因子σ越趨于0；而當(dāng)Llocalmin越小，搜索路徑越短時，動態(tài)因子σ越趨于1。所以搜索到的路徑長度越短，全局更新時它所遍歷的路徑信息素濃度越強，信息量增加就會較快。當(dāng)ω取不同值時，雙曲正切函數(shù)曲線以及與傳統(tǒng)蟻群算法動態(tài)因子的對比圖如圖1所示。

圖1 動態(tài)因子函數(shù)曲線圖

對于雙曲正切函數(shù)f(x)，當(dāng)x∈(-1,1)時，可以看到f(x)變化率最大，那么敏感度就較高，這樣有效區(qū)分了不同迭代最優(yōu)解對信息素加成的影響，加強局部最優(yōu)解中路徑更短的信息素濃度，加快收斂的全局最優(yōu)解的速度；當(dāng)x<-1時，f(x)緩慢趨向于0，這樣不但對不利解對信息素加成起到抑制作用，同時保留了其部分影響，進(jìn)而也增加了解空間的多樣性；當(dāng)x>-1時，f(x)緩慢趨于定值1，這樣更好地避免部分較短但不是全局最優(yōu)路徑被過度增強，有效地防止算法陷入局部最優(yōu)解。與此同時，對于自適應(yīng)動態(tài)因子σ是平滑過渡，故不會對信息素濃度造成波動影響。從圖中可以看出ω越大，f(x)對x的靈敏度就越高。

3 自適應(yīng)蟻群算法的步驟

以上是對傳統(tǒng)蟻群算法的改進(jìn)，改進(jìn)后的算法實現(xiàn)步驟如下：

步驟1:初始化信息啟發(fā)因子α(軌跡的相對重要性)，期望啟發(fā)因子β，路徑啟發(fā)因子ηij,ηij=1/dij。其中,dij為i→j的歐氏距離；q0為螞蟻狀態(tài)轉(zhuǎn)移的閾值。設(shè)最大迭代次數(shù)N,選定螞蟻數(shù)m。

步驟2：計算節(jié)點距離矩陣，初始化信息素濃度τij(0)，將m只螞蟻放在起點B，將各螞蟻的初始節(jié)點B置于當(dāng)前解集tabuk中，第k只螞蟻從節(jié)點i轉(zhuǎn)移到下一個節(jié)點j的規(guī)則：在0與1之間隨機生成一個實數(shù)q，把它與事先給定的閾值q0∈(0,1)進(jìn)行比較：

當(dāng)q>q0時，以輪盤賭的方式計算第k只螞蟻由i轉(zhuǎn)移到下一個節(jié)點l的概率：

(4)

步驟3:信息素濃度的局部更新。在螞蟻完成一次搜索后，信息素一方面要揮發(fā)掉一部分，另一方面螞蟻在走過的路徑上要釋放一定量的信息素。設(shè)揮發(fā)和增加信息素的系數(shù)均為ρ，更新規(guī)則如下：

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(5)

(6)

步驟4：重復(fù)步驟2和3，直到所有螞蟻都到達(dá)終點E，此時得到m條由初始節(jié)點到終點E的路徑{l1,l2,…,lm}。

步驟6：再將m只螞蟻放置于起點B，按照步驟2～4進(jìn)行搜索，這樣一直重復(fù)進(jìn)行，直到迭代N次，此時可以得到全局最優(yōu)解。

4 算法仿真

4.1 最短路徑問題求解

為檢驗文中自適應(yīng)蟻群算法的有效性，以哈爾濱市區(qū)部分交通路線圖為例，以道路交通事故現(xiàn)場作為起點，以哈爾濱市人民醫(yī)院作為終點，在事故和醫(yī)院之間尋找一條最短路徑，其目的是快速將傷員送往醫(yī)院，最大可能地減少人員傷亡和財產(chǎn)損失。

選取的參數(shù)如表1所示，分別采用文中的自適應(yīng)蟻群算法(M-ACO)、傳統(tǒng)蟻群算法(Ant Colony Optimization，ACO)、最大最小蟻群算法(Max-Min Ant System，MMAS)，節(jié)點與節(jié)點間的距離數(shù)據(jù)來源于文獻(xiàn)[13]。

表1 3種算法的公共參數(shù)設(shè)置

選取交通事故點離醫(yī)院有20個路口即對20個節(jié)點網(wǎng)絡(luò)進(jìn)行仿真實驗，實際最短路徑長度為3 186.25 km，用三種方法搜索的最短距離結(jié)果如表2所示。

表2 20路口網(wǎng)絡(luò)實驗數(shù)據(jù)統(tǒng)計結(jié)果

從表2可以看出：ACS經(jīng)歷21次迭代后迅速陷入局部最優(yōu)，并且在100次中只有8次搜索到最優(yōu)路徑；而搜索結(jié)果在平均解意義上有所提高的是MMAS，但平均迭代次數(shù)明顯升高，并且搜索到的最優(yōu)解的幾率只有19%；文中改進(jìn)的蟻群算法的搜索結(jié)果在最優(yōu)解和平均最優(yōu)解上都有顯著改善，搜索到最優(yōu)解的幾率為96%，基本上每次都能找到最優(yōu)解。

為進(jìn)一步驗證文中算法對路口數(shù)量多的適用性，現(xiàn)擴大交通事故點與醫(yī)院的距離，路口增加即研究的網(wǎng)絡(luò)節(jié)點數(shù)增加，使得研究的網(wǎng)絡(luò)圖變得更復(fù)雜。分別對20、30、40、50、60個路口進(jìn)行仿真，如表3和表4所示。

表3 最優(yōu)解搜索率統(tǒng)計結(jié)果 %

由表3可知，當(dāng)路口數(shù)增加時，改進(jìn)的M-ACS算法仍然具有較好的路徑搜索效果，30路口時最優(yōu)路徑搜索率為89%，遠(yuǎn)遠(yuǎn)優(yōu)于其他兩種算法。當(dāng)路口數(shù)為60時，由于研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)較為復(fù)雜，計算量較大，參考算法搜索率較低，而文中仍然有51%的搜索率。表4中，M-ACS算法平均迭代次數(shù)略大于其他算法，并且在路口數(shù)較少時，迭代數(shù)增加并不明顯，但帶來的搜索性能提升較大。

表4 平均迭代次數(shù)統(tǒng)計結(jié)果

3種算法對不同節(jié)點的收斂時間對比如圖2所示。

圖2 收斂時間對比圖

從圖2可以看出：在不同復(fù)雜程度的網(wǎng)絡(luò)圖中，3種算法中收斂時間最短的是文中提出的自適應(yīng)蟻群算法，主要因為M-ACS在迭代初期，對路徑的信息素濃度進(jìn)行了重新分配，并給予了一定的方向指導(dǎo)，節(jié)約了蟻群盲目的隨機搜索時間。在迭代后期全局信息素濃度更新時加入了自適應(yīng)動態(tài)因子，動態(tài)更新每次迭代最優(yōu)路徑的全局信息素濃度，使其最優(yōu)路徑上的信息素濃度進(jìn)一步加強，從而提高了算法的收斂速度。因此，在不同節(jié)點的收斂時間均小于其他2種算法。

4.2 TSP問題求解

旅游線路的優(yōu)化問題是旅行商問題(TSP)的一種典型代表。近幾年來對于TSP的求解提出了許多優(yōu)化算法，仿生算法是研究熱點，它有傳統(tǒng)算法不可替代的優(yōu)勢。文中引用文獻(xiàn)[14]中設(shè)計旅行線路為例，直觀地反映自適應(yīng)蟻群算法與其他算法的優(yōu)劣。為驗證文中算法的性能，引入遺傳算法和傳統(tǒng)的蟻群算法進(jìn)行求解。選取參數(shù)如表1，設(shè)置出發(fā)點都為重慶，且必須經(jīng)過每一個城市且只有一次，最后回到重慶。

由文獻(xiàn)[14]可知，利用遺傳算法得出的最優(yōu)路線如圖3所示，對應(yīng)最優(yōu)值為18 997.8 km。圖4為傳統(tǒng)蟻群算法得出旅行路徑的結(jié)果，其對應(yīng)的最優(yōu)值為18 696.1 km。從優(yōu)化效果來看，傳統(tǒng)蟻群算法的尋優(yōu)效果比遺傳算法的效果更好。

圖3 遺傳算法運行結(jié)果

圖4 傳統(tǒng)蟻群算法運行結(jié)果

圖5為采用自適應(yīng)蟻群算法設(shè)計旅行路徑的結(jié)果。對應(yīng)的線路如下：重慶→貴州→南寧→海口→澳門→香港→廣州→長沙→合肥→南京→上?！贾荨_北→福州→南昌→武漢→鄭州→太原→石家莊→濟(jì)南→哈爾濱→長春→沈陽→天津→北京→呼和浩特→西安→銀川→蘭州→西寧→烏魯木齊→拉薩→昆明→成都→重慶；所對應(yīng)的最優(yōu)值為17 887.4 km。從效果來看，自適應(yīng)蟻群算法的尋優(yōu)效果比遺傳算法和傳統(tǒng)的蟻群算法的效果更好。

通過三種算法的比較可以得出：文中在迭代過程中采用自適應(yīng)蟻群算法，在實際應(yīng)用中能夠得到更佳的效果且求解精度更高。

圖5 自適應(yīng)蟻群算法運行結(jié)果

5 結(jié)束語

針對傳統(tǒng)蟻群算法存在容易陷入局部最優(yōu)解且收斂速度慢的缺陷，提出了自適應(yīng)蟻群算法。通過在初始化信息素濃度時加入方向引導(dǎo)，在全局信息素更新過程中加入雙曲正切函數(shù)作為動態(tài)因子，自適應(yīng)地調(diào)整每次迭代最優(yōu)解的信息素更新的改進(jìn)策略。實驗結(jié)果表明：自適應(yīng)蟻群算法提高了求解最短路徑的收斂速度和精度，增強了算法的尋優(yōu)能力。為驗證文中算法的有效性，將其用于34個城市旅游線路的優(yōu)化，并與傳統(tǒng)的蟻群算法和遺傳算法進(jìn)行比較。結(jié)果表明：文中算法尋優(yōu)精度高，得到的線路最優(yōu)。

[1] Colomi A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C]//Proceeding of the first European conference of artificial life.Paris:Elsevier Publishing,1991.

[2] Dorigo M,Ganbardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[3] Colomi A,Dorigo M,Maniezzo V.Ant system for job-shop scheduling[J].Belgian Journal of Operations Research Statistics and Computer Science,1994,34(1):39-53.

[4] Dorigo M,Maniezzo V,Colomi A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on System Man and Cybernetics -Part B,1996,26(1):29-41.

[5] 王 健,劉衍珩,朱建啟.全局自適應(yīng)蟻群優(yōu)化算法[J].小型微型計算機系統(tǒng),2008,29(6)：1083-1087.

[6] 付 宇,肖健梅.動態(tài)自適應(yīng)蟻群算法求解TSP問題[J].計算機輔助工程，2008,15(4)：10-13.

[7] Stuzle H.MAX-MIN ant system[J].Future Generation Computer System,2000,16:889-914.

[8] Clornei I,Kyriakides E.Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization[J].IEEE Transactions on Systems Man and Cybernetics-Part B,Cybernetics,2012,42(1):234-245.

[9] 鄭衛(wèi)國,田其沖,張 磊.基于信息素強度的改進(jìn)蟻群算法[J].計算機仿真,2010,27(7):191-193.

[10] Shah S,Kothari R,Chandra S.Debugging ants:how ants find the shortest routs[C]//8th international conference on information,communications and signal processing.[s.l.]:IEEE,2011:1-5.

[11] 吳虎發(fā),李學(xué)俊,章玉龍.改進(jìn)的蟻群算法求解最短路徑問題[J].計算機仿真,2012,29(8):215-218.

[12] 張學(xué)敏,張 航.基于改進(jìn)蟻群算法的最短路徑問題研究[J].自動化技術(shù)與研究,2009(6):4-7.

[13] 哈爾濱市統(tǒng)計年鑒[R].哈爾濱:哈爾濱市統(tǒng)計局,2014.

[14] 走遍全中國方案的研究[EB/OL].2014-05-30.http://www.docin.com/p-105402921.html.

Solving of Shortest Path Problem and TSP with Adaptive Ant Colony Algorithm

YI Zheng-jun1,LI Yong-xia1,YI Xiao-shi2

(1.College of Mathematics and Statistics,Chongqing University，Chongqing 401331,China;2.College of Mathematics and Statistics,Chongqing Normal University,Chongqing 401131,China)

Direction guiding is utilized in the initial pheromone avoiding ant colony in the initial stage to blindly random search and to waste more time.Moreover,a dynamic factor (hyperbolic tangent function) is invited in the global renewal process to update adaptively the pheromone concentration on the optimal path,in which way the possibility of obtaining the global optimal solution is increased.Then two examples are optimized with the improved algorithm,and the optimization results are in step with the actual,illustrating the effectiveness and practicability of the improved algorithm.

ant colony algorithm;shortest path;direction guiding;dynamic factor;TSP

2016-01-27

2016-05-11

時間：2016-11-21

國家自然科學(xué)基金資助項目(69674012)；重慶市科技攻關(guān)計劃(CSTC2009AC3037)

易正俊(1963-)，男，博士，教授，全國專業(yè)學(xué)位研究生教育教指委專家,研究方向為人工智能、仿真系統(tǒng)、數(shù)據(jù)挖掘；李勇霞(1988-)，女，碩士生，研究方向為智能算法。

http://www.cnki.net/kcms/detail/61.1450.TP.20161121.1641.026.html

TP301

A

1673-629X(2016)12-0001-05

10.3969/j.issn.1673-629X.2016.12.001