模拟退火算法解决TSP问题-Read

模拟退⽕算法（SA）求解TSP问题（C语⾔实现） 这篇⽂章是之前写的智能算法（遗传算法（GA）、粒⼦群算法（PSO））的补充。

其实代码我⽼早之前就写完了，今天恰好重新翻到了，就拿出来给⼤家分享⼀下，也当是回顾与总结了。

⾸先介绍⼀下模拟退⽕算法（SA）。

模拟退⽕算法（simulated annealing，SA）算法最早是由Metropolis等⼈提出的。

其出发点是基于物理中固体物质的退⽕过程与⼀般组合优化问题之间的相似性。

模拟退⽕算法是⼀种通⽤的优化算法，其物理退⽕过程由以下三部分组成： （1）加温过程 （2）等温过程 （3）冷却过程 其中加温过程对应算法设定的初始温度，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。

这⾥能量的变化就是⽬标函数，要得到的最优解就是能量最低状态。

Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis准则以⼀定的概率接受恶化解，这样就使得算法可以跳离局部最优解的陷阱。

模拟退⽕算法为求解传统⽅法难以处理的TSP问题提供了⼀个有效的途径和通⽤的处理框架，并逐渐发展成为⼀种迭代⾃适应启发式概率搜索算法。

模拟退⽕算法可以⽤于求解不同的⾮线性问题，对于不可微甚⾄不连续函数的优化，能以较⼤概率求得全局最优解，该算法还具有较强的鲁棒性、全局收敛性、隐含并⾏性以及⼴泛的适应性，对⽬标函数以及约束函数没有任何要求。

SA 算法实现的步骤如下：（下⾯以最⼩化问题为例） （1）初始化：取温度T0⾜够⼤，令T = T0，取任意解S1，确定每个T时的迭代次数，即 Metropolis链长L。

（2）对当前温度T和k=1,2,3，...,L,重复步骤（3）~（6） （3）对当前解S1随机产⽣⼀个扰动得到⼀个新解 S2. （4）计算S2的增量df = f（S2） - f（S1），其中f（S1）为S1的代价函数。

（5）若df < 0,接受S2作为新的当前解，即S1 = S2；否则S2的接受概率为 exp（-df/T）,即随机产⽣（0,1）上的均匀分布的随机数rand，若 exp（-df/T）>rand,则接受S2作为新的当前解，S1 = S2；否则保留当前解。

用模拟退火算法求解TSP
TSP问题（旅行商问题）是一个NP难问题。

模拟退火算法是一种解决复杂问题的启发式优化算法，被广泛应用于求解TSP问题。

下面是使用模拟退火算法求解TSP1650的步骤：
1. 初始化：随机生成一个初始解集，即随机生成一个城市序列，并计算其路径长度。

2. 降温：将系统温度下降，即通过调节温度参数来控制搜索范围，随着时间的推移，温度逐渐下降。

3. 移动：通过移动城市序列来扰动当前解集，得到新的解集。

比如，随机选择两个城市交换其顺序，得到新的城市序列。

4. 计算路径长度：计算新的城市序列的路径长度。

5. 判断是否接受新的解集：按照一定概率接受新的解集，比如如果新解集的路径长度更短，则接受新解集，否则以一定概率接受新解集，以避免陷入局部最优解。

6. 重复以上步骤，直到温度降至最低，或者找到满足要求的解。

7. 输出最优解：得到满足要求的解后，输出路径长度和城市序列。

求解TSP1650很困难，需要大量的计算资源和时间，运行时间可能需要数小时或数天。

用模拟退火方法解决TSP 问题
一、 退火原理
退火是一种物理过程，金属物体在加热到一定温度后，他的分子状态在状态空间D 中自由运动。

随着温度的降低，这些分子停留在低能量状态的概率逐渐增大，当温度趋进于0时，分子停留在低能量状态的概率趋向于1。

二、
退火原理运用于组合优化问题
组合优化问题
金属物体 解
状态
最优解 能量最低状态
目标函数
能量
三、 模拟退火算法
步骤 1 任选一个初始解i ，初始温度t ，给定降温比例系数α，以及一个纪录最优解的变量bi 和其函数值best=+∞；
步骤2 若1t <，则停止计算，输出最优解best ；否则执行3；
步骤 3 从i 的邻域中随机选择一个j ， ()()ij f f j f i ∆=-；若0ij f ∆<，则令
i j =，执行4；否则若exp(/)(0,1)ij f t rand -∆>时，i j =，执行4；否则执行
3；
步骤4 若()f i best <，则bi i =，()best f i =，t t α=，执行2；否则t t α=，执行2； 四、
实验结果和分析
通过五个城市节点的TSP 问题的求解，其城市间的距离矩阵为：
01015621008139158020156132005291550⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭
模拟退火找到的最优路径为A C B D E →→→→，总路程为43；
由实验结果我们发现，对于小规模的TSP 问题，用模拟退火方法找到的解和用禁忌搜索方法找到的解不谋而合，都能够找到很好的解。

