求解TSP问题的并集搜索的新宏启发算法  

Union Search:A New Meta-Heuristic Algorithm to the Traveling Salesman Problem

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

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

出　　处：《中国科学技术大学学报》2005年第3期367-375,共9页JUSTC

基　　金：国家"九七三"项目(G1998030403).

摘　　要：利用TSP问题解的概率统计模型,分析了TSP问题的局部最优解并集的性质,发现局部最优解的并集规模较小且包含了绝大多数全局最优解的边.利用该性质,将局部最优解并集作为启发集,并调用局部搜索算子在其上求解TSP问题,由此得到一种称为并集搜索的新宏启发算法.利用该算法还改进了目前广泛使用的求解TSP问题的算法ILK、LKH,在TSPLIB中典型实例上的实验结果表明,新算法在解的质量上有了较显著的提高.The traveling salesman problem (TSP) is one of the classic NP-hard combinatorial optimization problems. It has been the focus of computer science research to develop heuristics for this problem. By analyzing the characteristic of the union of local optima based on the statistical model of solutions, this paper indicates that the union of local optima contains most of the edges of global optimal and the size of the union is comparatively small. Thus, this paper takes the union as the candidate set, and proposes a new meta-heuristic called “union search”. Furthermore,the paper indicates that, in ample experiments of instances from TSPLIB, incorporating the meta-heuristic in ILK and LKH would improve dramatically the quality of solutions.

关 键 词：TSP 启发集 统计模型 并集搜索 

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