模拟退火算法在TSP求解中的应用.docx
- 文档编号:3145121
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:11
- 大小:96.54KB
模拟退火算法在TSP求解中的应用.docx
《模拟退火算法在TSP求解中的应用.docx》由会员分享,可在线阅读,更多相关《模拟退火算法在TSP求解中的应用.docx(11页珍藏版)》请在冰点文库上搜索。
模拟退火算法在TSP求解中的应用
模拟退火算法在TSP求解中的应用
摘要:
模拟退火算法(SimulatedAnnealing,SA)是一种适合解大规模组合优化问题,特别是解NP完全问题的通用有效近似算法。
它与以往的近似算法相比,具有描述简单、使用灵活、运用广泛、运行效率高等优点,而且特别适合并行计算。
TSP问题即旅行商问题是一个组合优化问题,该问题被证明具有NPC计算复杂性。
因此,研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。
本文首先分析了SA的基本原理,针对TSP问题我们将SA应用到TSP上,并建立了TSP的数学模型,阐述了利用模拟退火算法解TSP的方法。
最后通过实验证明了模拟退火算法的高效性。
关键词:
模拟退火;组合优化;TSP问题
1引言
模拟退火的概念最初是人们为了研究组合优化问题而提出的,用于解决组合优化问题,其原理是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性:
通过设定一初始温度和初始状态,伴随温度的不断下降,结合概率突跳特性在解空间中通过邻域函数进行随机搜索,最终得到全局近似最优解。
SA算法在组合优化中取得了很好的效果,能解决传统的优化方法难于解决的许多问题。
SA算法具有较好的全局收敛性和适应性,并隐含着较好的并行性。
SA算法的一些变形方法还表明:
利用Metropolis过程并适当地控制温度下降过程的SA算法,在连续变量和混合变量的全局优化问题中具有很强的竞争力。
TSP(TravelingsalesmanProblem,旅行商问题)是一个组合优化问题。
具有NPC计算复杂性。
因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。
一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来,并逐一比较,选出最小的路径。
虽然该方法在理论上是可行的,但路径的个数与城市的个数成指数增长,当城市个数较大时,该方法的求解时间是难以忍受的,甚至是不可能完成的。
以每秒1亿次的计算速度来估算,如果TSP问题包含20个城市时,求解时间长达350年;如果要处理30个城市,则求解时间更长达1+10e16年。
如此长的时间,在实际中完成是不现实的。
基于模拟退火算法在处理全局优化、离散变量优化等困难问题中,具有传统优化算法无可比拟的优势。
本文介绍了模拟退火算法的基本原理,并利用SA算法实验求解TSP问题,借此显现了SA算法比传统算法的优势。
2算法理论分析
2.1模拟退火算法简介
模拟退火算法的思想最早由Metropolis等提出的。
其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。
模拟退火法是一种通用的优化算法,其物理退火过程由以下三部分组成:
(1)加温过程。
其目的是增强粒子的热运动,使其偏离平衡位置。
当温度足够高时,固体将熔为液体,从而消除系统原先存在的非均匀状态。
(2)等温过程。
对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡状态。
(3)冷却过程。
使粒子热运动减弱,系统能量下降,得到晶体结构。
其中,加温过程对应算法的设定初温,等温过程对应算法的Metropolis抽样过程,冷却过程对应控制参数的下降。
这里能量的变化就是目标函数,我们要得到的最优解就是能量最低态。
其中Metro-polis准则是SA算法收敛于全局最优解的关键所在,Metropolis准则以一定的概率接受恶化解,这样就使算法跳离局部最优的陷阱。
2.2模拟退火算法的模型
模拟退火算法可以分解为解空间、目标函数和初始解三部分。
模拟退火的基本思想:
1.初始化:
初始温度T(充分大),初始解状态S(是算法迭代的起点),每个T值的迭代次数L;
2.对k=1,…,L做第(3)至第6步;
3.产生新解S′;
4.计算增量Δt′=C(S′)-C(S),其中C(S)为评价函数;
5.若Δt′<0则接受S′作为新的当前解,否则以概率exp(-Δt′/T)接受S′作为新的当前解;
6.如果满足终止条件则输出当前解作为最优解,结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法;
7.T逐渐减少,且T->0,然后转第2步。
2.3TSP模型
(1)问题定义:
设n为城市数目,D=[dij]为n×n阶距离矩阵,dij代表从城市i到城市j的距离(i,j=1,2,3…n),则问题是要找出遍访每个城市恰好一次的一条回路,且其路径长度为最短。
(2)解空间:
解空间S是遍访每个城市恰好一次的所有回路,可表示为(1…n)的所有循环排列的集合,即S=[Sij]为(1…n)的排列,Si表示第i个城市第Si个被访问。
(3)目标函数:
目标函数为访问所有城市的回路长度或称为代价函数,需求其最小值,选d=
为最小。
3模拟退火算法求解TSP
求解TSP的模拟退火算法模型可描述如下:
图1模拟退火算法的流程图
我们要求的最优路径为目标函数为最小值时对应的路径。
新路径的产生:
随机产生1和n之间的两相异数k和m,不妨假设k (w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn)上述变换方法就是将k和m对应的两个城市在路径序列中交换位置,称为2-opt映射。 根据上述描述,模拟退火算法求解TSP问题的流程框图如图1所示。 图1展示了模拟退火算法的大体流程图。 选定初始状态X0,作为当前解: 并且确定初始温度T0,令当前的Xi=X0和Ti=T0。 然后从Xi的邻域中随即选择Xj,计算Xi与Xi的路径差,比较差值。 按一定方式将T降温,即令T(t+1)=k×T(t),i=i+1,然后检查退火过程是否结束,如果不是继续交换,如果是的话输出Si作为最优输出。 4仿真实验 实验环境: MATLAB7.1.0 实验算例: 20个城市TSP(自定义),相对坐标如图2所示。 参数设定: 初始温度: 4000,冷却速率: 0.95,阈值: 3500 算法终止条件为控制参数t的值小于某个充分小的正数D。 求解得到的最优路径图如图3所示。 图220座城市相对坐标 图3模拟退火算法得到的最优路径图 从实验结果看,利用模拟退火算法求解TSP问题是可行有效的,但当TSP求解的城市规模增大时,找到最优解的次数也在降低。 5结论 模拟退火算法是一种可行、有效的全局优化的数值计算方法,它在解决高维空间、高复杂度及非线性问题的优化中具有全局最优、效率高及易于并行计算等优点,有很强的解决实际问题的能力。 近年来在模式识别、自动控制、机器学习、人工神经网络结构参数优化等许多领域受到重视,应用范围不断扩大。 本文给出了用SA算法求解TSP问题的流程,并详述了各参数的取值,程序是在MATLAB环境中编写的,该程序基本实现了该课题的任务目标,研究SA算法的基本原理以及TSP组合优化问题,用一种程序语言实现基于SA算法的TSP问题求解方法。 并且本文说明了用SA算法能够较好地求解旅行商问题。 因而理论上能够找到最优解,但所得结论与实际应用还有一定距离,特别是对连续变量函数的优化问题。 目前,SA算法参数的选择仍然依赖于一些启发式准则和待求问题的性质。 SA算法的通用性很强,算法易于实现,但要真正取得质量和可靠性高、初值鲁棒性好的效果,客服计算时间较长、效率较低的缺点,并适用于规模较大的问题,尚需进行大量的研究工作。 参考文献: [1]王大志,汪定伟,闫杨.一类多旅行商问题的计算及仿真分析[J].系统仿真学报,2009(20): 6378-6381. [2]汪定伟等编著.智能优化方法[M],北京: 高等教育出版社,2007 [3]冯剑,岳琪.模拟退火算法求解TSP问题[J].森林工程,2008,24 (1): 94-96. [4]朱静丽.用模拟退火算法求解TSP[J].湖北广播电视大学学报,2011,31(9): 159-160. [5]庞峰.模拟退火算法的原理及算法在优化问题上的应用[D].吉林大学,2006. [6]马良.旅行推销员问题的算法综述[J].数学的实践与认识,2000,30 (2): 156-165. 附录: 程序代码 代码使用了模拟退火的思想解决TSP问题。 在仿真实验中解决了自定义的20个城市的TSP问题,在设定合适参数后每次的运行中都能得到一个比较理想的结果。 主要的程序代码如下: functionf=plotcities(inputcities) %将输入的城市在二维平面上表示出来,每个星号代表一个城市。 shg temp_1=plot(inputcities(1,: ),inputcities(2,: ),'b*'); set(temp_1,'erasemode','none'); temp_2=line(inputcities(1,: ),inputcities(2,: ),'Marker','*'); set(temp_2,'color','b'); x=[inputcities(1,1)inputcities(1,length(inputcities))]; y=[inputcities(2,1)inputcities(2,length(inputcities))]; xl=10*round(min(inputcities(1,: ))/10); yl=10*round(min(inputcities(2,: ))/10); ifxl>0 xl=0; end ifyl>0 yl=0; end xu=10*round(max(inputcities(1,: ))/10); yu=10*round(max(inputcities(2,: ))/10); ifxu==0 xu=1; end ifyu==0 yu=1; end axis([xlxuylyu]); temp_3=line(x,y); set(temp_3,'color','b'); dist=distance(inputcities); distance_print=sprintf(... 'Theroundtriplengthfor%dcitiesis%4.6funits'... length(inputcities),dist); text(xl/1.05,1.05*yu,distance_print,'fontweight','bold'); drawnow; functions=simulatedannealing(inputcities,initial_temperature,cooling_rate,threshold,numberofcitiestoswap) %模拟退火算法。 参数有输入城市数据,初始温度,冷却速率,阈值和交换城市数量。 globaliterations; temperature=initial_temperature; initial_cities_to_swap=numberofcitiestoswap; iterations=1; complete_temperature_iterations=0; previous_distance=distance(inputcities); whileiterations temp_cities=swapcities(inputcities,numberofcitiestoswap); current_distance=distance(temp_cities); diff=abs(current_distance-previous_distance); ifcurrent_distance inputcities=temp_cities; ifrem(iterations,100)==0 plotcities(inputcities); end ifcomplete_temperature_iterations>=10 temperature=cooling_rate*temperature; complete_temperature_iterations=0; end numberofcitiestoswap=round(numberofcitiestoswap*exp(-diff/(iterations*temperature))); ifnumberofcitiestoswap==0 numberofcitiestoswap=1; end previous_distance=current_distance; iterations=iterations+1; complete_temperature_iterations=complete_temperature_iterations+1; else ifrand (1) inputcities=temp_cities; ifrem(iterations,100)==0 plotcities(inputcities); end numberofcitiestoswap=round(numberofcitiestoswap*exp(-diff/(iterations*temperature))); ifnumberofcitiestoswap==0 numberofcitiestoswap=1; end previous_distance=current_distance; complete_temperature_iterations=complete_temperature_iterations+1; iterations=iterations+1; end end end functions=swapcities(inputcities,n) %随机交换两个城市。 s=inputcities; fori=1: n city_1=round(length(inputcities)*rand (1)); ifcity_1<1 city_1=1; end city_2=round(length(inputcities)*rand (1)); ifcity_2<1 city_2=1; end temp=s(: city_1); s(: city_1)=s(: city_2); s(: city_2)=temp; end functiond=distance(inputcities) %计算输入城市的距离解决旅行商问题。 d=0; forn=1: length(inputcities) ifn==length(inputcities) d=d+norm(inputcities(: n)-inputcities(: 1)); else d=d+norm(inputcities(: n)-inputcities(: n+1)); end end
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法 TSP 求解 中的 应用