| 一种改进的求解TSP问题的演化算法 |
| |
| 引用本文： | 蔡之华,彭锦国,高伟,魏巍,康立山.一种改进的求解TSP问题的演化算法[J].计算机学报,2005,28(5):823-828. |
| |
| 作者姓名： | 蔡之华 彭锦国 高伟 魏巍 康立山 |
| |
| 作者单位： | 1. 中国地质大学计算机学院,武汉,430074
2. 中国地质大学计算机学院,武汉,430074;武汉大学软件工程国家重点实验室,武汉,430072 |
| |
| 基金项目： | 国家自然科学基金(60473081)，湖北省自然科学基金(2001ABB006,2003ABA043)资助.~~ |
| |
| 摘 要： | 演化算法是解决组合优化问题的高效搜索算法．该文在现有求解TSP问题的演化算法的基础上，通过引入映射算子、优化算子以及增加一些控制策略，提出了一种高效的演化搜索算法．实验表明，该算法是有效的，通过对CHN144以及国际通用的TSPLIB中不同城市规模的数据进行测试表明，其中实例CHN144得到的最短路径为30353．860997，优于吴斌等运用分段算法得到的最短路径30354．3，亦优于朱文兴等人的结果，实例st70和kroB150得到的最短路径分别与运用分段算法得到的最短路径值相同，实例pr136得到的最短路径值为96770．924122，优于TSPLIB中提供的最短路径96772，对于其它实例也均能快速地得到和TSPLIB中提供的最优路径相同或更优的路径，该算法不仅很容易收敛到问题的最优解，而且求解速度极快．
|
| 关 键 词： | 旅行商问题 演化算法 算子 |
An Improved Evolutionary Algorithm for the Traveling Salesman Problem |
| |
| CAI Zhi-Hua,PENG Jin-Guo,GAO Wei,WEI Wei,Kang Li-shan.An Improved Evolutionary Algorithm for the Traveling Salesman Problem[J].Chinese Journal of Computers,2005,28(5):823-828. |
| |
| Authors: | CAI Zhi-Hua PENG Jin-Guo GAO Wei WEI Wei Kang Li-shan |
| |
| Affiliation: | CAI Zhi-Hua~1) PENG Jin-Guo~1) GAO Wei~1) WEI Wei~1) KANG Li-Shan~1),2) ~1) |
| |
| Abstract: | TSP(Traveling Salesman Problem) is one of the typical NP-hard problems in combinational optimization, and evolutionary algorithm is a more efficient and more effective for solving combinational optimization problem. This paper gives two operators, mapping operator and optimal operator, then proposes some control strategies, finally proposes an improved evolutionary algorithm based on Guotao algorithm for solving TSP. First four TSP instances are used to test the algorithm, then some standard test-instances are tested. Especially, authors test the CHN144 (Chinese 144 cities). The result,30353.860997, outperforms those from existing literatures,30354.3(from Wu),30355.01(from Zhu). |
| |
| Keywords: | traveling salesman problem evolutionary algorithm operator |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
