SA.rar_MáS_amp_sa TSP_优化 退火_模拟退火

function [BestShortcut,theMinDistance]=SimulateAnneal4(dislist,Clist,cnod) %TSP问题的模拟退火算法malab程序 clc; close all; % clear all; f=inf; % dislist=[f 2 3 2 f f f f f; % 2 f 2 3 3 f f f f; % 3 2 f 2 1 f f 1 f; % 2 3 2 f f 3 f 4 f; % f 3 1 f f f 3 2 f; % f f f 3 f f 2 2 4; % f f f f 3 2 f 2 3; % f f 1 4 2 2 2 f 3; % f f f f f 4 3 3 f]; % Clist=[0 1;0 0;1 0;1 1;1 -1;2 1;2 -1;1.5 0;3 0]; NodeNum=size(Clist,1);%TSP问题的规模,即城市数目 n=size(Clist,1); d=dislist; q=zeros(n,n); for j=1:n q(:,j)=j; end for k=1:n for i=1:n for j=1:n if d(i,j)>d(i,k)+d(k,j) d(i,j)=d(i,k)+d(k,j); q(i,j)=q(i,k); end end end end for j=1:n d(j,j)=0; end x=[2:NodeNum]; need=3-mod((NodeNum-1),3); x=[x,zeros(1,need)]; circlenum=floor((NodeNum-1)/3); x=x(randperm(length(x))); for i=1:circlenum x=[x(1:4*i-1),1,x(4*i:length(x))]; end x=[1,x]; x(x==0)=[]; NodeNum=length(x); %d=rand(100,100); [~,n]=size(d); t0=100; %t0初始温度=100K t=t0; tf=1; %tf最终温度=100K %x=randperm(n); %领域初始解表示第i个人做i个事 xbest=x; xrealbest=x; %领域最优解 c=1; fmin=fun(d,x); frealmin=fun(d,x);%将初始可行解下的目标函数设为当前最优目标值 num=1; figure(1); stop = uicontrol('style','toggle','string'... ,'stop','background','white'); tic; cc=0; while t>tf && num<2000 for k=1:500; %内循环停止准则5000次 fx=fun(d,x); %计算新解的函数值。 fb=fx-frealmin; if fb<=0 && cc<=3 xbest=x; fmin=fx; xrealbest=x; frealmin=fx;%无条件跳转，取最优值与最优解。 elseif fb>0 p=exp(-fb/t); if p>rand xbest=x; fmin=fx; %有条件跳转，取最优值与最优解。 elseif p<=rand x=x; %不处理 end end x=[2:n]; need=3-mod((n-1),3); x=[x,zeros(1,need)]; circlenum=floor((n-1)/3); x=x(randperm(length(x))); for i=1:circlenum x=[x(1:4*i-1),1,x(4*i:length(x))]; end x=[1,x]; x(x==0)=[]; %以下是添加约束：到c点路程不能超过3，cc为s到c的路程 cc=0; snod=1; add1=find(x==snod); add2=find(x==cnod); cha=add2-add1; cha=cha(cha>0); i=1; while i<=min(cha) if i==n cc=cc+d(x(i),x(1)); i=1; else cc=cc+d(x(i),x(i+1)); i=i+1; end end end t=0.997*t; %模拟退火操作 BestL=frealmin; ArrBestL(num)=BestL; NodeNum=n; BSF=xrealbest; ArrBestL(num)=BestL; for i=1:NodeNum-1 plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'bo-'); hold on; end plot([Clist(BSF(NodeNum),1),Clist(BSF(1),1)],[Clist(BSF(NodeNum),2),Clist(BSF(1),2)],'ro-'); title(['迭代次数:',int2str(num),' 优化最短距离:',num2str(BestL)]); hold off; pause(0.005); if get(stop,'value')==1 break; end %存储中间结果为图片 % if (p==1||p==5||p==10||p==20||p==60||p==150||p==400||p==800||p==1500||p==2000) % filename=num2str(p); % fileformat='jpg'; % saveas(gcf,filename,fileformat); % end num=num+1; %迭代次数加1 end len=length(BSF); add=find(BSF==cnod); bs=BSF(add:len); bs=[bs,BSF(1:add-1)]; BSF=bs; add=find(BSF==snod, 1, 'last' ); bs=BSF(add:len); bs=[bs,BSF(1:add-1)]; BSF=bs; toc %用来保存完成时间 BestShortcut=BSF; %最佳路线 theMinDistance=BestL; %最佳路线长度 set(stop,'style','pushbutton','string','close', 'callback','close(gcf)'); figure(2); plot(ArrBestL,'b'); xlabel('迭代次数'); ylabel('目标函数值'); title('适应度进化曲线'); grid; hold on; % function fmin=fun(d,x) % fmin=0; % n=length(x); % for i=1:n % fmin=fmin+d(i,x(i)); %计算第i个人做x（i）任务时总时间。 % end function fmin=fun(d,x) fmin=0; n=length(x); for i=1:n-1 fmin=fmin+d(x(i),x(i+1)); %计算第i个人做x（i）任务时总时间。 end fmin=fmin+d(x(n),x(1));