旅行商问题(TSP)的改进模拟退火算法

An improved Simulated Annealing Algorithm to TSP

旅行商问题是一种典型的求解多局部最优的最优化问题:有n个城市,一个旅行者从其中的一个城市出发,经过所有的城市一次并返回出发的城市,求最短的路线。在使用普通的模拟退火算法解决TSP时,一般采用2-opt算法来产生新的解空间,导致算法效率低下。本文提出引入多种算子(如:移位,交换,倒置等等)来产生新解空间。算法的分析和测试结果表明,改进后的模拟退火算法效率明显提高,在收敛性和运算结果上都有较大的进步。

Travelling Salesman Problem （TSP） is a typical combinatorial optimisation problem. The main idea of the problem is that given a number of cities and the distances between each city and tries to get the shortest path that visits each city exactly once and back to the starting point. In most simulated annealing algorithms, 2-opt algorithm is used to generate new path, which gives a low efficiency. This report introduces multiple arithmetic operators （e,g. transportation, switching and inversion）, The result shows that the improved simulated annealing algorithm is quite more efficient that the former one,