trp.m

SA-TSP 模拟退火算法求解旅行商问题

function[f,T]=trp(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
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;