基于改進蟻群算法的旅游路線優(yōu)化

張永強，王曉東

(西安工程大學 理學院,陜西 西安 710048)

基于改進蟻群算法的旅游路線優(yōu)化

張永強，王曉東

(西安工程大學 理學院,陜西 西安 710048)

蟻群算法是按照鄰近節(jié)點路徑最短的原理選取下一個節(jié)點,因此在全局路徑中不一定是最優(yōu)選擇.針對這一缺點,文中采用兩步節(jié)點最短路徑策略選取下一個節(jié)點的方法,對蟻群算法路徑選擇進行改進,并對禁忌表中節(jié)點順序進行調(diào)整.然后采用TSPLIB中的Benchmark31、Att48、kroA100、Pr136、tsp225問題,對旅游路線進行優(yōu)化和仿真,所得改進蟻群算法比基本蟻群算法搜尋結(jié)果更優(yōu).將Att48、Eil51問題運行結(jié)果與其他算法進行比較,結(jié)果表明，改進蟻群算法得到了較優(yōu)路徑.

蟻群算法;旅游路線;最優(yōu)解

0 引 言

目前,旅行已經(jīng)越來越受到人們的青睞,而旅游路線的選擇也成為人們出發(fā)前研究的一個重要問題,優(yōu)化旅游路線可以為人們的出行降低成本和提高效率.蟻群算法是解決線路優(yōu)化問題的有力工具,它是由意大利學者Dorigo M等在20世紀90年代初提出的一種新型的模擬進化算法[1-2].它的基本原理是基于蟻群相互協(xié)作找到一條從蟻穴到食物源的最短路徑,是一種群優(yōu)化算法[3],但蟻群算法易陷入局部最優(yōu)解,因此對蟻群算法的改進也就成為當前研究的熱點之一.學者們從蟻群算法的路徑選擇[4]、信息素更新準則[5-6]、局部搜索與全局搜索[7-9]、收斂速度[10-11]等方面做了大量的工作.德國學者Thomas sttzle與Jolger Hoos提出了“最大最小蟻群系統(tǒng)”的改進算法[12],避免了某條路徑的信息量遠大于其他路徑;鄭松等[13]提出一種動態(tài)調(diào)整的選擇策略以強化其全局搜索能力;侯文靜等[14]通過縮小算法的搜索范圍、改善解空間的質(zhì)量而提高了蟻群算法的搜索速度;柳長安等[15]借鑒狼群分配原則對信息素進行更新,避免了蟻群算法在搜索中陷入局部最優(yōu);針對基本蟻群算法收斂速度慢的問題,文獻[16-17]對其進行改進,改進后的算法加快了收斂速度.然而對于蟻群算法路徑選擇方面改進的文章目前還比較少,由于基本蟻群算法以鄰近節(jié)點最短路徑選取下一個節(jié)點,這樣選擇會使得全局的路徑長度總和不一定最小,針對這一缺陷,文章考慮用兩步節(jié)點最短路徑策略來選取下一個節(jié)點的思想對基本蟻群算法改進,并對禁忌表中節(jié)點順序進行調(diào)整,然后將改進后的算法應用于Benchmark31、Att48、kroA100、Pr136、tsp225問題,對旅游路線進行優(yōu)化和仿真,得到改進蟻群算法比基本蟻群算法能搜尋到更優(yōu)結(jié)果.

1 蟻群算法(ACO)原理

引入旅行商優(yōu)化問題說明蟻群系統(tǒng)模型[18].旅行商問題的實質(zhì)是在N個城市中,旅行商有且只有一次經(jīng)過每一個城市,使其總路程最短.設城市數(shù)目為N個,螞蟻有M只,螞蟻通過轉(zhuǎn)移概率選擇下一個要訪問的城市.在蟻群算法中人為地設置禁忌表tabu(k),用來存儲螞蟻已經(jīng)訪問過的城市.螞蟻根據(jù)記憶,按照轉(zhuǎn)移概率選擇下一個沒有在禁忌表中的城市,轉(zhuǎn)移概率表達式為

(1)

信息素τij會以一定的方式更新,其表達式為

(2)

(3)

其中LK表示一次旅游結(jié)束后螞蟻k目前訪問的總路徑長度,Q是常量.

2 蟻群算法的改進

2.1 啟發(fā)式因子的改進