用模拟退火算法解决TSP问题旅行商问题（Traveling Salesman Problem，TSP）是指一个旅行商要在不重复地经过全部的指定城市之后回到起点，所需要走的最短路径长度是多少。

由于TSP问题具有NP难度，因此传统的精确算法要花费大量的计算资源，得到的结果往往也只能是近似最优解。

而模拟退火算法是一种集合随机性和概率思想的启发式方法，可以快速地在解空间中搜索到一个较优的解。

一、模拟退火算法的原理及过程模拟退火算法是一种以概率为基础的全局优化算法，它的基本思想是利用随机性来逃离局部最优解，让搜索过程在解空间中跳跃，最终逐渐接近全局最优解。

模拟退火算法的过程可以分为三个阶段：初始化阶段、搜索阶段和收敛阶段。

初始化阶段：首先需要对问题进行建模，将问题转化为算法可处理的形式。

在TSP问题中，需要建立一个城市间距离矩阵。

然后随机生成一个初始解，通常是一个随机序列，表示旅行商经过城市的顺序。

搜索阶段：对生成的初始解进行扰动，得到一个新的解，并计算新解的目标函数值。

如果新解比原解更优，则直接接受该解。

如果新解比原解更劣，则有一定的概率接受该解，概率随着时间的推移逐渐降低。

收敛阶段：在搜索过程中，随着温度的不断下降，概率接受劣解的概率越来越小，这时算法逐渐收敛到一个局部最优解，也可能是全局最优解。

二、TSP问题的建模及求解TSP问题可以建立一张城市距离矩阵，然后用随机序列来表示旅行商经过城市的顺序。

目标函数可以定义为旅行商经过所有城市的总路径长度。

假设有n个城市，城市之间的距离矩阵为D，表示第i个城市和第j个城市之间的距离。

而旅行商经过城市的顺序可以用一个长度为n的序列{1,2,...,n}来表示，表示旅行商先经过第1个城市，然后是第2个城市，一直到第n个城市，然后再回到原点。

设目前的解序列为s={s1,s2,...,sn}，则其总路径长度为：L(s) = ∑i=1n D(si,si+1) + D(sn,1)其中D(si,si+1)表示城市si和si+1之间的距离，D(sn,1)表示最后回到起点的距离。

毕业论文（设计）题目模拟退火算法在TSP问题中的应用研究毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。

尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。

对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。

作者签名：日期：指导教师签名：日期：使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。

作者签名：日期：学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。

除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。

对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。

本人完全意识到本声明的法律后果由本人承担。

作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。

本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

涉密论文按学校规定处理。

作者签名：日期：年月日导师签名：日期：年月日目录摘要 (V)ABSTRACT........................................................... V I 第一章前言. (1)1.1 TSP问题的基本概念 (1)1.2 模拟退火算法的背景 (1)1.3 发展趋势 (2)第二章相关知识介绍 (3)2.1模拟退火算法的原理 (3)2.1.1 模拟退火的基本思想 (3)2.1.2 算法对应动态演示步骤 (4)2.2 TSP问题简述 (4)2.3组合优化问题简述 (5)2.4 蚁群算法及其它算法原理 (6)2.4.1蚁群优化算法 (6)2.4.2其它优化算法 (6)第三章问题描述与算法分析研究 (9)3.1应用研究整体规划 (9)3.2应用开发环境 (9)3.2.1开发语言 (9)3.2.2开发平台 (9)3.3 TSP问题的描述和分析 (9)3.4模拟退火算法的分析 (10)3.4.1模拟退火算法模型 (10)3.4.2模拟退火算法与优化问题分析 (11)3.5应用研究方案分析 (11)第四章算法具体设计与编码实现 (12)4.1基于模拟退火算法求解TSP问题详细设计 (12)4.1.1求解TSP问题的模拟退火算法及流程图 (12)4.1.2算法温度的选择和变化 (14)4.1.3定义坐标表的具体参数与具体实现 (15)4.1.4新解的产生方法 (17)4.2求解TSP问题的算法主体模块详细设计 (19)4.3算法的具体编码实现 (20)4.3.1建立城市坐标文本文件 (21)4.3.2 DOS下界面数据输出以及概率统计与分析 (21)第五章算法运行分析 (24)5.1 运行界面图示 (24)5.2 运行结果 (27)第六章结束语 (28)致谢 (29)参考文献 (29)摘要TSP问题是一个典型的NP 完全问题,模拟退火算法是求解此问题的一种理想方法。

