sa_tsp.m

模拟退火算法解决TSP问题

function [route,goal]=SA_TSP %(d,t0,k,te)
  clc
  %  1  2  3  4  5  6  7  8  9  10 
 d=[0  2  1  2  0  0  1  0  1  2     % 1
    2  0  1  4  1  0  1  1  1  3     % 2
    1  1  0  1  0  0  0  3  1  1     % 3
    2  4  1  0  1  1  2  1  0  2     % 4
    0  1  0  1  0  2  0  1  1  1     % 5
    0  0  0  1  2  0  1  2  1  1     % 6
    1  1  0  2  0  1  0  1  1  1     % 7
    0  1  3  1  1  2  1  0  1  2     % 8 
    1  1  1  0  1  1  1  1  0  1     % 9
    2  3  1  2  1  1  1  2  1  0 ];  % 10
  
  %   1  2  3  4  5  6  7  8  9
  %d=[0  2  5  9  3  2  8  5  1   % 1
  %   2  0  9  1  3  5  4  3  9   % 2
  %   5  9  0  5  4  6  6  7  6   % 3
  %   9  1  5  0  2  1  6  8  2   % 4
  %   3  3  4  2  0  7  7  5  9   % 5
  %   2  5  6  1  7  0  9  8  6   % 6
  %   8  4  6  6  7  9  0  8  1   % 7 
  %   5  3  7  8  5  8  8  0  2   % 8
  %   1  9  6  2  9  6  1  2  0]; % 9


  n=length(d);
  route=randperm(n);    % 初始路径
  goal=value(route,d);  % 初始路径值
  t0=500;               % 初始温度
  t=t0;
  k=0.85;               % 温度衰减因子
  te=0.01;             % 截至温度
  L=10*n;               % 马尔可夫链
  j=0;
  while t>te
      for i=1:L
         [route2,goal2]=insert(route,d);
         [route2,goal2]=swap(route,d);
         [route2,goal2]=inverse(route,d);
          if (goal2-goal)<0 
               goal=goal2;
              route=route2;
          elseif exp(-(goal2-goal)/t)>rand
              goal=goal2;
              route=route2;
          else
              goal=goal;
              route=route;
          end
      end
    t=k*t;                    % 温度衰减函数
    j=j+1;
    goal_value(j)=goal;
  end
  goal
  plot(1:j,goal_value);       % 收敛图形   
  
function goal=value(route,d)  % 评估所选路径的值
  n=length(d);
  goal=0;
  for i=1:n-1
    goal=goal+d(route(i),route(i+1));
  end
  goal=goal+d(route(n),route(1));

function [route2,goal2]=swap(route,d)  % 互换操作，适用于算法的大范围探索
   n=length(d);
   location1=round(rand*(n-1))+1;
   location2=round(rand*(n-1))+1;
   swap_route=route(location1);
   route(location1)=route(location2);
   route(location2)=swap_route;
   route2=route;
   goal2=value(route2,d);
 
function [route2,goal2]=insert(route,d)  % 插入操作，适用于随机性服从均匀分布的长串解算子
   n=length(d);
   location1=round(rand*(n-1))+1;
   location2=round(rand*(n-1))+1;
   loc1=min(location1,location2);
   loc2=max(location1,location2);
   insert_route=route(loc2);
   route(loc1+1:loc2)=route(loc1:loc2-1);
   route(loc1)=insert_route;
   route2=route;
   goal2=value(route2,d);
   
function [route2,goal2]=inverse(route,d)  % 逆序操作，适用于算法的小范围迁移
  n=length(d);
  location1=round(rand*(n-1))+1;
  location2=round(rand*(n-1))+1;
  loc1=min(location1,location2);
  loc2=max(location1,location2);
  inverse_route=fliplr(route(loc1:loc2));
  route2=[route(1:loc1-1) inverse_route route(loc2+1:n)];
  goal2=value(route2,d);