模拟退火算法及实例解析

模拟退火算法及MATLAB实例

       同遗传算法一样，模拟退火算法也是现代优化算法的一种。他对于解决组合优化问题，如TSP，JSP等问题效果较好。关于模拟退火算法的详细介绍，可以参考这里模拟退火算法。
       还是拿我先前在遗传算法中举的那个例子来说，这里给出用模拟退火算法来解决的代码以及详细注释：

%模拟退火算法
%%  该部分同遗传算法
clc, clear
sj0=load('sj.txt');    %加载100个目标的数据，数据按照表格中的位置保存在纯文本文件sj.txt中
x=sj0(:,[1:2:8]);x=x(:); %取经度
y=sj0(:,[2:2:8]);y=y(:); %取纬度
sj=[x y]; d1=[70,40];    %表示每个目标以及出发点的坐标
sj=[d1;sj;d1]; sj=sj*pi/180; %角度化成弧度
d=zeros(102);                %距离矩阵d初始化

for i=1:101       %计算相邻两点的距离（距离是弧线）
   for j=i+1:102
       d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2))); 
   end
end

d=d+d';   %距离矩阵
path=[];long=inf;           %巡航路径及长度初始化
rand('state',sum(clock));   %初始化随机数发生器
%%
for j=1:1000  %求较好的初始解
    path0=[1 1+randperm(100),102]; temp=0;
    for i=1:101
        temp=temp+d(path0(i),path0(i+1));
    end
    if temp<long
        path=path0; long=temp;
    end
end
e=0.1^30;L=20000;at=0.999;T=1;
for k=1:L  %退火过程
c=2+floor(100*rand(1,2));  %产生新解
c=sort(c); c1=c(1);c2=c(2);
  %计算代价函数值的增量
df=d(path(c1-1),path(c2))+d(path(c1),path(c2+1))-d(path(c1-1),path(c1))-d(path(c2),path(c2+1));
  if df<0 %接受准则
  path=[path(1:c1-1),path(c2:-1:c1),path(c2+1:102)]; long=long+df;
  elseif exp(-df/T)>rand
  path=[path(1:c1-1),path(c2:-1:c1),path(c2+1:102)]; long=long+df;
  end
  T=T*at;
   if T<e
       break;
   end
end
path, long % 输出巡航路径及路径长度
xx=sj(path,1);yy=sj(path,2);
plot(xx,yy,'-*', 'MarkerEdgeColor','g') %画出巡航路径

结果：

path =

  1 至 28 列

     1    95    35    93    36    43    52    46    59    83    87    74    30    20    42    15    40    60     9     5    54    55    44    38    98    50    80    51

  29 至 56 列

   100   101    99    21    56    96     6    89    37    12    53    75    33    73    13    32    24    49    61    28    25    68     7    71    22    81    58    23

  57 至 84 列

    90    66    34    29    26    63    62    86     8    39    78    47    57    88    16    91    41     4    76    69    11    64    70    19    94    65    85    77

  85 至 102 列

    79    31    97    18    84    10    27    14    72    48    82    92     2    67    45     3    17   102


long =

   4.4830e+04

>>