M模拟退火最短距离问题 Matlab代码 亲测完美运行

1、模拟退火算法基于模拟退火算法的TSP问题求解具体步骤如下：1）随机产生一个初始解path（作为当前最优路径），计算目标函数值pathfare(fare,path)=e0，并设置初始温度t0，内循环终止方差istd，外循环终止方差ostd降温系数lam，温度更新函数tk=lam*tk-1，并令k=1，输入各城市坐标coord，计算城市间的距离fare。2）根据控制参数更新函数来控制温度的下降过程，给定最大循环步数iLK，设置循环计数器的初始值in=1。3）对当前的最优路径作随机变动，产生一个新路径newpath，计算新路径的目标函数值pathfare(fare,newpath)=e1和目标函数值

2、的增量e1-e04）根据Metropolis准则，如果增量（e1-e0）<0，则接受新产生的路径newpath作为当前最优路径；如果（e1-e0）>=0，则以公式（1）来决定新路径newpath是否代替path。rand()随机产生一个在0,1之间的随机数。exp-(e1-e0)/t>rand()        4）如果目标函数值小于istd，则直接跳出内循环。5）如果in<iLK，则in=in+1并且转向3）。6）如果目标函数值小于ostd，则算法结束；否则，转向2）。1. distance.mfunctio

3、n fare=distance(coord)%coord为各城市的坐标%fare为城市间的距离矩阵,m=size(coord); %m为城市的个数fare=zeros(m);for i=1:m %外层为行 for j=1:m %内层为列        fare(i,j)=(sum(coord(:,i)-coord(:,j).2)0.5;        fare(j,i)=fare(i,j); %距离矩阵对称    endend2. myplot.mfunc

4、tion =myplot(path,coord,pathfar)%做出路径的图形%path为要做图的路径,coord为各个城市的坐标%pathfar为路径path对应的费用len=length(path);clf;hold on;title('近似最短路径下的目标函数值',num2str(pathfar);xlabel('各城市坐标x');ylabel('各城市坐标y');plot(coord(1,:),coord(2,:),'ok');pause(0.4);for ii=2:len    plot(coord

5、(1,path(ii-1,ii),coord(2,path(ii-1,ii),'-b');    x=sum(coord(1,path(ii-1,ii)/2;    y=sum(coord(2,path(ii-1,ii)/2;    text(x,y,'(',num2str(ii-1),')');pause(0.4);endplot(coord(1,path(1,len),coord(2,path(1,len),'-b');x=sum(coord(1,path(1,len

6、)/2;y=sum(coord(2,path(1,len)/2;text(x,y,'(',num2str(ii-1),')');pause(0.4);hold off;3. swap.mfunction newpath,position=swap(oldpath,number)%对oldpath进行互换操作%number为将要产生的新路径的个数% position为对应newpath互换的位置m=length(oldpath); %城市的个数newpath=zeros(number,m);position=sort(randi(m,number,2),2); %

7、随机产生交换的位置for i=1:numbernewpath(i,:)=oldpath; %交换路径中选中的城市newpath(i,position(i,1)=oldpath(position(i,2);newpath(i,position(i,2)=oldpath(position(i,1);end4. pathfare.mfunctionobjval=pathpare(fare,path)%计算路径path的目标函数值objval=pathpare(fare,path)%path为1到m的排列，代表城市的访问顺序m,n=size(path);objval=zeros(1,m);for i=

8、1:m    for j=2:n        objval(i)=objval(i)+fare(path(i,j-1),path(i,j);    end    objval(i)=objval(i)+fare(path(i,n),path(i,1);end5. 主程序clear all;%输入各城市坐标coord=0.6683,0.6195,0.4,0.2439,0.1707,0.2293,0.5171,0.8732,0.6878,0.8488; 0.2536,0.263

9、4,0.4439,0.1463,0.2293,0.761,0.9414,0.6536,0.5219,0.3609;%参数的设定t0=1; %初始温度iLK=20; %内循环最大迭代次数oLK=50; %外循环最大迭代次数lam=0.95; %降温系数istd=0.001; %内循环结束标准ostd=0.001; %外循环结束标准ilen=5; %内循环保存的目标函数值的个数olen=5; %外循环保存的目标函数值的个数,m=size(coord); %城市的个数fare=distance(coord); %计算城市间的距离矩阵path=1:m; %产生初始解（作为当前最优路径）pathfar=

10、pathfare(fare,path); %计算目标函数值ores=zeros(1,olen); %外循环保存的目标函数值e0=pathfar;t=t0;for out=1:oLK %外循环    ires=zeros(1,ilen); %内循环保存的目标函数值    for in=1:iLK %内循环        newpath,=swap(path,1); %产生新路径        e1=pathfare(fare,newpat

11、h); %计算目标函数值        r=min(1,exp(-(e1-e0)/t); %metropolis准则函数        if rand<r            path=newpath;            e0=e1;        

12、;end        ires=ires(2:end),e0;        if std(ires,1)<istd%内循环终止条件：连续ilen个目标函数值波动小于istd            break;        end    end    ores=ores(2:end),e0;    if std(ores,1)<ostd%外循环终止条件：连续olen个目标函数值波动小于ostd       &#