【转】模拟退火算法心得

我要吃章鱼丸子

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

: m( q" m* i" Q0 i: J, Q& k$ X文件http://www.cnblogs.com/growing/archive/2010/12/16/1908255.html
. N4 T8 V! {9 ~- e' r0 @7 X, C3 I% a由于在做一些Sat（可满足性问题）的事情，所以也尝试了多种方法来求解，其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想：
' {( f9 p! G1 M4 A) I% v一、模拟退火算法的起源
1）它受益于物理退火过程
) T# O4 I8 l, d: ^& l9 |　　加温过程
$ p  X+ L) E2 G+ E- M* T0 B　　等温过程
9 I$ i* p' [' H* j　　冷却（退火）过程
+ A9 D) s, j0 X: G# v2）等温下热平衡过程可用Monte Carlo方法模拟，计算量大。
1 s% ^0 {( U6 k- v. E1 h5 _3）1953年，Metropolis提出重要性采样法，即以概率接受新状态，称Metropolis准则，计算量相对Monte Carlo方法显著减少。

4）1983年，Kirkpatrick等提出模拟退火算法，并将其应用于组合优化问题的求解。
二、模拟退火的基本思想
       它可以分解为解空间、目标函数和初始解三部分。
  H5 h- V7 M! \

• (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步。
  

三、模拟退火算法的流程

' ~, w! }6 D7 Q* v8 K四、需注意因素

7 u0 Q! R' D/ G9 [1 B. J! N
2 n+ Y% `; x" l1 w
+ B: @; q) D1 o4 a& l5 H
; h% W; Q9 G7 u5 F9 A& q" o

1 h$ s$ z0 ^6 n/ ]
  I; C4 I1 `3 S$ M9 h% k( w: [2 E7 w
$ {& \8 m0 @4 h# n" s# X' Z: M: N  j
0 D. D  v' y5 w+ X7 W2 Z五、本人的心得
4 x! D$ I: |- q5 w& i8 g      在使用模拟退火算法求解Sat问题时，遇到了几个问题，觉得有必要提出来探讨一下，这也是模拟退火算法需要注意的地方：
' g7 O+ j& C4 V5 h1 ~2 }6 [2 P' a      1）温度的设定及其变化函数；
9 l- E- K1 ?, [9 c  a( D      2）在每个温度值下，进行尝试的次数；
% }0 K. @3 O0 Y, l5 b2 E+ T8 Q      3）评估函数选取问题。
$ r1 w/ O! F+ Q9 y9 q+ s: j6 {     这三个问题我觉得需要经过不断的实验得出一个最优值，目前本人的研究及实验都很有限，得出这几个结论未必正确，如果有新的建议可以提出，谢谢。同时，由于本人目前还没有找到自认为比较合理的解决方案，所以具体算法及所列三个问题将在后期发布，有兴趣者可以留意。




6 ]- L, I4 L0 i1 Q