改进模拟退火算法在TSP中的应用

Application of Improved Simulated Annealing Algorithm in TSP

为了有效优化旅行商问题(TSP)的旅行路径,通过分析传统模拟退火算法的优缺性,提出了一种改进扰动机制并结合分支定界的模拟退火算法。为了弥补模拟退火(SA)算法对初始解的依赖性,该算法首先通过分支定界产生一个较优的初始解,通过对SA温度参数和扰动机制的的有效控制,进行全局优化。采用TSPLIB中的标准库文件验证,测试的数据显示改进的SA算法和传统算法相比较,在针对此类问题的求解上有着良好的性能。

In order to optimize the tavel path in the traveling salesman problem effectively, an improved pertur- bation mechanism and simulated annealing algorithm combined with the proposed branch and bound was put for-ward through the analysis of advantages and disadvantages of traditional simulated annealing algorithm. In order to compensate for the simulated annealing （SA） algorithm to the dependence of the initial solution, resulting in a better initial solution firstly by branch and bound by effectively controlling the disturbance mechanism of SA temperature parameters and the global optimization. Using the standard library file verification in TSPLIB, the test data show that the improved SA algorithm is better than the traditional algorithm in solving such problems.