一种双近邻表示的演化算法解决TSP

A 2-Adjacency Representation in Evolutionary Algorithm for Traveling Salesman Problems

用演化算法解决旅行商问题(TSP)时,传统的路径表示方法是非常不适合演化过程处理的。提出了一种双近邻表示法。这种能够将每个路径唯一表示的新的方法提高了演化算子的继承能力。为了提高收敛速度,演化算子中还使用了一种混合的局部搜索。大量的标准测试题的实验结果可以表明该文提出的算法能够全部达到或更优于现存最优解。

When solving Traveling Salesman Problems with evolutionary algorithm, the traditional routing representations were not considerably appropriate for evolutionary processing, and would depress the global efficiency of the performance. A 2- adjacency representation was presented in this paper. The new representation which was exclusive for each routing improved the heritability of genetic operators. A hybrid local search was also applied to genetic operators in order to speed up the convergence. The experimental results showed that the proposed scheme was obviously able to compete with the existing optimal results in many standard benchmark problems, some of them were even better.