求解旅行商问题的波动温控模拟退火算法

针对传统模拟退火算法在求解旅行商问题时运行时间长,易陷入局部最优,且随着问题规模的增大缺陷愈发明显的问题,对传统算法的内循环过程和退火机制进行改进,使得内循环的搜索强度根据温度的变化自适应调整,同时提出波动温度控制机制,使得算法在保持温度幅值递减的总趋势下实现多次升温过程,增强求解效果,缩短求解时间,并通过TSPLIB数据库提供的大量实例得以验证.

A simulated annealing algorithm with wave temperature control for the traveling salesman problem

In view of the fact that the traditional simulated annealing algorithm has a long running time, easily been trapped in local optimum in solving the traveling salesman problem, especially the defects become more obvious with the increase of the problem scale, the inner loop and annealing mechanism of the traditional algorithm are improved, so that the search strength of the inner loop can be adjusted adaptively according to the change of temperature. At the same time, a fluctuation temperature control mechanism is proposed, so that the algorithm can realize multiple heating processes while maintaining the general trend of decreasing in temperature amplitude, which enhances the solution effect and shortens the solution time. It is verified by a large number of examples from the TSPLIB database.