基于混合遗传模拟退火算法求解TSP问题杜宗宗;刘国栋【摘要】TSP问题是典型的NP-hard组合优化问题,遗传算法是求解此类问题的一种方法,但它存在如何较快地找到全局最优解,并防止"早熟"收敛的问题.针时上述问题并结合TSP问题的特点,提出将遗传算法与模拟退火算法相结合形成遗传模拟退火算法.为了解决群体的多样性和收敛速度的矛盾,采用了部分近邻法来生成初始种群,生成的初始种群优于随机产生初始种群.仿真实验结果证明.该算法相对于基本遗传算法的收敛速度、搜索质量和最优解输出概率方面有了明显的提高.【期刊名称】《计算机工程与应用》【年(卷),期】2010(046)029【总页数】4页(P40-42,46)【关键词】混合遗传算法;模拟退火算法;旅行商问题【作者】杜宗宗;刘国栋【作者单位】江南大学,通信与控制工程学院,江苏,无锡,214122;江南大学,通信与控制工程学院,江苏,无锡,214122【正文语种】中文【中图分类】TP301.61 引言旅行商问题（Traveling Salesman Problem，TSP）可描述为：已知N个城市之间的相互距离，现有一推销员必须遍访这N个城市，并且每个城市只能访问一次，最后又必须返回出发城市。

如何安排他对这些城市的访问次序，使其旅行路线总长度最短。

旅行商问题是一个典型的组合优化路径规划问题，其可能的路径数目是与城市数目N呈指数型增长的，一般很难精确地求出其最优解，因而寻找其有效的近似求解算法具有重要的理论意义。

另一方面，很多实际应用问题，经过简化处理后，均可化为旅行商问题，因而对旅行商问题求解方法的研究具有重要的应用价值。

近年来，遗传算法由于它强大的优化能力已经被广泛应用于TSP问题的求解中[1-3]。

遗传算法就其本质而言是处理复杂问题的一种鲁棒性强的启发式随机搜索方法。

它是求解TSP问题的一种理想方法。

遗传算法中一个较难解决的问题是如何较快地找到最优解、保证全局收敛性、提高局部寻优能力并防止“早熟”收敛问题。

模拟退火算法解决TSP问题一、代码介绍:这段代码使用了模拟退火的思想解决TSP问题。

在这个仿真实验中解决了自定义的20个城市的TSP问题，在设定合适参数后每次的运行中都能得到一个比较理想的结果。

Main.m文件是程序入口。

Data_file.m文件设置自定义的城市数据。

Swapcities.m文件中包含随机交换两个城市的函数。

Plotcities.m文件中包含将城市数据在二维平面上表示的函数。

Distance.m文件中包含计算城市距离的函数，用来解决旅行商问题。

Simulatedannealing.m文件中包含模拟退火算法。

这部分是程序的主体，我参考了许多讨论关于模拟退火算法方面的论文。

二、模拟退火算法原理：模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

根据Metropolis准则，粒子在温度T 时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann 常数。

用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。

退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

三、模拟退火的基本思想:(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) 如果满足终止条件则输出当前解作为最优解，结束程序。

智能优化方法课题报告专业班级：电子信息科学与技术12-3班课题名称：模拟退火算法解决TSP问题指导教师：**学生姓名：***学号： ********（课题设计时间：2015年3月28日——2015年 4月13日）中国矿业大学计算机学院一、问题描述旅行商问题（Traveling monituihuolesman Problem ，简称TSP ）又名货郎担问题，是威廉·哈密尔顿爵士和英国数学家克克曼(T.P.Kirkman)于19世纪初提出的一个数学问题，也是著名的组合优化问题。

问题是这样描述的：一名商人要到若干城市去推销商品，已知城市个数和各城市间的路程（或旅费），要求找到一条从城市1出发，经过所有城市且每个城市只能访问一次，最后回到城市1的路线，使总的路程（或旅费）最小。

TSP 刚提出时，不少人认为这个问题很简单。

后来人们才逐步意识到这个问题只是表述简单，易于为人们所理解，而其计算复杂性却是问题的输入规模的指数函数，属于相当难解的问题。

这个问题数学描述为：假设有n 个城市，并分别编号，给定一个完全无向图G=（V ，E ），V={1，2，…，n}，n>1。

其每一边(i,j)∈E 有一非负整数耗费 Ci,j(即上的权记为Ci,j ，i ，j ∈V)。

