一种改进的求解TSP问题的演化算法  

An Improved Evolutionary Algorithm for the Traveling Salesman Problem

作　　者：蔡之华[1] 彭锦国[1] 高伟[1] 魏巍[1] 康立山[1] 

机构地区：[1]中国地质大学计算机学院,武汉430074

出　　处：《计算机学报》2005年第5期823-828,共6页Chinese Journal of Computers

基　　金：国家自然科学基金(60473081);湖北省自然科学基金(2001ABB006;2003ABA043)资助.~~

摘　　要：演化算法是解决组合优化问题的高效搜索算法.该文在现有求解TSP问题的演化算法的基础上,通过引入映射算子、优化算子以及增加一些控制策略,提出了一种高效的演化搜索算法.实验表明,该算法是有效的,通过对CHN144以及国际通用的TSPLIB中不同城市规模的数据进行测试表明,其中实例CHN144得到的最短路径为30353.860997,优于吴斌等运用分段算法得到的最短路径30354.3,亦优于朱文兴等人的结果,实例st70和kroB150得到的最短路径分别与运用分段算法得到的最短路径值相同,实例pr136得到的最短路径值为96770.924122,优于TSPLIB中提供的最短路径96772,对于其它实例也均能快速地得到和TSPLIB中提供的最优路径相同或更优的路径,该算法不仅很容易收敛到问题的最优解,而且求解速度极快.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).

关 键 词：旅行商问题 演化算法 算子 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]