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

doi:10.3778/j.issn.1002-8331.2010.15.011

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (15): 34-36.DOI: 10.3778/j.issn.1002-8331.2010.15.011

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

杨卫波^1，2，赵燕伟²

1.温州大学物理与电子信息工程学院，浙江温州 325035
2.浙江工业大学机械制造自动化教育部重点实验室，杭州 310014

收稿日期:2010-01-13 修回日期:2010-03-01 出版日期:2010-05-21 发布日期:2010-05-21
通讯作者: 杨卫波

Improved simulated annealing algorithm for TSP

YANG Wei-bo^1，2，ZHAO Yan-wei²

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

摘要/Abstract

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

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

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

中图分类号:

TP301.6

杨卫波^1，2，赵燕伟². 求解TSP问题的改进模拟退火算法[J]. 计算机工程与应用, 2010, 46(15): 34-36.

YANG Wei-bo^1，2，ZHAO Yan-wei². Improved simulated annealing algorithm for TSP[J]. Computer Engineering and Applications, 2010, 46(15): 34-36.

[1]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[2]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[3]	马艳芳，李保玉，杨屹夫，冯翠英. 客户分类下生鲜配送两级路径问题与算法研究[J]. 计算机工程与应用, 2021, 57(20): 287-298.
[4]	童文林，陈德旺，黄允浒，吕宜生. 结合模拟退火与规则约简的模糊系统优化方法[J]. 计算机工程与应用, 2021, 57(16): 142-150.
[5]	郭佳丽，王秋萍，王晓峰. 融合学习策略和邻域搜索的飞蛾火焰算法[J]. 计算机工程与应用, 2021, 57(12): 170-179.
[6]	禹忠，顾仁彬，范九伦. 基于LBT-SA的LoRaWAN信道接入方法研究[J]. 计算机工程与应用, 2020, 56(24): 95-101.
[7]	吴树景，游有鹏，罗福源. 变邻域保优遗传算法求解柔性车间调度问题[J]. 计算机工程与应用, 2020, 56(22): 236-243.
[8]	陈思远，林丕源，黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
[9]	周克良，龚达欣，张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[10]	蔡延光，陈厚仁，戚远航. 变邻域量子烟花算法求解CVRP[J]. 计算机工程与应用, 2019, 55(9): 230-236.
[11]	涂兵1，2，3，张晓飞1，3，潘建武1，3，张国云1，2，3，周紫璇1，3. 多特征与边缘校正融合的天际线检测算法研究[J]. 计算机工程与应用, 2019, 55(6): 178-185.
[12]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[13]	陈桂兰，奚宝华，杨兰英. 改进混合粒子群算法的立体车库存取调度[J]. 计算机工程与应用, 2019, 55(19): 263-270.
[14]	胡士娟，鲁海燕，黄洋，许凯波. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
[15]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.

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

Improved simulated annealing algorithm for TSP

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics