自適應蟻群算法求解最短路徑和TSP問題

易正俊，李勇霞，易校石

(1.重慶大學 數學與統計學院，重慶 401331;2.重慶師范大學 數學科學學院，重慶 401131)

自適應蟻群算法求解最短路徑和TSP問題

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

(1.重慶大學 數學與統計學院，重慶 401331;2.重慶師范大學 數學科學學院，重慶 401131)

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

蟻群算法；最短路徑；方向引導；動態因子：旅行商問題

0 引 言

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

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

1 最短路徑問題的描述

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

2 蟻群算法的改進

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

2.1 算法初始時刻濃度改進

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

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

(1)

算法的這種改進使得螞蟻在搜索過程產生了比較合理的方向引導，進而對無關路徑起到抑制作用，避免螞蟻的盲目搜索,提高了搜索全局最優解的速率。

2.2 全局更新規則的改進

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

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

(2)

(3)

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

圖1 動態因子函數曲線圖

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

3 自適應蟻群算法的步驟

以上是對傳統蟻群算法的改進，改進后的算法實現步驟如下：

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

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

當q>q0時，以輪盤賭的方式計算第k只螞蟻由i轉移到下一個節點l的概率：

(4)

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

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

(5)

(6)

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

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

4 算法仿真

4.1 最短路徑問題求解

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

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

表1 3種算法的公共參數設置

選取交通事故點離醫院有20個路口即對20個節點網絡進行仿真實驗，實際最短路徑長度為3 186.25 km，用三種方法搜索的最短距離結果如表2所示。

表2 20路口網絡實驗數據統計結果

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

為進一步驗證文中算法對路口數量多的適用性，現擴大交通事故點與醫院的距離，路口增加即研究的網絡節點數增加，使得研究的網絡圖變得更復雜。分別對20、30、40、50、60個路口進行仿真，如表3和表4所示。

表3 最優解搜索率統計結果 %

由表3可知，當路口數增加時，改進的M-ACS算法仍然具有較好的路徑搜索效果，30路口時最優路徑搜索率為89%，遠遠優于其他兩種算法。當路口數為60時，由于研究網絡拓撲結構較為復雜，計算量較大，參考算法搜索率較低，而文中仍然有51%的搜索率。表4中，M-ACS算法平均迭代次數略大于其他算法，并且在路口數較少時，迭代數增加并不明顯，但帶來的搜索性能提升較大。

表4 平均迭代次數統計結果

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

圖2 收斂時間對比圖

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

4.2 TSP問題求解

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

由文獻[14]可知，利用遺傳算法得出的最優路線如圖3所示，對應最優值為18 997.8 km。圖4為傳統蟻群算法得出旅行路徑的結果，其對應的最優值為18 696.1 km。從優化效果來看，傳統蟻群算法的尋優效果比遺傳算法的效果更好。

圖3 遺傳算法運行結果

圖4 傳統蟻群算法運行結果

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

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

圖5 自適應蟻群算法運行結果

5 結束語

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

[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] 王 健,劉衍珩,朱建啟.全局自適應蟻群優化算法[J].小型微型計算機系統,2008,29(6)：1083-1087.

[6] 付 宇,肖健梅.動態自適應蟻群算法求解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] 鄭衛國,田其沖,張 磊.基于信息素強度的改進蟻群算法[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] 吳虎發,李學俊,章玉龍.改進的蟻群算法求解最短路徑問題[J].計算機仿真,2012,29(8):215-218.

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

[13] 哈爾濱市統計年鑒[R].哈爾濱:哈爾濱市統計局,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

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

易正俊(1963-)，男，博士，教授，全國專業學位研究生教育教指委專家,研究方向為人工智能、仿真系統、數據挖掘；李勇霞(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