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

浅夏110

一些用于模型求解的启发式算法，主要针对很难求解的NP问题。
现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索（tabu search），模拟退火（simulated annealing），遗传算法（genetic algorithms），人工神经网 络（neural networks）。它们主要用于解决大量的实际应用问题。目前，这些算法在理论 和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目 标－求 NP-hard 组合优化问题的全局优解。虽然有这些目标，但 NP-hard 理论限制它 们只能以启发式的算法去求解实际问题。

% N; z3 {0 p5 I0 P; H) w; @/ F启发式算法包含的算法很多，例如解决复杂优化问题的蚁群算法（Ant Colony Algorithms）。有些启发式算法是根据实际问题而产生的，如解空间分解、解空间的限 制等；另一类算法是集成算法，这些算法是诸多启发式算法的合成。
6 }9 z3 h; P/ c/ u3 R" x
现代优化算法解决组合优化问题，如 TSP（Traveling Salesman Problem）问题，QAP （Quadratic Assignment Problem）问题，JSP（Job-shop Scheduling Problem）问题等效 果很好。
" h8 F% q- l! D1 M
模拟退火算法简介
模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不 同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和 重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过 程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，终形 成处于低能状态的晶体。
: C# j6 P& Q, T" Q
9 V/ h7 I0 [6 F% ~3 e
# p# I" Q' J4 c
; o* y+ f0 K; q# z! k; X- o, P

% n8 K! F; b" k' s1 T1 T* c


; N3 ~' g4 R9 [
9 j2 a$ C0 D7 E" `6 j" i在模拟退火算法中应注意以下问题：

1 q% U! b1 J8 N6 i（1）理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算 机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢， 相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能终得不到全局 优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。
8 x. J2 r8 f2 w6 i+ k
1 V+ C* @! d7 ]8 E& W2 u7 w（2）要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续m 次的 转换过程没有使状态发生变化时结束该温度下的状态转换。终温度的确定可以提前定 为一个较小的值  ，或连续几个温度下转换过程没有使状态发生变化算法就结束。
! p& A* ~2 x/ }2 s
% B+ o7 j# T; r0 l# z+ C& ?（3）选择初始温度和确定某个可行解的邻域的方法也要恰当。
) P; n7 u7 J6 W, L" }4 [/ Q
1.2  应用举例
2 v+ }7 b( x/ E; s; {0 c" B2 P7 Z例  已知敌方 100 个目标的经度、纬度如表 1 所示。

8 Y' t5 y# x$ P# S, F$ j+ w. n


) S) p3 F' E/ H9 ^2 V9 g/ {- f

# E8 d# F# u2 V0 I- u+ M


我们编写如下的 matlab 程序如下：
1 R) }8 K! W' U3 C8 }7 l# Q  u
$ g# N) T' e* j
clc,clear
0 B% V$ V1 `' Uload sj.txt    %加载敌方 100 个目标的数据，数据按照表格中的位置保存在纯文本 文件 sj.txt 中
x=sj(:,1:2:8);x=x(;
y=sj(:,2:2:8);y=y(;
sj=[x y];
d1=[70,40];
' G; ?$ f; z3 T5 o% Msj=[d1;sj;d1];
1 y. I# W5 G- Csj=sj*pi/180; %距离矩阵
d
d=zeros(102);
for i=1:101     
6 {5 `( N2 n* L" T! K    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));
4 M3 q* x* Q( [& n" |' ~! h        d(i,j)=6370*acos(temp);     
' z& L; u7 ^% X, F    end
end
d=d+d';
) W! [" v1 x! q" {2 M; h2 hS0=[];Sum=inf;
- z% l/ c' P$ e: S" J( Q" n& Brand('state',sum(clock));
for j=1:1000     
    S=[1 1+randperm(100),102];     
    temp=0;
    for i=1:101         
" C/ Z  o& S% I7 x& r        temp=temp+d(S(i),S(i+1));     
4 l9 }+ A& L( T( @    end     
    if temp<Sum         
  `- u' S5 U" a0 f        S0=S;Sum=temp;     
' w! e! G+ e9 X8 T9 x/ {( d4 i    end
end
e=0.1^30;L=20000;at=0.999;T=1;
%退火过程
9 E7 l5 \, o  a" c% ~for k=1    %产生新解
    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)); %接受准则   
    if df<0   
        S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];         
        Sum=Sum+df;   
    elseif exp(-df/T)>rand(1)   
4 Y; }8 N" k" W' E        S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];   
        Sum=Sum+df;   
5 E' ^: Y0 d! S! Z    end   
    T=T*at;   
; Q# V/ \6 g4 _6 \- G6 X    if T<e        
2 C0 ?* V: n9 M$ s        break;   
% K9 P; @# t' T% E4 K1 v    end
, `. I5 x( _5 ?' s6 _9 D8 Jend  
% 输出巡航路径及路径长度
0 u+ P+ T1 u, n6 q  d% xS0,Sum
4 W8 R; B7 Z* b, A7 A$ n- y, A
% k, a# S) \7 `, m

计算结果为 44 小时左右。其中的一个巡航路径如图 1 所示。


) A  _9 I0 a  q$ }" k
————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89459183