基于模拟退火算法的旅行商问题求解.docVIP

目 录 II 关键词 II Abstract II Keywords II 引言 1 1 旅行商问题和模拟退火算法 2 1.1 旅行商问题 2 1.1.1 旅行商问题的描述 2 1.1.2 旅行商问题的应用 3 1.2 模拟退火算法 3 1.2.1 基本思想 3 1.2.2 关键技术 4 1.3 小结 4 2 TSP模拟退火算法的实现 5 2.1 TSP算法实现 5 2.1.1 TSP算法描述 5 2.1.2 TSP算法流程 5 2.2 TSP的MATLAB实现 6 2.2.1 加载数据文件 6 2.2.2 计算总距离的函数 7 2.2.3 绘制路线的函数 7 2.2.4 交换城市的函数 8 2.2.5 执行模拟退火的函数 8 2.3 小结 9 3 仿真实例 10 3.1 仿真分析与评价 10 3.2 结论 12 总结与展望 12 致谢 13 参考文献 13  基于模拟退火算法的旅行商问题求解 光信息科学与技术 董铸祥 指导教师 张明强 摘要: 旅行商问题是组合优化领域里的一个典型的、易于描述却难以处理的NP难题，其可能的路径数目与城市数目是呈指数型增长的，求解非常困难。首先介绍了旅行商问题，进而给出解决TSP的一种比较精确的算法——模拟退火算法。然后阐述了模拟退火算法的基本原理运用MATLAB语言实现了该算法并将其运用到解决旅行商问题的优化之中。数值仿真的结果表明了该方法能够数进行全局寻优，有效克服了基于导数的优化算法容易陷入局部最优的问题。 关键词: 模拟退火 旅行商 NP 组合优化 Solution of Travelling Salesman ProblemBaced on Simulated Annealing Algorithm Optical Information Science and Technology Dong Zhuxiang Tutor Zhang Mingqiang Abstract: Travelling Salesman Problem is one of the typical NP-hard problems in combinatorial optimization, which is easy to be described but hard to be solved. Its possible amounts of path increase exponentially with the amounts of city, so it is very difficult to solve it. First this paper introduces Travelling Salesman Problem, gives TSP mathematical description and practical application.In turn, a precise algorithm——simulated annealing algorithmthe to the address of TSP is given. And then this paper describes the basic principle of simulated annealing, highlights the basic ideas and key technology. Finally, we use MATLAB language to implement the algorithm, and applied it to solve the traveling salesman problem into the optimization. Numerical simulation results show that this method can globally optimizes data, effectively overcomes the problem of derivative-based optimization algorithm which is easy fall into local optimum. Keywords: simulated annealing; travelling salesman problem;Non-deterministicPolynomial; combinatorial optimization 引言 旅行商问题(Traveling Salesman Proble