混合遗传模拟退火算法求解旅游线路优化问题
2018-01-05黄华升张波
黄华升+张波



摘 要:广西旅游资源丰富,对出行线路的规划可以能让旅游线路更为优化合理。本文以广西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]。……
