模拟退火算法在TSP问题中的应用研究—毕业设计论文.doc
《模拟退火算法在TSP问题中的应用研究—毕业设计论文.doc》由会员分享,可在线阅读,更多相关《模拟退火算法在TSP问题中的应用研究—毕业设计论文.doc(56页珍藏版)》请在三一办公上搜索。
1、目 录摘 要IIIABSTRACTIV第一章前言11.1 TSP问题的基本概念11.2 模拟退火算法的背景11.3 发展趋势1第二章相关知识介绍12.1模拟退火算法的原理12.1.1 模拟退火的基本思想12.1.2 算法对应动态演示步骤12.2 TSP问题简述12.3组合优化问题简述12.4 蚁群算法及其它算法原理12.4.1蚁群优化算法12.4.2其它优化算法1第三章 问题描述与算法分析研究13.1应用研究整体规划13.2应用开发环境13.2.1开发语言13.2.2开发平台13.3 TSP问题的描述和分析13.4模拟退火算法的分析13.4.1模拟退火算法模型13.4.2模拟退火算法与优化问题
2、分析13.5应用研究方案分析1第四章 算法具体设计与编码实现14.1基于模拟退火算法求解TSP问题详细设计14.1.1求解TSP问题的模拟退火算法及流程图14.1.2算法温度的选择和变化14.1.3定义坐标表的具体参数与具体实现14.1.4新解的产生方法14.2求解TSP问题的算法主体模块详细设计14.3算法的具体编码实现14.3.1建立城市坐标文本文件14.3.2 DOS下界面数据输出以及概率统计与分析1第五章 算法运行分析15.1 运行界面图示15.2 运行结果1第六章 结束语1致 谢1参考文献1摘 要TSP问题是一个典型的NP 完全问题,模拟退火算法是求解此问题的一种理想方法。模拟退火算
3、法是将物理退火过程与组合优化相结合在一起的一种随机迭代寻优算法,TSP问题即旅行商问题是一个组合优化问题,该问题被证明具有NPC计算复杂性。因此,研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。本文主要阐述了模拟退火算法的原理和一些与其相关联的知识结构点。通过对其算法的原理,以及退火算法在函数优化问题上的应用,与优化组合问题的研究来了解TSP问题以及模拟退火算法上解决实际问题上的应用与研究。帮助理解模拟退化算法的基本原理及其在TSP问题求解中的应用。关键词 模拟退火算法,TSP,组合优化,C/C+,遗传算法ABSTRACTTSP problem is a typical
4、NP-complete problem, using simulated annealing algorithm to solve this problem is an ideal way.Simulated Annealing Algorithm combines the process of physical annealing and combinatorial optimization together ,it is a stochastic iterative optimization algorithm, TSP problem that the traveling salesma
5、n problem is a combinatorial optimization problem that is shown to have NPC computational complexity. Therefore, studying the basic principles of simulated annealing algorithm and its application in problem solving TSP should have a high degree of attention. This article focuses on the principle of
6、simulated annealing algorithm and some of the knowledge structure what associated with the first point. By studying the principle of their algorithm, simulated annealing algorithm to optimize the application function, and optimization of research to understand the problem and the simulated annealing
7、 algorithm for TSP The practical application and research. Help to understand the basic principles of simulated annealing algorithm and its application in solving TSP problems.KEY WORDS: SAA,Genetic Algorithm,Combinatorial Optimization, TSP,C/C+第一章 前言模拟退火算法是将物理退火过程与组合优化相结合的一种随机迭代寻优算法,TSP问题即旅行商问题是一个组
8、合优化问题,该问题被证明具有NPC计算复杂性,因此研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。因此采用模拟退火算法来解决TSP旅行问题是一种比较理想的方法。1.1 TSP问题的基本概念旅行商问题( Traveling Salesman Problem) 是一个NP 完全问题,目前求解 TSP 问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、Hopfield 神经网络算法、蚁群算法等,还包括许多算法。TSP(Traveling salesman Problem,旅行商问题)是指给定n个城市和各城市间的距离,要求确定一条经过各个城市当且仅当一次的最短路线。它是一种典
9、型的组合优化问题,其最优解的求解代价是指数级的。已经证明TSP问题是一个NP-hard问题。基于智能优化算法求解TSP问题,是近年来刚刚兴起的热门课题。 然而在科学管理与经济决策的许多应用领域中,现实世界存在着大量的多目标优化问题。对于旅行商问题(Traveling salesman Problem ,TSP),实际中经常要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、合理的解是比较复杂的问题。1.2 模拟退火算法的背景模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升
10、变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-E/(kT),其中E为温度T时的内能,E为其改变量,k为 Boltzman 常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling
11、 Schedule)控制,包括控制参数的初值t及其衰减因子 t、每个t值时的迭代次数L和停止条件S1。1.3 发展趋势TSP的历史很久,最早的描述是1759年欧拉研究的骑士周游问题,即对于国际象棋棋盘中的64个方格,走访64个方格一次且仅一次,并且最终返回到起始点。TSP由美国RAND公司于1948年引入,该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。TSP在中国的研究,同样的问题,在中国还有另一个描述方法:一个邮递员从邮局出发,到所辖街道投邮件,最后返回邮局,如果他必须走遍所辖的每条街道至少一次,那么他应该如何选择投递路线,使所走的路程最短?这个描述之所以称为中
12、国邮递员问题(Chinese Postman Problem CPP)因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。TSP问题是一个典型的、容易描述但是难以处理的NP完全问题,同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。目前求解TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。对于用模拟退火算法对求解旅行商组合优化问题做来了在满足模拟退火算法全局收敛性的情况下,子排列反序并移位抽样方式对求解NP完全问题是非常有效的。 很多实际问题,经过简化处理后均可转化为TSP问题,对TSP问题求解方法的研
13、究具有重要的应用价值。人们在努力寻找大维数最优化算法的同时,构造出了许多近似求解法,如遗传法、局部搜索算法、蚁群算法等,特别是提出了如模拟退火等用统计方法近似求解TSP的随机算法,为人们求解TSP问题开辟了新的途径。第二章 相关知识介绍本章主要介绍一些关于模拟退火算法的原理、TSP问题简述以及相关重要算法的原理,并且对其进行了一些细致的阐述,以便于对模拟退火算法了解。2.1模拟退火算法的原理模拟退火算法是近年来在国内外都比较受关注的算法。它的思想最早在1953年由Metropolis提出,在1983年被Kirkpatrick等人成功引入组合优化领域。由于它具有很强的实用性和极佳的性能表现,迅速
14、引起了很多专家学者的兴趣,不断对其进行研究。模拟退火算法主要应用在各种优化问题上,函数优化是其中非常重要的一个方面。NP问题是一个比较麻烦的问题,其解的规模随问题规模的增大而成指数级增长,对于一般的方法而言,当问题规模过大时,就失去了可行性。模拟退火作为一种随机算法,它的特点非常适于求解NP问题,比如著名的旅行商问题(Traveling Salesman Problem)。模拟退火算法在解决这类问题上有着优异的表现。2.1.1 模拟退火的基本思想模拟退火是一种通用概率算法,用来在一个大的搜寻空间内找寻命题的最优解。模拟退火来自冶金学的专有名词淬火。模拟退火的原理也和金属退火的原理近似:将热力学
15、的理论套用到统计学上,将搜寻空间内每一点想像成空气内的分子;分子的能量,就是它本身的动能;而搜寻空间内的每一点,也像空气分子一样带有“能量”,以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始:每一部先选择一个“邻居”,然后再计算从现有位置到达“邻居”的概率。模拟退火算法可以分解为解空间、目标函数和初始解三部分。(1) 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点), 每个T值的迭代次数L (2) 对k=1,L做第(3)至第6步: (3) 产生新解S (4) 计算增量 t=C(S)-C(S),其中C(S)为评价函数。(5) 若 t0,然后转第2步。2.1.2 算法对
16、应动态演示步骤模拟退火算法新解的产生和接受可分为如下四个步骤: 第一步是由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropo1is
17、准则: 若 t0则接受S作为新的当前解S,否则以概率exp(- t/T)接受S作为新的当前解S。 第四步是当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。2.2 TSP问题简述旅行商问题,即TSP问题(Travelling
18、 Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。旅行商问题TSP( Traveling Salesman Problem) 问题是一个NP 完全问题,目前求解TSP 问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、Hopfield 神经网络算法、蚁群算法等,各种算
19、法各有千秋。模拟退火算法最早思想由Met ropolis 在20世纪1953 年提出,1983 年Kirkpat rick 等成功地将退火思想引入组合优化领域。模拟退火算法是局部搜索算法的扩展,理论上来说,它是一个全局最优算法。如何在初始解附近找出一个“好的解”是一项关键技术,它直接影响算法的收敛速度。TSP问题是经典的NP Hard组合优化问题之一,求解该问题的启发式算法一直是数学,计算机科学研究的热点之一。假设有一个旅行商人要拜访N个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值,这是一个
20、NP难问题。2.3组合优化问题简述在给定有限集的所有具备某些条件的子集中,按某种目标找出一个最优子集的一类数学规划。又称组合规划。从最广泛的意义上说,组合规划与整数规划这两者的领域是一致的,都是指在有限个可供选择的方案的组成集合中,选择使目标函数达到极值的最优子集。 组合最优化发展的初期,研究一些比较实用的基本上属于网络极值方面的问题 ,如广播网的设计 、开关电路设计、航船运输路线的计划、工作指派、货物装箱方案等。自从拟阵概念进入图论领域之后,对拟阵中的一些理论问题的研究成为组合规划研究的新课题,并得到应用。现在应用的主要方面仍是网络上的最优化问题,如最短路问题、最大(小)支撑树问题、最优边无
21、关集问题、最小截集问题、推销员问题等2。组合优化( Combinatorial Optimization )问题的目标是从组合问题的可行解集中求出最优解,通常可描述为:令 s1,s2,sn 为所有状态构成的解空间,C (si) 为状态 si 对应的目标函数值,要求寻找最优解 s*,使得对于所有的si ,有 C(s*) minC(si) 。组合优化往往涉及排序、分类、筛选等问题,它是运筹学的一个重要分支3。典型的组合优化问题有旅行商问题(Traveling Salesman ProblemTSP)、加工调度问题 (Scheduling Problem,如Flow-Shop,Job-Shop) 、
22、0-1背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem)、图着色问题 (Graph Coloring Problem)、聚类问题(Clustering Problem)等。这些问题描述非常简单,并且有很强的工程代表性,但最优化求解很困难,其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间,以致根本不可能在现有计算机上实现,即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。组合优化问题在实践中有着广泛的应用,同时也是计算机科学中的重要研究课题4。2.4 蚁群算法及其它算法原理2.4.1蚁群优化算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法 TSP 问题 中的 应用 研究 毕业设计 论文
链接地址:https://www.31ppt.com/p-3971989.html