基于路径共同顺序的TSP遗传算法

A Genetic Algorithm Based on Common Path for TSP

遗传算法是一种解决TSP问题的有效算法。文章提出了一种基于路径共同顺序的新型遗传操作方法,即首先寻找父辈的共有路径信息,然后构建后代,该方法缩小了搜索优解的范围,加快了优化过程的收敛速度。在此基础上针对TSP实例,实现了基于共同顺序的优化方法来解决小规模TSP问题,以及更有效的基于共同顺序的循环优化方法来解决大规模TSP问题。实验结果验证了该方法的有效性。

Genetic algorithm is a promising approach for solving Traveling Salesman Problem(TSP).This paper presents an original GA operator that first finds the common path of two parent paths and then constructs the child paths.This approach constructs offspring based on common path,decreases the search space of optima and accelerates optimal con-vergent rate.For TSP problems ,first an optimal method based on common path for TSP of small scale is given,then a more efficient method based on common path with loop optimization for TSP of large scale is given.Experiment analysis proves its efficacy.