基本蟻群算法以鄰近節(jié)點路徑最短的原理選取下一個節(jié)點,即為一個城市離螞蟻所在地越近,則螞蟻就會以較大的概率選擇該城市.然而,在這個過程中,螞蟻以該原理選擇的兩步路徑之間的距離長度不一定是最小的,并通過正反饋使得該誤差值進一步放大,從而導致螞蟻向錯誤的方向?qū)ふ?對整個算法性能造成影響.也就是說螞蟻從上一個城市以最短路徑選擇下一個城市,步步如此,最后選擇的路徑不一定是最優(yōu)路徑,這樣最終的路徑長度總和不一定最小.如圖1所示,假定從A點出發(fā),要求到達D點.ACD為最短路徑,然而,螞蟻按照鄰近節(jié)點路徑最短的選擇規(guī)則,以較大的概率選擇下一節(jié)點B,所以螞蟻所走路徑為ABD,而路徑ABD的路徑長度6大于路徑ACD的路徑長度4.5.

通過上面的例子可以看出,蟻群算法以相鄰的兩個節(jié)點(即一步)路徑最短的原理選取下一個節(jié)點,得到的結(jié)果不一定是最優(yōu)的,因此考慮三個節(jié)點(即兩步)之間的路徑距離,且利用這一策略對啟發(fā)式因子進行改進,按照式(1)中距離越大,啟發(fā)式因子越小,轉(zhuǎn)移概率越小的原則,改進如下:

ηij=1/(di，j+dj,j+1).

(4)

其中ηij為啟發(fā)式因子,di，j表示節(jié)點i與節(jié)點j之間的距離長度.節(jié)點j按照式(5)選取:

(5)

其中節(jié)點j是從節(jié)點i要選取的下一個節(jié)點,節(jié)點j+1是從節(jié)點j要選取的下一個節(jié)點,k是任意節(jié)點,D表示完全圖的賦權(quán)鄰接矩陣,則D(i,j)表示節(jié)點i與節(jié)點j之間的距離,R=tabu.

基本蟻群算法的啟發(fā)式因子是由一步節(jié)點之間的距離界定的,一步距離越小,啟發(fā)式因子越大,則選擇該一步路徑概率越大;改進后的啟發(fā)式因子是由兩步節(jié)點之間的距離決定的,兩步之間距離越小則啟發(fā)式因子越大,則選擇該路徑的概率就越大.基本蟻群算法完成一步之后,再搜尋第二步,而且這種分離式的兩步距離之和不一定是最短的,如圖1所示.螞蟻在搜索初期,各條路徑上的信息素量是一樣的,對螞蟻誘導作用不是很大,而主要以啟發(fā)式因子值為導向進行搜索,與基本蟻群算法相比,改進后的算法采用兩步距離策略更有全局性,因此在搜索初期進行比較,改進蟻群算法將會得到比基本蟻群算法較優(yōu)的路徑.在圖2中,迭代初期,改進蟻群算法得到的路徑長度小于基本蟻群算法得到的路徑長度,從而可以從啟發(fā)式因子的角度有效避免分離式兩步距離不是最短的缺點.

2.2 禁忌表中節(jié)點順序調(diào)整

在蟻群算法中,螞蟻按照概率選擇公式去選擇下一個節(jié)點,并將選擇的這個節(jié)點添加到禁忌表tabu中,在此過程中選擇概率是按鄰近節(jié)點路徑最短的原理選取下一個節(jié)點的,文中通過2.1的改進,采用兩步節(jié)點最短路徑策略選取下一個節(jié)點的方法來影響轉(zhuǎn)移概率.當螞蟻遍歷所有節(jié)點之后,將所有節(jié)點全部添加到禁忌表tabu中,然后按照禁忌表tabu中的順序來計算最短距離,然而按此時禁忌表tabu中節(jié)點的順序計算出的距離不一定是全局最短距離,因為選擇概率是由啟發(fā)式因子和信息素共同決定的,在螞蟻搜尋后期路徑上的信息素量會越來越大,從而降低了啟發(fā)式因子對選擇概率的影響,如果在之前有螞蟻搜尋到非最優(yōu)路徑,則后來螞蟻也會按照這條路徑搜尋,導致搜尋得到的結(jié)果不是全局最優(yōu)值.所以文中考慮用(6)式進行調(diào)整禁忌表tabu中節(jié)點的順序.

(6)

