数学建模社区-数学中国
标题:
【转】模拟退火算法心得
[打印本页]
作者:
我要吃章鱼丸子
时间:
2016-4-11 17:37
标题:
【转】模拟退火算法心得
模拟退火算法心得
本文属于原创，make by 刘润佳，转载请注明出处。
3 X; ]7 r8 B! `) _( ]
8 H4 a8 V# c q* C) m3 U
文件
http://www.cnblogs.com/growing/archive/2010/12/16/1908255.html
) i4 l2 M4 y Y: G5 d
由于在做一些Sat（可满足性问题）的事情，所以也尝试了多种方法来求解，其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想：
3 b7 b0 g6 a+ \5 r
一、模拟退火算法的起源
2 M: F+ o) w# J( i0 W* `2 x
1）它受益于物理退火过程
( Q3 P* r$ x& G+ }5 R" R' ?
加温过程
, x. x4 U' B* M
等温过程
7 s3 T$ I4 C4 G( n7 n( w. l
冷却（退火）过程
& r+ q5 U3 N8 ?1 B: h$ }
2）等温下热平衡过程可用Monte Carlo方法模拟，计算量大。
4 a+ s# e8 Y: \, x! W, [1 J: W5 s
3）1953年，Metropolis提出重要性采样法，即以概率接受新状态，称Metropolis准则，计算量相对Monte Carlo方法显著减少。
% H& x4 y/ M0 p: l
$ N- p% `/ ~+ c$ S; p
4）1983年，Kirkpatrick等提出模拟退火算法，并将其应用于
组合优化问题
的求解。
5 t9 \* X2 i+ A9 x$ R
二、模拟退火的基本思想
! L1 ~2 m* N" _- |" _
它可以分解为解空间、目标函数和初始解三部分。
) ]& M% |9 s, }( t/ i7 N0 t6 a5 W
(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步。
: p) q7 A! o/ z: p9 X$ _* O( ~
三、模拟退火算法的流程
% d+ c' O7 r N
8 F. l7 |9 _" H8 r) k
四、需注意因素
* H |4 a9 M$ y; u4 F8 {
5 _5 j* C+ H; s# Y9 F
/ k& k' E1 }/ h4 P& w
3 O, Q6 }( |7 p% y
! R+ \- ^2 h$ ]- q/ T9 p- B2 N
: z: | W) P' N C
& ~4 C9 ~7 Q2 x: M$ u3 l! \5 e8 e
; g, i. _4 x* Z4 V) o# B
% R9 Z( [- H. m; N" i0 h
( M/ D$ \* u/ B" {( ?( Q
五、本人的心得
) u5 H* @, d: }9 ]% s
在使用模拟退火算法求解Sat问题时，遇到了几个问题，觉得有必要提出来探讨一下，这也是模拟退火算法需要注意的地方：
8 h5 E J5 e% M& {
1）温度的设定及其变化函数；
" k) |5 j+ p% M& z( O% m! ~
2）在每个温度值下，进行尝试的次数；
/ e: Q* A. A( s4 f
3）评估函数选取问题。
: [ d) J/ t s7 w7 Y0 z
这三个问题我觉得需要经过不断的实验得出一个最优值，目前本人的研究及实验都很有限，得出这几个结论未必正确，如果有新的建议可以提出，谢谢。同时，由于本人目前还没有找到自认为比较合理的解决方案，所以具体算法及所列三个问题将在后期发布，有兴趣者可以留意。
. [8 z# L: w \. J
. `# O5 ~- T! e+ Z; G
9 e* i: [8 ^/ J& [' R" }+ [0 _
/ L- o4 ^% Y7 |; N, u' G
" t$ }5 N+ E! O9 V
+ B8 r$ ~' k, S1 t- @0 G# b1 P) M
( t) i- G) D/ a( q" A8 I* |
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
5 _5 j* C+ H; s# Y9 F
3 O, Q6 }( |7 p% y
( M/ D$ \* u/ B" {( ?( Q