作　　者： ; ; ;

机构地区： 中国科学技术大学计算机科学与技术学院

出　　处： 《中国科学技术大学学报》 2005年第5期683-692,共10页

摘　　要： 建立了描述TSP问题启发集性质的概率模型,并指出了改进启发集的一般方法.进一步,利用局部最优解交集作为近似骨架,提出了一种动态改进启发集的宏启发算法———自适应可变启发集搜索.并将自适应可变启发集搜索与目前广泛使用的算法ILK、LKH相结合,TSPLIB中典型实例上的实验结果表明,改进后的算法在求解质量上有了较大的改进. A statistical model depicting the properties of candidate sets is built, and the general ways are given to improve them. Using the intersection of local optimal solutions as the approximate backbone, a new meta-heuristic-Self-Adaptive Variable Candidate Sets Search （SAVCSS）, which shrinks the candidate sets dynamically, is proposed. Furthermore, ILK and LKH are incorporated in the new meta-heuristic, Experiment results on TSPLIB indicated that the modified algorithms is capable of better performance in terms of solution quality.

关 键 词： 旅行商问题 启发集 局部搜索 骨架

领　　域： [自动化与计算机技术] [自动化与计算机技术]