混合遗传模拟退火算法求解旅游线路优化问题

黄华升+张波

摘 要：广西旅游资源丰富，对出行线路的规划可以能让旅游线路更为优化合理。本文以广西30个城市的旅游线路优化问题构造TSP问题，分析了遗传算法和模拟退火算法的优缺点。利用两种算法的互补性，构造了混合遗传模拟退火算法，指出三种算法对旅游线路的求解算法过程。通过对实验数据的对比分析，得出了混合遗传模拟退火算法在求解精度上优于遗传算法或模拟退火算法。

关键词：混合遗传模拟退火算法；旅游线路优化；TSP问题

中图分类号：TP399 文献标识码：A

Abstract：Due to the abundant tourism resources in Guangxi，reasonable route planning can effectively optimize the travel schedule.The paper constructs TSP problems of tourist route optimization for 30 cities in Guangxi province.The paper analyzes the advantages and disadvantages of the genetic algorithm and the simulated annealing algorithm.Making use of the complementarity of the two algorithms，the paper constructs a hybrid genetic simulated annealing algorithm，and proposes the solution procedures of tourist route optimization with the three algorithms.Through the comparative analysis of experimental data，it is concluded that the hybrid genetic simulated annealing algorithm is superior to the genetic algorithm and the simulated annealing algorithm in solution accuracy.

Keywords：the hybrid genetic simulated annealing algorithm；tourist route optimization；TSP problems

1 引言（Introduction）

遺传算法是一种通过模拟自然进化过程如适者生存、优胜劣汰遗传机制而来的搜索最优解的启发式算法。遗传算法适应能力强，但是存在着“早熟”的问题，也就是空间的探索能力有限，很容易收敛到局部最优解，无法达到全局最优。模拟退火算法也是一种随机寻优智能算法，其借助金属固体退火过程的原理，设定高的初温度，采用Meteropolis接受准则，以一定的温度参数不断降低温度，能有效避免陷入局部极小，得出一个近似最优解。但模拟退火算法也有收敛速度慢、执行时间长等问题。遗传算法和模拟退火算法具有较强的互补性，将两种算法组合在一起发挥各自优势，避免缺陷，就形成了混合模拟退火遗传算法，简称MGASA[1-3]。

2 广西旅游线路优化问题（Optimization of tourist

routes in Guangxi）

广西旅游资源丰富，要实现浏览一遍广西所有旅游资源需要合理安排旅游线路。广西旅游线路优化就是选取广西的30个城市浏览一遍，要求每个城市有且仅经过一次，这样的一条旅游的最短路线就是我们的优化目标[4]。这个问题的实质就是构造广西旅游线路优化的TSP问题。广西30个旅游城市的坐标见表1。

TSP问题是比较典型的组合优化问题，求解方法主要有线性规划法、分支定界法、遗传算法和模拟退火算法等。但这些常规的算法往往存在一些弊端，本文使用混合模拟退火遗传算法，通过对比实验的方式来求广西的30个城市的旅游线路最优解。

3 算法比较（Algorithm comparison）

3.1 遗传算法求解旅游线路优化问题

遗传算法是搜索最优解的启发式算法，使用遗传算法求广西旅游线路过程描述如下：

步骤1初始化种群：设置染色体长度n，初始化种群的规模nind。

步骤2适应度函数计算。

步骤3选择操作：选择适应度高的染色体。

步骤4交叉操作：采用部分映射杂交，确定交叉操作的父代，将父代样本两两分组为p1和p2，每组重复如下操作。第一，产生[1，30]区间内的随机整数p1和p2，确定两个位置，对两个位置的中间数据进行交叉。第二，交叉后，同一个个体中有重复的城市编号，不重复的数字保留，有冲突的数字利用中间段的对应关系进行映射的方法消除冲突。

步骤5变异操作：随机选取两个点，将其对换位置。产生[1，30]范围内的随机整数r1和r2，确定两个位置，将其对换位置。

步骤6进化逆转操作：产生两个[1，30]区间的随机整数r1和r2，确定两个位置，将其对换位置。

步骤7检查判断是否满足设定的最大遗传代数MAXGEN，不满足则跳入适应度值的计算；否则，结束遗传操作[5，6]。

实验的初始变量交叉概率为0.9，变异概率为0.05，代沟为0.9，分组后得到的最短路径为：25.267。最短路径是[1 9 2221 29 26 5 20 8 17 23 24 27 3 16 28 14 11 30 2 13 7 15 25 12 19 4 6 10 181]。路径如图1所示。

3.2 模拟退火算法求解旅游线路优化问题

模拟退火算法是模拟固态物体降温过程，解决一般组合优化问题的优化算法。基于模拟退火算法的TSP问题求解具体步骤如下：

步骤1设置算法参数：初始温度T0，降温系数q，结束温度Tend和链长L；设置代数计数器初始化，t=0。

