一些解决TSP问题算法源代码Word格式.docx

1、前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法 决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则:0则接受S作 为新的当前解S，否则以概率exp（-t/T接受S作为新的当前解S。第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换

2、部分予以实现，同时修正 目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮实验。而当新解被判定为舍弃时，则在原当前解的 基础上继续下一轮实验。模拟退火算法与初始值无关，算法求得的解与初始解状态S（是算法迭代的起点无关；模拟退火算法具有渐近收敛性，已在 理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。3.5.2 模拟退火算法的简单应用 作为模拟退火算法应用，讨论货郎担问题（Travelling Salesman Problem，简记为TSP：设有n个城市，用数码1,n代表 。城市i和城市j之间的距离为d（i，j i, j=1,nTSP问题是要找

3、遍访每个域市恰好一次的一条回路，且其路径总长度为最 短.。求解TSP的模拟退火算法模型可描述如下：解空间 解空间S是遍访每个城市恰好一次的所有回路，是1，n的所有循环排列的集合，S中的成员记为（w1,w2 , ，wn，并记wn+1= w1。初始解可选为（1，n目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数：我们要求此代价函数的最小值。新解的产生 随机产生1和n之间的两相异数k和m，若k变为：（w1, w2 ,，wm , wm-1 ,，wk+1 , wk ,，wn. 如果是k（wm, wm-1 ,，w1 , wm+1 ,，wk-1 ,wn , wn-1 ,，wk上述变换方法可

4、简单说成是“逆转中间或者逆转两端”。也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。代价函数差 设将（w1, w2 ,，wn变换为（u1, u2 ,，un, 则代价函数差为：根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：Procedure TSPSA:begin init-of-T。 T为初始温度 S=1，n。 S为初始值 termination=false。while termination=false begin for i=1 to L do begin generate（Sform S 从当前回路S产生新回路S t:=f（S-f（S

5、f（S为路径总长 IF（t OR （EXP（-t/TRandom-of-0,1S=S。IF the-halt-condition-is-TRUE THEN termination=true。End。T_lower。End。End 模拟退火算法的应用很广泛，可以较高的效率求解最大截问题（Max Cut Problem、0-1背包问题（Zero One Knapsack Problem、图着色问题（Graph Colouring Problem、调度问题（Scheduling Problem等等。3.5.3 模拟退火算法的参数控制问题 模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控

6、制，其主要问题有以下三点： 温度T的初始值设置问题。温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但 因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要 依据实验结果进行若干次调整。 退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索（退火是相当必要的，但这 需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。 温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，因为必须考虑计算复杂度

7、的切实可行性等问题，常采 用如下所示的降温方式：T（t+1kT（t式中k为正的略小于1.00的常数，t为降温的次数 使用SA解决TSP问题的Matlab程序：function out = tsp（loc% TSP Traveling salesman problem （TSP using SA （simulated annealing.% TSP by itself will generate 20 cities within a unit cube and% then use SA to slove this problem.% TSP（LOC solve the traveling sal

8、esman problem with cities% coordinates given by LOC, which is an M by 2 matrix and M is% the number of cities.% For example:% loc = rand（50, 2% tsp（locif nargin = 0,% The following data is from the post by Jennifer Myers （jmyersnwu.edu% to comp.ai.neural-nets. Its obtained from the figure in% Hopfie

9、ld & Tanks 1985 paper in Biological Cybernetics% （Vol 52, pp. 141-152loc = 0.3663, 0.9076。 0.7459, 0.8713。 0.4521, 0.8465。0.7624, 0.7459。 0.7096, 0.7228。 0.0710, 0.7426。0.4224, 0.7129。 0.5908, 0.6931。 0.3201, 0.6403。0.5974, 0.6436。 0.3630, 0.5908。 0.6700, 0.5908。0.6172, 0.5495。 0.6667, 0.5446。 0.198

10、0, 0.4686。0.3498, 0.4488。 0.2673, 0.4274。 0.9439, 0.4208。0.8218, 0.3795。 0.3729, 0.2690。 0.6073, 0.2640。0.4158, 0.2475。 0.5990, 0.2261。 0.3927, 0.1947。0.5347, 0.1898。 0.3960, 0.1320。 0.6287, 0.0842。0.5000, 0.0396。 0.9802, 0.0182。 0.6832, 0.8515。endNumCity = length（loc % Number of citiesdistance = ze

11、ros（NumCity % Initialize a distance matrix% Fill the distance matrixfor i = 1:NumCity,for j = 1:distance（i, j = norm（loc（i, - loc（j, % To generate energy （objective function from path%path = randperm（NumCity%energy = sum（distance（path-1*NumCity + path（2:NumCity path（1% Find typical values of dEcount

