毕业论文模拟退火算法在旅行商问题中的应用

1、设计（论文）题目：模拟退火算法在旅行商问题中的应用1毕业设计（论文）的主要内容及基本要求主要内容：利用模拟退火算法和MATLAB工具箱建立求解TSP问题的模型，并在多项式时间内找到TSP问题的最优解。基本要求：1)熟读参考文献；2)掌握模拟退火算法的基本理论和结构；3)能够利用MATLAB工具箱建立模型。2指定查阅的主要参考文献及说明1)MATLAB在数学建模中的应用（卓金武主编）；它以数学建模为主，比较全面的讲解了模拟退火算法以及MATLAB的相关知识;2)神经网络、模糊系统及其在运动控制中的应用（丛爽主编）；它主要系统的讲述了模拟退火算法的理论知识，全面的介绍的模拟退火算法的模型以及相关知

2、识;；3)基于MATLAB的模拟退火算法的实现（曲强，陈雪波）阐述了模拟退火算法的基本原理及实现过程，运用MATLAB语言实现模拟退火算法，并将其用于解决TSP问题。3进度安排12345设计（论文）各阶段名称确定论文题目，接受任务查阅文献资料，完成文献综述和开题报告完成论文初稿修改并完成论文直至定稿论文答辩起止日期2012年3月15日2012年3月25日2012年5月12日2012年5月23日2012年5月29日注：本表在学生接受任务时下达摘要摘要旅行商问题（即TSP问题）是组合优化中著名的NPhard问题,而模拟退火算法在处理全局优化、离散变量优化等困难问题中，具有传统优化算法无可比拟的势，

3、因此它也是解决TSP的有效方法之一。这里介绍和描述模拟退火算法的原理及其基本框架结构，并应用模拟退火算法对TSP问题进行研究,给出用模拟退火算法求解TSP问题的具体实现方法，同时为MATLAB语言编程提供了程序设计思路，并且分析说明模拟退火算法的优缺点。关键词：模拟退火算法;组合优化;旅行商问题;MATLABIABSTRACTABSTRACTTravelingsalesmanproblem（TSP）isafamousNP-hardprobleminthetheoryofcombinationoptimization.However,simulatedannealingalgorithmhaso

4、bviouscomparativeadvantageinsolvingthedifficultproblems,suchasglobaloptimizationanddiscretevariablesoptimization.SosimulatedannealingalgorithmisaneffectivemethodforsolvingTSP.Frameworkandprincipleofsimulatedannealingalgorithmweredescribed,computationalmethodtosolveTSPproblemwasgiven,programdesignide

5、asoftheMATLABprogramminglanguagewereprovidedaswell,andtheadvantagesanddisadvantagesofsimulatedannealingalgorithmwerealsoshowninthispaper.Keywords:simulatedannealingalgorithm;combinatorialoptimization;travelingsalesmanproblem;MATLABII目录目录摘要.IABSTRACT.II目录.III第一章前言.1第二章模拟退火算法及其应用.32.1Metropolis准则与模拟退火

6、算法5.32.1.1Metropolis准则.32.1.2模拟退火算法.42.2模拟退火算法的原理.42.2.1物理退火过程.52.2.2模拟退火的原理和物理退火的原理的相似性.52.3模拟退火算法模型.62.3.1模拟退火算法的基本思想.62.3.2算法新解的产生和接受.72.3.3冷却进度表.82.4模拟退火算法的应用.8第三章旅行商问题.103.1组合优化问题简述.103.2TSP问题简述.113.2.1TSP问题的基本概念.113.2.2TSP问题的发展趋势.113.2.3旅行商问题的应用.12第四章基于模拟退火算法求解TSP问题.144.1TSP问题的模拟退火算法实现.144.1.1

7、TSP算法描述.144.1.2TSP算法流程.164.2TSP问题的MATLAB实现16.174.2.1选取初始点并初始化变量.17III目录4.2.2固定温度的模拟退火子函数.174.2.3降温继续优化过程.194.3实例仿真17.194.3.1N=10的TSP模型.204.3.2N=20的TSP模型.21第五章结论.23参考文献.24致谢.26附录.27文献综述.35IV四川理工学院毕业论文第一章前言在生物医药、组合概率、分子物理、电子工程、模式识别、图象处理等众多科技领域中存在大量的组合优化问题(CombinatorialOptimizationProblem)，其中很多的问题至今都没有

8、找到有效的算法.这些优化问题的目标函数大部分都是非凸的，存在很多局部最优解.这些问题已经被证明是NP难问题，其中的旅行商(TravelingSalesmanProblem，TSP)问题就是最经典的一个NP难问题1，其求解时间随问题规模呈指数级增长,当规模稍大时就会因时间限制而失去可行性(Feasibility)。就以目前已成熟的数值计算理论和算法，或者根本无法求解，或者其求解的计算量是爆炸的，其花费的代价将是人们所不接受的2。旅行商问题(TravelingSalesmanProblem,简记为TSP)又译为旅行推销员问题、货郎担问题，是一个典型的NP完全问题，涉及求多个变量的函数的最小值。它可

