针对旅行商问题的改进循环交叉算子遗传算法

Improved Cyclic Crossover Operator Genetic Algorithm for Traveling Salesman Problem

旅行商问题是现代计算机科学、工程、运筹学、离散数学、图论等领域的基础问题,利用遗传算法进行旅行商问题的求解相比于其他精确算法能够解决计算消耗的问题,但遗传算法易陷入局部最优的问题也较为明显.针对以上问题,对交叉算子进行改进,提出一种新的改进循环交叉算子,通过对两个子代分别进行交叉基因两次移动和一次移动,解决循环交叉算子中子代与父代相同的情况,并以TSPLAB实例为基础,通过与多种经典交叉算子对比,证明所提出的改进循环交叉算子具有良好性能,在绝大多数的实例中收敛精度有一定提升.

Traveling salesman problem,which is a basic problem in the fields of modern computer science,engineering,operations research,dis⁃crete mathematics,graph theory,etc.The use of genetic algorithms to solve the traveling salesman problem can solve the problem of com⁃puting consumption compared to other precise algorithms,but genetic The problem that the algorithm is easy to fall into local optimum is also obvious.In view of the above problems,this paper improves the crossover operator,and proposes a new improved cyclic crossover op⁃erator.By performing two crossover gene movements and one move for the two offsprings,respectively,the cyclic crossover operator seed and the parent are solved.In the same situation,and based on TSPLAB examples,by comparing with a variety of classic crossover opera⁃tors,it is proved that the improved cyclic crossover operator proposed in this paper has good performance,and in some cases,the conver⁃gence accuracy is improved.