一种改进的遗传算法求解TSP问题

An Improved Genetic Algorithms in Solving Traveling Salesman Problem

提出一种基于顶点的候选表进行交配的遗传算法(Candidate Crossover Genetic Algorithm,CCGA)求解旅行商问题(TSP)。遗传算法(GAs)是一种广泛使用的全局优化算法,并且已经成功地用于求解TSP。但是传统的遗传算法的交配算子缺乏指导性和启发性,交配算子随机的选择父体基因进行交配,导致GAs求解速度慢、解的精度不高等不足。通过分析TSP问题本身的特征,给出了一个使用已有的邻接边的信息和路径信息生成顶点的候选表,然后基于顶点的候选表进行交配的交配算子,使用该交配算子的遗传算法在求解TSP问题时性能上得到了很大的提高,通过TSP Lib上的测试样例将该CCGA和传统的遗传算法进行比较。比较结果表明CCGA具有更大的优势,它能使算法求解到近似最优解和最优解只存在很小的偏差。

This paper proposed a candidate crossover genetic algorithm （CCGA） to solve the traveling salesman problem （TSP）. GAs are widely used as optimized technology and has been applied to the TSP successfully. However,the traditional crossover methods in GAs lack heuristic guidance, and the crossover operator chooses parent gene randomly for crossing. This paper analyzed the characteristics of TSP and presented the best candidate table which can use the existing adjacent side and the information of the path and the crossover operator that was based on the best candidate table. Using this crossover operator, this genetic algorithm could greatly improve its performance when solving TSP. When compared with conventional GA using the test cases from the TSP lib, CCGA demonstrated greater advantages, for it not only got the best solution but also had the smallest deviation.