步骤2初始解：使用randperm函数产生随机初始线路。

步骤3解变换生成新解：采用产生随机数的方法产生两个要交换的城市，用二领域变换法产生新的路径，确定新的可行解S'。

步骤4Metropolis准则：计算增量Δt'=C（S'）-C（S），其中C（S）为评价函数。根据Metropolis准则，如果增量Δt'<0，则以S'接受新的路径；如果Δt'>=0，则以概率exp（-Δt'/T）接受新的路径。

步骤5降温：如果满足终止条件，则输出当前解作为最优解，结束程序。否则转步骤3继续迭代。

实验参数设置为降温速率0.9，初始问题1000，结束温度0.001，链长200，最后最短路程为：26.1658。最短路径是[[1 18 10 6 4 19 7 13 2 23 324 27 28 16 30 14 11 25 12 15 17 8 20 5 26 29 21 22 9 1]。路径如图2所示。

3.3 混合遗传模拟退火算法求解旅游线路优化问题

遗传算法的优点是快速随机的搜索能力，缺点是容易“早熟”，局部搜索能力较差；而模拟退火算法的优点是具有较强的局部搜索能力。因此将模拟退火算法和遗传算法结合起来，取长补短就能形成更为合理的优化问题的优化算法，这就是混合遗传模拟退火算法。使用混合遗传模拟退火算法求解广西旅游线路优化的方法过程描述如下：

步骤l初始化：设置种群F（k）的初始值，设置初始退火温度t0，设置降温系数a等；设置代数计数器初始化，t=0。

步骤2随机产生初始群体F（k）的适应度。

步骤3计算F（k）中个体的适应度，执行个体交叉操作，采用淘汰算法进行最优个体保存，到新的群体Fl（k）。

步骤4执行个体变异操作，得到新的群体F2（k）。

步骤5采用模拟退火规则产生新的种群。

步骤6执行个体的模拟退火操作得到F3（k）。

步骤7判断模拟退火抽样是否稳定，如果不稳定，返回步骤5；如果稳定，继续执行退温操作。

步骤8个体的选择复制操作，F（k+1）=Re_Produce[F（k）F3（k）]。

步骤9如果满足终止条件，输出当前最优解，结束程序；否则k=k+l，转步骤2，继续进化过程[7，8]。

实验设置初始种群规模为50，终止温度为1，降温系数为0.5，初始温度为70，最后最短路程为：23.9795。最短路径是[1 9 22 21 29 26 5 20 8 17 2324 27 3 1628 14 1130 2 13 7 15 25 12 19 4 6 10 18 1]。路径如图3所示。

3.4 实验分析

将每种算法进行10次计算，最后结果数据对比见表2。

由实验数据对比可以看出，使用混合遗传模拟退火算法计算的最佳解、最差解及平均解在三种算法中都是最小，平均进化代数也是最小的，因此使用混合遗传模拟退火算法是能有效提高对线路优化问解的求解精确度。

4 结论（Conclusion）

本文分别使用遗传算法、模拟退火算法、混合遗传模拟退火算法三种算法对旅游线路的优化问题进行计算，从数据的对比分析来看，混合遗传模拟退火算法能够较快地收敛并获得全局最优解，在精准度上比单一的遗传算法和模拟退火算法要高。下一步还需要继续探究混合遗传模拟退火算法中的参数设置对算法性能的影响，找出参数与求解旅游线路优化之间的逻辑联系，以获得更优的精度解。

参考文献（References）

[1] 刘锦.混合遗传算法和模拟退火算法在TSP中的应用研究[D].广州：华南理工大学，2014：30-53.

[2] 崔穎.排水管道设计优化的遗传与模拟退火混合算法研究[D].重庆：重庆大学，2009：39-43.

[3] 丁书斌.基于混合遗传算法的车间调度方法研究与应用[D].大连：大连理工大学，2006：23-32.

[4] 姚君.遗传模拟退火算法——黑龙江TSP问题[J].价值工程，2016，35（36）：206-208.

[5] 郁磊，史峰，王辉，等.MATLAB智能算法30个案例分析[M].北京：北京航空航天大学出版社，2010：38-187.

[6] 曹小凤.基于遗传算法的药物疗效评价模型研究[J].软件工程，2017，20（05）：39-42.

[7] 刘怀亮，刘淼.一种混合遗传模拟退火算法及其应用[J].广州大学学报（自然科学版），2005（02）：141-145.

[8] 乔彦平，张骏.基于一种改进遗传模拟退火算法的TSP求解[J].计算机仿真，2009，26（05）：205-208.

作者简介：

黄华升（1978-），男，硕士，高级工程师.研究领域：软件开发.

张 波（1983-），男，硕士，讲师.研究领域：自然语言处理.