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

模拟退火算法基于模拟退火算法的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和目标函数值的增量e1-e04）根据Metropolis准则，如果增量（e1-e0）0，则接受新产生的路径newpath作为当前最优路径；如果（e1-e0）=0，则以公式（1）来决定新路径newpath是否代替path。rand()随机产生一个在[0,1]之间的随机数。exp[-(e1-e0)/t]rand()? ?? ???4）如果目标函数值小于istd，则直接跳出内循环。5）如果iniLK，则in=in+1并且转向3）。6）如果目标函数值小于ostd，则算法结束；否则，转向2）。1. distance.mfunction [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.mfunction []=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(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])))/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);%随机产生交换的位置fori=1:numbernewpath(i,:)=oldpath;%交换路径中选中的城市newpath(i,position(i,1))=oldpath(position(i,2));newpath(i,position(i,2))=oldpath(position(i,1));end4. pathfare.mfunction[objval]=pathpare(fare,path)%计算路径path的目标函数值objval=pathpare(fare,path)%path为1到m的排列，代表城市的访问顺序[m,n]=size(path);objval=zeros(1,m);fori=1:m? ? for j=2:n? ?? ???objval(i)=objval(i)+fare(path(i,j-1),path(i,j));? ? end? ? objval(i)=objval(i)+fa