Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (15): 34-36.DOI: 10.3778/j.issn.1002-8331.2010.15.011

• 研究、探讨 • Previous Articles     Next Articles

Improved simulated annealing algorithm for TSP

YANG Wei-bo1,2,ZHAO Yan-wei2   

  1. 1.College of Physics & Electronic Information Engineering,Wenzhou University,Wenzhou,Zhejiang 325035,China
    2.The MOE Key Laboratory of Mechanical Manufacture and Automation,Zhejiang University of Technology,Hangzhou 310014,China
  • Received:2010-01-13 Revised:2010-03-01 Online:2010-05-21 Published:2010-05-21
  • Contact: YANG Wei-bo

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

杨卫波1,2,赵燕伟2   

  1. 1.温州大学 物理与电子信息工程学院,浙江 温州 325035
    2.浙江工业大学 机械制造自动化教育部重点实验室,杭州 310014
  • 通讯作者: 杨卫波

Abstract: By analyzing the principles and the shortcomings of traditional simulated annealing algorithm,an improved simulated annealing algorithm for solving TSP is proposed.In order to avoid missing current optimal solution,the new algorithm increases memory function to remember current best state and set up dual-threshold to reduce the amount of calculation while maintaining the premise of optimality.According to the characteristics of TSP and SA,individual neighborhood search methods and efficient energy increment calculation method are designed to speed up algorithm speed.Experimental test results show that the new algorithm has faster convergence and better solution than traditional simulated annealing algorithm.

Key words: simulated annealing algorithm, neighborhood search, Traveling Salesman Problem

摘要: 通过分析传统模拟退火算法的原理和存在的不足,提出了一个用于求解TSP问题的改进模拟退火算法。新算法增加了记忆当前最好状态的功能以避免遗失当前最优解,并设置双阈值使得在尽量保持最优性的前提下减少计算量。根据TSP和SA的特征设计了个体邻域搜索方法和高效的计算能量增量方法,加快了算法的运行速度。实验测试的结果表明,新算法比传统的模拟退火算法具有更快的收敛速度和更优的解质量。

关键词: 模拟退火算法, 邻域搜索, 旅行商问题

CLC Number: