【转】模拟退火算法心得

我要吃章鱼丸子

模拟退火算法心得      本文属于原创，make by 刘润佳，转载请注明出处。
2 l% P5 N, O3 }6 h% A/ O# l
文件http://www.cnblogs.com/growing/archive/2010/12/16/1908255.html
& p/ I2 p2 P6 T2 b& R& z4 U, ]由于在做一些Sat（可满足性问题）的事情，所以也尝试了多种方法来求解，其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想：
0 ]% L4 U. m/ G( Y( |" I一、模拟退火算法的起源
1）它受益于物理退火过程
9 [: [0 U& ]- A0 |: H/ Y8 E' m1 C% ~　　加温过程
  e. _0 b# q3 ~$ m' l3 R2 n2 h　　等温过程
　　冷却（退火）过程
, c' r0 H) t8 `" C$ ]8 a2）等温下热平衡过程可用Monte Carlo方法模拟，计算量大。
( c: {4 N4 R$ c# a" u0 E3 X5 x3）1953年，Metropolis提出重要性采样法，即以概率接受新状态，称Metropolis准则，计算量相对Monte Carlo方法显著减少。
( n' Q2 c) c1 O
5 z: K/ Q2 ~! L5 U4）1983年，Kirkpatrick等提出模拟退火算法，并将其应用于组合优化问题的求解。
二、模拟退火的基本思想
. h0 _7 Y* G: }% |  [       它可以分解为解空间、目标函数和初始解三部分。

• (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步。
    o6 w, S; f0 Y1 A

三、模拟退火算法的流程
8 X1 K7 |9 ^0 c' f% R# j9 S7 E7 W( W; O
) H( }' R+ P7 p' X) ]; v四、需注意因素


: v$ j% Q) n  E% y  o


7 i& z0 H+ J; H. N8 b  [5 V
( ^$ B* _1 V) p1 q* i, U/ u
" Q6 R7 n% s4 z8 Z0 _1 S
, ?* T6 [  A) K9 D, i# {" M
# z  |  \7 t4 ?五、本人的心得
      在使用模拟退火算法求解Sat问题时，遇到了几个问题，觉得有必要提出来探讨一下，这也是模拟退火算法需要注意的地方：
      1）温度的设定及其变化函数；
      2）在每个温度值下，进行尝试的次数；
      3）评估函数选取问题。
( M. s# ?/ l% `: U     这三个问题我觉得需要经过不断的实验得出一个最优值，目前本人的研究及实验都很有限，得出这几个结论未必正确，如果有新的建议可以提出，谢谢。同时，由于本人目前还没有找到自认为比较合理的解决方案，所以具体算法及所列三个问题将在后期发布，有兴趣者可以留意。


: U& J& [3 i4 v- u) l
) B. r% q4 u4 B1 K
& x5 a, C0 S: Y1 @& T: T
$ c) w4 x/ ?$ ?" C
! R; V4 W2 v7 u5 I, O