其中R=tabu,L記錄本次迭代最佳路線,L(i)表示從起點到節(jié)點i的路線長度,D(R(i),R(j))表示禁忌表中節(jié)點i和節(jié)點j之間的距離.

2.3 改進的蟻群算法步驟

根據(jù)以上的改進思路,改進后的算法實現(xiàn)步驟如下：

Step 1 初始化蟻群算法中的參數(shù)α,β,ρ,Q,NC_max,m,設置迭代計數(shù)器初始值NC=1;

Step 2 隨機選擇每只螞蟻的初始位置,初始化禁忌表tabu,按式(4)計算啟發(fā)因子;

Step 3 m只螞蟻按概率函數(shù)式(1)選擇下一座城市,將所選城市節(jié)點添加到tabu中;

Step 4 若禁忌表tabu未滿轉(zhuǎn)至Step 3,若已滿,得出螞蟻此次的最優(yōu)路徑長度LNC,并且更新Lbest的值;

Step 5 按照式(6)調(diào)整節(jié)點之間的順序,記錄本次迭代最佳路線;

Step 6 按式(2)更新信息素,禁忌表tabu清零;

Step 7 判斷迭代次數(shù)是否滿足條件NC

Step 8 算法結(jié)束,輸出最優(yōu)路徑長度Lbest.

3 改進蟻群算法在旅游路線優(yōu)化中的應用

在Windows 7環(huán)境下,運用Matlab7.0語言進行編程,采用TSPLIB中的Benchmark31、Att48、kroA100、Pr136、tsp225問題,對旅游路線進行優(yōu)化和仿真.首先將基本蟻群算法和改進后的蟻群算法對其進行求解,各運行10次,結(jié)果如表1所示,迭代圖如圖2所示.然后將Benchmark31單獨運行10次,結(jié)果如表2、圖3～4所示;最后將Att48、Eil51問題運行結(jié)果與其他算法進行比較,結(jié)果如表3～4,圖5～6所示．算法參數(shù)選擇如下:α=1,β=5,ρ=0.1,Q=100,取迭代次數(shù)200為終止條件,螞蟻個數(shù)為31.

表 1 路線優(yōu)化問題實驗比較

通過比較表1中最優(yōu)值和平均值發(fā)現(xiàn),改進蟻群算法對于Benchmark31、Att48、kroA100、Pr136、tsp225問題的運行結(jié)果都優(yōu)于基本蟻群算法的結(jié)果.

觀察圖2，在每個圖中改進蟻群算法迭代曲線的最低位置總是低于基本蟻群算法迭代曲線的最低位置,表明改進蟻群算法總是可以收斂到比基本蟻群算法更優(yōu)的結(jié)果.

在圖3中,用基本蟻群算法求得該旅游線路的最短距離為15 602,最優(yōu)解路徑為14→12→13→11→23→16→5→6→7→2→4→8→9→10→3→18→17→19→24→25→20→21→22→26→28→27→30→31→29→1→15.

在圖4中,用改進的蟻群算法求得該旅游線路問題的最短距離為15 398,最優(yōu)解路徑為6→5→16→4→2→8→9→10→3→18→17→19→24→25→20→21→22→26→28→27→30→31→29→11→23→13→12→14→1→15→7.

序號基本蟻群算法改進蟻群算法序號基本蟻群算法改進蟻群算法1156021549671588415797215829157168159481560031597315398915772157604156021549610156021563251594815502平均路徑長度157981559061581815498

由表2可以看出,基本蟻群算法最優(yōu)路徑長度為15 602,平均路徑長度為15 798;改進蟻群算法最優(yōu)路徑長度為15 398,平均路徑長度為15 590.改進蟻群算法比基本蟻群算法能夠找到更短的路徑.

如圖5所示,改進蟻群算法優(yōu)化Att48 TSP問題得到的最優(yōu)路徑為37→6→30→28→36→18→7→44→31→38→9→1→8→22→16→3→23→11→12→15→ 40→33→46→20→47→21→13→25→14→34→41→29→2→42→10→24→45→35→26→4→ 5→48→39→32→17→27→43→19.

表 3 Att48 實驗比較

表 4 Eil51 的實驗比較

如圖6所示,改進蟻群算法優(yōu)化Eil51 TSP問題得到的最優(yōu)路徑為19→41→13→25→14→18→47→12→46→51→27→48→6→23→24→43→7→26→8→31→28→3→20→35→36→22→1→32→11→38→5→49→9→50→16→2→29→21→34→30→10→39→33→45→15→44→37→17→4→42→40.

