一种基于改进模拟退火算法的TSP问题的应用研究

An Applied Research on TSP Problem Based on Improved Simulated Annealing Algorithm

旅行商问题(TSP)是一种经典路径优化选择问题,可以通过暴力枚举、分支定界、动态规划、爬山算法等方法解决该问题,这些方法各有利弊。基于此,笔者对模拟退火算法进行改进处理,一是对扰动过程设置随机接受概率从而跳出局部最优解陷阱,二是设置循环阈值以较少的时空消耗获得一个最优解或者极其接近最优解的满意解。笔者使用Matlab软件进行仿真,结果表明该算法较好地解决了TSP问题。

Traveling salesman problem(TSP)is a classical path optimization problem,which can be solved by violent enumeration,branch and bound,dynamic planning,mountain climbing algorithm and other methods,each of which has its own advantages and disadvantages.Based on this,the author improves the simulated annealing algorithm.One is to set the random acceptance probability for the disturbance process to jump out of the local optimal solution trap.The other is to set the cycle threshold to obtain an optimal solution or a satisfactory solution close to the optimal solution with less time and space consumption.The author uses MATLAB software to simulate,and the result shows that the algorithm solves the TSP problem well.