基于模拟退火算法的TSP算法

专业综合设计报告课程名称： 电子专业综合设计 设计名称： 基于模拟退火算法的TSP算法 姓 名： 学 号: 班 级： 电子0903 指导教师： 朱正为 起止日期： 2012.11.1-2012.12.30 专 业 综 合 设 计 任 务 书学生班级： 电子0903 学生姓名： 学号： 20095830 设计名称： 基于模拟退火算法的TSP算法 起止日期： 2012.11.1-2012.12.30 指导教师 设计要求： 旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 此设计是用模拟退火算法来实现TSP问题的寻求最优解。专 业 综 合 设 计 学 生 日 志时间设计内容2012.11.9初步了解模拟退火算法的TSP算法2012.11.12设计算法流程、确定解题思路2012.11.20 讨论算法流程及解题思路的可行性，为仿真做准备2012.12.2运用MATLAB软件进行实验仿真，分析仿真结果2012.12.8 整理实验报告2012.12.17 答辩 专 业 综 合 设 计 考 勤 表周星期一星期二星期三星期四星期五专 业 综 合 设 计 评 语 表指导教师评语： 成绩： 指导教师： 年 月 日一 设计目的和意义5二 设计原理5 2.1 模拟退火算法的基本原理.52.2 TSP问题介绍.6三 详细设计步骤.73.1.算法流程83.2模拟退火算法实现步骤8四 设计结果及分析9 4.1 MATLAB程序实现及主函数.9 4.1.1 计算距离矩阵.9 4.1.2 初始解.10 4.1.3 生成新解.10 4.1.4 Metropolis 准则函数. .10 4.1.5 画路线轨迹图.11 4.1.6 输出路径函数.12 4.1.7 可行解路线长度函数.12 4.1.8 模拟退火算法的主函数.134.2.仿真结果15五 体会18六 参考文献19基于模拟退火算法的TSP算法一 、设计目的和意义 旅行商问题是组合优化领域里的一个典型的、易于描述却难以处理的NP难题，其可能的路径数目与城市数目是呈指数型增长的，求解非常困难。首先介绍了旅行商问题，给出了其数学描述以及实际应用，进而给出解决TSP的一种比较精确的算法模拟退火算法。然后阐述了模拟退火算法的基本原理，重点说明了其基本思想及关键技术。最后运用MATLAB语言实现了该算法，并将其运用到解决旅行商问题的优化之中。数值仿真的结果表明了该方法能够对数据进行全局寻优，有效克服了基于导数的优化算法容易陷入局部最优的问题。 了解模拟退火算法的TSP算法的基本思路及原理，并应用MATLAB实现仿真，熟练掌握MATLAB的操作方式及应用，能正确书写报告。 二 、设计原理 2.1 模拟退火算法的基本原理 模拟退火算法足2O世纪8O年代初提出的一种基于蒙特卡罗(Mente Carlo)迭代求解策略的启发式随机优化算法。它通过Metropolis接受准则概率接受劣化解并以此跳出局部最优，通过温度更新函数的退温过程进行趋化式搜索并最终进入全局最优解集。其出发点是基于物理中固体物质的退火过程与一搬的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成。（1） 加温过程。 其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。（2） 等温过程。 对于与周围环境交换热量而温度不变的密封系统，系统状态的自发变化总是朝自由能减少的方向进行的，当自由能达到最小时，系统达到平衡状态。（3） 冷却过程。 使粒子热运动减弱，系统能量下降，得到晶体结构。 其中，加热过程对应算法的设定初温，等温过程对应算法的 Metropolis 抽样过程，冷却过程对应控制参数的下降。这里能量的变化就是目标函数，要得到的最优解就是能量最低态。Metropolis 准则是SA算法收敛于全局最优解的关键所在，Metropolis 准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。 模拟退火算法为求解传统方法难处理的TSP问题提供了一个有效的途径和通用框架，并逐渐发展成一种迭代自适应启发式概率性搜索算法。模拟退火算法可以用以求解不同的非线性问题，对不可微甚至不连续的函数优化，能以较大的概率求的全局有化解，该算法还具有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性，并且能处理不同类型的优化设计变量（离散的、连续的和混合型的），不需要任何的辅助信息，对目标函数和约束函数没有任何要求。利用 Metropolis 算法并适当的控制温度下降过程，在优化问题中具有很强的竞争力，此设计即为基于模拟退火算法的TSP算法。 SA算法实现过程如下（以最小化问题为例）： （1）初始化：取初始温度T0足够大，令T=T0,任取初始解S1,确定每个T时的迭代次数，即 Metropolis 链长 L。 （2）对当前温度T和k=1,2，l，重复步骤（3）（6）。 （3）对当前S1随机扰动产生一个新解S2。 （4）计算S2的增量df=f（S2）-f（S1） 其中f为S1的代价函数。 （5）若dfrand也接受S2作为新的当前解，S1=S2；否则保留当前解S1。 （6）如果满足终止条件Stop，则输出当前解s1为最优解，结束程序。终止条件Stop 通常为：在连续若干个 Metropolis 链中新解s2都没有被接受时终止算法，或是设定结束温度。否则按衰减函数衰减 T 后返回步骤（2）。 以上步骤成为 Metropolis 过程。逐渐降低控制温度，重复 Metropolis 过程，直至满足结束准则 Stop，求出最优解。 2.2 TSP问题介绍 旅行商问题（Traveling Salesman Problem，简称TSP）又名货郎担问题，是威廉哈密尔顿爵士和英国数学家克克曼(T.P.Kirkman)于19世纪初提出的一个数学问题，也是著名的组合优化问题。问题是这样描述的：一名商人要到若干城市去推销商品，已知城市个数和各城市间的路程（或旅费），要求找到一条从城市1出发，经过所有城市且每个城市只能访问一次，最后回到城市1的路线，使总的路程（或旅费）最小。TSP刚提出时，不少人认为这个问题很简单。后来人们才逐步意识到这个问题只是表述简单，易于为人们所理解，而其计算复杂性却是问题的输入规模的指数函数，属于相当难解的问题。这个问题数学描述为：假设有n个城市，并分别编号，给定一个完全无向图G=（V，E），V=1，2，n，n1。其每一边(i,j)E有一非负整数耗费 Ci,j(即上的权记为Ci,j，i，jV)。G的一条巡回路线是经过V中的每个顶点恰好一次的回路。一条巡回路线的耗费是这条路线上所有边的权值之和。TSP问题就是要找出G的最小耗费回路。人们在考虑解决这个问题时，一般首先想到的最原始的一种方法就是:列出每一条可供选择的路线(即对给定的城市进行排列组合)，计算出每条路线的总里程，最后从中选出一条最短的路线。假设现在给定的4个城市分别为A、B、C和D，各城市之间的耗费为己知数，如图1所示。我们可以通过一个组合的状态空间图来表示所有的组合，如图 图 1 顶点带权图 图 2 TSP问题的解空间树从图中不难看出，可供选择的路线共有6条，从中很快可以选出一条总耗费最短的路线：顶点序列为（A,C,B,D,A）。由此推算，若设城市数目为n时，那么组合路径数则为(n-1)!。很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。假设现在城市的数目增为20个，组合路径数则为(20-1)!1.2161017，如此庞大的组合数目，若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间6。 三 、详细设计步骤3.1算法流程模拟退火算法求解流程框图如图1所示。 图3 模拟退火算法求解流程框图3.2模拟退火算法实现步骤如下： （1）控制参数的设置 需要设置的主要控制参数有降温速率q、初始温度T0、结束温度Tend以及链长L。 （2）初始解 对于n个城市TSP问题，得到的解就是对1n的一个排序，其中每个数字为对应城市的编号，如对10个城市的TSP问题1,2,3,4,5,6,7,8,9,10，则 |1|10|2|4|5|6|8|7|9|3就是一个合法的解，采用产生随机排列的方法产生一个初始解S。 （3）解变换生成新解 通过对当前解S1进行变换，产生新的路径数组即新解，这里采用的变换是产生随机数的方法来产生将要交换的两个城市，用二邻域变换法产生新的路径，即新的可行解S2。 例如n=10时，产生两个1,10范围内的随机整数r1和r2，确定两个位置，将其对换位置，如r1=4，r2=7 9 5 1 6 3 8 7 10 4 2 得到的新解为 9 5 1 7 3 8 6 10 4 2 （4）Metropolis准则 若路径长度函数为（S），新解的路径为（S2），路径差为d=（S2）-（S1）,则Metropolis准则为 如果df0,则以概率1接受新路线，否则以概率exp（-df/T）接受新路线。 （5）降温 利用降温速率q进行降温，即T=qT,若T小于结束温度，则停止迭代输出当前状态，否则继续迭代。 四 、设计结果及分析4.1 MATLAB程序实现及主函数4.1.1 计算距离矩阵 利用给出的N个城市的坐标，算出N个城市的两两之间的距离，得到距离矩阵（NN）。计算函数为Distance，得到初始群种。程序如下function D=Distanse(a)% 计算两两城市之间的距离%输入 a 各城市的位置坐标%输出 D 两两城市之间的距离row=size(a,1);D=zeros(row,row);for i=1:row for j=i+1:row D(i,j)=(a(i,1)-a(j,1)2+(a(i,2)-a(j,2)2)0.5; D(j,i)=D(i,j); endend4.1.2 初始解 初始解的产生直接使用MATLAB自带的函数randperm，如城市格式为N个，则产生初始解：S1=randperm（N）； %随机产生一个初始路线 4.1.3 生成新解 解变换生成新解函数为NewAnswer，程序代码如下：function S2=NewAnswer(S1)% 输入% S1:当前解% 输出% S2：新解N=length(S1);S2=S1; a=round(rand(1,2)*(N-1)+1); %产生两个随机位置 用来交换W=S2(a(1);S2(a(1)=S2(a(2);S2(a(2)=W; %得到一个新路线4.1.4 Metropolis 准则函数Metropolis 准则函数为 Metropolis，程序代码如下：function S,R=Metropolis(S1,S2,D,T)% 输入% S1： 当前解% S2: 新解% D: 距离矩阵（两两城市的之间的距离）% T: 当前温度% 输出% S： 下一个当前解% R： 下一个当前解的路线距离%R1=PathLength(D,S1); %计算路线长度N=length(S1); %得到城市的个数 R2=PathLength(D,S2); %计算路线长度dC=R2-R1; %计算能力之差if dC=rand %以exp(-dC/T)概率接受新路线 S=S2; R=R2;else %不接受新路线 S=S1; R=R1;end4.1.5 画路线轨迹图 画出给的路线的轨迹图函数为DrawPath，程序代码如下：function DrawPath(Chrom,X)% 画路径函数%输入% Chrom 待画路径 % X 各城市坐标位置R=Chrom(1,:) Chrom(1,1); %一个随机解(个体)figure;hold onplot(X(:,1),X(:,2),o,color,0.5,0.5,0.5)plot(X(Chrom(1,1),1),X(Chrom(1,1),2),rv,MarkerSize,20)for i=1:size(X,1) text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),color,1,0,0);endA=X(R,:);row=size(A,1);for i=2:row arrowx,arrowy = dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2);%坐标转换 annotation(textarrow,arrowx,arrowy,HeadWidth,8,color,0,0,1);endhold offxlabel(横坐标)ylabel(纵坐标)title(轨迹图)box on4.1.6 输出路径函数 将得到的路径输出显示在Command Window 中，函数名为OutputPath。function p=OutputPath(R)% 输出路径函数%输入：R 路径R=R,R(1);N=length(R);p=num2str(R(1);for i=2:N p=p,num2str(R(i);enddisp(p)4.1.7 可行解路线长度函数 计算可行解的路线长度函数为PathLength ，程序代码如下：function len=PathLength(D,Chrom)% 计算各个体的路径长度% 输入：% D 两两城市之间的距离% Chrom 个体的轨迹row,col=size(D);NIND=size(Chrom,1);len=zeros(NIND,1);for i=1:NIND p=Chrom(i,:) Chrom(i,1); i1=p(1:end-1); i2=p(2:end); len(i,1)=sum(D(i1-1)*col+i2);end4.1.8 模拟退火算法的主函数 模拟退火算法参数设置如表一所列。 表一 参数设定 降温速率q 初始温度T0 结束温度Tend 链长L 0.9 1000 0.001 200clc;clear;close all;%ticT0=1000; % 初始温度Tend=1e-3; % 终止温度L=500; % 各温度下的迭代次数（链长）q=0.9; %降温速率% 加载数据load CityPosition1;%D=Distanse(X); %计算距离矩阵N=size(D,1); %城市的个数% 初始解S1=randperm(N); %随机产生一个初始路线% 画出随机解的路径图DrawPath(S1,X)pause(0.0001)% 输出随机解的路径和总距离disp(初始种群中的一个随机值:)OutputPath(S1);Rlength=PathLength(D,S1);disp(总距离：,num2str(Rlength);% 计算迭代的次数TimeTime=ceil(double(solve(1000*(0.9)x=,num2str(Tend);count=0; %迭代计数Obj=zeros(Time,1); %目标值矩阵初始化track=zeros(Time,N); %每代的最优路线矩阵初始化% 迭代while T0Tend count=count+1; %更新迭代次数 主函数代码如下： temp=zeros(L,N+1); for k=1:L % 产生新解 S2=NewAnswer(S1); % Metropolis法则判断是否接受新解 S1,R=Metropolis(S1,S2,D,T0); %Metropolis 抽样算法 temp(k,:)=S1 R; %记录下一路线的及其路程 end % 记录每次迭代过程的最优路线 d0,index=min(temp(:,end); %找出当前温度下最优路线 if count=1 | d0Obj(count-1) Obj(count)=d0; %如果当前温度下最优路程小于上一路程则记录当前路程 else Obj(count)=Obj(count-1);%如果当前温度下最优路程大于上一路程则记录上一路程 end track(count,:)=temp(index,1:end-1); %记录当前温度的最优路线 T0=q*T0; %降温 fprintf(1,%dn,count) %输出当前迭代次数end% 优化过程迭代图figureplot(1:count,Obj)xlabel(迭代次数)ylabel(距离)title(优化过程)% 最优解的路径图DrawPath(track(end,:),X)% 输出最优解的路线和总距离disp(最优解:)S=track(end,:);p=OutputPath(S);disp(总距离：,num2str(PathLength(D,S);disp(-)toc4.2仿真结果及分析优化前的一个随机路线图如图4所示： 图4总路线距离约为57.00优化以后的最优解路线如下图5： 图5该优化路径的总路程近似为30.00，已为最优解。模拟退火算法进化过程图如下图6：由图可以看出，优化前后路径长度得到很大改进，变为原来的52.4%，65代以后路径长度已经保持不变了，可以认为已经是最优解了。 上图为用模拟退火算法解决TSP的GUI（Graphics User Interface,图形用户界面）。这是由14个城市构成的一个对称TSP实例，利用上述算法对该实例进行模拟退火求解，设定初始温度T0=1000，冷却速率为0.9，经过仿真得到的最优解与已知最优解非常接近，所需时间也令人满意。五 、体会使用MATIAB对求解TSP问题的模拟退火算法程序进行了仿真。平均结果表明，首先该算法能够找到TSP问题的最优解，说明算法的正确性。其次算法对TSP问题的求解时间并不呈指数增长，说明了算法的有效性。5.1关于MATLAB的体会MATLAB 是当今科学界最具影响力、也是最具活力的软件，它起源于矩阵运算，并已经发展成一种高度集成的计算机语言。 然后，了解到了MATLAB软件的功能。它提供了强大的科学运算、灵活的程序设计流程、高质量的图形可视化与界面设计、便捷的与其他程序和语言接口的功能。我们应该熟练掌握其使用方法。5.2关于基于模拟退火算法的TSP算法的体会 模拟退火算法是依据Metropolis准则接受新解，该准则除了接受优化解外，还在一定的限定范围内接受劣解，这正是模拟退火算法与局部搜索法的本质区别，在避免陷入局部极小值、提高解空间的搜索能力和扩大搜索范围方面具有明显的优越性。本次设计给出了一种TSP的求解算法，并用MATLAB语言编程实现了算法。算法实验结果表明，对大多数组合优化问题而言，模拟退火算法在求最优解和求解时间均达到了满意的结果。利用MATLAB语言实现的模拟退火程序，能够找到系统的最优解，仿真结果证明了该方法的有效性。采用该方法既可使我们熟悉MATLAB语言，又可以加深对模拟退火算法的认识和理解，以此来设计智能系统。 旅行商问题一直都是业界