张永强，王晓东

(西安工程大学 理学院,陕西 西安 710048)

基于改进蚁群算法的旅游路线优化

张永强，王晓东

(西安工程大学 理学院,陕西 西安 710048)

蚁群算法是按照邻近节点路径最短的原理选取下一个节点,因此在全局路径中不一定是最优选择.针对这一缺点,文中采用两步节点最短路径策略选取下一个节点的方法,对蚁群算法路径选择进行改进,并对禁忌表中节点顺序进行调整.然后采用TSPLIB中的Benchmark31、Att48、kroA100、Pr136、tsp225问题,对旅游路线进行优化和仿真,所得改进蚁群算法比基本蚁群算法搜寻结果更优.将Att48、Eil51问题运行结果与其他算法进行比较,结果表明，改进蚁群算法得到了较优路径.

蚁群算法;旅游路线;最优解

0 引 言

目前,旅行已经越来越受到人们的青睐,而旅游路线的选择也成为人们出发前研究的一个重要问题,优化旅游路线可以为人们的出行降低成本和提高效率.蚁群算法是解决线路优化问题的有力工具,它是由意大利学者Dorigo M等在20世纪90年代初提出的一种新型的模拟进化算法[1-2].它的基本原理是基于蚁群相互协作找到一条从蚁穴到食物源的最短路径,是一种群优化算法[3],但蚁群算法易陷入局部最优解,因此对蚁群算法的改进也就成为当前研究的热点之一.学者们从蚁群算法的路径选择[4]、信息素更新准则[5-6]、局部搜索与全局搜索[7-9]、收敛速度[10-11]等方面做了大量的工作.德国学者Thomas sttzle与Jolger Hoos提出了“最大最小蚁群系统”的改进算法[12],避免了某条路径的信息量远大于其他路径;郑松等[13]提出一种动态调整的选择策略以强化其全局搜索能力;侯文静等[14]通过缩小算法的搜索范围、改善解空间的质量而提高了蚁群算法的搜索速度;柳长安等[15]借鉴狼群分配原则对信息素进行更新,避免了蚁群算法在搜索中陷入局部最优;针对基本蚁群算法收敛速度慢的问题,文献[16-17]对其进行改进,改进后的算法加快了收敛速度.然而对于蚁群算法路径选择方面改进的文章目前还比较少,由于基本蚁群算法以邻近节点最短路径选取下一个节点,这样选择会使得全局的路径长度总和不一定最小,针对这一缺陷,文章考虑用两步节点最短路径策略来选取下一个节点的思想对基本蚁群算法改进,并对禁忌表中节点顺序进行调整,然后将改进后的算法应用于Benchmark31、Att48、kroA100、Pr136、tsp225问题,对旅游路线进行优化和仿真,得到改进蚁群算法比基本蚁群算法能搜寻到更优结果.

1 蚁群算法(ACO)原理

引入旅行商优化问题说明蚁群系统模型[18].旅行商问题的实质是在N个城市中,旅行商有且只有一次经过每一个城市,使其总路程最短.设城市数目为N个,蚂蚁有M只,蚂蚁通过转移概率选择下一个要访问的城市.在蚁群算法中人为地设置禁忌表tabu(k),用来存储蚂蚁已经访问过的城市.蚂蚁根据记忆,按照转移概率选择下一个没有在禁忌表中的城市,转移概率表达式为

(1)

信息素τij会以一定的方式更新,其表达式为

(2)

(3)

其中LK表示一次旅游结束后蚂蚁k目前访问的总路径长度,Q是常量.

2 蚁群算法的改进

2.1 启发式因子的改进

基本蚁群算法以邻近节点路径最短的原理选取下一个节点,即为一个城市离蚂蚁所在地越近,则蚂蚁就会以较大的概率选择该城市.然而,在这个过程中,蚂蚁以该原理选择的两步路径之间的距离长度不一定是最小的,并通过正反馈使得该误差值进一步放大,从而导致蚂蚁向错误的方向寻找,对整个算法性能造成影响.也就是说蚂蚁从上一个城市以最短路径选择下一个城市,步步如此,最后选择的路径不一定是最优路径,这样最终的路径长度总和不一定最小.如图1所示,假定从A点出发,要求到达D点.ACD为最短路径,然而,蚂蚁按照邻近节点路径最短的选择规则,以较大的概率选择下一节点B,所以蚂蚁所走路径为ABD,而路径ABD的路径长度6大于路径ACD的路径长度4.5.

通过上面的例子可以看出,蚁群算法以相邻的两个节点(即一步)路径最短的原理选取下一个节点,得到的结果不一定是最优的,因此考虑三个节点(即两步)之间的路径距离,且利用这一策略对启发式因子进行改进,按照式(1)中距离越大,启发式因子越小,转移概率越小的原则,改进如下:

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

(4)

其中ηij为启发式因子,di，j表示节点i与节点j之间的距离长度.节点j按照式(5)选取:

(5)

其中节点j是从节点i要选取的下一个节点,节点j+1是从节点j要选取的下一个节点,k是任意节点,D表示完全图的赋权邻接矩阵,则D(i,j)表示节点i与节点j之间的距离,R=tabu.

基本蚁群算法的启发式因子是由一步节点之间的距离界定的,一步距离越小,启发式因子越大,则选择该一步路径概率越大;改进后的启发式因子是由两步节点之间的距离决定的,两步之间距离越小则启发式因子越大,则选择该路径的概率就越大.基本蚁群算法完成一步之后,再搜寻第二步,而且这种分离式的两步距离之和不一定是最短的,如图1所示.蚂蚁在搜索初期,各条路径上的信息素量是一样的,对蚂蚁诱导作用不是很大,而主要以启发式因子值为导向进行搜索,与基本蚁群算法相比,改进后的算法采用两步距离策略更有全局性,因此在搜索初期进行比较,改进蚁群算法将会得到比基本蚁群算法较优的路径.在图2中,迭代初期,改进蚁群算法得到的路径长度小于基本蚁群算法得到的路径长度,从而可以从启发式因子的角度有效避免分离式两步距离不是最短的缺点.

