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

摘要：

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

关键词：遗传算法、旅行商问题、候选表、交配算子、邻接边、距离

所属期刊栏目：8

分类号：TP18(自动化基础理论)

资助基金：大理学院科研基金资助项目2006X38

在线出版日期：2009-06-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：5-8