9、简单地描述为:对于N个城市，它们之间的距离已知，有一旅行商要从某一城市出发走遍所有的城市，且每一个城市只能经过一次，最后回到出发城市，问如何选择路线可使他所走过的路程最短。这与我们外出旅游十分相似，TSP问题中对每个城市都访问一次对应于旅游问题中对每个景点都游览一遍。因此，可以说TSP问题代表了一类组合优化问题，因而探讨TSP问题的有效求解方法有着广泛的应用前景，如旅游问题、电子地图、运输线路、电器布线、计算机联网等3。TSP问题表面看很简单，其实不然。当TSP问题的规模为N个城市时，可行解集中的路径数为(N-1)!/2,要从(N-1)!/2个可行解中找出哪条路径最短，若以路径间的比较为基本操

10、作，则需进行的基本操作数是(N-1)!/2-1,随N的不断增长，将出现“指数爆炸”现象。若用每秒运算一亿次的计算机,N=10时只需0.0018秒,N=20时就需19年,N=30时则猛增为1.41015年！显然，这样求TSP问题的方法是不可行的。模拟退火算法(SimulatedAnnealingAlgorithm，简称SAA)为求解上述传统方法难处理的问题提供了一个有效的途径和通用框架，并逐渐发展成一种迭代自适应启发式概率性搜索算法。用以求解不同的非线性问题;对不可微甚至不连续的函数优化，SAA能通过Metropolis接受准则概率接受劣化解并以此跳出局部最优，通过温度更新函数的退温过程进行趋化

11、式搜索并最终进入全局最优解集，从而以较大概率求得全局优化解;具有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性;并且能处理不同类型的优化1第一章前言设计变量(离散的、连续的和混合型的);不需要任何的辅助信息，对目标函数和约束函数没有任何要求。利用Metropolis算法并适当地控制温度下降过程，在优化问题中具有很强的竞争力，因此研究SAA算法在优化中的应用显得尤为重要4。本文就应用SAA解决TSP问题，并针对典型的TSP问题，应用MATLAB语言给出了这一方法的具体实现过程,在此基础上对旅行商问题的仿真运行结果说明了方法和编程的正确性。2四川理工学院毕业论文第二章模拟退火算法及其应用模拟退

12、火算法（SimulatedAnnealingAlgorithm，简称SAA）也是一种适合解大规模组合优化问题，特别是解NP完全问题的通用有效的全局优化解法，它与其他近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高和较小受初始条件限制等优点，而且特别适合并行运算。模拟退火算法是将组合优化问题与统计力学中的热平衡问题类比，找到求解优化问题的新方法。对固体问题进行退火时，通常先将它加温熔化，使其中的粒子可以自由运动，然后随着温度的逐渐下降，粒子也逐渐形成了低能态的晶格。若在凝固点附近的温度下降足够慢，则固体物质一定会形成最低能态的基态。对于组合优化问题来讲，也有这样类似的过程。1982年，

13、Kirkpatrick等将退火思想引入组合优化领域，提出一种解大规模组合优化问题，尤其是NP完全组合优化问题的有效近似算法模拟退火算法。它是通过对固体退火过程的模拟，采用Metropolis接收准则，并用一组成为冷却进度表的参数控制算法进程，是算法在多项式时间里给出一个近似最优解。2.1Metropolis准则与模拟退火算法52.1.1Metropolis准则从物理学有关知识知道，固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法进行模拟。MonteCarlo方法的特点是算法简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。从物理系统倾向于能量较低的状态，而热运动又妨碍它

14、准确落入最低态的原理触发，所以采样时着重去那些有重要贡献的状态，这样才能够较快地达到较好的结果。1953年，Metropolis等提出来重要性采样法。他们用以下方法产生固体的状态序列：首先给定以粒子相对位置表征的初始状态i，作为固体的当前状态，该状态的能量是错误!未找到引用源。；然后用摄动装置使随机选取的某个粒子的位移随机地产生一个微小的变化，得到一个新的状态j，新状态的能量是错误!未找到引用源。；如果错误!未找到引用源。，则该新状态就作为“重要”状态，如果错误!未找到引用源。，则要考虑热运动的影响，该新状态是否可以作为“重要”状态，得依据固体处于该状态的几率来判断。而固体处于状态i和j的几率

