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

摘要

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