基于对称TSP问题的研究
摘 要 旅行商问题（简称TSP）是一个著名的NP-Hard问题，也是离散优化的一个经典的重要问题，对其相关求解算法的研究非常重要。本文在介绍了TSP问题本身相关的问题后，又详细讨论了求解TSP问题的动态规划方法、改良圈算法、二交换算法、模拟退火算法、蚁群算法、遗传算法，并通过整合各种优化方式，对遗传算法进行了少量优化。针对测试库中的的改良圈算法、模拟退火算法、蚁群算法、遗传算法。本文使用MATLAB软件实现这些算法，并对这些算法的运行时间和解进行比较分析等研究。结果表明在任何清空下改良圈算法的性能都最差，其余算法在小型TSP问题下差别不大，在较大型TSP问题下，模拟退火所用时间最短，蚁群算法所用时间最长，遗传算法的解最好。实验结果证明，改进后的遗传算法效果不明显，在解的大小上改善1%-3%，但时间提高了10%。
关键词 对称TSP问题; 算法研究; 近似算法;模拟退火;遗传算法;蚁群算法
Study based on symmetric TSP problem
Xu Bu-Fan Yan Yang-Sheng Dong Xiu-Liang Wang You-Wei Yu Yong-Xun
Abstract Travelling salesman problem (TSP) is both a well-known problem as a NP-Hard problem and a classical problem in the field of discrete-optimization. This paper first introduce something about itself, then discusses many ways such as dynamic programming, 2-opt, exchange algorithm, simulated annealing algorithm, ant colony optimization and genetic algorithm in detail. After that, this paper proposes an improved genetic algorithm by the means of integrating many papers’ methods.Finaly, this paper .Experiments show that Improved cycle algorithm perFORms worst, and when it comes to small TSP problems, those algorithms perFORms familiar. However, when solving big TSP problems, simulated annealing algorithm solves quickest as ant colony optimization takes longest, and YICHUAN makes the best solution. Experiments also show that the improved algorithm makes approximately 3%~5% improvement FOR the last length but time takes 10% more.
Key words Symmetric TSP problem; Algorithm research; approximate algorithm; simulated annealing; genetic algorithm; ant colony algorithm
目录
基于对称TSP问题的研究 1
Study based on symmetric TSP problem 1
1 引言 2
1.1 TSP问题 2
2 相关概念与工作 3
2.1 TSP相关算法概述 3
2.2 动态规划算法 4
2.3 改良圈算法 4
2.4 交换算法 4
2.5 模拟退火算法 5
2.6 蚁群算法 5
2.7 遗传算法 5
2.8 郭涛算法 5
3 算法设计 7
3.1 模拟退火算法 7
3.1.1 算法设计思想 7
3.1.2 伪代码 7
3.2 改良圈算法 7
3.2.1 算法设计思想 7
3.2.2 伪代码 7
3.3 动态规划算法 8
3.3.1 算法设计思想 8
3.3.2 伪代码 8
3.4 蚁群算法 8
3.4.1 算法设计思想 8
3.4.2 伪代码 8
3.5 遗传算法 9
3.5.1 算法设计思想 9
3.5.2 伪代码 9
3.6 遗传算法的优化 10
3.6.1 算法的设计思想 10
3.6.2 改进方法[5] 10
4 实验 10
4.1 实验环境 10
4.2 实验结果分析 10
4.2.1 改良圈算法 10
4.2.2 模拟退火算法 12
4.4.3 蚁群算法 13
4.4.4 遗传算法 15
4.4.5 改进的遗传算法 16
4.3 总体数据及分析 18
5参考文献 20
I.附录1——分工 22
II.附录2——心得与体会 22
(1)： 22
(2： 23
(3)： 23
(4)： 23
(5)： 23
III.附录3——失败的改进之一 23
