| 求解TSP问题的改进模拟退火算法 |
| |
| 引用本文： | 杨卫波,赵燕伟.求解TSP问题的改进模拟退火算法[J].计算机工程与应用,2010,46(15):34-36. |
| |
| 作者姓名： | 杨卫波 赵燕伟 |
| |
| 作者单位： | 1.温州大学 物理与电子信息工程学院，浙江 温州 325035 2.浙江工业大学 机械制造自动化教育部重点实验室，杭州 310014 |
| |
| 基金项目： | 国家自然科学基金 No.60970021;;浙江省重大科技专项项目No.2009C11039~~ |
| |
| 摘 要： | 通过分析传统模拟退火算法的原理和存在的不足，提出了一个用于求解TSP问题的改进模拟退火算法。新算法增加了记忆当前最好状态的功能以避免遗失当前最优解，并设置双阈值使得在尽量保持最优性的前提下减少计算量。根据TSP和SA的特征设计了个体邻域搜索方法和高效的计算能量增量方法，加快了算法的运行速度。实验测试的结果表明，新算法比传统的模拟退火算法具有更快的收敛速度和更优的解质量。
|
| 关 键 词： | 模拟退火算法 邻域搜索 旅行商问题 |
| 收稿时间： | 2010-1-13 |
| 修稿时间： | 2010-3-1
|
Improved simulated annealing algorithm for TSP |
| |
| YANG Wei-bo,ZHAO Yan-wei.Improved simulated annealing algorithm for TSP[J].Computer Engineering and Applications,2010,46(15):34-36. |
| |
| Authors: | YANG Wei-bo ZHAO Yan-wei |
| |
| Affiliation: | 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 |
| |
| 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... |
| |
| Keywords: | simulated annealing algorithm neighborhood search Traveling Salesman Problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
