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

Using Gene Clusters for Solving TSP in a Peer to Peer Genetic Algorithm

应用遗传算法求解旅行商问题时,极易破坏已经发现的较短线路片段.为此,引入基因簇以便保护较短的线路片段,基于P2P设计了TSP求解遗传算法P2PTSPGA.在交叉和变异操作的过程中,基因簇完整地遗传到下一代;在获得第一个近优解后粉碎基因簇,以避免算法陷入局部最优.使用CHN144找到了当前最优路径,并使用TSPLIB进行了串行和并行试验.TSP225实验获得了最短环路路径3859,优于目前已经公布的结果3916.实验表明,P2PTSPGA具有较高的求解性能,并具备5000左右城市的持续寻优能力.

When a genetic algorithm is used to solve a TSP （ Traveling Salesman Problem ）, it is very possible of destroying shorter paths found before. While the gene clusters are introduced to protect shorter paths mentioned above, this paper presents a P2P based TSP solving genetic algorithm P2FTSPGA. The gene clusters are totally past down to their offspring of the chromosomes during the genetic operations, and are smashed after the first near optimum is found in order to prevent from falling into a local optimum. In the experiments for CHN144 and for instances in TSPLIB, the current optimal solution is found for CHN144 by our P2PTSPGA, and the solution 3859 for TSP225 is found better than the up-to-date best result 3916. Our experiments show that the P2PTSPGA has a high performance in solving TSPs and own an ability of searching optimal tours for 5000-city TSPs.