并设1,i j 0{ij X =边（，）在最优线路上， 其他G 的一条巡回路线是经过V 中的每个顶点恰好一次的回路。

一条巡回路线的耗费是这条路线上所有边的权值之和。

TSP 问题就是要找出G 的最小耗费回路。

人们在考虑解决这个问题时，一般首先想到的最原始的一种方法就是:列出每一条可供选择的路线(即对给定的城市进行排列组合)，计算出每条路线的总里程，最后从中选出一条最短的路线。

假设现在给定的4个城市分别为A 、B 、C 和D ，各城市之间的耗费为己知数，如图1-1所示。

我们可以通过一个组合的状态空间图来表示所有的组合，如图1-2所示。

（1-1）图1-1 顶点带权图图1-2 TSP问题的解空间树1.模拟退火是什么?首先,让我们看看模拟退火是如何工作的,以及为什么它是善于解决旅行商问题。

用模拟退火算法或者遗传算法解决TSP问题程序用模拟退火算法、遗传算法（或蚁群算法）求解10城市的TSP （旅行商）问题，计算旅行封闭的最短旅行距离。

解：用遗传算法解决TSP 问题，首先需要确定城市个数及城市间的距离，随机产生城市序列作为一个个体，确定目标函数，通过遗传算法的复制、交叉、变异求出最优解。

目标函数f x = d i ,i +1 +d (n ,0)n i =0适应度函数F x = ?f x +C max f x <="" p="">遗传算法的步骤为复制+交叉+变异=新一代遗传算法主程序：DG=0.9;MAXDD=100;ZQDX=150;Pc=0.7;Pm=0.01;ZQ=[0 118 1272 2567 1653 2097 1425 1177 3947 1574118 0 1253 2511 1633 2077 1369 1157 3961 15181272 1253 0 1462 380 1490 821 856 3660 3852567 2511 1462 0 922 2335 1562 2165 3995 9331653 1633 380 922 0 1700 1041 1135 3870 4562097 2077 1490 2335 1700 0 2311 920 2170 19201425 1369 821 1562 1041 2311 0 1420 4290 6261177 1157 856 2165 1135 920 1420 0 2870 12903947 3961 3660 3995 3870 2170 4290 2870 0 40901574 1518 385 993 456 1920 626 1290 4090 0];D=size(ZQ,1);EE=CSHZQ(ZQDX,D);disp('初始种群中的一个随机值:')SCXL(EE(1,:));RTH=XLCD(ZQ,EE(1,:));disp('总距离:');disp(num2str(RTH));Q=0;OV=XLCD(ZQ,EE);POV=min(OV);while (Q<maxdd)< p=""> OV=XLCD(ZQ,EE);POV=min(OV);SYD=SHYD(OV);XZ=XUANZE(EE,SYD,DG);XZ=JIAOC(XZ,Pc);XZ=BY(XZ,Pm);XZ=NZ(XZ,ZQ);EE=CCZ(EE,XZ,OV);Q=Q+1;endOV=XLCD(ZQ,EE); [minOV,minInd]=min(OV); disp('最优解:')p=SCXL(EE(minInd(1),:)); disp('总距离：');disp(num2str(OV(minInd(1)))); 初始化全局变量：function EE=CSHZQ(ZQDX,D) EE=zeros(ZQDX,D);for (i=1: ZQDX)EE(i,:)=randperm(D);end适应度函数：function SYD=SHYD(len)SYD=1./len;选择程序：function XZ=XUANZE(EE,SYD,DG)ZQDX =size(EE,1);NSel=max(floor(ZQDX *DG+.5),2);ChrIx=sus(SYD,NSel);XZ=EE(ChrIx,:);function NewChrIx=sus(SYD,Nsel)[Nind,ans]=size(SYD);cumfit=cumsum(SYD);trials=cumfit(Nind)/Nsel*(rand+(0:Nsel-1)');Mf=cumfit(:,ones(1,Nsel));Mt=trials(:,ones(1,Nind))';[NewChrIx,ans]=find(Mt<="Mt);" [ans,shuf]="sort(rand(Nsel,1));</p">NewChrIx=NewChrIx(shuf);交叉：function XZ=JIAOC(XZ,Pc)NSel=size(XZ,1);for (i=1:2:NSel-mod(NSel,2))if (Pc>=rand)[XZ(i,:),XZ(i+1,:)]=ICS(XZ(i,:),XZ(i+1,:));endendICS函数function [a,b]=ICS(a,b)L=length(a);r1=randsrc(1,1,[1:L]);r2=randsrc(1,1,[1:L]);if r1~=r2a0=a;b0=b;s=min([r1,r2]);e=max([r1,r2]);for i=s:ea1=a;b1=b;a(i)=b0(i);b(i)=a0(i);x=find(a==a(i));y=find(b==b(i));i1=x(x~=i);i2=y(y~=i);if ~isempty(i1)a(i1)=a1(i);endif ~isempty(i2)b(i2)=b1(i);endendend变异：function XZ=BY(XZ,Pm) [NSel,L]=size(XZ);for (i=1:NSel)if (Pm>=rand)R=randperm(L);XZ(i,R(1:2))=XZ(i,R(2:-1:1)); endend进化逆转：function XZ=NZ(XZ,ZQ)[row,col]=size(XZ);OV=XLCD(ZQ,XZ);XZ1=XZ;for i=1:rowr1=randsrc(1,1,[1:col]);r2=randsrc(1,1,[1:col]);mininverse=min([r1,r2]);maxinverse=max([r1,r2]);XZ1(1,mininverse:maxinverse)=XZ1(i,maxinverse:-1:mininverse); endOV1=XLCD(ZQ,XZ1);index=OV1<ov;< p="">XZ(index,:)=XZ(index,:);得到新一代：function EE=CCZ(EE,XZ,OV)ZQDX =size(EE,1);NSel=size(XZ,1);[TobjV,index]=sort(OV);EE=[EE(index(1: ZQDX -NSel),:);XZ]; 计算线路长度：function len=XLCD(ZQ,EE)[row,col]=size(ZQ);ZQDX =size(EE,1);len=zeros(ZQDX,1);for (i=1: ZQDX)p=[EE(i,:) EE(i,1)];i1=p(1:end-1);i2=p(2:end);len(i,1)=sum(ZQ ((i1-1)*col+i2)); end输出线路长度：function p=SCXL(R)R=[R,R(1)];N=length(R);p=num2str(R(1));for (i=2:N)p=[p,'->',num2str(R(i))]; enddisp(p)</ov;<></maxdd)<>。

模拟退火算法解决TSP问题本文主要使用模拟退火算法解决旅行商(TSP)问题，并成功的在Matlab中仿真并得到优化结果。

下面的算法程序中有详细的注释以方便大家了解。

1 算法仿真的收敛曲线2 路径规划结果图模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis[1]等人于1953年提出。

1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。

它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

算法程序：程序分为五部分，下面第一部分是主程序，每个function函数用虚线分开，大家在使用时需要放在不同的.m文件中。

主程序：---------------------------------------------------------------------------------------------------------------------------------- function saclearCityNum=50; %城市个数可分别选30，50，70[dislist,Clist]=tsp(CityNum); %tsp函数中包含城市坐标，dislist是距离矩阵，clist是城市坐标tf=0.01;%最后的温度alpha=0.80;%温度参数L=100*CityNum; %马尔可夫链的长度for i=1:100route=randperm(CityNum);%随机城市序列，即将citynum个城市序列打乱fval0(i)=CalDist(dislist,route);%城市距离之和最优endt0=-(max(fval0)-min(fval0))/log(0.9);%初始温度fval=fval0(100);route_best=route;%最优城市序列fval_best=fval;%城市距离之和最优t=t0;ii=0;%% 搜索开始while t>tf %tf最终温度是while循环的结束条件for i=1:L[fval_after,route_after]=exchange(route,dislist);if fval_after<fvalroute=route_after;fval=fval_after;elseif exp((fval-fval_after)/t)>randroute=route_after;fval=fval_after;endendii=ii+1;drawTSP(Clist,route,fval,ii,0);%作图程序if fval<fval_bestroute_best=route;fval_best=fval;endt=alpha*t;fval_sequence(ii)=fval;enddrawTSP(Clist,route_best,fval_best,ii,1);%作图程序figure(2);plot(1:ii,fval_sequence);%plot the convergence figuretitle('搜索过程');string1=['最短距离',num2str(fval_best)];gtext(string1);end----------------------------------------------------------------------------------------------------------------------------------function [DLn,cityn]=tsp(n)%坐标函数，可根据自己需要修改if n==10city10=[0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414;0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634];%10 cities d'=2.691for i=1:10for j=1:10DL10(i,j)=((city10(i,1)-city10(j,1))^2+(city10(i,2)-city10(j,2))^2)^0.5;endendDLn=DL10;cityn=city10;endif n==30city30=[41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50];%30 cities d'=423.741 by D B Fogelfor i=1:30for j=1:30DL30(i,j)=((city30(i,1)-city30(j,1))^2+(city30(i,2)-city30(j,2))^2)^0.5;endendDLn=DL30;cityn=city30;endif n==50city50=[31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57;17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22;27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33;58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67];%50 cities d'=427.855 by D B Fogelfor i=1:50for j=1:50DL50(i,j)=((city50(i,1)-city50(j,1))^2+(city50(i,2)-city50(j,2))^2)^0.5; DL50(i,j)=((city50(i,1)-city50(j,1))^2+(city50(i,2)-city50(j,2))^2)^0.5;endendDLn=DL50;cityn=city50;endif n==75city75=[48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30;55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36;20 30;26 29;40 20;36 26;62 48;67 41;62 35;65 27;62 24;55 20;35 51;30 50;45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15;44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56;10 70;17 64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26];%75 cities d'=549.18 by D B Fogelfor i=1:75for j=1:75DL75(i,j)=((city75(i,1)-city75(j,1))^2+(city75(i,2)-city75(j,2))^2)^0.5; DL75(i,j)=((city75(i,1)-city75(j,1))^2+(city75(i,2)-city75(j,2))^2)^0.5;endendDLn=DL75;cityn=city75;end----------------------------------------------------------------------------------------------------------------------------------function F=CalDist(dislist,s)DistanV=0;n=size(s,2);for i=1:(n-1)DistanV=DistanV+dislist(s(i),s(i+1));endDistanV=DistanV+dislist(s(n),s(1));F=DistanV;-----------------------------------------------------------------------------------function [fval_after,route_after]=exchange(route,d)n=length(d);location1=ceil(n*rand);location2=location1;while location2==location1location2=ceil(n*rand);%the location of two exchanged numberendloc1=min(location1,location2);loc2=max(location1,location2);middle_route=fliplr(route(loc1:loc2));%the part route which has been exchangedroute_after=[route(1:loc1-1) middle_route route(loc2+1:n)];%the after traveling route fval_after=CalDist(d,route_after);end----------------------------------------------------------------------------------function m=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);for i=1:CityNum-1plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'ms-', 'LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');hold on;endplot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2) ],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');title([num2str(CityNum),'城市TSP']);if f==0text(5,5,['第 ',int2str(p),' 步',' 最短距离为 ',num2str(bsf)]);elsetext(5,5,['最终搜索结果：最短距离 ',num2str(bsf)]);endhold off;pause(0.05);----------------------------------------------------------------------------------- 结束。