12、 = 20。all_dE = zeros（count, 1countpath = randperm（NumCityenergy = sum（distance（path-1path（1new_path = path。index = round（rand（2,1*NumCity+.5inversion_index = （min（index:max（indexnew_path（inversion_index = fliplr（path（inversion_indexall_dE（i = abs（energy - .sum（sum（diff（loc（new_path new_path（1,.2dE =

13、 max（all_dEtemp = 10*dE。 % Choose the temperature to be large enoughfprintf（Initial energy = %fnn,energy% Initial plotsout = path path（1。plot（loc（out（, 1, loc（out（, 2,r., Markersize, 20axis square。 hold onh = plot（loc（out（, 1 hold offMaxTrialN = NumCity*100。 % Max. # of trials at atemperatureMaxAcce

14、ptN = NumCity*10。 % Max. # of acceptances at aStopTolerance = 0.005。 % Stopping toleranceTempRatio = 0.5。 % Temperature decrease ratiominE = inf。 % Initial value for min. energymaxE = -1。 % Initial value for max. energy% Major annealing loopwhile （maxE - minE/maxE StopTolerance,maxE = 0。TrialN = 0。

15、% Number of trial movesAcceptN = 0。 % Number of actual moveswhile TrialN MaxTrialN & AcceptN new_energy = sum（distance（ .（new_path-1*NumCity+new_path（2:new_path（1if rand /temp, % acceptit!energy = new_energy。path = new_path。minE = min（minE, energymaxE = max（maxE, energyAcceptN = AcceptN + 1。TrialN =

16、 TrialN + 1。% Update plotset（h, xdata, loc（out（, 1ydatadrawnow。% Print information in command windowtemp. = %fn, temptmp = sprintf（%d ,pathpath = %sn, tmpenergy = %fn, energyminE maxE = %f %fn, minE, maxEAcceptN TrialN = %d %dnn, AcceptN, TrialN% Lower the temperaturetemp = temp*TempRatio。% Print se

17、quential numbers in the graphic windowtext（loc（path（i,1+0.01, loc（path（i,2+0.01, int2str（i, .fontsize, 8end 又一个相关的Matlab程序functionX,P=zkp（w,c,M,t0,tfm,n=size（wL=100*n。t=t0。clear m。x=zeros（1,nxmax=x。fmax=0。while ttffor k=1:Lxr=change（xgx=g_0_1（w,xgxr=g_0_1（w,xrif gxrf=f_0_1（x,cdf=fr-f。if dfx=xr。if fr

18、fmaxfmax=fr。xmax=xr。elsep=rand。if pt=0.87*tP=fmax。X=xmax。%下面的函数产生新解function d_f,pi_r=exchange_2（pi0,dm,n=size（du=rand。u=u*（n-2u=round（uif un-2u=n-2。v=rand。v=v*（n-u+1v=round（vif vnv=n。pi_1（u=pi0（v=pi0（u（u-1pi_1（k=pi0（k（u+1（v-u-1pi_1（u+k=pi0（v-kfor k=（v+1d_f=0。d_f=d（pi0（u-1,pi0（v+d（pi0（u,pi0（v+1for k=

19、（u+1d_f=d_f+d（pi0（k,pi0（k-1-d（pi0（vd_f=d_f-d（pi0（u-1,pi0（ud_f=d_f-d（pi0（k-1,pi0（k,pi0（1-d（pi0（u-1d_f=d_f-d（pi0（kpi_r=pi_1。遗传算法GA遗传算法：旅行商问题（traveling saleman problem,简称tsp已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图 g=（v,e，其中v是顶点集，e是边集，设d=（dij是

20、由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题（dij=dji,任意i,j=1,2,3，,n和非对称旅行商问题（dijdji,任意i,j=1,2,3，,n若对于城市v=v1,v2,v3,vn的一个访问顺序为t=（t1,t2,t3,ti,tn,其中tiv（i=1,2,3,n，且记tn+1= t1，则旅行商问题的数学模型为：min l=d（t（i,t（i+1 评价函数eval（vi用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，

21、适应性强的染色体被选择产生后台的机会要大，设alpha（0,1，本文定义基于序的评价函数为eval（vi=alpha*（1-alpha.（i-1 。随机规划与模糊规划选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1 、对每个染色体vi,计算累计概率qi，q0=0。qi=eval（vj j=1,i。i=1,pop-size.step2、从区间（0,pop-size中产生一个随机数r；step3、若qi-1rqi,则选择第i个染色体 ；step4、重复step2和step3共pop-size次，这样可

22、以得到pop-size个复制的染色体。grefenstette编码：因为常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefenstette编码遗传算法原理及应用可以避免这种情况的出现。所谓的grefenstette编码就是用所选队员在未选不含淘汰）队员中的位置，如：8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1对应：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到pop-size重复以下过程：从0，1中产生一个随机数r，如果rpc ，则选择vi作为一个父代。将所选的父代两两组队，随机产生一个位置进行交叉，如：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 16 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1交叉后为：8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 16 12 3 5 6 8 5 6 3 7 3