蚁群系统求解TSP问题的性能分析  

PERFORMANCE ANALYSIS ON ANT COLONY SYSTEM FOR SOLVING TSP

作　　者：劳眷[1,2] 林亚平[2] 伍超奎[1,2] 

机构地区：[1]广西大学计算机与电子信息学院,广西南宁530004 [2]湖南大学计算机与通信学院,湖南长沙410082

出　　处：《计算机应用与软件》2009年第2期270-271,282,共3页Computer Applications and Software

摘　　要：TSP问题是组合优化中经典的问题,蚁群系统是求解TSP问题诸多算法中取得较好性能的一种启发式算法。从运行时间分布和解的性能分布角度对算法求解TSP的性能进行了分析,得出了一些有实际指导意义的结论:算法找到最优解的概率是随着运行时间的增加而增大的;算法运行前期改进解的性能速度较快,但后期明显减慢;可以通过重启策略获得与最优解距离在一定范围内的解。The Travelling Salesman Problem （TSP） is one of the classical problems in combinational optimization. Ant colony system （ACS） is one of the efficient meta-heuristics algorithm for solving the TSP. This paper gives the performance analysis on ant colony system for solving TSP through the running time distributions of ACS and the solution performance distributions of ACS, obtains some practical conclusions that may give guidance to solving the TSP：The probability of finding best solution is increasing as the running time becomes longer; the speed of improving solution is fast in earlier stage but becomes slow evidently in later stage; it can reduce the running time and increase the probability of obtaining best solution by way of restarting the algorithm.

关 键 词：蚁群系统 运行时间分布 解的性能分布 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O224[自动化与计算机技术—计算机科学与技术]