基于模拟退火算法的TSP问题求解算法研究旅行商问题（Traveling Salesman Problem，TSP）是运筹学中一个经典的问题，它是一个非常著名的NP难题。

该问题的简化版本就是，给定一些城市和每对城市之间的距离，求解访问每个城市一次且仅一次，并回到起点所需要的最短路径。

这个问题在实际生产和科学研究中具有重要的应用价值，例如供应链物流、电路设计等领域。

由于该问题是NP难问题，传统的精确求解算法在处理较大的实例时会遇到很大的困难。

因此，研究者们通常选择利用启发式算法来求解TSP问题。

其中一种较为经典的启发式算法是模拟退火算法（Simulated Annealing Algorithm，SAA）。

模拟退火算法的基本原理是模拟物质的固化过程，从一个高温状态开始，利用概率方法在状态空间中随机漫步，降低温度，直至固化为止。

在求解TSP问题中，SAA的核心思想是通过迭代寻找更优解，它的求解过程类似于热力学中的退火过程。

SAA解决TSP问题的具体步骤如下：1.建立初始解：随机生成一条回路2.设定初始温度T，以一定的步长降温3.在当前解的邻域内，随机产生一个新解4.计算ΔE = Enew - Eold，其中Enew为新解的目标函数值，Eold为当前解的目标函数值5.当ΔE < 0，接受新解。

