6 ?8 Q9 \( Z7 O3 E, V+ @ 爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。5 a( v- E" w: O5 a1 J, n3 L
0 z, D. ]! ]1 N" w7 ~# d7 W 模拟退火算法描述：% t% L# n4 H5 q8 ~
* v5 I J* p3 L0 _
若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解)，则总是接受该移动 1 u* s$ w: j* j# D: b3 V. X9 c" T i+ m* p
若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定） 6 R( R' V9 i2 D( x5 n2 N2 W6 F' C/ R; Z6 P7 g" y# B$ N
这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。 9 u; M" c4 B0 V; `9 q- S 7 j% \9 Y; x( @5 k: A* C" B! a1 S; C 根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为： d4 Q/ ?; j- q- H# e
2 {$ z& {7 s7 N! j6 K( f( h' N P(dE) = exp( dE/(kT) ) 1 G q. D' y* W4 N4 X, N4 r i+ p& S4 z7 N
其中k是一个常数，exp表示自然指数，且dE<0。这条公式说白了就是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（否则就不叫退火了），因此dE/kT < 0 ，所以P(dE)的函数取值范围是(0,1) 。3 c3 X5 B- i: o+ j$ A" L
5 Z! E' m3 A: ] 随着温度T的降低，P(dE)会逐渐降低。 9 c0 Y8 Q8 ]5 b* ^, J6 z3 F 7 P# z. }6 J1 u3 L 我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。8 w; M# y7 u7 g( A
# {. {# X p+ j) w8 _, S' e P; ]; K" y 关于爬山算法与模拟退火，有一个有趣的比喻：9 t: [/ b+ h0 g$ Z8 X* n9 o
- C6 `' ^3 X c( M f5 N q
爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。9 d, P3 V) {3 L, m0 ^& N( h
: m4 b$ z9 B7 j. [
沙发沙发
…