| 一种解决TSP的改进遗传算法 |
| |
| 引用本文： | 巩固,胡晓婷,郝国生,黄永清.一种解决TSP的改进遗传算法[J].计算机应用与软件,2009,26(4). |
| |
| 作者姓名： | 巩固 胡晓婷 郝国生 黄永清 |
| |
| 作者单位： | 1. 徐州师范大学计算机科学与技术学院,江苏,徐州,221116
2. 中国矿业大学信息与电气工程学院,江苏,徐州,221008 |
| |
| 基金项目： | 江苏省高校自然科学基金基础研究项目 |
| |
| 摘 要： | 旅行推销员问题TSP(Traveling Salesman Problem)问题是组合优化中的经典NP难题,一些典型的遗传算法(GA)在求解TSP问题时的性能并不理想.提出基于"最小邻域接入法"CBMC(Connecting Based on Minimum Circle)思想的改进的遗传算法,并在算法中增加一些控制策略,与其他算法相比,获得了更好的性能和收敛速度.通过用中国33个省会的TSP问题对提出算法进行实验验证,结果证明了改进后的算法在收敛速度和收敛到最优解的概率都优于其他遗传算法.
|
| 关 键 词： | 遗传算法 最小邻域接入 最短路径 |
AN IMPROVED GENETIC ALGORITHM FOR TRAVELING SALESMAN PROBLEM |
| |
| Gong Gu,Hu Xiaoting,Hao Guosheng,Huang Yongqing.AN IMPROVED GENETIC ALGORITHM FOR TRAVELING SALESMAN PROBLEM[J].Computer Applications and Software,2009,26(4). |
| |
| Authors: | Gong Gu Hu Xiaoting Hao Guosheng Huang Yongqing |
| |
| Affiliation: | College of Computer Science and Technology;Xuzhou Normal University;Xuzhou 221116;Jiangsu;China;College of Information and Electronic Engineering;China University of Mining and Technology;Xuzhou 221008;China |
| |
| Abstract: | Travelling salesman problem(TSP) is a well-known classical NP complete problem in Combination Optimization,and some typical genetic algorithm(GA) algorithms are quite unsatisfied in solving it.The paper puts forward a new solution of the improved GA using the idea of connecting based on minimum circle(CBMC),and some controlling strategies are added to the new algorithm.Comparing with other GA algorithms for the TSP,the new algorithm performs better with faster convergence.The experimental validation for the... |
| |
| Keywords: | TSP |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
