【转】模拟退火算法心得

我要吃章鱼丸子

模拟退火算法心得      本文属于原创，make by 刘润佳，转载请注明出处。
: [. D# ^) I* p. [# h
" t0 ^$ p' C9 X' ^7 q6 Z文件http://www.cnblogs.com/growing/archive/2010/12/16/1908255.html
; z# u* t$ Y5 U# X8 c由于在做一些Sat（可满足性问题）的事情，所以也尝试了多种方法来求解，其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想：
- R7 {2 g* A) M8 d" Q& l; u一、模拟退火算法的起源
3 y+ z( ?. X  Z; E) h7 N& U3 \1）它受益于物理退火过程
　　加温过程
" E& Q/ }/ n  c5 i; B& t# K0 B0 z* J　　等温过程
+ ~7 E2 t6 G5 o( H+ E* l　　冷却（退火）过程
0 F8 c; m/ d: l! _9 i2）等温下热平衡过程可用Monte Carlo方法模拟，计算量大。
( m8 K0 Y' `$ v: I6 ~4 o3 I3）1953年，Metropolis提出重要性采样法，即以概率接受新状态，称Metropolis准则，计算量相对Monte Carlo方法显著减少。

; X7 ^. G3 C& n. c$ [) @4 `4）1983年，Kirkpatrick等提出模拟退火算法，并将其应用于组合优化问题的求解。
二、模拟退火的基本思想
       它可以分解为解空间、目标函数和初始解三部分。

• (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L
• (2) 对k=1，……，L做第(3)至第6步：
• (3) 产生新解S′
• (4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数
• (5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
• (6) 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。
• (7) T逐渐减少，且T->0，然后转第2步。
  ) w2 J3 J& P* ]( k8 {  y4 Y

三、模拟退火算法的流程

" O, p- J" {5 b7 Z) [% R; Z四、需注意因素
4 \- b; G, p* D1 {2 L


$ k6 H6 y, P2 r: @6 i+ D$ h, c) d, D
5 ~8 L3 \$ F) d

( C6 U* Z: C# i3 N) M9 m6 P6 }
1 u* u8 G* s5 k) \) r" r
& z" d3 K% H- n
五、本人的心得
1 D/ N9 E5 A* O1 J2 C      在使用模拟退火算法求解Sat问题时，遇到了几个问题，觉得有必要提出来探讨一下，这也是模拟退火算法需要注意的地方：
# ]% Y# F  k) m0 i6 Q. {1 ~      1）温度的设定及其变化函数；
8 f7 C1 j7 w% \6 S  S      2）在每个温度值下，进行尝试的次数；
4 v- z0 z& b( P/ Q# h$ M      3）评估函数选取问题。
     这三个问题我觉得需要经过不断的实验得出一个最优值，目前本人的研究及实验都很有限，得出这几个结论未必正确，如果有新的建议可以提出，谢谢。同时，由于本人目前还没有找到自认为比较合理的解决方案，所以具体算法及所列三个问题将在后期发布，有兴趣者可以留意。
* w! b9 z  J! `. a/ E# P0 }

6 v, `) u5 l! J. Q
. J5 X. h4 I! k7 o
3 B5 D: Z( p% `3 \
# Y% v% c" T+ i2 X9 x2 [- J