模拟退火算法在TSP问题中的优化研究+源码
时间:2017-04-24 22:29 来源:毕业论文 作者:毕业论文 点击:次
| 摘 要：随着计算机技术的发展以及人们利用计算机解决实际问题的需求的增长，对模拟退火算法的研究人数日益增加。依据模拟退火算法求解旅行商问题（TSP）对人们的日常生活有很大的意义。在传统的模拟退火算法的基础上上，通过对传统模拟退火算法在运算结果的优化以及快速的找到最优解范围上进行优化，使模拟退火算法解决TSP等优化组合问题的方面的研究来更加普遍的解决日常生活中的大数据搜索或者是优化组合问题。关键词：模拟退火算法；TSP问题；优化组合7618 Application of Simulated Annealing Algorithm in TSP Problem Abstract: With the development of computer technology and the use of computer to solve practical problems of demand growth, growing Numbers of studies of simulated annealing algorithm. Based on simulated annealing algorithm to solve traveling salesman problem (TSP) has a great significance to People's Daily life. And the basis of the traditional simulated annealing algorithm, based on the traditional simulated annealing algorithm to optimize the results of operation and fast optimization to find the optimal solution of the scale, make the optimization combination problem such as simulated annealing algorithm to solve TSP research to the solution of the more common in daily life's big data search, or combination optimization problem. Key Words: Simulated annealing algorithm; TSP problem; Optimal Combination 目 录 摘 要 1 引言 2 1.相关解决算法简介 2 1.1 遗传算法 2 1.2粒子群算法 2 1.3模拟退火算法 3 2.模拟退火算法的退火过程的分析 3 2.1模拟退火算法的伪代码： 3 2.2 模拟退火算法求解分析 4 3.模拟退火算法仿真实验环境 6 3.1算法的应用开发环境 6 3.2算法实现的开发语言 6 3.3算法实现的开发平台 6 4.模拟退火算法对TSP问题的仿真实验 6 4.1传统模拟退火算法的缺点 6 4.2模拟退火算法的实现 7 4.1.1对模拟退火算法的优化改进 7 4.1.2模拟退火算法的退火过程 8 4.3改进的模拟退火算法在解决TSP问题中的比较 8 5.总结 11 参考文献 12 致谢 13 模拟退火算法在TSP问题中的优化研究引言 随着社会生活精确化和效率化的加剧，对生活中的常见问题的解决办法的要求也在向着资源节约和更加优化的方向发展，对这方面的研究也越来越受到重视和关注。那么，TSP问题，即旅行商问题，是指一名推销员要从一个地点（开始地点）到另一个地点（目的地点）时，如何找到在拜访每个地点一次后再回到起点的最短路径。模拟退火算法是将物理退火过程与组合优化问题相结合的一种概率性搜索迭代启发式算法。在现今的研究现状中对模拟退火算法的优化成为热点，主要分为三个方向：一、运算速率的优化；二、运算结果的优化；三、前两者的结合优化。该论文就运算结果进行的优化以及对传统模拟退火算法的比较。 1.相关解决算法简介 1.1 遗传算法 遗传算法是和模拟退火算法搜索方法相同，其核心思想为：以随机化搜索方法为辅助搜索同时以生物界的进化规律（适者生存，优胜劣汰遗传机制）为核心演化而来的。生物进化的过程本身是一个并发生的、自然、稳健、漫长的优化过程。生物进化的原因是生物个体有其自己内部结构即基因结构，生物体经过变异、繁殖，大量新的结构随之产生，由于生存和外在条件的驱使，胜劣汰选择使个体能适应环境，使好的基因得以保存，再经过后期的繁殖、交叉、变异，优秀的个体重新组合，会产生更优的个体，并逐渐使群体进化到包含或者接近最优解的状态。遗传算法的编码方法和操作比较简单，容易实现，不受限制性条件的约束，但是很容易出现过早稳定和收敛性差的现象。 (责任编辑：qin) |