摘要
通过分析传统模拟退火算法的原理和存在的不足,提出了一个用于求解TSP问题的改进模拟退火算法。新算法增加了记忆当前最好状态的功能以避免遗失当前最优解,并设置双阈值使得在尽量保持最优性的前提下减少计算量。根据TSP和SA的特征设计了个体邻域搜索方法和高效的计算能量增量方法,加快了算法的运行速度。实验测试的结果表明,新算法比传统的模拟退火算法具有更快的收敛速度和更优的解质量。
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.
出处
《计算机工程与应用》
CSCD
北大核心
2010年第15期34-36,共3页
Computer Engineering and Applications
基金
国家自然科学基金 No.60970021
浙江省重大科技专项项目No.2009C11039~~
关键词
模拟退火算法
邻域搜索
旅行商问题
simulated annealing algorithm
neighborhood search
Traveling Salesman Problem
