基于交叉与变异组合的TSP问题研究

摘要：

遗传算法是一种在自然选择与遗传机制基础上的随机化的搜索类算法,是求解TSP(Travelling Salesman Problem)问题的一种常用算法.但是该算法在解决TSP问题时,存在着收敛速度过慢,容易出现早熟的问题.本文针对该问题,创新性地提出使用5种交叉算法和3种变异算法进行组合的算法设计,得出15种不同的组合方法,然后使用Java语言进行编程实验,最后通过对中国144个城市相对坐标(CHN144)的实例进行测试,证明了在使用交叉算法与变异算法进行组合得出的15种组合方法中,使用三交换交叉算法与逆序变异算法进行结合,这种组合方式的遗传算法在解决TSP这一问题时能够取得最优的效果.

关键词：遗传算法、TSP问题、三交换交叉、逆序变异

分类号：TP31(计算技术、计算机技术)

资助基金：吉林省科技发展计划项目20160307006 GX

在线出版日期：2018-04-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：54-59