引入基因簇求解TSP的遗传算法

Using Gene Clusters for TSP Solving Genetic Algorithm

在用遗传算法求解TSP时,极易破坏已经发现的较短线路片段,从而使遗传算法的收敛变慢。为了保护较短的线路片段,遗传操作以基因和基因簇为单位进行,优良基因簇可完整地遗传到下一代。在获得第一个近似最优解后,粉碎已发现的基因簇并继续寻优,以期能够获得全局最优解。使用CHN144及TSPLIB中的数据进行试验,找到了CHN144问题的当前最优路径。通过对TSP225的实验获得了最短路径3859,优于目前已经公布的最短路径3916。实验表明,基于基因簇的算法具备3000个城市左右的寻优能力。

When a genetic algorithm is used to solve the TSP （Traveling Salesman Problem）, shorter paths found before are accessible to be destroyed, and thus the convergence of the genetic algorithm slows down. To prevent the shorter paths from being destroyed, the gene cluster was introduced into genetic operations so that the superior gene piece can be wholly inherited to descendent off-springs. After a near optimum is found, all gene clusters are smashed and the optimum finding process is continued for global optimums. Experiments are done for CHN144 and instances in TSPLIB, in which the current optimal solution for CHN144 is found and a solution 3859 for TSP225 is found better than the best result 3916 up-to-date. Our experiments show that the gene cluster based genetic algorithm has the optimum searching ability for 3000-city-about TSPs.