一种解决TSP的改进遗传算法

• 作 者: 巩固 胡晓婷 郝国生 黄永清
• 机 构: 徐州师范大学计算机科学与技术学院,中国矿业大学信息与电气工程学院
• 出 处: 计算机应用与软件
• 发表日期: 2009年04期
• 关键词: TSP 遗传算法 最小邻域接入 最短路径 TSP Genetic algorithm Connecting based on minimum circle（CB

旅行推销员问题TSP(Traveling Salesman Problem)问题是组合优化中的经典NP难题,一些典型的遗传算法(GA)在求解TSP问题时的性能并不理想。提出基于"最小邻域接入法"CBMC(Connecting Based on Minimum Circle)思想的改进的遗传算法,并在算法中增加一些控制策略,与其他算法相比,获得了更好的性能和收敛速度。通过用中国33个省会的TSP问题对提出算法进行实验验证,结果证明了改进后的算法在收敛速度和收敛到最优解的概率都优于其他遗传算法。