当ΔE > 0，计算概率P = exp(-ΔE/T)，如果P > rand(0, 1)，则接受新解。

6.重复3-5步，直至温度降至指定值在应用SAA求解TSP问题时，邻域搜索空间的大小和搜索速度是需要考虑的两个重要因素。

为了提高算法的效率，改进SAA算法成为了许多研究的重点。

一些常见的SAA改进方法包括：1.使用启发式算子，如2-opt算子和3-opt算子，来生成新解，避免了随机产生新解的盲目性。

2.设置合适的退火迭代次数，可以在短时间内获得较好的解，同时提高搜索速度。

3.采用并行计算的方式，多个线程同时搜索，并将较优解合并，可以进一步提高搜索效率。

模拟退火算法解决TSP问题一、算法说明：模拟退火算法求解TSP问题的流程框图如图所示二、结果分析蓝色字表示输出结果运行时间表示算法复杂度1)数据集一:模式城市数量为5时输入模式城市数量5为了方便查看，数据和结果保存在文件中<<<<邻接矩阵保存在文件模拟退火算法-随机产生数据.txt 中<<<<访问顺序保存在文件模拟退火算法-结果数据.txt 中模拟节点个数 5运行时间: 10 ms邻接矩阵0 1 57 20 811 0 59 49 3657 59 0 90 8220 49 90 0 7581 36 82 75 0访问节点顺序3 5 24 12)数据集二:模式城市数量为10时输入模式城市数量10为了方便查看，数据和结果保存在文件中<<<<邻接矩阵保存在文件模拟退火算法-随机产生数据.txt 中<<<<访问顺序保存在文件模拟退火算法-结果数据.txt 中模拟节点个数 10运行时间: 15 ms邻接矩阵0 1 57 20 81 59 49 36 90 821 0 75 18 86 71 52 31 2 1057 75 0 37 16 17 99 45 13 120 18 37 0 2 38 54 58 61 6181 86 16 2 0 17 67 46 36 759 71 17 38 17 0 61 79 80 5249 52 99 54 67 61 0 31 88 7336 31 45 58 46 79 31 0 96 9390 2 13 61 36 80 88 96 0 5482 10 1 61 7 52 73 93 54 0访问节点顺序176****94533)数据集三:模式城市数量为20时输入模式城市数量20为了方便查看，数据和结果保存在文件中<<<<邻接矩阵保存在文件模拟退火算法-随机产生数据.txt 中<<<<访问顺序保存在文件模拟退火算法-结果数据.txt 中模拟节点个数 20运行时间: 17ms邻接矩阵0 1 57 20 81 59 49 36 90 82 75 18 86 71 52 31 2 10 37 161 0 17 99 45 13 12 38 54 58 61 61 17 67 46 36 7 61 7957 17 0 80 52 31 88 73 96 93 54 15 47 24 86 22 78 85 100 100 20 99 80 0 62 40 27 30 84 3 38 10 68 7 2 92 28 28 59 6981 45 52 62 0 84 73 49 21 75 47 46 95 75 12 60 39 74 61 58 59 13 31 40 84 0 37 16 23 43 80 52 99 75 35 18 66 50 7 7049 1 88 27 73 37 0 51 16 95 15 91 70 31 43 8 97 69 16 8836 2 73 30 49 16 51 0 82 59 20 19 82 48 16 51 73 41 29 5790 38 96 84 21 23 16 82 0 69 76 72 48 13 37 84 4 52 67 4382 54 93 3 75 43 95 59 69 0 11 95 92 55 35 48 38 85 32 4675 58 54 38 47 80 15 20 76 11 0 28 98 30 74 57 20 76 84 40 18 61 15 10 46 52 91 19 72 95 28 0 51 89 4 99 58 6 54 2086 61 47 68 95 99 70 82 48 92 98 51 0 84 63 66 21 84 13 12 71 17 24 7 75 75 31 48 13 55 30 89 84 0 75 32 94 29 34 1552 67 86 2 12 35 43 16 37 35 74 4 63 75 0 74 84 71 60 7531 46 22 92 60 18 8 51 84 48 57 99 66 32 74 0 26 15 1 72 36 78 28 39 66 97 734 38 20 58 21 94 84 26 0 81 85 2210 7 85 28 74 50 69 41 52 85 76 6 84 29 71 15 81 0 12 5637 61 100 59 61 7 16 29 67 32 84 54 13 34 60 1 85 12 0 216 79 100 69 58 70 88 57 43 46 40 20 12 15 75 7 22 56 2 0访问节点顺序19 12 20 6 1 7 5 18 15 2 13 3 9 10 16 8 4 14 11 17代码：#include<iostream>#include<ctime>#include<cstdio>#include<cstdlib>#include<cmath>#include<time.h>#include<stdlib.h>#include<stdio.h>#include <windows.h>#define MAX 10000#define INF 10000000#define E 0.000000001 // 迭代误差#define L 20000 // 迭代次数#define AT 0.999 // 降温系数#define T 1 // 初始温度using namespace std;struct element{ //用来排序的数据结构int data; // 数据int index; // 序号};int tsp(int d[][MAX], int n, double e,int l,double at,double t,int s0[]); //利用模拟退火算法求解最短路径int cmp(const void *a,const void *b); //升序排列void rand_of_n(int a[],int n); //产生 1-n 的随机排列并存到 a[] 中int random(int m,int n);int dis[MAX][MAX]; // d[i][j] 表示客户i到客户j的距离，0 表示起始点void rand_of_n(int a[],int n){int i;struct element ele[MAX];srand((int)time(0)); // 初始化随机数种子for(i=0;i<n;i++){ele[i].data=rand(); // 随机生成一个数ele[i].index=i+1;}qsort(ele,n,sizeof(ele[0]),cmp); //排序for(i=0;i<n;i++){a[i]=ele[i].index;}}int random(int m,int n){ //产生m-n的随机数int a;double x=(double)rand()/RAND_MAX;a=(int)(x*(n-m)+0.5)+m;return a;}int cmp(const void *a,const void *b){ // 升序排序return((struct element*)a)->data - ((struct element*)b)->data;}int tsp(int d[][MAX], int n, double e,int l,double at,double t,int s0[]){ int i,j,s[MAX],sum,temp;sum=INF;for(i=0;i<1000;i++){ //利用蒙特卡洛方法产生初始解rand_of_n(&s[1],n);s[0]=0; s[n+1]=0; //第一个和最后一个点为起始点temp=0;for(j=0;j<=n;j++)temp=temp+d[s[j]][s[j+1]];if(temp<sum){for(j=0;j<=n+1;j++)s0[j]=s[j];sum=temp;}}for(i=0;i<l;i++){ //退火过程int c1,c2;c1=random(1,n);c2=random(1,n);if(c1>c2){int temp=c2; c2=c1; c1=temp;}if(c1==c2)continue;int df=d[s0[c1-1]][s0[c2]] + d[s0[c1]][s0[c2+1]] - d[s0[c1-1]][s0[c1]] - d[s0[c2]][s0[c2+1]]; //计算代价函数if(df<0){ //接受准则while(c1<c2){int temp=s0[c2]; s0[c2]=s0[c1]; s0[c1]=temp;c1++;c2--;}sum=sum+df;}else if(exp(-df/t)>((double)rand()/RAND_MAX)){while(c1<c2){int temp=s0[c2]; s0[c2]=s0[c1]; s0[c1]=temp;c1++;c2--;}sum=sum+df;}t=t*at;if(t<e)break;}return sum;}int main(){DWORD start, stop;int i,j;int n;cout<<"输入模式城市数量然后输入回车,例如 10 回车"<<endl;cin>>n;start = GetTickCount();//程序开始时间for(i=0;i<n;i++) // 随机产生距离 1-100for(j=i;j<n;j++)if(i==j)dis[i][j]=0;elsedis[i][j]=dis[j][i]=random(1,100);FILE*fp = fopen("模拟退火算法-随机产生数据.txt","w"); // 将距离存入文件中for(i=0;i<n;i++){for(j=0;j<n;j++)fprintf(fp,"%d ",dis[i][j]);fprintf(fp,"\n");}fclose(fp);int sum,sum0,s0[MAX];sum0=0; //顺序遍历时的路程for(i=0;i<n;i++)sum0=sum0+dis[i][i+1];sum0=sum0+dis[n][0];sum=tsp(dis,n, E,L,AT,T,s0);fp = fopen("模拟退火算法-结果数据.txt","w"); //将结果存入文件中for(i=1;i<=n;i++)fprintf(fp,"%d ",s0[i]);fclose(fp);cout<<endl;cout<<"为了方便查看，数据和结果保存在文件中"<<endl;cout<<"<<<<邻接矩阵保存在文件模拟退火算法-随机产生数据.txt 中"<<endl<<"<<<<访问顺序保存在文件模拟退火算法-结果数据.txt 中"<<endl;cout<<endl;printf("模拟节点个数 %d\n", n);stop = GetTickCount();//程序结束时间printf("运行时间: %lld ms\n", stop - start);system("pause");return 0;}。

