tsp best.m

利用模拟退火算法解决旅行商问题

clc;
N=1;
Num=20;
T=1000;
T0=1e-3;
k=150;
s=0.98;
x=[17 7 16 9 18 12 1 14 2 15 3 10 11 4 6 5 8 19 13 20];
y=[1 18 4 7 15 13 11 20 6 19 5 3 8 17 12 9 2 16 14 10];
z=[x;y];
z(1,21)=z(1,1);
z(2,21)=z(2,1);
p1=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21];
while T>T0
        for t=1:k
            R1=0;
            for i=1:Num
                R1=R1+sqrt((z(1,p1(i))-z(1,p1(i+1))).^2+(z(2,p1(i))-z(2,p1(i+1))).^2);
            end
            R1
            p2=p1;
            a=round(rand(1,2)*19+1);
            W=p2(a(1));
            p2(a(1))=p2(a(2));
            p2(a(2))=W;
            R2=0;
            for i=1:Num
                R2=R2+sqrt((z(1,p2(i))-z(1,p2(i+1))).^2+(z(2,p2(i))-z(2,p2(i+1))).^2);
            end 
            if (R2-R1)<0
              p1=p2;
            elseif exp((R1-R2)/T)>rand
              p1=p2;
            end
              temp(t,1:length(p1))=p1;
              R1=0;
              for i=1:Num
                  R1=R1+sqrt((z(1,p1(i))-z(1,p1(i)+1)).^2+(z(2,p1(i))-z(2,p1(i)+1)).^2);
              end
              temp(t,length(p1)+1)=R1;
          end
          [fmin i]=min(temp(:,length(p1)+1));
          p1=temp(i,1:length(p1));
          ret(N,:)=p1;
          se(N)=fmin;
          N=N+1;
          T=s*T
end
      tt=1:N-1;
      size(se);
      p1
      R1
      figure(1)
      plot(tt,se)
      figure(2)
      plot(tt,ret)