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

Research on TSP Problem Based on Crossover and Mutation Combination

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

Genetic algorithm is a kind of random search algorithm based on natural selection and natural genetic mechanism,which is a relatively common algorithm for solving TSP problem.However,when the algorithm solves the TSP problem,there is a problem that the convergence speed is slow and easy to get premature.This paper proposes an algorithm design that combines five kinds of crossover algorithms and three kinds of mutation algorithms,then achieves15kinds of combination methods,and then uses Java language programming experiment,and finally through the Chinese144(CHN144),it is proved that the genetic algorithm combined with the THGA algorithm and the reverse order mutation algorithm can solve the traveling salesman problem by using the combination of the crossover algorithm and the mutation algorithm to achieve the best results.