改进模拟退火算法求解ＴＳＰ问题作者：盛国华陈玉金来源：《电脑知识与技术·学术交流》2008年第15期摘要：对模拟退火算法进行了改进，从不同的初始状态开始搜索来解决TSP问题，并将计算的结果与遗传算法的计算结果进行比较，优于文献[1]中遗传算法的结果。

关键词：TSP；模拟退火；Metropolis准则；二邻域法中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)15-20ppp-0cModified Simulated Annealing Algorithm for TSPSHENG Guo-hua,CHEN Yu-jin(People's Liberation Army University of Science & Technology,Nanjing 210007,China)Abstract: Modify the simulated annealing algorithm .Begin to search for solving TSP from different initial states ,and compares the result with the result of genetic algorithm. We find that the result excels the result of genetic algorithm in the literature[one].Key words: TSP; Simulated Annealing; Metropolis rule; two neighbourhood method1 TSP问题描述TSP问题可描述为：有n个城市，且已知城市i到城市j的距离矩阵D=[dij]n×n，其中，dij≥0，dij=dji，dii=0且对于任意的k，有dik+dkj≥dij(i,j,k=1,2,…n)。

模拟退火遗传算法求解TSP问题
郭晓利;李航宇
【期刊名称】《福建电脑》
【年(卷),期】2014(000)005
【摘要】本文提出了一个用于求解TSP问题的改进模拟退火的遗传算法，利用遗传算法的全局搜索能力弥补了模拟退火算法容易陷入局部最优的问题。

用100个城市和255个城市的TSP问题验证算法，实验测试的结果表明该方法具有较好的收敛效果和可靠的稳定性。

【总页数】2页(P15-16)
【作者】郭晓利;李航宇
【作者单位】东北电力大学吉林吉林 132012;东北电力大学吉林吉林 132012【正文语种】中文
【相关文献】
1.多种群自适应模拟退火遗传算法求解TSP问题 [J], 夏仁强
2.改进的模拟退火和遗传算法求解TSP问题 [J], 姚明海;王娜;赵连朋
3.求解TSP问题的改进模拟退火遗传算法 [J], 王银年;葛洪伟
4.基于遗传模拟退火策略的霍普菲尔德神经网络求解TSP问题 [J], 于兆敏
5.求解TSP问题的改进模拟退火算法 [J], 何锦福;符强;王豪东
因版权原因，仅展示原文概要，查看原文内容请购买。