求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析  

Analysis of the Run-Time Distribution and Solution Performance Distribution of Iterated Local Search for the TSP

作　　者：邹鹏[1] 周智[1] 江贺[1] 陈国良[1] 顾钧[1] 

机构地区：[1]中国科学技术大学计算机科学技术系国家高性能计算中心(合肥),合肥230027

出　　处：《计算机学报》2006年第1期92-99,共8页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(G1998030403)资助

摘　　要：旅行商问题(Traveling Salesm an Prob lem,TSP)是组合优化中最典型的NP难问题之一,长期以来人们都在寻求快速高效的近似算法以在合理的计算时间内准确地解决大规模问题,并设计出许多高效实用的启发式和宏启发式算法,其中循环LK算法是性能最好和最具代表性的算法之一.作者研究了该算法的运行时间分布:通过对TSPLIB中大量不同规模的TSP实例的运行时间分布的统计分析和拟合,发现求解TSP问题的循环LK算法的运行时间分布很好地服从W e ibu ll分布,并进一步给出了该分布对求解TSP问题的物理意义.作者同时首次给出了循环LK算法求解TSP问题得到的解的性能分布以及由此得到的一些有实际指导意义的结论.The Traveling Salesman Problem （TSP） is one of the most classical problems in combinatorial optimization. Many heuristics, as well as efficient meta-heuristics that followed, have been developed for the TSP. In this paper authors investigate the empirical run-time distributions （RTDs） of Iterated Lin-Kernighan algorithm, one of the state-of-the-art meta-heuristics algorithms for TSP, on a series of scalable TSP instances in TSPLIB. It has been shown that the resulted run-time distributions can be well approximated by Weibull distributions. Moreover, authors propose, for the first time, the solution performance distributions （SPDs） of iterated LK algorithm. By analyzing the characteristics of SPDs, authors obtain some practical conclusions that may give guidance to application design for the TSP.

关 键 词：旅行商 循环LK算法 运行时间分布 解的性能分布 WEIBULL分布 

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