15、的比值等于相应Boltzmann因子的比值P，即：3第二章模拟退火算法及其应用(2-1)其中，P是一个小于1的数。用随机数发生器产生一个0,1区间的随机数random，若Prandom，则新状态j作为重要状态，否则舍去。若新状态j是重要状态，就以j取代i成为当前状态，否则仍以i为当前状态。重复以上新状态的产生过程，在经过大量固体状态的如此变换后，系统逐渐趋于能量较低的平衡状态，固体状态的概率分布趋于指数形式的正态分布。其中，接受新状态的准则称为Metropolis准则，相应的算法称为Metropolis算法。2.1.2模拟退火算法1982年，Kirkpatrick等首先意识到固体退火过程与组合

16、优化问题之间存在的类似性，加上Metropolis等对固体在恒定温度下达到热平衡过程的模拟给他们以启迪：应该将Metropolis准则引入到优化过程中来。最终他们得到了一种对Metropolis算法进行迭代的组合优化算法，这种算法模拟固体退火过程，称为“模拟退火算法”(SimulatedAnnealingAlgorithm，简称SAA)。2.2模拟退火算法的原理模拟退火算法(SAA)来源于物理热力学原理,综合了固体退火与组合优化之间的类似性6，是模拟熔化状态下物体由逐渐冷却至最终达到结晶状态的物理过程。模拟退火算法是利用问题的求解过程与熔化物体退火过程的相似性，采用随机模拟物体退火过程来完成问

17、题的求解，也就是在控制参数(温度)的作用下对参数的值进行调整，直到所选取的参数值最终使能量函数达到全局极小值。模拟退火算法是近年来在国内外都比较受关注的算法。它的思想最早是由Metropolis等人于1953年提出的7，在1983年被Kirkpatrick等人成功引入组合优化领域。由于它具有很强的实用性和极佳的性能表现，迅速引起了很多专家学者的兴趣，不断对其进行研究。模拟退火算法主要应用在各种优化问题上，函数优化是其中非常重要的一个方面。NP问题是一个比较麻烦的问题，其解的规模随问题规模的增大而成指数级增长，对于一般的方法而言，当问题规模过大时，就失去了可行性。模拟退火作为一种随机算法，它的特

18、点非常适于求解NP问题，比如著名的旅行商问题(TravelingSalesmanProblem)。模拟退火算法在解决这类问题上有着优异的表现。4四川理工学院毕业论文2.2.1物理退火过程模拟退火算法是一种通用的优化算法，其物理退火过程由以下三部分组成:(1)加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。(2)等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡状态。(3)冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。其中，加温过程对

19、应算法的设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。这里能量的变化就是目标函数，我们要得到的最优解就是能量最低态。其中Metropolis准则是SAA算法收敛于全局最优解的关键所在，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。2.2.2模拟退火的原理和物理退火的原理的相似性模拟退火是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火来自冶金学的专有名词淬火。模拟退火的原理和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间

20、内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一部先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。其相似性比较如下表：表2-1组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程5第二章模拟退火算法及其应用续表2-1Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量2.3模拟退火算法模型模拟退火算法可以分解为解空间、目标函数和初始解三部分。解空间：它为问题的所有可能（可行的或者不可行的）解的集合，它限定了初始解选取和新解产生的范围。在许多组合优化问题中，一个解除了满足目标最优化的要求外，还必

21、须满足一组约束，因此在解集中往往可能包含一些不可行解，为此，可以限定解空间仅为所有可行解的集合，即在构造解时就考虑到对解的约束，这可以通过在目标函数中加上所谓的惩罚函数以”惩罚“不可行解的出现。目标函数：组合优化问题的目标是从组合问题的可行解集中求出最优解。优化问题有三个基本要素：变量、约束和目标函数。在求解过程中选定的基本参数称为变量，对变量取值的各种限制称为约束，表示可行方案衡量标准的函数称为目标函数。目标函数的选取必须正确体现对问题的整体优化要求。此外，目标函数式应当是容易于计算的。初始解：它是算法开始迭代的起点。初始解的选取应当使得算法导出比较好的最终解。不过，大量实验表明，模拟退火算

22、法的最终解并不十分依赖初始解的选取。2.3.1模拟退火算法的基本思想2.3.1.1基本思想(l)选S作为初始状态，令S0S，同时设初始温度T，令i=0；00(2)令TT，以T和S调用Metropolis抽样算法，返回状态S作为本算法的当前解，iiSS；i(3)按照一定方式降温，即TT,其中TT,i=i+1;i1ii1(4)检查终止条件，如果满足则转步骤(5),否则转步骤(2);6四川理工学院毕业论文(5)当前解S为最优解，输出结果，停止。i2.3.1.2Metropolis抽样算法描述8(1)令k=0时，当前解S0S，在温度T下，进行以下各步操作；(2)按某个规定的方式根据当前解S(k)所处的

