【转】模拟退火算法心得

我要吃章鱼丸子

模拟退火算法心得      本文属于原创，make by 刘润佳，转载请注明出处。

' P: }# D0 V6 ]文件http://www.cnblogs.com/growing/archive/2010/12/16/1908255.html
由于在做一些Sat（可满足性问题）的事情，所以也尝试了多种方法来求解，其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想：
: Q8 ^) k% q$ S7 R' L一、模拟退火算法的起源
' ^6 e8 w1 n! s' A8 j1）它受益于物理退火过程
　　加温过程
$ {0 W4 C0 f6 p1 M+ p2 L$ Y　　等温过程
; D6 L2 Q, _1 [  X4 l$ m　　冷却（退火）过程
- g/ K- O" A: x9 z2 c' x( C2）等温下热平衡过程可用Monte Carlo方法模拟，计算量大。
  Z; f/ A- `9 G9 X" ~4 V9 n3）1953年，Metropolis提出重要性采样法，即以概率接受新状态，称Metropolis准则，计算量相对Monte Carlo方法显著减少。

4）1983年，Kirkpatrick等提出模拟退火算法，并将其应用于组合优化问题的求解。
# ?# O; `: ^8 r$ v二、模拟退火的基本思想
       它可以分解为解空间、目标函数和初始解三部分。

• (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步。
  & D# k  Y+ [. X3 @. L# x/ y

三、模拟退火算法的流程

$ h9 O5 D9 f9 t2 k' y$ D四、需注意因素
6 S& v+ q  C# i+ p' k
8 I8 }5 b7 h" ~" G0 v- L5 D2 f- W$ @
  C% v$ A- c* F# ?- \: D9 C
( P8 S$ b7 i. j6 y% ~4 J7 {



1 V7 Y: g. e2 \6 X
$ d- w, {0 o; {" D6 V9 l: }2 h
1 t5 O+ @2 E1 t9 x五、本人的心得
+ V4 j. o0 V, p, y8 Y: g      在使用模拟退火算法求解Sat问题时，遇到了几个问题，觉得有必要提出来探讨一下，这也是模拟退火算法需要注意的地方：
      1）温度的设定及其变化函数；
/ w; y# K' U, I/ P9 G      2）在每个温度值下，进行尝试的次数；
3 w+ m- `" z4 o3 N5 ^      3）评估函数选取问题。
0 v& y: w7 D# }: ?4 c9 Y' K     这三个问题我觉得需要经过不断的实验得出一个最优值，目前本人的研究及实验都很有限，得出这几个结论未必正确，如果有新的建议可以提出，谢谢。同时，由于本人目前还没有找到自认为比较合理的解决方案，所以具体算法及所列三个问题将在后期发布，有兴趣者可以留意。
( Q: N. ]: _/ Y7 @( G5 d8 Q

) D* R  e5 n" E# ]
+ g9 m" T- M. g  o8 B: n$ K* n
2 I; S8 A/ E. |

1 ^# B0 R( ]; N1 s0 z$ K