4 結(jié)束語

路徑優(yōu)化問題是實際生活中一個重要的現(xiàn)實問題,文中采用兩步節(jié)點最短路徑策略選取下一個節(jié)點的方法,對蟻群算法路徑選擇進行改進,并對禁忌表中節(jié)點順序進行調(diào)整,然后采用TSPLIB中的Benchmark31、Att48、kroA100、Pr136、tsp225問題進行仿真,并將改進蟻群算法運行Att48、Eil51的結(jié)果與其他算法運行結(jié)果進行比較.結(jié)果表明,在迭代次數(shù)小于100時得到Att48的最優(yōu)路徑長度為32 112,在迭代次數(shù)小于150時得到Eil51的最優(yōu)路徑長度為442.76,比其他算法的運行結(jié)果更優(yōu).因此改進蟻群算法可用于解決旅游路線優(yōu)化問題.

[1] COLORNI A,DORIGO M,MANIEZZO V.Distributed optimization by ant colonies[C]//Proceedings of the First European Conference on Artificial Life.Pans:Elsevier,1991,142:134-142.

[2] DORIGO M,MANIEZZO V,COLORNI A. Ant system:Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems,Man,and Cybernetics,Part B,1996,26(1):29-41.

[3] YANG Xinshe,HE Xingshi.Swarm intelligence and smart optimization algorithms[J]. Basic Sciences Journal of Textile Universities,2013,26(3):287-296.

[4] 張志協(xié),曹陽.基于改進型蟻群算法的最優(yōu)路徑問題求解[J].計算機系統(tǒng)應用,2012,21(10):76-80.

ZHANG Zhixie,CAO Yang.Solving optimal path problem based on improved ant colony algorithm[J]. Computer Systems & Applications,2012,21(10):76-80.

[5] LEE S G,JUNG T U,CHUANG T C. An effective dynamic weighted rule for ant colony system optimization[C]//Proceedings of the IEEE International Conference on Evolutionary Computation,Indianapolis:IEEE,2001,2:1393-1397.

[6] 楊延慶,李鵬飛,何博.求解TSP問題的改進最大最小蟻群算法[J].西安工程大學學報,2010,24(6):818-821.

YANG Yanqing,LIPengfei,HE Bo.Improved algorithm of maxinized and minimized ants on solving TSP[J].Journal of Xi′an Polytechnic University,2010,24(6):818-821.

[7] 馬良.全局優(yōu)化的一種新方法[J].系統(tǒng)工程與電子技術(shù),2000,22(9):61-63.

MA Liang.A new method for global optimization[J].Systems Engineering and Electronics,2000,22(9):61-63.

[8] 陳建軍.蟻群算法在物流配送路徑優(yōu)化中的研究[J].計算機仿真,2011,28(2):268-271.

CHEN Jianjun.Study on routing optimization for physical distribution based on ant colony algorithm[J]. Computer Simulation,2011,28(2):268-271.

[9] 王勝訓,李艷穎.一種求解TSP的自適應蟻群優(yōu)化算法[J].西安工程大學學報,2013,27(6):840-844.

WANG Shengxun,LI Yanying.Adaptive ant colony optimization algorithm and TSP simulation[J]. Journal of Xi′an Polytechnic University,2013,27(6):840-844.

[10] 李擎,張超,陳鵬,等.一種基于粒子群參數(shù)優(yōu)化的改進蟻群算法[J].控制與決策,2013,28(6):873-878.

LI Qing,ZHANG Chao,CHEN Peng,et al.Improved ant colony optimization algorithm based on particle swarm optimization[J]. Control and Decision,2013,28(6):873-878.

[11] 羅慧,蹇興亮,盧偉.基于動態(tài)蟻群算法的模擬電路最優(yōu)測點選擇[J].儀器儀表學報,2014,35(10):2231-2236.

LUO Hui,JIAN Xingliang,LU Wei.Optimal test node selection based on dynamic ant colony algorithm for analog circuit[J]. Chinese Journal of Scientific Instrument,2014,35(10):2231-2236.

[12] STUTZLE T,HOOS H. Max-min ant system and local search for the traveling salesman problem[C]//IEEE International Conference on Evolutionary Computation,Indianapolis:IEEE,1997: 309-314.

