《基于模拟退火算法的TSP算法.docx》由会员分享，可在线阅读，更多相关《基于模拟退火算法的TSP算法.docx（10页珍藏版）》请在三一办公上搜索。
1、专业综合设计报告课程名称：电子专业综合设计设计名称：基于模拟退火算法的TSP算法姓名：学号：班级：电子0903指导教师：朱正为起止日期：专业综合设计任务书学生班级：电子0903学生姓名：学号：20235830设计名称：基于模拟退火算法的TSP算法起止日期：指导教师设计要求：旅行商问题，即TSP问题(TravellingSalesmanProblem)又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。此设计是用
2、模拟退火算法来实现TSP问题的寻求最优解。专业综合设计学生日志时间设计内容2023,H.9初步了解模拟退火算法的TSP算法2023.11.12设计算法流程、确定解题思路2023.11.20讨论算法流程及解题思路的可行性，为仿真做准备2023.12.2运用MATLAB软件进行实验仿真，分析仿真结果整理实验报告辩论专业综合设计考勤表周星期i星期二星期三星期四星期五专业综合设计评语表指导教师评语:成绩;指导教师:年月口-设计目的和意义4二设计原理错误!未定义书签。2.1 模拟退火算法的根木原理52.2 2TSP问题介绍6三详细设计步骤错误!未定义书签.3.1 .算法流程83.2 模拟退火算法实现步骤
3、错误!未定义书签。四设计结果及分析91.1.2 1MATLAB程序实现及主函数9计算距离矩阵91.1.3 初始解101.1.4 生成新解101.1.5 Metropolis准那么函数.,.,.101.1.6 画路线轨迹图111.1.7 输出路径函数121.1.8 可行解路线长度函数121.1.9 模拟退火算法的主函数134.2.仿真结果15五体会9六参考文献10基于模拟退火算法的TSP算法一、设计目的和意义旅行商问题是组合优化领域里的一个典型的、易于描述却难以处理的NP难题，其可能的路径数目与城市数目是呈指数型增长的，求解非常困难。首先介绍了旅行商问题,给出了其数学描述以及实际应用，进而给出解
4、决TSP的一种比拟精确的算法一一模拟退火算法。然后阐述了模拟退火算法的根本原理，重点说明了其根本思想及关键技术。最后运用MATLAB语言实现了该算法，并将其运用到解决旅行商问题的优化之中。数值仿真的结果说明了该方法能够对数据进行全局寻优，有效克服了基于导数的优化算法容易陷入局部最优的问题。了解模拟退火算法的TSP算法的根本思路及原理，并应用MATLAB实现仿真，熟练掌握MATLAB的操作方式及应用，能正确书写报告。二、设计原理2.1 模拟退火算法的根本原理模拟退火算法足20世纪80年代初提出的一种基于蒙特卡罗(MenteCarIo)迭代求解策略的启发式随机优化算法。它通过MetroPOIiS接
5、受准那么概率接受劣化解并以此跳出局部最优，通过温度更新函数的退温过程进行趋化式搜索并最终进入全局最优解集。其出发点是基于物理中固体物质的退火过程与一搬的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法，其物理退火过程由以下三局部组成。(1)加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。(2)等温过程。对于与周围环境交换热量而温度不变的密封系统，系统状态的自发变化总是朝自由能减少的方向进行的，当自由能到达最小时，系统到达平衡状态。(3)冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。其中，加热过程对应算法的
6、设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。这里能量的变化就是目标函数，要得到的最优解就是能量最低态。MetrOPOIiS准那么是SA算法收敛于全局最优解的关键所在，Metropolis准那么以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。模拟退火算法为求解传统方法难处理的TSP问题提供了一个有效的途径和通用框架，并逐渐开展成一种迭代自适应启发式概率性搜索算法。模拟退火算法可以用以求解不同的非线性问题，对不可微甚至不连续的函数优化，能以较大的概率求的全局有化解,该算法还具有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性，并且能处理不同类型的
7、优化设计变量(离散的、连续的和混合型的)，不需要任何的辅助信息，对目标函数和约束函数没有任何要求。利用Metropolis算法并适当的控制温度下降过程，在优化问题中具有很强的竞争力，此设计即为基于模拟退火算法的TSP算法。SA算法实现过程如下(以最小化问题为例)：(1)初始化：取初始温度L足够大，令T=To,任取初始解Si,确定每个T时的迭代次数，即Metropolis链长L。,1,重复步骤(3) (6)。(2)对当前温度T和k=l,2,(3)对当前Sl随机扰动产生一个新解S.计算一的增量df=f(SI-f(SJ其中f为Sl的代价函数。(5)假设dfO,那么接受8作为新的当前解，即S1=S否那
8、么计算S?的接受概率exp(-dfT),即随机产生(0,1)区间上均匀分布的随机数rand,假设exp(-dfT)rand也接受S2作为新的当前解，S1=S25否那么保存当前解Sli.(6)如果满足终止条件Stop,那么输出当前解Sl为最优解，结束程序。终止条件Stop通常为：在连续假设干个Metropolis链中新解s2都没有被接受时终止算法，或是设定结束温度。否那么按衰减函数衰减T后返回步骤(2)o以上步骤成为Metropolis过程。逐渐降低控制温度，重复Metropolis过程，直至满足结束准那么Stop,求出最优解。2.2 TSP问题介绍旅行商问题(TravelingSalesman
9、Problem,简称TSP)又名货郎担问题，是威标哈密尔顿爵士和英国数学家克克曼(TPKirkman)于19世纪初提出的一个数学问题，也是著名的组合优化问题。问题是这样描述的：一名商人要到假设干城市去推销商品，城市个数和各城市间的路程(或旅费)，要求找到一条从城市I出发，经过所有城市且每个城市只能访问一次，最后回到城市1的路线，使总的路程(或旅费)最小。TSP刚提出时,不少人认为这个问题很简单。后来人们才逐步意识到这个问题只是表述简单，易于为人们所理解，而其计算复杂性却是问题的输入规模的指数函数，属于相当难解的问题。这个问题数学描述为：假设有n个城市，并分别编号，给定一个完全无向图G=(V,E
10、),V=b2,，n,nl。其每一边(i,j)wE有一非负整数消耗Cij(即上的权记为Cki,i,jV)oG的一条巡回路线是经过V中的每个顶点恰好一次的回路。一条巡回路线的消耗是这条路线上所有边的权值之和。TSP问题就是要找出G的最小消耗回路。人们在考虑解决这个问题时,一般首先想到的最原始的一种方法就是:列出每一条可供选择的路线(即对给定的城市进行排列组合)，计算出每条路线的总里程，最后从中选出一条最短的路线。假设现在给定的4个城市分别为A、B,C和D,各城市之间的消耗为己知数，如图1所示。我们可以通过一个组合的状态空间图来表示所有的组合，如图图1顶点带权图图2TSP问题的解空间树从图中不难看出
11、，可供选择的路线共有6条，从中很快可以选出一条总消耗最短的路线:顶点序列为(A,C,B,D,A)。由此推算，假设设城市数目为n时，那么组合路径数那么为(n-1)!。很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至到达无法计算的地步，这就是所谓的组合爆炸问题。假设现在城市的数目增为20个，组合路径数那么为(20-l)!l,2161017,如此庞大的组合数目，假设计算机以每秒检索I(X)O万条路线的速度计算，也需要花上386年的时间向。三、详细设计步骤3.1 算法流程模拟退火算法求解流程框图如图1所示。图3模拟退火算法求解流程框
12、图3.2 模拟退火算法实现步骤如下：(I)控制参数的设置需要设置的主要控制参数有降温速率q、初始温度To、结束温度Tend以及链长Lo(2)初始解对于n个城市TSP问题，得到的解就是对ln的一个排序，其中每个数字为对应城市的编号，如对10个城市的TSP问题1,2,3,4,5,6,7,8,9,10,那么l1024568793就是一个合法的解，采用产生随机排列的方法产生一个初始解So(3)解变换生成新解通过对当前解S1进行变换，产生新的路径数组即新解，这里采用的变换是产生随机数的方法来产生将要交换的两个城市，用二邻域变换法产生新的路径，即新的可行解Sio例如n=10时，产生两个1,10范围内的随机
13、整数和n,确定两个位置，将其对换位置，如r=4,n=795163871042得到的新解为95173861042(4) MetroPOliS准那么假设路径长度函数为f(三),新解的路径为F(S2),路径差为d/=/(S2)-/(S1),那么Metropolis准那么为1,#OT如果dfO,那么以概率1接受新路线，否那么以概率exp(-df/T)接受新路线。(5)降温利用降温速率q进行降温，即T=qT,假设T小于结束温度，那么停止迭代输出当前状态，否那么继续迭代。四、设计结果及分析4.1 MATLAB程序实现及主函数4.1.1 计算距离矩阵利用给出的N个城市的坐标，算出N个城市的两两之间的距离，得
14、到距离矩阵(NN)o计算函数为DiStance,得到初始群种。程序如下functionD-Distanse(a)%计算两两城市之间的距离%输入a各城市的位置坐标%输出D两两城市之间的距离row=size(a,l);Sl=randperm (N)：%随机产生一个初始路线forj=i+krowUi.i)=afi.D-a伍nM2+(afi.2Lafi2、)A2VH)S:funct沁nS2=NewAnswer(S1)%输入%S1:当前解%输出%S2：新解N=Ienglh(Sl);Fnncfjcn1Pl=IVlQfrCrVU；c/1SOT、R2=PalhLength(D,S2);%计算路线长度dC=R2
15、-Rl;%计算能力之差ifdC=rand%以exp(-dCT)概率接受新路线S=S2;R=R2;else%不接受新路线S=Sl;R=Rl;figure:holdonpk)t(X(:,l),X(:,2),o?COlOH0.5,0.5,0.5)plot(X(Chrom(1,1),1),X(Chrom(1,1),2),rv,MarkerSize,20)fori=Irsize(XJ)text(X(i,l)+0.05,X(i,2)+0.05jum2str(i),color,l,0,0);functionlen=PathLength(D,Chrom)4.%计算各个体的路径长度%输入：%D两两城市之间的距离
16、%Chrom个体的轨迹row,col=size(D);NIND=size(Chrom,l);len=zeros(NIND,1);-fori=kNINDtemp=zeros(L,N+1);fork=l:L%产生新解S2=NewAnswer(S1);%Metropolis法那么判断是否接受新解ISl,R=Metropolis(S1,S2,D,T0);%Metropolis抽样算法temp(k,:)=SlR;%记录下一路线的及其路程end%记录每次迭代过程的最优路线dOJndcx=min(temp(,cnd);%找出当前温度下最优路线ifcount=lHdOObj(count-l)Obj(count
17、)=dO:%如果当前温度下最优路程小于上一路程那么记录当前路程elseObj(COUnt)=Obj(CoUnt.1);%如果当前温度下最优路程大于上路程那么记录上一路程endtrack(count,:)=temp(indexj:end-l);%记录当前温度的最优路线TO=q*TO;%降温frintf(I%dncount)%输出当前迭代次数end%优化过程迭代图figureplot(lxount,Obj)XIabdC迭代次数)y1abe(距离)titlee优化过程)%最优解的路径图DrawPath(track(end,:),X)%输出最优解的路线和总距离dispC最优解:)S=track(end
18、,:);P=OutputPath(三);disp(总距离：num2str(PathLength(D,S);disp()toe的与其他程序和语言接口的功能。我们应该熟练掌握其使用方法。5.2关于基于模拟退火算法的TSP算法的体会模拟退火算法是依据MetroPoIiS准那么接受新解，该准那么除了接受优化解外，还在一定的限定范围内接受劣解，这正是模拟退火算法与局部搜索法的本质区别，在防止陷入局部极小值、提高解空间的搜索能力和扩大搜索范围方面具有明显的优越性。本次设计给出了一种TSP的求解算法，并用MATLAB语言编程实现了算法。算法实验结果说明,对大多数组合优化问题而言，模拟退火算法在求最优解和求解
19、时间均到达了满意的结果。利用MATLAB语言实现的模拟退火程序，能够找到系统的最优解，仿真结果证明了该方法的有效性。采用该方法既可使我们熟悉MATLAB语言，又可以加深对模拟退火算法的认识和理解，以此来设计智能系统。旅行商问题-直都是业界研究的重点，其应用范围广，在许多领域都有其重要的指导意义。随着对TSP问题研究的深入，目前己经提出了多种TSP问题的变种，如：多目标TSP问题、局部重复路径的TSP问题、多人TSP问题以及带时间约束的TSP问题等等。TSP的算法研究领域中，除非有新的解决组合优化问题的算法框架出现，各种仿自然的算法结合局部优化的算法思想仍将是研究的重点。针对各种模拟退火算法的优
20、劣，如何扬长避短，提高算法的时间效率和寻优能力，目前许多学者致力于各种求解算法的综合集成的研究，如遗传模拟退火算法、模拟退火蚁群算法、混合遗传算法、混合蚂蚁算法等等。结合实际问题设计适当的算法参数和局部优化策略以构造混合算法将是解决TSP的重要途径。客观地说，目前并不存在一种求解TSP问题的最正确算法，各个算法都有其应用的局限性：经典算法追求精确解，但是忽略了算法的时空消耗，可行性不高；而现代流行改良算法那么是追求近似解，降低了算法的时空消耗，但是在求解结果上往往不能让人满意。我认为今后在TSP的算法研究上应该把握3个方面：继续改良已有TSP算法；采用人工智能的思想，创造新的TSP算法；集合各
21、个算法的优点，进行混合TSP算法的研究。目前这些相关方向业界人士都有所涉及，也都取得了一定成效，相信在不久的将来，TSP问题一定会有更好的解决方案。六、参考文献11高海昌,冯博琴,朱莉.只能优化算法求解TSP问题J.控制与决策,2006,21(03):241-247.252.2苗卉,杨韬.旅行商问图TSP)的改良模拟退火算法.微计算机信息僧控一体化),2007,23(11):2413万军洲.基于模拟退火技术的旅行商问题求解算法.软件导刊,2006,(8):88,88-89.4盛国华,陈玉金,改良模拟退火算法求解TSP问题J.电脑知识与技术，2023(15)：1103-1104,1103.15J曲强，陈雪波.基于MATLAB的模拟退火算法的实现.鞍山科技大学学报,2003,26(3):197-19816冯剑,岳琪，模拟退火算法求解TSP问题J.森林工程,2023,24(01):94-96.
