( h3 O5 n. W5 j9 m! ?$ R9 g+ r! k$ t5 S' w) l3 ` K
. K9 D) G( X- u8 b- t8 @! {4 `1 X模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 # [! z, i. v. A9 D/ f; Z( O 3 Y$ d! L- }! Z- g0 h; [7 Z7 H3.5.1 模拟退火算法的模型 0 s% W$ F* l# Y4 u$ |, F " f: B' V) [* M 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 / d5 Q" }8 t' T' n% N; F. Y! E: b- s
% _+ h' X/ Y! z8 D! E/ d! {' L
模拟退火的基本思想: 5 T8 z$ ?; Z0 @$ w' O0 ~" l0 {2 R; g0 s) X6 k F
(1) 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点), 每个T值的迭代次数L & c0 d( G- e3 | d ' s% [' ~( w9 {; Y, r (2) 对k=1,……,L做第(3)至第6步: 7 ^ _3 o. F8 M; i6 w 2 Q/ s9 S7 \5 }7 I* z5 a1 N (3) 产生新解S′ ( `, C: H# c) x+ e V* O ; M, I- }, E8 c7 y: n (4) 计算增量Δt′=C(S′)-C(S),其中C(S)为评价函数 " }( z2 k9 z* X, C5 i1 l 1 B: `, S; A% R# }2 T; e- E (5) 若Δt′<0则接受S′作为新的当前解,否则以概率exp(-Δt′/T)接受S′作为新的当前解. 7 q: @$ \- D/ r6 L" v
# {1 C; M1 f3 E ]! g8 m% H/ {; [, T (6) 如果满足终止条件则输出当前解作为最优解,结束程序。 . s7 ~' X5 m; z& t# g7 Y+ {0 p
( D' n# G* {+ s" a4 t/ G终止条件通常取为连续若干个新解都没有被接受时终止算法。 ) b0 a# C/ N% A* v E6 I4 [2 F$ o8 O" A( a) X
(7) T逐渐减少,且T->0,然后转第2步。 2 u% Y# u$ S' D1 f- m7 b/ O " j8 n3 Z+ Z8 Y) E) g) v算法对应动态演示图: 8 h* _- o! B: P6 }1 Y% G: T : @$ B+ m2 Q% f0 I; z6 Y模拟退火算法新解的产生和接受可分为如下四个步骤: 2 R8 s0 c. C% F% N+ C# k+ \% ^5 i
- r9 Y G2 ?2 B6 q- {* z5 D9 F" g
第一步是由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。 % {, O3 ?" ? j Y! L+ v3 w
3 `3 g& m% f9 ^9 q4 l4 r m6 R 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。 3 N0 s" ^5 u/ J4 L% R
) {- O' X' z8 I @0 G9 f+ O+ \- O
第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。 5 a/ _8 c) E. m) q8 I% T' m$ ? w
$ M# e5 r2 T4 k; Y% p: p+ I3 ]0 H 第四步是当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。 7 B1 c: T$ M; L: T! N
6 L* u, b! T3 Y( {9 R3 `
模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。 : t9 M' k3 v# e! f& I, l, d 4 S# G5 g$ ~ a6 Y8 a" R" A$ \5 H9 n. f9 `0 j7 I1 m
. F$ `7 A. x$ d& y! q4 R T3.5.2 模拟退火算法的简单应用 - v/ o) i. K4 b7 Q; }' L" c8 t/ f% \
作为模拟退火算法应用,讨论货郎担问题(Travelling Salesman Problem,简记为TSP):设有n个城市,用数码1,…,n代表。城市i和城市j之间的距离为d(i,j) i, j=1,…,n.TSP问题是要找遍访每个域市恰好一次的一条回路,且其路径总长度为最短.。 : x1 [8 h( ?* y 5 N" |/ {& z! w$ {" { 求解TSP的模拟退火算法模型可描述如下: ; N+ u6 l( C* s
7 U' a5 s( R3 m/ p2 N" v+ [* O" ~" u 解空间 解空间S是遍访每个城市恰好一次的所有回路,是{1,……,n}的所有循环排列的集合,S中的成员记为(w1,w2 ,……,wn),并记wn+1= w1。初始解可选为(1,……,n) p# d' |6 T+ t2 O; U
6 T# [& H2 r# O
目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数: 8 A, v: K1 }5 M& ^* Q' |
% P& s% S6 W0 I termination=false; 2 ^# W* \6 a* V4 M
; N1 o, n$ U7 u& T2 t$ r* W
while termination=false - l2 S- x. A5 C1 X 4 \8 N$ }: k( w$ a2 d begin 9 a8 U+ v2 @+ P6 Z/ O6 t ; O. n' W" [! K for i=1 to L do 7 ]8 Y8 z! p; p! W% n S/ `$ d) v' j j8 F5 P4 k o
begin - }% T" ?# v4 R/ W
" x5 t/ i( ~. R) e# v generate(S′form S); { 从当前回路S产生新回路S′} , m) q# X' S# _: A9 N; X " _4 m. I( Y7 P, l8 _7 \( _" z8 y2 ] Δt:=f(S′))-f(S);{f(S)为路径总长} ; C Z0 N' H0 R, R/ r, S 9 h" Z1 s( r# n6 ]4 S IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1]) ( B0 z. t8 T. P* W
9 M+ w$ s. C8 Y, l% l9 G$ h% z; S, ] S=S′; ! _/ b, ?4 n. V0 Z, q+ ^
+ y, |1 x5 x% U5 r! W IF the-halt-condition-is-TRUE THEN & G; q8 S5 r0 _, V& A* u% v) J9 B# C2 a
termination=true; ; Y2 _! M3 L9 |' [/ {/ E
* v; j) t% A4 g1 A End; " |) }! R# l4 W- P
# ^* L, S+ x( i: T; H; [0 _ T_lower; " j; d; v: x. \8 G/ { e' u1 {9 K( [7 V! R; W
End; 1 r: W' j* x5 C2 b! C- f" B% [( a7 a3 |- \3 q+ i3 E
End ' L$ N5 e+ K/ ~8 f1 P* n% H! A% n4 E2 L1 M' r) j5 Z( i0 x+ D
模拟退火算法的应用很广泛,可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 8 I3 S' x6 |& R* O' K8 L
0 v6 v Q% m% L: G& I+ I4 i6 C1 r U3 P9 ?' |: X6 z
5 m2 @2 C- x- k& r: Y! e V
3.5.3 模拟退火算法的参数控制问题 : a/ i% f- b" x
$ Z* x x( U4 ^: {# _ 模拟退火算法的应用很广泛,可以求解NP完全问题,但其参数难以控制,其主要问题有以下三点: 0 {3 `' K! O6 I; o) r0 }/ r* o
7 A% {! n! k# ^ m! T7 z (1) 温度T的初始值设置问题。 ; V8 `. }1 R( ^7 k( I8 {# f$ h. h9 n0 y. U) Y# F! d; L
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高,则搜索到全局最优解的可能性大,但因此要花费大量的计算时间;反之,则可节约计算时间,但全局搜索性能可能受到影响。实际应用过程中,初始温度一般需要依据实验结果进行若干次调整。 5 n/ t# f* U, z* Z) x3 Y* h4 r
9 @2 i" k7 F/ C* u (2) 退火速度问题。 8 b7 h# X, o$ w# N, y+ ~ / H) M( A9 [) s8 C 模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间。实际应用中,要针对具体问题的性质和特征设置合理的退火平衡条件。 4 m2 |6 G: |5 A# W# A" _ }7 F
7 L3 O+ d6 }8 s9 t6 x9 H (3) 温度管理问题。 0 s5 R* k3 r2 z, B
- ]3 Y x; a, @" r# a" A4 W* V2 N 温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式: % {2 t( N; K8 I+ F$ k: \) Z
: B* n' E/ X' P( S