[13] 鄭松,侯迪波,周澤魁.動態(tài)調(diào)整選擇策略的改進蟻群算法[J].控制與決策,2008,23(2):225-228.

ZHENG Song,HOU Dibo,ZHOU Zekui.Ant colony algorithm with dynamic transition probability[J]. Control and Decision,2008,23(2):225-228.

[14] 侯文靜,馬永杰,張燕,等.求解TSP的改進蟻群算法[J].計算機應用研究,2010,27(6):2087-2089.

HOU Wenjing,MA Yongjie,ZHANG Yan,et al.Improved ant colony algorithm for solving TSP[J]. Application Research of Computers,2010,27(6):2087-2089.

[15] 柳長安,鄢小虎,劉春陽,等.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學報,2011,39(5):1220-1224.

LIU Chang′an,YAN Xiaohu,LIU Chunyang,et al. Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J]. Acta Electronica Sinica,2011,39(5):1220-1224.

[16] 吳華鋒,陳信強,毛奇凰,等.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學報,2013,34(4):165-170.

WU Huafeng,CHEN Xinqiang,MAO Qihuang,et al.Improved ant colony algorithm based on natural selection strategy for solving TSP problem[J]. Journal on Communications,2013,34(4):165-170.

[17] 劉建華,楊建國,劉華平,等.基于勢場蟻群算法的移動機器人全局路徑規(guī)劃方法[J].農(nóng)業(yè)機器學報,2015,46(9):18-27.

LIU Jianhua,YANG Jianguo,LIU Huaping,et al.Robot global path planning based on ant colony optimization with artificial potential field[J].Transactions of the Chinese Society for Agricultural Machinery,2015,46(9):18-27.

[18] 段海濱.蟻群算法原理及其應用[M].北京:科學出版社,2005:24-43.

DUAN Haibin.Ant colony algorithms theory and applications[M].Beijing: Science Press,2005:24-43.

[19] 孟曉琳,黃天民,陳尚云.基于信息素更新和揮發(fā)因子調(diào)整的改進蟻群算法[J].成都大學學報:自然科學版,2015,34(1):48-51.

MENG Xiaolin,HUANG Tianmin,CHEN Shangyun.Improved ant colony optimization algorithm based on pheromone updating and evaporation factor adjusting[J].Journal of Chengdu University:Natural Science Edition,2015,34(1):48-51.

[20] 張家善,王志宏.基于信息素的改進蟻群算法及其在TSP中的應用[J].數(shù)學的實踐與認識,2013,43(22):157-160.

ZHANG Jiashan,WANG Zhihong.Improved ant colony algorithm based on pheromone and application in the TSP[J]. Mathematics in Practice and Theory,2013,43(22):157-160.

編輯：武 暉；校對：師 瑯

Tourist routes optimization based on improved ant colony algorithm

ZHANGYongqiang,WANGXiaodong

(School of Science,Xi′an Polytechnic University, Xi′an 710048,China)

The basic ant colony algorithm is the shortest path in accordance with the principles of neighboring nodes to select the next node, the global path is not the necessarily best choice. Aimed at the disadvantage, two-node shortest path strategy of selecting the next node methods is used, the path selection of ant colony algorithm is improved, and the tabu list of nodes in sequence is adjusted.Then the TSPLIB Benchmark31, Att48, kroA100, Pr136, tsp225 problem are used for tourism route optimization and simulation,the improved ant colony algorithm can find better results than the basic ant colony algorithm. Att48, operating results Eil51 problems with other algorithms were compared, the results show that the improved ant colony algorithm obtained optimum path.

ant colony algorithm; tourist routes; the optimal solution

1006-8341(2016)04-0570-07

10.13338/j.issn.1006-8341.2016.04.026

2016-08-11

陜西省教育廳專項科研計劃項目(14JK1299)

王曉東(1974—),女,陜西省咸陽市人,西安工程大學副教授,研究方向為智能算法.

E-mail:wangxiaodong1225@126.com

張永強,王曉東.基于改進蟻群算法的旅游路線優(yōu)化[J].紡織高校基礎科學學報,2016,29(4)：570-576.

ZHANG Yongqiang,WANG Xiaodong.Tourist routes optimization based on improved ant colony algorithm[J].Basic Sciences Journal of Textile Universities,2016,29(4):570-576.

TP 301.6

A