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

周茂杰，张翠

（1.桂林理工大学，桂林 541004；2.桂林理工大学博文管理学院，桂林 541004）

0 引言

近年来，国家对旅游信息化发展高度重视，相继出台了《关于促进智慧旅游发展的指导意见》、《关于实施“旅游+互联网”行动计划的通知》、《关于促进旅游业与信息化融合发展的若干意见》等一系列重大政策，利用通讯、信息技术与旅游业的结合，建立智慧旅游产业。随着人们的生活水平不断提高，旅游成为人民幸福生活新指标，随着旅游消费升级，游客更需要个性化的旅游产品。在信息化时代，游客需要更加丰富、多元的旅游服务信息，在外出旅游时，通过各类数据信息进行自主选择意识也不断增强[1]。对于游客而言，合理、舒适、节约的旅游线路是提升旅行体验的重要标准。智能线路规划可以为游客推荐合理的个性化旅游线路，既节约时间，又减少花销，可以改善旅游体验，提升旅游目的地的形象，对促进当地旅游业的可持续发展，实现旅游服务智慧化具有重要意义。

旅游线路规划要考虑交通网络、个人喜好、时间成本和金钱成本等因素。首先，游客可以在各类网站查询到各类景点及景点间的可达线路，然后，要确定在各景点间的游览顺序、游览时间，在两点间选择和某种交通方式出行。旅游线路规划系统要为游客提供个性化的旅游线路，并对出游时间进行合理安排，根据现有条件，设计出游客的旅游费用支出、时间花费较少的线路，是一个在多个约束条件下的组合优化问题，本文拟采用蚁群算法解决此问题，并对蚁群算法进行改进，达到路径选择的优化效果。

1 蚁群算法原理

20世纪90年代初期，意大利学者M.Dorigo，V.Ma⁃niezzo等人首次提出蚁群算法（Ant Colony Algorithm，缩写为ACO）。蚁群算法是一种仿生进化算法，具有种群的启发功能，专家们通过模拟自然界中真实蚁群集体觅食行为得到本算法[2-3]。

单个蚂蚁选择路径具有随机性，但蚁群中的蚂蚁根据一种称之为信息素的指示信息从巢穴到食物源寻找到最短路径[4-6]。一群蚂蚁寻找食物源时，一只蚂蚁走过某条路时会在经过的路留下信息素，后面的蚂蚁可以感知信息素，并根据信息的浓度大小，在所有可以到达食物源的路径中逐个比较，最后选择一条最短路径，同时在自己走过时也释放信息素。具体的方法是：对比两点间各条可达路径上的信息素的浓度，当某条路径的信息素浓度比其他的路径的信息素浓度都要大时，蚂蚁选择这条路径的概率就大，反之蚂蚁选择信息素浓度小的路径概率就小。同时，蚂蚁在走过某条路时会再次留下信息素，所有的信息素会随着时间的推移不断挥发，这样一来，蚂蚁选择信息素浓度大的路径的概率大，走的蚂蚁数量多了后留下的信息素也有所增大。信息素浓度小的路径蚂蚁选择的概率小，所以走过此路径的蚂蚁数量少，留下的信息也在减少，随着信息素的不断挥发，蚂蚁选择此路径的概率越来越小。经过多次迭代，蚂蚁依据信息素浓度选择，最后可以选择出一条最短路径，实现线路的优化选择。

蚁群算法的原理是根据信息素的浓度进行路经选择。首先，在n个城市里随机放置m只蚂蚁，位于某个城市i的第k只蚂蚁选择下一个城市j的概率为Pk（i,j），可以表示为：

其中：

τ(i,j)是两个城市i和j间信息素浓度，概率与信息度成正比；

η(i,j)=1/d(i,j)是一个启发信息，d（i,j）表示城市 i和j间的距离，启发信息与两点间距离成反比；

α和β为信息启发因子，反映了信息素与启发信息的重要性；

tabuk表示蚂蚁k已经访问过的城市列表，也称之为禁忌列表。

蚂蚁按照概率选择的方法选择路径对所有城市进行遍历，完成遍历后，需要按照信息的增加及挥发进行更新，更新方法如公式（2）所示。

其中：ρ为小于1的常数，表示信息素的持久性因子，（1-ρ）表示挥发因子，Δτij表示本次蚂蚁走过本路径留下的信息素，下一次遍历的信息素浓度为本次增加量与上一次挥发后的剩余量之和。

其中：Q为一个常数，可以对其进行设置；Lk表示第k只蚂蚁在本次迭代中走过的路径长度，那么信息素的浓度就与路径的蚂蚁走过的路径成反比。

2 蚁群算法改进

蚁群算法系统可以用式（1）和式（2）表示，在式中可以看出算法的性能会受到启发因子α、信息素浓度τ(i,j)、启发式因子β、局部更新信息素的持久性因子ρ等等影响，算法的收敛性也会受到各参数组合的影响。参数ρ表示信息素的持久性因子，同时也反映了挥发率。信息素的更新采用了正反馈机制，容易造成一种信息素累积，导致算法陷入局部最优解。