2.2 禁忌表中节点顺序调整

在蚁群算法中,蚂蚁按照概率选择公式去选择下一个节点,并将选择的这个节点添加到禁忌表tabu中,在此过程中选择概率是按邻近节点路径最短的原理选取下一个节点的,文中通过2.1的改进,采用两步节点最短路径策略选取下一个节点的方法来影响转移概率.当蚂蚁遍历所有节点之后,将所有节点全部添加到禁忌表tabu中,然后按照禁忌表tabu中的顺序来计算最短距离,然而按此时禁忌表tabu中节点的顺序计算出的距离不一定是全局最短距离,因为选择概率是由启发式因子和信息素共同决定的,在蚂蚁搜寻后期路径上的信息素量会越来越大,从而降低了启发式因子对选择概率的影响,如果在之前有蚂蚁搜寻到非最优路径,则后来蚂蚁也会按照这条路径搜寻,导致搜寻得到的结果不是全局最优值.所以文中考虑用(6)式进行调整禁忌表tabu中节点的顺序.

(6)

其中R=tabu,L记录本次迭代最佳路线,L(i)表示从起点到节点i的路线长度,D(R(i),R(j))表示禁忌表中节点i和节点j之间的距离.

2.3 改进的蚁群算法步骤

根据以上的改进思路,改进后的算法实现步骤如下：

Step 1 初始化蚁群算法中的参数α,β,ρ,Q,NC_max,m,设置迭代计数器初始值NC=1;

Step 2 随机选择每只蚂蚁的初始位置,初始化禁忌表tabu,按式(4)计算启发因子;

Step 3 m只蚂蚁按概率函数式(1)选择下一座城市,将所选城市节点添加到tabu中;

Step 4 若禁忌表tabu未满转至Step 3,若已满,得出蚂蚁此次的最优路径长度LNC,并且更新Lbest的值;

Step 5 按照式(6)调整节点之间的顺序,记录本次迭代最佳路线;

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

Step 7 判断迭代次数是否满足条件NC

Step 8 算法结束,输出最优路径长度Lbest.

3 改进蚁群算法在旅游路线优化中的应用

在Windows 7环境下,运用Matlab7.0语言进行编程,采用TSPLIB中的Benchmark31、Att48、kroA100、Pr136、tsp225问题,对旅游路线进行优化和仿真.首先将基本蚁群算法和改进后的蚁群算法对其进行求解,各运行10次,结果如表1所示,迭代图如图2所示.然后将Benchmark31单独运行10次,结果如表2、图3～4所示;最后将Att48、Eil51问题运行结果与其他算法进行比较,结果如表3～4,图5～6所示．算法参数选择如下:α=1,β=5,ρ=0.1,Q=100,取迭代次数200为终止条件,蚂蚁个数为31.

表 1 路线优化问题实验比较

通过比较表1中最优值和平均值发现,改进蚁群算法对于Benchmark31、Att48、kroA100、Pr136、tsp225问题的运行结果都优于基本蚁群算法的结果.

观察图2，在每个图中改进蚁群算法迭代曲线的最低位置总是低于基本蚁群算法迭代曲线的最低位置,表明改进蚁群算法总是可以收敛到比基本蚁群算法更优的结果.

在图3中,用基本蚁群算法求得该旅游线路的最短距离为15 602,最优解路径为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,最优解路径为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可以看出,基本蚁群算法最优路径长度为15 602,平均路径长度为15 798;改进蚁群算法最优路径长度为15 398,平均路径长度为15 590.改进蚁群算法比基本蚁群算法能够找到更短的路径.

如图5所示,改进蚁群算法优化Att48 TSP问题得到的最优路径为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所示,改进蚁群算法优化Eil51 TSP问题得到的最优路径为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 结束语

路径优化问题是实际生活中一个重要的现实问题,文中采用两步节点最短路径策略选取下一个节点的方法,对蚁群算法路径选择进行改进,并对禁忌表中节点顺序进行调整,然后采用TSPLIB中的Benchmark31、Att48、kroA100、Pr136、tsp225问题进行仿真,并将改进蚁群算法运行Att48、Eil51的结果与其他算法运行结果进行比较.结果表明,在迭代次数小于100时得到Att48的最优路径长度为32 112,在迭代次数小于150时得到Eil51的最优路径长度为442.76,比其他算法的运行结果更优.因此改进蚁群算法可用于解决旅游路线优化问题.

[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] 张志协,曹阳.基于改进型蚁群算法的最优路径问题求解[J].计算机系统应用,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] 马良.全局优化的一种新方法[J].系统工程与电子技术,2000,22(9):61-63.

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

[8] 陈建军.蚁群算法在物流配送路径优化中的研究[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的自适应蚁群优化算法[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] 李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[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] 罗慧,蹇兴亮,卢伟.基于动态蚁群算法的模拟电路最优测点选择[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] 郑松,侯迪波,周泽魁.动态调整选择策略的改进蚁群算法[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] 柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[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] 刘建华,杨建国,刘华平,等.基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机器学报,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] 孟晓琳,黄天民,陈尚云.基于信息素更新和挥发因子调整的改进蚁群算法[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].数学的实践与认识,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

张永强,王晓东.基于改进蚁群算法的旅游路线优化[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