一个基于填充函数变换的对称TSP问题的局部搜索算法  

A Filled Function Method for the Traveling Salesman Problem

作　　者：朱文兴[1] 傅清祥[1] 

机构地区：[1]福州大学计算机科学与技术系

出　　处：《计算机学报》2002年第7期701-707,共7页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目 (G19980 3 0 60 0 );福建省自然科学基金 (A0 0 10 0 10 );福建省教育厅科技开发基金 (JA0 0 14 3 );福州大学科技发展基金 (XKJ(QD) -0 12 2 )资助

摘　　要：该文提出了求对称 TSP问题近优解的填充函数算法 .首先 ,在用局部搜索算法求得对称 TSP问题的一个局部极小解后 ,对该问题作填充函数变换得到一新的组合优化问题 ,新问题的局部极小解和最优解分别是原问题的局部极小解和最优解 ,而且在对称 TSP问题的目标函数值大于或等于其目标函数当前极小值的区域中 ,新问题只有一个已知的局部极小解 .随后用局部搜索算法求新问题的一个局部极小解 ,它或者是已知的局部极小解 ,或者是对称 TSP问题的更好的局部极小解 .对多个标准实例的计算试验表明 ,该文所构造的算法优于直接求解对称 TSP问题的局部搜索算法 .This paper presents a local search method based on a filled function transformation method. Given a current best local minimal solution of the TSP, the filled function transformation method converts the TSP into a combinatorial optimization problem with the same solution space, but with less number of local minimal solutions. The combinatorial optimization problem has only one prescribed local minimal solution in the solution space where the length of any tour of the TSP is larger than that of the current best local minimal solution of the TSP. Moreover, a local minimal solution of the combinatorial optimization problem is either the prescribed local minimal solution, or else, is a strictly better local minimal solution of the TSP than the current best solution. Then the well known 3 opt algorithm is used to solve the combinatorial optimization problem to find a better local minimal solution of the TSP. If a better local minimal solution of the TSP is found, then a new combinatorial optimization problem is constructed using the filled function transformation method, and the 3 opt algorithm is applied to solve it again. This method is tested by some standard test instances, and the method presented in this paper is more efficient and more effective than the 3 opt algorithm for the TSP. It is easy to use, and can be directly generalized to solve other NP hard combinatorial optimization problems.

关 键 词：填充函数变换 对称TSP问题 局部搜索算法 近似最优解 组合优化问题 

分 类 号：O224[理学—运筹学与控制论] TP301.6[理学—数学]