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

作者：何锦福; 符强^*; 王豪东

来源：计算机时代, 2019, (07): 47-50.

DOI：10.16644/j.cnki.cn33-1094/tp.2019.07.015

• TSP问题
• 模拟退火算法
• 跳跃式降温
• 二重退火

模拟退火算法是一种结构简单,鲁棒性强的群智能方法,在旅行商问题(Traveling Salesman Problem TSP)中得到了较好的应用。但是该算法在获取高性能解的过程中需要放慢降温过程,因此收敛速度较慢。为了解决该问题,本文对求解TSP问题的模拟退火算法进行了降温方式的改进,针对温度设置能量值,并根据能量值的高低状态判断是否进行跳跃式降温,从而在保证精度的同时,加快了算法的收敛速度。用TSPLIB标准库数据测试的结果表明,与改进前的模拟退火算法相比,改进的算法具有更加高效的寻优能力。

• 单位
  宁波大学; 宁波大学科学技术学院