求解TSP的改进模拟退火算法

Improved Simulated Annealing Algorithm of Solving TSP

利用模拟退火算法给出了求解旅行商问题的一种新方法.在模拟退火算法的基本原理基础上,针对解变换只交换两个城市而容易落入局部最优解的缺点,提出了在解变换产生新解的过程中,采用逆转操作的改进方法.这使得迭代过程突破局部最优圈,然后跳到另一个搜索空间.这样能够使其更具多样性,改善了模拟退火算法的局部搜索能力.并将其应用于求解旅行商问题,显著改善了它局部寻优的能力.在几个公共测试数据集上的结果表明,算法稳定可行,在求解组合优化问题方面,具有良好的性能.

A new method of solving traveling salesman problem is given by using simulated annealing algorithm. Based on the basic principle of simulated annealing algorithm, in view of the faults easily falling into local optimal solution when transformation only exchange two of the cities, puts forward an improved method by using reverse operation in the process of creating new solution. This makes the iterative process breakthrough circle of local optimum and jumps to another search space, which makes it more diversified and improves the local search ability of simulated annealing algorithm. And it is applied to solve TSP, which improves its ability of local search. The experiment results on several public test data show that the proposed approach is stable and feasible. Moreover, it has good performance in solving combinatorial optimization problems.