改进模拟退火算法在TSP中的应用

张驰　汪海涛　姜瑛　陈星

摘要：为了有效优化旅行商问题（TSP）的旅行路径，通过分析传统模拟退火算法的优缺性，提出了一种改进扰动机制并结合分支定界的模拟退火算法。为了弥补模拟退火（SA）算法对初始解的依赖性，该算法首先通过分支定界产生一个较优的初始解，通过对SA温度参数和扰动机制的的有效控制，进行全局优化。采用TSPLIB中的标准库文件验证，测试的数据显示改进的SA算法和传统算法相比较，在針对此类问题的求解上有着良好的性能。

关键词：旅行商问题；扰动机制；分支定界算法；模拟退火算法endprint