数学建模社区-数学中国

标题: 【转】模拟退火算法心得 [打印本页]

作者: 我要吃章鱼丸子    时间: 2016-4-11 17:37
标题: 【转】模拟退火算法心得
模拟退火算法心得      本文属于原创,make by 刘润佳,转载请注明出处。
4 T8 Q3 n% x/ y! c; q
! [9 p! G5 @0 ]2 v; x4 I文件http://www.cnblogs.com/growing/archive/2010/12/16/1908255.html( `* I6 \, w. S0 f/ ~1 E
由于在做一些Sat(可满足性问题)的事情,所以也尝试了多种方法来求解,其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想:
( g8 W/ k' |; }$ P' B9 |一、模拟退火算法的起源* [+ o" j# H( Y& K
1)它受益于物理退火过程
9 U! I6 z4 B$ Q/ ]/ I0 ~% y  加温过程2 l5 X! t# g' e9 ]4 @( `2 O2 D, K; z
  等温过程' E6 A/ f2 ?; p# o8 S
  冷却(退火)过程) P& x+ l/ K1 r* r3 d
2)等温下热平衡过程可用Monte Carlo方法模拟,计算量大。  E7 }# ]* @& |) K' B
3)1953年,Metropolis提出重要性采样法,即以概率接受新状态,称Metropolis准则,计算量相对Monte Carlo方法显著减少。
6 ~9 j2 j4 `( r1 `- e' x3 R% Z" O  s6 `: Y' w: w
4)1983年,Kirkpatrick等提出模拟退火算法,并将其应用于组合优化问题的求解。
$ n( z$ h3 Q. Z二、模拟退火的基本思想
2 }1 P$ h! ]. b- b% p# l! @       它可以分解为解空间、目标函数和初始解三部分。 * [; I5 m% A0 Z5 ?: J% ]" Z. c
三、模拟退火算法的流程
6 {- w- s7 z9 U/ ~. {2 E1 \" E+ @7 r! K
四、需注意因素4 N% h1 [$ m/ w1 E6 H3 ]# Q
2 j& ~" W4 M8 a' o

$ g, j3 Q% ^8 M* m5 F6 f6 C
0 S; W- M" }- z* h- ~  Y* Y7 G2 P3 i3 X' S1 L5 M
9 R+ p0 v/ `3 M* @, F4 ?
9 M4 W, N, g' i# w

! r' F; s; C- U; M, W1 T+ L) Q) @, _1 L) B+ q

- ]! o0 C4 R! N五、本人的心得* Y9 P* I( C3 n( T5 ]
      在使用模拟退火算法求解Sat问题时,遇到了几个问题,觉得有必要提出来探讨一下,这也是模拟退火算法需要注意的地方:! f) W: p( v" w, D# T9 Q
      1)温度的设定及其变化函数;; z  k$ }* F$ @7 M4 i
      2)在每个温度值下,进行尝试的次数;% O  a; f, C& H  P3 o9 w/ V/ s) v
      3)评估函数选取问题。
4 F1 ]: E, D; G! M! p9 k& R) u     这三个问题我觉得需要经过不断的实验得出一个最优值,目前本人的研究及实验都很有限,得出这几个结论未必正确,如果有新的建议可以提出,谢谢。同时,由于本人目前还没有找到自认为比较合理的解决方案,所以具体算法及所列三个问题将在后期发布,有兴趣者可以留意。
1 Q" ~) Q8 U9 }7 B7 x$ K
6 I% i/ B5 v5 \/ ~
8 E- i5 ]$ k, _4 _; n- F* k  f
- H9 S3 a% Z* T
, c; j; O  L2 G' V! X* i3 W
- [8 q" j/ O  N/ c0 O$ ?. l" q' X3 A% ^$ l; g/ R# [5 g! ]7 O8 t





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5