蚁群和遗传算法在旅行路线规划中的研究

陈春燕，彭阳，许环梓，何宇佳，石苗

蚁群和遗传算法在旅行路线规划中的研究

陈春燕，彭阳，许环梓，何宇佳，石苗

（湘南学院 数学与金融学院，湖南 郴州 423000）

随着国家经济迅速的发展，旅游成为了大部分人生活中必不可少的部分，经济式出行旅游规划中最重要的是最优路线的选择．以郴州旅游行业为研究背景，把旅行最优路线规划问题看成旅行商问题，建立蚁群算法和遗传算法模型．通过使用Matlab软件研究旅行问题，找出最优路线，并且通过比较选择出更合适的一种算法来解决商业上路线的问题．旅游行业可以通过使用这个最优算法建立一个智能旅游出行规划系统，来弥补旅游市场行程规划系统的缺陷，为游客提供最为经济、便利的旅行规划．

最优路线规划；旅行商问题；蚁群算法；遗传算法

郴州有着“林邑郴州”“林中之城，休闲之都”的称号，其自然型、生态型旅游资源和历史文化资源丰富，地理位置优越，是中国优秀旅游城市．郴州的旅游业虽起步晚，但是发展较快，目前已经初步形成规模．

随着国家经济的迅速发展，旅游成为人们休闲生活的重要方式之一．出行的旅游规划就变得尤为重要．在旅游规划中，旅游路线的选择直接影响到旅行者在旅行中金钱消费和时间消费，所以在出行旅游的规划中选择最优的路线尤为重要．目前，出行旅游的路线多数是单一的路线，一天到一个景点，不能多个景点，耗费很多的时间和金钱，造成这样的结果主要归结于没有选择一条好的路线，现有的单一旅行路线已经不能满足市场大部分用户的需求，最优路线的选择对旅游市场的推广有着不可替代的作用．从郴州旅游现状看，由于地域差距较为突出，交通等基础设施较为落后，为郴州旅游业的发展带来了一定的影响．本文提出旅游出行最优路线问题，同时把旅游出行最优路线的选择问题看成旅行商问题来进行研究，研究旅行商问题的算法分别有线性规划法、蚁群算法[1]、贪心算法[2]、遗传算法[3]、动态规划法[4]、模拟退火法[5]等，本文从中选择蚁群算法和遗传算法对其进行研究．

1 TSP最优路线研究现状分析

TSP问题又称旅行商问题，是典型的所有非确定型多项式时间可解的判定问题，也是组合优化问题．早期的研究者使用分支定界法、线性规划法、动态规划法等精确的算法来进行研究，但是随着数量的增大，实现很复杂，这些算法也都无能为力．随后，许多国外研究者着重使用遗传算法、蚁群算法、模拟退火法、贪婪算法和神经网络等近似算法或者启发式算法．针对旅行商问题的算法主要是蚁群算法和遗传算法，这2种算法又称为智能算法．蚁群算法是模拟蚂蚁，根据蚂蚁分泌的信息素的浓度为依据来迭代搜索，遗传算法是依据适应度来迭代搜索．2种算法都有相同的群体特点，也同样有着收敛速度慢和迭代次数多的缺陷，对于这2点的缺陷，近年国内的学者对蚁群算法和遗传算法进行了优化[6]．这2种算法哪个更适合于旅行商问题中的最优路线，并且把这种算法应该于旅行商业上，这是我们需要研究的．

2 TSP的蚁群算法和遗传算法

旅行规划的最优路线问题看成旅行商问题，通过用Matlab智能算法（蚁群算法 遗传算法[7]）得出最优路线值．

2.1 蚁群算法

用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间．路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多，从而得出最优路线（即待优化问题的最优解）．

2.2 遗传算法

遗传操作是模拟生物基因遗传的做法[8]．在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度（适应度评估）施加一定的操作，从而实现优胜劣汰的进化过程．从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解．可以把这个思想转化为旅行商的思想，从而得出最优路线.

3 Matlab建立的最优路线模型和运行结果

3.1 Matlab 蚁群算法

算法理念：从郴州一个起点出发，每个景点均仅经过一次，最终回到起点的最优路线．

数学规划模型为：

建立数学模型

给出10个景点的坐标，蚂蚁为30，迭代次数200次，求出最优路线值和最优路线．

图1 蚁群算法的适应度进化曲线

蚁群算法所得的结果见图1，其纵坐标的目标函数值表示的是最优距离，即最短距离．从图1中可以看出，总共迭代了200次，蚁群算法迭代2次就可以达到最优解．

蚁群算法的平均距离和最短距离见图2．从图2可以看到最大距离与最短距离和不确定性的路况距离的波动性，从而让旅行者在选择适合的路径时考虑到不确定因素的影响．