本文针对蚁群算法存在着收敛速度慢、容易陷入局部最优的缺陷，对算法进行改进。信息素持久性因子ρ的大小可以影响到蚁群算法的全局搜索能力，同时，也可以影响到算法的收敛速度，所以ρ不宜过大或者过小，要根据实际情况适时改变；在公式（3）中，Q是一个常数，表示信息素强度，Lk表示第k只蚂蚁在本次对路径的遍历中所走过的总长度。从公式（3）可以看出，蚂蚁所走的某次遍历中走过的路径越短，即LK越小，越大，说明这只蚂蚁在路上留下的信息素也就越多，所有的信息素叠加后，得到Δτij也就越大，最终得到的pij也就越大，说明后续蚂蚁经过这条路径的概率越大。本文要根据LK的作用进行算法的改进，针对LK只考虑了第K只蚂蚁走过的路径长度的问题，对前K-1只蚂蚁所走的路径进行综合比较后，进行加权后计算信息素浓度，增加全局影响因素。

首先，假设最优路径一般都会在较短路径中得到，所以增加较短路径的影响力。蚂蚁k走过全程以后，在信息素更新前，先和平均路径总长度进行比较，如果说明这一只蚂蚁所走路径劣于前K-1只蚂蚁走过路径的平均值，在最优路径上的可能性较小，蚂蚁留下的信息素应相应减小，使得此路径的选择概率减小；反之，如果Lk＜Laverage，说明这一只蚂蚁走过的路径优于前K-1只蚂蚁走过路径的平均值，在最优路径上的可能性增加，蚂蚁留下的信息素相应增加，从而使得该路径选择概率变大，加快寻优速度，同时考虑了全局最优性，减小了局部最优的可能性。具体的方是在计算第K只蚂蚁的信息素时，即计算在Δτkij时，加入影响因子λ，计算公式如式（4）所示，令对Lk加权后，增加走过全局短路径的影响力，增加了算法全局最优性表现。本文算法图1所示。

图1 本文算法流程图

3 实验及结果分析

为了验证改进行蚁群算法的有效性和收敛性，根据上一节和蚁群算法设计流程，在Windows7系统下，用MATLAB R2015a软件进行仿真实验，实验数据采用30城市TSP标准数据库，对算法的初始值设置如表1所示。

表1 算法的参数设置

对30城市TSP问题加以测试，用传统ACO算法与本文算法计算最优路径，对于不同的迭代次数得到最短路径长度果，如图2所示，在相同的迭代次数条件下，本文算法所得到的最短距离比传统ACO算法要小，而且在150次迭代与200次迭代的结果相同，算法趋于收敛，所以本文算法收敛的速度要快。本算法在200次迭代时所得的最优路径如图3所示。

图2 ACO算法与本文算法测试结果对比

图3 本文算法在200次迭代时得到的最优路径

4 结语

本文分析了旅游线路问题，并建立数学模型，在线路规划时采用蚁群算法，并且对基于蚁群算法的旅游线路规划算法进行改进。首先对ACO蚁群算法进行了分析，然后基于ACO算法进行了改进设计。改进算法在信息素更新前，先和平均路径总长度进行比较，如果大于平均路径，说明该蚂蚁走过的路径不是最短的；反之，说明该只蚂蚁走过的路径优于前次，从而使得该路径转移概率变大，加快寻优速度。将本算法在MATLAB开发平台上实现算法进行仿真实验，得到的最优路径优于ACO算法。实验结果验证了该旅游线路规划算法的可行性和有效性。

[1]张凌云.智慧旅游:个性化定制和智能化公共服务时代的来临[J].旅游学刊2012,27（2）:3-5.

[2]Colomi A,Dorigo M,Maniezzo V.Didtributed Optimization by Ant Colonies[C].Proc of the First European Conference of Artificial Life.Paris:Elsevier Publishing,1991.

[3]Dorigo M,Ganbardella L M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Trans on Evolutionary Computation,1997,1（1）:53-66.

[4]张学敏,张航.基于改进蚁群算法的最短路径问题研究[J].自动化技术与研究,2009（6）:4-7.

[5]李士勇.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.

[6]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.

[7]孙力娟.改进的蚁群算法及其在TSP中的应用研究[J].通信学报，2004,25（10）:111-116.

[8]吴华锋,陈信强，毛奇凰.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报，2013，34（4）：165-170.

[9]姜坤霖,李美安，张宏伟.面向旅行商问题的蚁群算法改进[J].计算机应用，2015，35（S2）:114-117.

[10]张永刚，张思博，薛秋实.求解约束满足问题的改进蚁群优化算法[J].通信学报，2013，34（4）：1-7.