tsp.m

神经网络中的tsp的模拟退火算法的matlab实现

function tsp()
clc
N=10;
t0=10;
tf=0.7;
xx(1)=0.4;yy(1)=0.4493;
xx(2)=0.2493;yy(2)=0.1463;
xx(3)=0.1707;yy(3)=0.2293;
xx(4)=0.2293;yy(4)=0.7610;
xx(5)=0.5171;yy(5)=0.9414;
xx(6)=0.8732;yy(6)=0.6536;
xx(7)=0.6878;yy(7)=0.5219;
xx(8)=0.8488;yy(8)=0.3609;
xx(9)=0.6683;yy(9)=0.2536;
xx(10)=0.6195;yy(10)=0.2643;
for i=1:N
    for j=1:N
        if i==j
            continue;
        end
        d(i,j)=sqrt((xx(i)-xx(j)).^2+(yy(i)-yy(j)).^2);
    end
end
[f,T]=trp(d,t0,tf);
f
disp('最优路线')
T
function [f,T]=trp(d,t0,tf)%f为目标函数最优值，T为最优路线，d为距离矩阵
                            %t0为初始温度，tf为结束温度
   [m,n]=size(d);
   L=100*n;
   t=t0;
   pi0=1:n;
   min_f=0;
   for k=1:(n-1)
        min_f=min_f+d(pi0(k),pi0(k+1));
    end
    min_f=min_f+d(pi0(n),pi0(1));
    p_min=pi0;
    while t>tf
        for k=1:L
            kk=rand;
            [d_f,pi_1]=exchange_2(pi0,d);
            r_r=rand;
            if d_f<0
                pi0=pi_1;
            elseif exp(d_f/t)>r_r
                pi0=pi_1;
            else
                pi0=pi0;
            end
        end
        f_temp=0;
        for k=1:(n-1)
            f_temp=f_temp+d(pi0(k),pi0(k+1));
        end
        f_temp=f_temp+d(pi0(n),pi0(1));
        if min_f>f_temp
              min_f=f_temp;
              p_min=pi0;
          end
          t=0.87*t;
      end
      f=min_f;
      T=p_min;
      %下面的函数产生新解
      function [d_f,pi_r]=exchange_2(pi0,d)
      [m,n]=size(d);
      clear m;
      u=rand;
      u=u*(n-2);
      u=round(u);
      
      if u<2
          u=2;
      end
      
      if u>n-2
          u=n-2;
      end
      v=rand;
      v=v*(n-u+1);
      v=round(v);
      
      if v<1
          v=1;
      end
      v=u+v;
      
      if v>n
          v=n;
      end
      pi_1(u)=pi0(v);
      pi_1(v)=pi0(u);
      
      if u>1
          for k=1:(u-1)
              pi_1(k)=pi0(k);
          end
      end
      
      if v>(u+1)
          for k=1:(v-u-1)
              pi_1(u+k)=pi0(v-k);
          end
      end
      
      if v<n
          for k=(v+1):n
              pi_1(k)=pi0(k);
          end
      end
      d_f=0;
      
      if v<n
          d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
          for k=(u+1):n
              d_f=d_f+d(pi0(k),pi0(k-1));
          end
          d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
          for k=(u+1):n
              d_f=d_f-d(pi0(k-1),pi0(k));
          end
      else
          d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
          for k=(u+1):n
              d_f=d_f+d(pi0(k),pi0(k-1));
          end
          for k=(u+1):n
              d_f=d_f-d(pi0(k-1),pi0(k));
          end
      end
      pi_r=pi_1;