蚁群算法在旅行商问题优化的结果见图3．从图3可以看到景点坐落的坐标点，把10个景点坐标按照输入从1~10排序，运行的结果可以得出最优路线．

最优路线为Shortest_Route = 4 5 6 7 8 9 10 2 3 1

最短距离为Shortest_Length = 2.690 7．

图2 蚁群算法的平均距离和最短距离

图3 蚁群算法在旅行商问题优化的结果

3.2 Matlab 遗传算法

数学规划模型：

给出10个景点的坐标（10个景点坐标与蚁群算法的坐标相同），初始种群为30，迭代次数200次，求出最优路线值和最优路线．

遗传算法的平均距离和最短距离见图4．从图4中可以看到遗传算法迭代多少次达到最优解，也可以知道在不确定因素下的最大距离．

遗传算法在旅行商问题优化的结果见图5．从图5可以看到遗传算法需迭代12次，才能达到最优函数值，其得到的最优路线与蚁群算法的相同．

最优路线为Shortest_Route =4 5 6 7 8 9 10 2 3 1

最短距离为Shortest_Length = 2.690 7．

图4 遗传算法所得的结果

图5 遗传算法在旅行商问题优化的结果

4 结语

蚁群算法和遗传算法都是智能随机算法[9-10]，从运行结果来看（图3与图5），最优路线和最优路线值是一致的[11}；从运行的速度来看（图1与图5），蚁群算法迭代的次数要小于遗传算法，所有蚁群算法的收敛速度要优于遗传算法；从最优路线的波动性来看（图2与图4），蚁群算法不确定因素下的最大距离要小于遗传算法，遗传算法的搜索能力要比蚁群算法强．综上所述，可以知道蚁群算法有较强的鲁棒性、并行求解质量好，同时也有较强的全局优化能力，收敛的速度也比遗传算法的要快．虽然遗传算法有比较强的全局搜索能力，但是从旅行商业角度来看，算法中迭代的次数越多，消费成本可能就越高，所以蚁群算法更适合旅行商业中解决旅游路线规划问题，可以考虑利用蚁群算法建立一个智能旅游出行规划系统，为游客提供最为合适的旅行路线．

[1] 刘中强，游晓明，刘升．一种启发式动态信息素更新策略的蚁群算法[J]．计算机工程与应用，2018（20）：20-27

[2] 毕龙阁．贪心算法和线性规划[J]．计算机产品与流通，2017（11）：239，251

[3] 胡士娟，鲁海燕，黄洋，等．求解工作量平衡多旅行商问题的改进遗传算法[J]．计算机工程与应用，2019（17）：150-155，231

[4] 吕丹，杨子寒，周君．动态规划算法在生活中的应用[J]．电脑知识与技术，2018，14（17）：253-255，268

[5] 冯玉蓉．模拟退火算法的研究及其应用[D]．昆明：昆明理工大学，2005

[6] 陈洋卓，李青青，罗天扬，等．基于遗传算法的TSP问题优化方法[J]．科技风，2019（1）：59-60

[7] 史小明．浅谈MATLAB下的遗传算法优化软件设计[J]．数学技术与应用，2019（1）：59-60

[8] 蒋然．改进遗传算法在TSP问题中的应用[J]．软件导刊，2016（12）：44-45

[9] 武海峰．基于Matlab的遗传算法程序设计探讨[J]．电脑迷，2017（1）：38-39

[10] 杜洋．遗传算法的原理及应用[J]．才智，2010（9）：49

[11] 陈少杰，麻莉娜．蚁群算法基本原理及综述[J]．科技创新与应用，2016（11）：62-64

Study on ant colony and genetic algorithm in traveling route planning

CHEN Chunyan，PENG Yang，XU Huanzi，HE Yujia，SHI Miao

（School of Mathematics and Finance，Xiangnan University，Chenzhou 423000，China）

With the rapid development of the national economy，travelling has become an indispensable part of most people′ s life．The most significant thing of economical travel plans is to choose the best route．Takes the Chenzhou tourist industry as background，comparing the best travel route planning to the traveling salesman problem（TSP）to find the best travel route by using Matlab to establish the model of ant colony optimization（ACO）and genetic algorithm（GA），and get the most suitable way to settle commercial routine issues．The tourist industry will establish a intelligent travel planning system to perfect the defect of the formal travel planning system and provide tourists with the most economical and convenient travel planning．

optimal route planning；traveling salesman problem（TSP）；ant colony optimization（ACO）；genetic algorithm（GA）

1007-9831（2020）07-0033-04

TP18

A

10.3969/j.issn.1007-9831.2020.07.008

2020-02-27

湘南学院2018年度校级大学生研究性学习和创新性项目（第29项）；2017年湘南学院校级教改项目（第31项）

陈春燕（1998-），女，湖南永州人，在读本科生．

石苗（1981-），女，湖南常德人，讲师，从事最优化算法研究．E-mail：jingui0531@126.com