模拟退火算法求解TSP问题.doc

模拟退火算法在TSP问题中的应用研究摘 要旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。TSP问题是一个典型的NP 完全问题,模拟退火算法是求解此问题的一种比较理想的方法。模拟退火算法是迭代求解策略的一种随机寻优算法，TSP问题即旅行商问题是一个组合优化问题，该问题被证明具有NPC计算复杂性。因此，研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。本文主要阐述了模拟退火算法的原理以及退火算法在函数优化问题上的应用和优化组合问题的研究，以便来了解TSP问题以及如何应用模拟退火算法解决实际问题上，帮助理解模拟退化算法的基本原理及其在TSP问题求解中的应用。关键词模拟退火算法；TSP；NPC；组合优化ABSTRACTInto TSP problem, the problem of travelling merchants （ traveling salesman ） and the problem of travelling canvasser venterlast problem, the problem, in the field of mathematics. TSP problem famous one problem is a typical NP, impersonate all annealing algorithm is the solution of the problem of a rather ideal method.Simulation of annealing the algorithm is not an iterative the solution of a random TSP problem, this algorithm for the travel company is a combination of optimization problem. The question was shown to the complexity of the NPC. Thus, research on degradation is the basic principle of the TSP problem and solution of the application by a high degree of concern.This article focuses on the principle of 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 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 WORDSSAA；TSP；NPC；Combinatorial Optimization 1目 录摘 要1ABSTRACT1第一章引言21.1 TSP问题的基本概念21.2 模拟退火算法的背景21.3 发展前景3第二章 2.1模拟退火算法的原理42.1.1 模拟退火的基本思想42.1.2 算法对应动态演示步骤42.2 TSP问题简述5第三章 问题描述与算法分析研究63.1应用研究整体规划63.2应用开发环境63.2.1开发语言63.2.2开发平台63.3 TSP问题的描述和分析73.4模拟退火算法的分析73.4.1模拟退火算法模型73.4.2模拟退火算法与优化问题分析83.5应用研究方案分析8第四章 算法具体设计与编码实现94.1基于模拟退火算法求解TSP问题详细设计94.1.1求解TSP问题的模拟退火算法及流程图94.1.2主要代码11第五章 算法运行分析135.1 运行界面图示135.2 运行结果15第六章 结束语16致 谢17参考文献18引言旅行商问题（Traveling Salesman Problem，TSP）可描述为：已知N个城市之间的相互距离，现有一推销员必须遍访这N个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，使其旅行路线总长度最短。旅行商问题是一个典型的组合优化路径规划问题，其可能的路径数目是与城市数目N呈指数型增长的，一般很难精确地求出其最优解，因而寻找其有效的近似求解算法具有重要的理论意义。另一方面，很多实际应用问题，经过简化处理后，均可化为旅行商问题，因而对旅行商问题求解方法的研究具有重要的应用价值。1.1 TSP问题的基本概念旅行商问题( Traveling Salesman Problem) 是一个NP 完全问题,目前求解 TSP 问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、Hopfield 神经网络算法、蚁群算法等，还包括许多算法。TSP(Traveling salesman Problem,旅行商问题)是指给定n个城市和各城市间的距离,要求确定一条经过各个城市当且仅当一次的最短路线。它是一种典型的组合优化问题,其最优解的求解代价是指数级的。已经证明TSP问题是一个NP-hard问题。然而在科学管理与经济决策的许多应用领域中,现实世界存在着大量的多目标优化问题。对于旅行商问题,实际中经常要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、合理的解是比较复杂的问题。1.2 模拟退火算法的背景模拟退火算法来源于固体物质降温原理，在高温条件下，粒子将自由运动， 在达到稳定状态后，再缓慢的降低其温度，则固体物质最终会形成最低能量的状态。可以将这种思想应用于求解组合优化问题，将组合优化问题解空间中的一个解对应于固体降温过程中的一个状态，将目标函数对应于该状态下的能量。以控制参数T来模拟固体的温度。对于每一个T，进行迭代过程：“解变换产生新解判别准则新解的取舍”，采用Metropolis准则4来决定解的取舍，随着温度的降低，该算法有可能从局部极值区域跳出，从而达到全局最优解。1.3 发展前景TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。在中国的研究，TSP还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题（Chinese Postman Problem CPP）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。TSP问题是一个典型的、容易描述但是难以处理的NP完全问题，同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。目前求解TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。对于用模拟退火算法对求解旅行商组合优化问题做来了在满足模拟退火算法全局收敛性的情况下，子排列反序并移位抽样方式对求解NP完全问题是非常有效的。 很多实际问题，经过简化处理后均可转化为TSP问题，对TSP问题求解方法的研究具有重要的应用价值。人们在努力寻找大维数最优化算法的同时，构造出了许多近似求解法，如遗传法、局部搜索算法、蚁群算法等，特别是提出了如模拟退火等用统计方法近似求解TSP的随机算法，为人们求解TSP问题开辟了新的途径。 19模拟退火算法在TSP问题中的应用研究 2.1模拟退火算法的原理模拟退火算法近年来在国内外颇受关注。在1953年，Metropolis提出模拟退火算法，随后在1983年被Kirkpatrick等人成功引入组合优化领域。由于它具有很强的实用性和极佳的性能表现，模拟退火算法主要应用在各种优化问题上，而函数优化是其中非常重要的一方面。NP问题是一个比较麻烦的问题，其解的规模随问题规模的增大而成指数级增长，对于一般的方法而言，当问题规模过大时，就失去了可行性。模拟退火作为一种随机算法，它的特点非常适于求解NP问题，比如著名的旅行商问题(Traveling Salesman Problem)。模拟退火算法在解决这类问题上有着优异的表现。2.1.1 模拟退火的基本思想模拟退火是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火来自冶金学的专有名词淬火。模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一部先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。模拟退火算法可以分解为解空间、目标函数和初始解三部分。(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 算法对应动态演示步骤模拟退火算法新解的产生和接受： step1：由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。step2：计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 step3：判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若 t0则接受S作为新的当前解S，否则以概率exp(- t/T)接受S作为新的当前解S。 step4：当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。2.2 TSP问题简述旅行商问题，即TSP问题（Travelling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。旅行商问题TSP( Traveling Salesman Problem) 问题是一个NP 完全问题,目前求解TSP 问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、Hopfield 神经网络算法、蚁群算法等,各种算法各有千秋。模拟退火算法是局部搜索算法的扩展,理论上来说,它是一个全局最优算法。如何在初始解附近找出一个“好的解”是一项关键技术,它直接影响算法的收敛速度。模拟退火算法在TSP问题中的应用研究 问题描述与算法分析研究本章介绍了模拟退火算法解决TSP问题的需求分析阶段的内容，是本次程序设计中的关键环节。主要对系统进行了整体的分析，明确了系统目标，确定了开发环境，构建了基本的框架结构和功能模块。并且确定了模拟退火算法在TSP问题中的应用研究的主要设计思想。3.1应用研究整体规划通过对程序的理解和分析，这个课题项目应该分为2个阶段进行。第一阶段是模拟退火算法的描述和实现；第二阶段是在TSP问题中应用模拟退火算法解决问题，即模拟退火算法在TSP问题中的具体实现。3.2应用开发环境一个完整并且优秀的程序，为其配置一个良好的系统开发环境是十分必要的，接下来是介绍模拟退火算法解决TSP问题所需要配置的环境要求。以下介绍下开发语言和系统运行平台。3.2.1开发语言开发语言必须是一种优秀的面向对象程序设计语言并且适合于系统程序设计。matlab 语言在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且mathwork也吸收了像Maple等软件的优点,使MATLAB成为一个强大的数学软件。3.2.2开发平台本课题开发语言选用matlab语言，可以选用的开发平台可以从matlab语言平台中选择一种出来，本课题选用matlab6.5。3.3 TSP问题的描述和分析旅行商问题，即TSP问题（Travelling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。一个实例如图3.1所示图3.1 TSP问题的示意图从图3.1中可以看出下面的总体路径要小于上面的总体路径。TSP问题的实现目标就是选择出路径路程为所有路径之中的最小值的路径。目前人们已经构造出了许多近似求解法，如遗传法、蚁群算法、模拟退火算法等10。3.4模拟退火算法的分析以下介绍并且分析模拟退火算法的模型和组合优化的问题。3.4.1模拟退火算法模型模拟退火算法起源于物理退火。物理退火过程： （1） 加温过程 （2） 等温过程 （3） 冷却过程模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想:(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每 个T值的迭代次数L; (2) 对k=1，L做第(3)至第6步： (3) 产生新解S (4) 计算增量t=C(S)-C(S)，其中C(S)为评价函数 (5) 若t0，然后转第2步。3.4.2模拟退火算法与优化问题分析模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性11。模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性。算法的基本思想是从一给定解开始的，从邻域中随机产生另一个解，接受准则允许目标函数在有限范围内变坏。它由一控制参数t决定，其作用类似于物理过程中的温度T，对于控制参数t的每一取值，算法持续进行“产生新解判断接受或舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。经过大量的解变换后，可以求得给定控制参数t值时优化问题的相对最优解。然后减小控制参数t的值，重复执行上述迭代过程。当控制参数逐渐减小并趋于零时，系统亦越来越趋于平衡状态，最后系统状态对应于优化问题的整体最优解。3.5应用研究方案分析根据该课题要求，研究模拟退化算法的基本原理以及TSP组合优化问题，用一种程序语言实现基于模拟退火算法的TSP问题求解方法。并且在3.3中构建了1个TSP问题，问题的目标是选择出路径路程为所有路径之中的最小值的路径。通过matlab语言编写并且实现出模拟退火算法。在利用编写出的模拟退火算法模型去解决之前所建立的TSP问题模型。模拟退火算法在TSP问题中的应用研究 算法具体设计与编码实现前面的章节主要介绍了问题描述与算法分析研究的内容，而本章主要是对该系统的具体实现进行了详细设计。描绘出模拟退火算法的流程图，该算法的运行机制一目了然，明确了算法在系统整体设计中的具体功能和应用，并且对应用模拟退火算法求解TSP问题做了详细的划分和描述。具体分为基于模拟退火算法求解TSP问题详细设计和求解TSP问题的算法主体模块详细设计。4.1基于模拟退火算法求解TSP问题的详细设计第三章提供了模拟退火算法的大体框架和组合优化要注意的问题，这节将了解模拟退火算法的具体流程图和算法模型描述以及模拟退火算法的参数控制问题。模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点温度T的初始值设置问题，退火速度问题，温度管理问题。并且这部分包括一些关键代码。4.1.1求解TSP问题的模拟退火算法及流程图模拟退火算法是解决TSP问题的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。求解TSP的模拟退火算法模型可描述如下:解空间：解空间S是遍访每个城市恰好一次的所有路经，解可以表示为w1,w2 , wn，w1, , wn是1,2,n的一个排列，表明w1城市出发，依次经过w2, , wn城市，再返回w1城市。初始解可选为(1, n) ;目标函数：目标函数为访问所有城市的路径总长度;我们要求的最优路径为目标函数为最小值时对应的路径。新路径的产生：随机产生1和n之间的两相异数k和m，不妨假设km，则将原路径(w1,w2,wk,wk+1,wm,wm+1,wn)变为新路径：(w1,w2,wm,wk+1,wk,wm+1,wn)上述变换方法就是将k和m对应的两个城市在路径序列中交换位置,称为2-opt映射。 根据上述描述，模拟退火算法求解TSP问题的流程框图如图4.1所示。YYYYNNNN选择初始路径X0确定初始温度T0当前路径Xi=X0当前温度Ti=T0当前路径Xi=Xjfrandom(0,1)跳出内循环跳出外循环结 束当前温度Ti下降从Xi的邻域中随机选择Xi，计算Xi与Xj的路程差f=f(Xj)-f(Xi)图4.1模拟退火算法的流程图图4.1展示了模拟退火算法的大体流程图。选一初始状态X0,作为当前解:并且确定初始温度T0，令当前的Xi=X0和Ti=T0。然后从Xi的邻域中随即选择Xj，计算Xi与Xi的路径差，比较差值。按一定方式将T降温，即令T(t+1)kT(t)，i=i+1，然后检查退火过程是否结束，如果不是继续交换，如果是的话输出Si作为最优输出。4.1.2主要代码对应于流程框图，实现流程的主体函数的代码如下： filename=att48.txt;%att48.txt,att48.txt%pathname=F:毕业设计程序模拟退火算法求解tsp;pathname=F:论文资料;fullname=pathname,filename;fid=fopen(fullname,r);A,count=fscanf(fid,%f);fclose(fid);M=count/3;B=zeros(M,3);for i=1:M for j=1:3 B(i,j)=A(i-1)*3+j); endendT_max=100;T_min=1;T_step=1;iter_max=100;s_max=100;order1=randperm(size(B,1);plot(B(order1,2),B(order1,3),*r-)totaldis1=distance(B,order1);T=T_max;while TT_min iter_num=1; s_num=1; plot(T,totaldis1) hold on while iter_numiter_max&s_nums_max; order2=exhgpath(order1); totaldis2=distance(B,order2); r=rand; deltadis=totaldis2-totaldis1; if deltadisr) order1=order2; totaldis1=totaldis2; else s_num=s_num+1; end iter_num=iter_num+1; end T=T*0.99;endorder1totaldis1figure(2)plot(B(order1,2),B(order1,3),*r-)模拟退火算法在TSP问题中的应用研究 算法运行分析第4章给出了应用开发的组织结构和各个功能模块的具体实现，这章介绍程序编码实现后的运行界面图示以及结果分析情况。5.1 运行界面图示1运行matlab,打开提前准备好的glory主文件，输入要打开的文件名att48.txt。界面如图5.1-1， 图5.1-12按F10运行程序，成功运行程序跳出界面显示如下图，图5.1-2 图5.1-3.图5.1-4成功运行了程序代码，matlab环境下显示出所要达到的目的。3输入错误的文件名在显示要输入文件名的地方输入一个错误的文件观看系统反应，输入at48.txt文件名，程序反应如图5.1-5，.图5.1-5 输入一个错误的文件名4再次输入正确的文件名，matlab重新成功运行并弹出结果界面图程序运行正确的文件后，程序已经开始运行模拟退火算法进行分析解决TSP问题。图5.1-4显示的内容是产生的新邻域解和该新邻域解的所产生的路径总和。5.2 运行结果通过上面的运行图示截图展示了程序的总体流程，在图5.1-4中可以看出最终程序运行得到的最优解序列，通过它计算出文件att48.txt中给出的48个坐标点的最短路径问题，计算的结果为5.0964e+004。毕业设计课题研究到此已完成模拟退火算法求解TSP问题基本系统及其编码部分，程序实现均已演示完毕。因为个人知识水平有限，程序运行界面做的十分粗糙并且简陋，整体不太美观。，但是基本功能已经实现，符合实验要求，以后我将继续学习相关知识去丰富自己。模拟