数学建模社区-数学中国
标题:
【转】模拟退火算法心得
[打印本页]
作者:
我要吃章鱼丸子
时间:
2016-4-11 17:37
标题:
【转】模拟退火算法心得
模拟退火算法心得
本文属于原创，make by 刘润佳，转载请注明出处。
+ x8 z* u4 H! ^5 x! \: W# Z
$ d% D9 \) r9 a1 T7 w, ` }
文件
http://www.cnblogs.com/growing/archive/2010/12/16/1908255.html
6 o% Q" N7 K/ i
由于在做一些Sat（可满足性问题）的事情，所以也尝试了多种方法来求解，其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想：
( t/ H( d9 j6 x, H4 b
一、模拟退火算法的起源
4 |$ s4 w7 V; j- W0 Y. h* F( e% ?
1）它受益于物理退火过程
9 F. B" o; @5 ^/ [
加温过程
. L# Z8 S. T7 b7 {
等温过程
0 M, V5 v& ?+ x$ p3 V( D
冷却（退火）过程
6 [) `2 t% b4 W F7 p
2）等温下热平衡过程可用Monte Carlo方法模拟，计算量大。
& s) B% Q/ B C5 i% J
3）1953年，Metropolis提出重要性采样法，即以概率接受新状态，称Metropolis准则，计算量相对Monte Carlo方法显著减少。
) `: M7 v m5 G5 {2 ^$ s
- A, L, O+ `; @
4）1983年，Kirkpatrick等提出模拟退火算法，并将其应用于
组合优化问题
的求解。
3 k8 f9 S1 E5 S$ `1 v$ H, Y0 h
二、模拟退火的基本思想
! D" v' J- H# {0 f: Y2 @( R' w
它可以分解为解空间、目标函数和初始解三部分。
/ l# h' P# H M0 s
(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步。
8 H# s1 {9 i! `. }7 l5 {' v
三、模拟退火算法的流程
, G" K! |/ d6 R# X/ d$ R7 i
( o( `3 w$ a2 e9 a: s: C; B+ I
四、需注意因素
9 d* J; Z L" e0 y! _7 o
4 \+ N+ O' |4 @2 M
8 @1 G) ]% {; k o: |4 }2 W2 |
9 O* Z6 g. n/ y d' C! |2 B
. V7 {0 d# X2 y
$ F3 c/ K5 r% y5 A% J
0 Y9 a8 a0 T; \; E
* n8 ]' o1 N- d; v) h
5 Q* Z3 @0 I1 h. n! c
/ {7 A8 N- A$ |" z# \
五、本人的心得
& p I1 z0 z1 t
在使用模拟退火算法求解Sat问题时，遇到了几个问题，觉得有必要提出来探讨一下，这也是模拟退火算法需要注意的地方：
5 L2 o+ H, W. ]. u8 F5 t
1）温度的设定及其变化函数；
" D- j6 `& |* \$ K! J$ ~4 _6 F
2）在每个温度值下，进行尝试的次数；
7 g) K0 p6 H: d/ s$ g: C% X
3）评估函数选取问题。
" i$ L1 |% Q2 V) z0 n ^
这三个问题我觉得需要经过不断的实验得出一个最优值，目前本人的研究及实验都很有限，得出这几个结论未必正确，如果有新的建议可以提出，谢谢。同时，由于本人目前还没有找到自认为比较合理的解决方案，所以具体算法及所列三个问题将在后期发布，有兴趣者可以留意。
, s. J4 I0 S# n( T
3 H. p( _% C' a) l2 {6 ^: o4 T
* a$ L7 O4 R4 Q5 w
1 D" N* ^: L& i; V$ W
, E6 |) w! P7 q8 c; A/ q
2 |4 v @7 n) E H( x7 O$ U# R
% w5 h. H Y. _
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
8 @1 G) ]% {; k o: |4 }2 W2 |