23、状态S产生一个近邻子集N(S(k)+S，从N(S(k)中随机得到一个新状态S作为下一个候选解，计算能量之差：C=C(S)-C(S(k)；(3)如果eqoac(,C)0，则接受S作为下一个当前解，否则，以概率exp(-C/T)接受S作为下一个当前解。若S被接受，则令S(k+1)=S，否则S(k+1)=S(k)；(4)k=k+1，检查算法是否满足终止条件，若满足，则转步骤(5)，否则转步骤(2):(5)返回S(k)，结束。2.3.2算法新解的产生和接受模拟退火算法新解的产生和接受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选

24、择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropolis准则:若C0则接受S作为新的当前解S，否则以概率exp(-C/T)接受S作为新的当前解S。第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解

25、时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。7第二章模拟退火算法及其应用模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。2.3.3冷却进度表它是用于控制算法进度的一组参数的集合，包括控制参数的初始值及其衰减函数。对应的Mapkob链的长度和停止准则。冷却进度表的选取是算法性能的主要因素。2.4模拟退火算法的应用模拟退火算法最早由Kirk

26、patrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。基于SAA算法的一些实用系统已经问世，面简要介绍一些主要的应用领域：1）模拟退火算法在函数优化领域中的应用函数优化不仅是模拟退火算法的经典应用领域，而且各类复杂的测试函数也是对模拟退火算法进行性能评价的依据。另外，对于一些使用其他优化方法很难求解的非线性、多目标函数优化问题，应用模拟退火算法一般可以得到满意的优化结果。2）模拟退火算

27、法在VLSI设计中的应用9利用SAA算法进行VLSI的最优设计，是目前SAA算法最成功的应用实倒之一。用SAA算法几乎可以很好地完成所有关于优化的VLSI设计工作，如全局布线、布板、布局和逻辑最小化等等。实践证明，SAA算法在解决这些问题时给出了很好的结果，优于传统算法所得到的结果。3）模拟退火算法在神经网计算机中的应用SAA算法由于具有跳出局部最优陷阱的能力，因此被D.H.Ackley等人用作Boltzmann机拘学习算法，从而使Boltzmana机克服了Hopfeld神经网模型的缺点（即经常收敛到局部最优值)。在Boltzmann机中，即使系境落人了局部最优的陷阱，经过一段8四川理工学院毕

28、业论文时间后，它还能再跳出来，使系统最终将往全局最优值的方向收敛。4）模拟退火算法在图象处理中的应用SAA掉法可用来进行图象恢复等工作，即把一幅被污染的图象重新恢复成清晰的原圈，滤掉其中被畸变的部分S.Geman等人的实验结果表明，SAA算法不但可以很好地完成图象恢复工作，而且它还具有很大的并行性。因此它在图象处理方面的应用前景是广阔的。5）模拟退火算法在自动控制领域中的应用模拟退火算法在参数辨识、模糊控制器的优化设计、模糊控制规则的学习中的应用取得了很显著的成果。另外，模拟退火算法在航空控制系统的优化、空间交会控制器的设计、故障诊断和机器人行走路径规中的应用也取得了成功。6）模拟退火算法在社

29、会与经济领域中的应用基于模拟退火算法的基本思想，软件开发人员设计了很多的软件包，服务于各类社会和经济行业，比如金融系统和股票投资分析行业。7）模拟退火算法的其它应用除了上述应用外，SAA算法还用于人工智能与科学计算。因为很多求解问题的复杂性，往往得不到问题的解析解，人们尝试运用各种算法求出最优解的近似解来逼近最优解。模拟退火算法是这类算法中一种典型的方法，被广泛应用在很多问题求解中。例如本文给出了模拟退火算法在旅行商问题中的应用实例，如果将优化结果应用在旅游业中，能从很大程度上降低旅游的成本，具有很好的经济应用价值。9第三章旅行商问题第三章旅行商问题TSP(TravelingsalesmanP

30、roblem,旅行商问题)是指给定n个城市和各城市间的距离,要求确定一条经过各个城市当且仅当一次的最短路线。它是一种典型的组合优化问题,其最优解的求解代价是指数级的。已经证明TSP问题是一个NP-hard问题。基于智能优化算法求解TSP问题,是近年来刚刚兴起的热门课题。然而在科学管理与经济决策的许多应用领域中,现实世界存在着大量的多目标优化问题。对于旅行商问题(TravelingSalesmanProblem,TSP),实际中经常要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、合理的解都是比较复杂的问题。3.1组

31、合优化问题简述伴随着计算机技术的飞速发展，计算机正日益成为人们解决问题的不可缺少的重要工具。但是在实践中人们发现，存在这样一类问题，运用精确的算法在多项式时间内无法找到问题的最优解，这类问题称为组合优化问题。这类问题通常随着问题规模的扩大，问题空间呈现组合爆炸特征，求解问题的空间、时间复杂度将呈指数级增长，使用常规的方法求解，在现有条件下是无法实现的，属于NP完全问题。旅行商问题（TSP）就是其中最经典的问题之一。组合优化问题发展的初期，研究一些比较实用的基本上属于网络极值方面的问题，如广播网的设计、开关电路设计、航船运输路线的计划、工作指派、货物装箱方案等。自从拟阵概念进入图论领域之后，对拟

32、阵中的一些理论问题的研究成为组合规划研究的新课题，并得到应用。现在应用的主要方面仍是网络上的最优化问题，如最短路问题、最大（小）支撑树问题、最优边无关集问题、最小截集问题、推销员问题等10。组合优化（CombinatorialOptimization问题的目标是从组合问题的可行解集中求出最优解，通常可描述为：令s1，s2，sn为所有状态构成的解空间，C(si)为状态si对应的目标函数值，要求寻找最优解s*，使得对于所有的si，有C(s*)minC(si)。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支11。典型的组合优化问题有旅行商问题（TravelingSalesmanPr

33、oblem，TSP）、加工调度问题（SchedulingProblem，如Flow-Shop，Job-Shop）、0-1背包问题（KnapsackProblem）、装箱问题（BinPackingProblem）、图着色问题（GraphColoringProblem）、聚类问题10四川理工学院毕业论文（ClusteringProblem）等。这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。

34、组合优化问题在实践中有着广泛的应用，同时也是计算机科学中的重要研究课题12。3.2TSP问题简述3.2.1TSP问题的基本概念旅行商问题（TravelingSalesmanProblem,TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，由爱尔兰数学家SirWilliamRowanHamilton和英国数学家ThomasPenyngtonKirkman在19世纪提出的数学问题,它是指给定n个城市并给出每两个城市之间的距离,旅行商必须以最短路径访问所有的城市一次且仅一次,并回到原出发地,现已证明它属于NP难题。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。历史上的

35、第一个正式用来解决TSP问题的算法诞生于1954年,它被用来计算49个城市的TSP问题。到现在为止,运用目前最先进的计算机技术可解决找出游历24,978个城市的TSP问题。TSP问题是组合优化领域中的一个典型问题，涉及求多个变量的函数的最小值。虽然它陈述起来很简单，但求解却很困难，它一直是运筹学中最富挑战性的问题之一，并且已经被证明是NP完全问题。对于具有N个城市的TSP问题，其可能的路径数目为(N-1)!/2-1，至今尚未找到有效的求解方法，在理论上枚举法可以解这一问题，但是当N较大时，解题的时间消耗会使枚举法显得没有任何实际价值。因此利用启发式算法，在较短的时间内，求得问题的满意解，就成为

36、许多学者研究的重点13。3.2.2TSP问题的发展趋势TSP问题的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。1948年，美国RAND公司引入TSP问题，该公司的声誉以及线形规划这一新方法的出现使得TSP问题成为一个知名且流行的问题。此外，哈密尔顿于1856年推出了11第三章旅行商问题二十城游戏(LcosianGame)。TSP问题在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？这个描

37、述之所以称为中国邮递员问题（ChinesePostmanProblem,CPP）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。TSP问题是经典的NPHard组合优化问题之一,求解该问题的启发式算法一直是数学、计算机科学研究的热点之一。目前求解TSP问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、Hopfield神经网络算法、蚁群算法等,各种算法各有千秋。模拟退火算法最早思想由Metropolis在20世纪1953年提出,1983年Kirkpatrick等成功地将退火思想引入组合优化领域。模拟退火算法是局部搜索算法的扩展,理论上来说,它是一个全局最优算法。如何在初始

38、解附近找出一个“最优的解”是一项关键技术,它直接影响算法的收敛速度。对于用模拟退火算法对求解旅行商组合优化问题做来了在满足模拟退火算法全局收敛性的情况下，子排列反序并移位抽样方式对求解NP完全问题是非常有效的。事实上，很多实际问题，经过简化处理后均可转化为TSP问题，对TSP问题求解方法的研究具有重要的应用价值。人们在努力寻找大维数最优化算法的同时，构造出了许多近似求解法，如遗传法、局部搜索算法、蚁群算法等，特别是提出了如模拟退火等用统计方法近似求解TSP的随机算法，为人们求解TSP问题开辟了新的途径14。3.2.3旅行商问题的应用TSP问题是一种典型的组合优化问题,其最优解的求解代价是指数级

39、的。已经证明TSP问题是一个NP-hard问题。基于智能优化算法求解TSP问题,是近年来刚刚兴起的热门课题。然而在科学管理与经济决策的许多应用领域中,现实世界存在着大量的多目标优化问题。对于旅行商问题(TravelingsalesmanProblem,TSP),实际中经常要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素。下面举几个实例：1）车辆选路。一个经典的路由问题是在一个网络上发现从源节点到一个目的节点的最佳交通线路，使与距离成比例的流动费用降低到最小。这个问题的关键是在交通网12四川理工学院毕业论文络上计算从源节点到目的节点之间的最短路径。对这个最小费用流动问题

40、进行扩展，就构成TSP问题，在这个问题中，车辆从源点出发访问多个目的地并且最后回到源点。2）电路板钻孔进度的安排。机器在电路板上钻孔的调度问题是TSP应用的经典例子，在一电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游。把这个问题转化为TSP，孔相当于城市，转头从一个孔移到另一个孔所耗的时间相当于TSP中的旅费。3）基因测序。Cnoocdre是一种求解旅行商问题的程序。美国国家卫生机构的研究人员利用这一程序来进行基因测序。在这一应用DNA片断作为城市，它们之间的相似程度作为城市与城市的距离。研究人员试图寻找一种可能性最高的连接方式把这些DNA片断合成为整张DNA。4）

41、半导体制造厂家使用CONCORDE(一种主要用于计算TSP的程序代码)中链式LinKemighan启发式样算法来优化整个电路的扫描链路。用来检测的扫描链路包含在一个芯片当中，它可以最小化时间或者能量的消耗。更重要的是，TSP问题提供了一个研究组合优化问题的理想平台。很多组合优化问题，比如背包问题、分配问题、车间调度问题，和TSP问题同属NP-Hard类，它们难度同等，如果其中一个能用多项式确定性算法解决，那么其他所有NP-Hard类问题也能用多项式确定性算法解决。很多方法都是从TSP发展起来的，后来推广到其他NP-Hard类问题上去15。13第四章基于模拟退火算法求解TSP问题第四章基于模拟退

42、火算法求解TSP问题TSP是经典的组合优化问题之一，而模拟退火算法实际上是一种随机搜索算法，即在相应的解空间内随机地产生新解并对其进行取舍。但不同于一般的随机搜索算法，模拟退火算法允许接受使目标函数增大的新解，其优点在于能跳出局部极小值，而有利于在多项式时间内求得全局最小值，即近似最优解。将TSP与模拟退火算法相结合，不失为求解TSP问题的有效方法之一。4.1TSP问题的模拟退火算法实现在第一章中，我们知道TSP问题是数学领域中著名的NP-Hard问题之一，其数学表示如下：i设有N个城市和距离矩阵Ddij，其中，d表示城市i到城市j的距离，、j=1，ij2，3，n，求遍访每一个城市恰好一次的一

43、条回路，并且其路径长度最短。4.1.1TSP算法描述4.1.1.1TSP问题的解空间和初始解TSP的解空间S是遍访每个城市恰好一次的所有回路，是所有城市排列的集合。TSP问题的解空间S可表示为1,2,n的所有排列的集合，即S=(c1,c2,cn)|(c1,c2,cn)为1,2,n的排列），其中每一个排列Si表示遍访n个城市的一个路径，ci=j表示在第i次访问城市j。由于模拟退火算法的最优解与初始状态无关，故初始解为随机函数生成一个1,2,n的随机排列作为S0，即初始解S0=1,2,n。4.1.1.2目标函数TSP问题的目标函数即为访问所有城市的路径总长度，也可称为代价函数：nCc,c,，c1d

44、c,cdcc12nii11,n（4-1）i1现在TSP问题的求解就是通过模拟退火算法求出目标函数C(c1,c2,cn)的最小值，相应地，s*=(c*1,c*2,c*n)即为TSP问题的最优解。14四川理工学院毕业论文的定义为：NijSj可由i经一次k变换得到，其中i和j分别是给定的实例4.1.1.3新解产生我们在描述新解产生的方法之前，先来定义一个TSP的k变换领域：定义4.1（TSP的k变换领域（k2）设N是一个k变换领域结构，则k变换领域kk的两个不同的解5。其实，所谓的k变换是将i对应的路径去掉k条边，再用另外k条边放入，已得到j对应的路径。新解的产生对问题的求解非常重要。新解可通过分别

45、或者交替用以下2种方法产生(设i为旧解，j为新解)：二变换法：任选序号u,v(设uvn)，交换u和v之间的访问顺序，若交换前的sc,c,c,c,c,c,c,c,c解为sc,c,c,c,c,交换后的路径为新路径，即：i12uvnj12u1vv1u1uv1n(4-2)二变换的邻域规模:1n1n22若交换前的解为sic1,c2,cu,cv,cw,cn，交换后的路径为的新路三变换法：任选序号u,v和(uv)，将u和v之间的路径插到之后访问，径为：sc,c,c,c,c,c,c,c,c,cj12u1v1v2wuvw1n（4-3）三变换的邻域规模:1n1n2n32无论是二变换法还是三变换法，新解产生的概率都

46、服从均匀分布。4.1.1.4目标函数差目标函数数差是指计算变换前的解和变换后目标函数的差值，即cc(sj)-c(si)4.1.1.5Metropolis接受准则根据目标函数的差值和概率exp(-C/T)接受si作为新的当前解si，接受准则：15第四章基于模拟退火算法求解TSP问题p1,c0exp(c/T)c0（4-4）4.1.2TSP算法流程根据以上对TSP的算法描述，可以写出用模拟退火算法解TSP问题的流程图2-1所示：选择初始路径X0确定初始温度T0当前路径Xi=X0当前温度Ti=T0从Xi的邻域中随机选择Xi，计算Xi与Xj的路程差c=c(Xj)-c(Xi)crandom(0,1)NYY

47、当前路径Xi=XjN跳出内循环当前温度Ti下降Y跳出外循环Y结束图2-1TSP的模拟退火流程N16四川理工学院毕业论文4.2TSP问题的MATLAB实现16TSP问题是指旅行商轮流到N个城市去旅行，每个城市只去一次，再回到原出发城市的最短路径。4.2.1选取初始点并初始化变量首先选取一个优化的初始点，优化初始点可以随机选取也可以根据经验选取。我们这里随机选取一个初始点，其程序如下：fori=1:Nforj=1:NDistance(i,j)=norm(Location(i,:)-Location(j,:);endendPath=randperm(N);Energy=sum(Distance(Pa

48、th-1)*N+Path(1:N)Path(1);在上述程序中，首先要根据需要旅行的城市总数N和各城市的位置矩阵Location计算各城市之间的距离，然后用MATLAB函数randperm随机产生一条旅行路线，最后计算该路线的总长度Distance。4.2.2固定温度的模拟退火子函数当温度值比较高时，可利用生成函数确定新的搜索点。一般MATLAB常用的生成函数有：Boltzman机使用的高斯密度函数，Cauchy机使用的Cauchy分布函数等。当然为了方便确定新数据是否能够被接受，必须选择一个适当的接受函数。functionMaxE，MinE，Path=Annealing(Path，Energ

49、y，Temp，MaxE，MinE)Trial.N=0；WhileTrial.NMaxTrial.N17第四章基于模拟退火算法求解TSP问题yEnergyxxy2NewPath=Path;Index=dell(rand(2,1)*N);Temp=NewPath(Index);NewPath(Index(1,1)=Temp(1,2);NewPath(Index(2,1)=Temp(1,1);NewEnergy=sum(Distance(NewPath-1)*N+NewPath(2:N)NewPath(1);ifrandStopToleranceMaxE，MinE=Annealing（Path，En

50、ergy，Temp，MaxE，MinE）；Temp=Temp*TempRatio；end其中，(MaxE-MinE)/MaxE为路径相对误差，StopTolerance为停止误差。由以上的程序可知，采用旅行路径最大值与最小值之间的相对误差为停止推理条件，即(MaxE-MinE)/MaxE89101245320四川理工学院毕业论文4.3.2N=20的TSP模型利用模拟退火算法求解如下20个城市的TSP问题，如表4.2所示表4.1N=20城市坐标表城市点X坐标Y坐标城市点X坐标Y坐标10.66830.2536110.55340.323420.61950.2634120.45430.235330.4

51、0000.4439130.76450.457840.24390.1463140.46320.613550.17070.2293150.35250.754360.22930.7610160.23640.477270.51710.9414170.64270.575380.87320.6536180.14630.743790.68780.5219190.83360.4525100.84880.3609200.65370.2557运行结果如下：最优解为：Columns1through1419138714151654121318621第四章基于模拟退火算法求解TSP问题Columns15through2

52、01722091110最短距离：4.879522四川理工学院毕业论文第五章结论模拟退火算法是将物理退火过程与组合优化相结合的一种随机迭代寻优算法，TSP问题即旅行商问题是一个组合优化问题，该问题被证明具有NPC计算复杂性，因此研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。而利用MATIAB对求解TSP问题的模拟退火算法程序进行仿真，实验结果结果表明：首先，模拟退火算法能够多项式时间内找到TSP问题的最优解，说明了该算法的正确性、有效性和实用性；其次，说明了利用模拟退火算法求解TSP问题是可行有效的，但当TSP求解的城市规模增大时，找到最优解的次数也在降低；同时，也表明了

53、在理论上，模拟退火算法在某一温度下，只要计算时间足够长，就可以保证以概率1收敛于全局最优解。但在算法的实现过程中，由于计算速度和时间的限制，往往在优化结果和计算时间之间存在着矛盾，这是有待我们解决的。但模拟退火算法在解决中小规模组合优化问题上的优势是显而易见的。用模拟退火算法能够较好地求解旅行商问题。因而理论上能够找到最优解，但实际使用过程中诸多的参数如起始温度，温度下降速率，迭代次数等都需要人为的测试和调整，而这些参数将直接影响能否搜索到最优解，所以模拟退火算法仍然存在一些缺点。本次毕业设计也存在一些缺点，如程序运行太简陋没有详细的最优化路线图，但总体上还是达到了课题的要求。23致谢参考文献

54、1周杰明，邓迎春，黄娅，一种带记忆的模拟退火算法求解TSP问题，湖南文理学院学报（自然科学版），湖南，湖南师范大学，2010，22(2):70_732冯剑，岳琪，模拟退火算法求解TSP问题，森林工程，哈尔滨，东北林业大学，2008，20(1):94_963兰兆青，Hopfield神经网络在TSP问题中的应用，硕士学位论文，中北大学，2008:24杨若黎，顾基发,一种高效的模拟退火全局优化算法J，系统工程理论与实践，1997，17(5):30_33.5丛爽，神经网络、模糊系统及其在运动控制中的应用，中国科学技术大学出版社，2001:224_2256李香平,张红阳,模拟退火算法原理及改进,软件导刊

55、,2008,7(4):47_487杨建刚，人工神经网络实用教程，浙江大学出版社，2001:928刘燕德，无损智能检测技术及应用，华中科技大学出版社.20079姚新，陈国良，模拟退火算法及其应用，计算机研究与发展，合肥，中国科学拄术大学，1990,7:1_910汪定伟.智能优化方法M，北京：高等教育出版社，200711田景文，高美娟.人工神经网络算法研究及应用M,北京：北京理工大学出版社，200612雷德明，严新平编著.多目标智能优化算法及其应用M，北京：科学出版社，200913鄢克雨Hopfield神经网络的稳定性分析D。电子科技大学200414严晨，王直杰，以TSP为代表的组合优化问题研究现

56、状与展望，计算机仿真24参考文献J，2007，24(6):171_17315陈志平，徐宗本,计算机数学计算复杂性理论与NPC、NP难题的求解M.北科学出版社，200116曲强，陈雪波，基于MATLAB的模拟退火算法的实现，鞍山科技大学学报.2003.26(3):196_19917卓金武，MATLAB在数学建模中的应用，北京航空航天大学出版社，201125致谢致谢首先感谢高媛媛老师，她在论文选题及研究过程中给予我悉心的指导和帮助，高老师平易近人，做事认真负责。在此也要感谢这四年里教授我知识的所有老师和辅导员，他们不仅给我传授了基本的学习本领，更重要的是帮助我树立正确的人生观、价值观和优良的品德。

57、在我感到迷茫时，老师们的开导指引；在我遇到专业问题时，老师们的悉心指导，尤其是在我学习的过程中所有老师给予我的不记报酬的帮助，我将铭记于心。感谢我朝夕相处的兄弟们，让我感受到家的温暖，毕业了我们要为各自的理想去努力开始人生新的篇章。最后，我要感谢我最亲爱的父母，是他们让我在漫长的求学道路上不感到孤单，让我在拼搏和奋斗的历程中不感到疲倦。感谢我的女友，陪我走过了奋斗的每一天。26附录附录程序一：clearclca=0.99;t0=97;tf=3;t=t0;Markov_length=10000;coordinates=10.66830.2536;20.61950.2634;30.40000.44

58、39;40.24390.1463;50.17070.2293;60.22930.7610;70.51710.9414;80.87320.6536;90.68780.5219;100.84880.3609;coordinates(:,1)=;amount=size(coordinates,1);dist_matrix=zeros(amount,amount);coor_x_tmp1=coordinates(:,1)*ones(1,amount);coor_x_tmp2=coor_x_tmp1;coor_y_tmp1=coordinates(:,2)*ones(1,amount);coor_y_t

59、mp2=coor_y_tmp1;dist_matrix=sqrt(coor_x_tmp1-coor_x_tmp2).2+.(coor_y_tmp1-coor_y_tmp2).2);sol_new=1:amount;E_current=inf;E_best=inf;sol_current=sol_new;sol_best=sol_new;p=1;whilet=tf27附录forr=1:Markov_lengthif(rand0.5)ind1=0;ind2=0;while(ind1=ind2)ind1=ceil(rand.*amount);ind2=ceil(rand.*amount);endtm

60、p1=sol_new(ind1);sol_new(ind1)=sol_new(ind2);sol_new(ind2)=tmp1;elseind1=0;ind2=0;ind3=0;while(ind1=ind2)|(ind1=ind3).|(ind2=ind3)|(abs(ind1-ind2)=1)ind1=ceil(rand.*amount);ind2=ceil(rand.*amount);ind3=ceil(rand.*amount);endtmp1=ind1;tmp2=ind2;tmp3=ind3;if(ind1ind2)&(ind2ind3);elseif(ind1ind3)&(ind3