组合优化算法-现代优化算法 （一）：模拟退火算法 及应用举例

浅夏110

一些用于模型求解的启发式算法，主要针对很难求解的NP问题。
8 y' `1 q  x8 m2 _' U) C2 X+ g; Z现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索（tabu search），模拟退火（simulated annealing），遗传算法（genetic algorithms），人工神经网 络（neural networks）。它们主要用于解决大量的实际应用问题。目前，这些算法在理论 和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目 标－求 NP-hard 组合优化问题的全局优解。虽然有这些目标，但 NP-hard 理论限制它 们只能以启发式的算法去求解实际问题。
* s. W) k" v5 ~+ i
+ I8 F; {; s7 {- `/ g启发式算法包含的算法很多，例如解决复杂优化问题的蚁群算法（Ant Colony Algorithms）。有些启发式算法是根据实际问题而产生的，如解空间分解、解空间的限 制等；另一类算法是集成算法，这些算法是诸多启发式算法的合成。
$ ]4 R" X! b. T6 N
" ?" M* H  c: C6 }现代优化算法解决组合优化问题，如 TSP（Traveling Salesman Problem）问题，QAP （Quadratic Assignment Problem）问题，JSP（Job-shop Scheduling Problem）问题等效 果很好。
1 ]$ U" N; t5 c( K  A$ N
; _+ s$ B% |: s) \模拟退火算法简介
, n% x+ |- G) a$ D0 |, E7 x4 ~9 R模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不 同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和 重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过 程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，终形 成处于低能状态的晶体。



7 m% s$ \7 o: B$ |# C


6 A3 `. m. f2 A6 ^/ C
7 m- c7 b/ `+ }- O" g
0 p# H( z1 o, @7 k4 l
在模拟退火算法中应注意以下问题：
9 F0 n1 m7 Q( E+ n: G
& ]4 x! z# t. l. k5 h8 ^5 }（1）理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算 机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢， 相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能终得不到全局 优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。
# R5 y9 f" g+ s, c
; B, ^' f' p! }+ f( I( }（2）要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续m 次的 转换过程没有使状态发生变化时结束该温度下的状态转换。终温度的确定可以提前定 为一个较小的值  ，或连续几个温度下转换过程没有使状态发生变化算法就结束。

+ N8 Y, n# F" L0 w. S  r（3）选择初始温度和确定某个可行解的邻域的方法也要恰当。

1.2  应用举例
9 d5 ~  N) b" e, x3 [例  已知敌方 100 个目标的经度、纬度如表 1 所示。


" J4 ?* q7 k- C. e" H

1 U; J; N' H- R# X0 e; ]



' h; M4 d7 B, b1 k& b$ g
我们编写如下的 matlab 程序如下：


$ M0 M4 x6 H0 ?7 |/ X3 Xclc,clear
load sj.txt    %加载敌方 100 个目标的数据，数据按照表格中的位置保存在纯文本 文件 sj.txt 中
x=sj(:,1:2:8);x=x(;
- r. R; d  ]3 [5 C3 ~+ Q; B+ _y=sj(:,2:2:8);y=y(;
" Z4 w' ?& W4 o1 V& Lsj=[x y];
% l. v- ?/ {, u( ]: ?9 c, w7 Fd1=[70,40];
/ l2 P; }: n( M5 g' W. P! Y1 Hsj=[d1;sj;d1];
7 w; i. d* P) n( M7 qsj=sj*pi/180; %距离矩阵
d
d=zeros(102);
for i=1:101     
  F( r$ ]' t. a1 P- R! E    for j=i+1:102         
        temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
        d(i,j)=6370*acos(temp);     
    end
end
d=d+d';
' r2 l; O+ r/ ~, d" Q: L) QS0=[];Sum=inf;
rand('state',sum(clock));
for j=1:1000     
    S=[1 1+randperm(100),102];     
! `. X* s7 U% D) F4 U" ~    temp=0;
. S" K  j6 D' F& b1 b    for i=1:101         
        temp=temp+d(S(i),S(i+1));     
    end     
/ d2 P3 N7 n3 s' Z1 _    if temp<Sum         
        S0=S;Sum=temp;     
    end
end
0 m  m4 P8 D, _e=0.1^30;L=20000;at=0.999;T=1;
%退火过程
for k=1    %产生新解
4 j6 p3 |1 @2 u: G    c=2+floor(100*rand(1,2));
    c=sort(c); c1=c(1);c2=c(2);   %计算代价函数值   
    df=d(S0(c1-1),S0(c2))+d(S0(c1),S0(c2+1))-d(S0(c1-1),S0(c1))-d(S0(c2),S0(c2+1)); %接受准则   
7 N1 r/ P. y/ F. b* H  w    if df<0   
9 u8 g6 X/ A% A  [        S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];         
# f; v  o+ C1 {) q2 |; Q/ y        Sum=Sum+df;   
; X4 o  j/ z% D8 c% e  A    elseif exp(-df/T)>rand(1)   
        S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];   
% c9 s& O5 \$ W- _        Sum=Sum+df;   
, P; h9 }7 y, j    end   
    T=T*at;   
    if T<e        
. C9 V2 F5 C: K7 w2 C' g0 D        break;   
. U; J# [$ {' R  k: E0 p5 i    end
7 f, `& K# @6 \7 A/ Wend  
. Z/ A1 v% s+ A1 a; f% 输出巡航路径及路径长度
S0,Sum

* r7 n- n( G' z. g# }
! z' I' d$ h  `6 f1 O9 E4 o
) G2 ^- m% ~5 H) P8 g6 v计算结果为 44 小时左右。其中的一个巡航路径如图 1 所示。
3 T: f7 E- r% }9 E: @* A


0 J0 p9 [8 B8 l9 T% W6 ^————————————————
3 P& _9 F6 {/ o8 j* h3 V% h9 d5 C版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- n1 k  A6 u& `6 I原文链接：https://blog.csdn.net/qq_29831163/article/details/89459183