数学建模社区-数学中国

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

作者: 我要吃章鱼丸子    时间: 2016-4-11 17:37
标题: 【转】模拟退火算法心得
模拟退火算法心得      本文属于原创,make by 刘润佳,转载请注明出处。
$ N, [, B; O3 |; W) R3 |3 W- w9 K3 X0 v5 `6 c/ V/ ]) y6 S
文件http://www.cnblogs.com/growing/archive/2010/12/16/1908255.html/ Z- p% T' A0 {3 _( s
由于在做一些Sat(可满足性问题)的事情,所以也尝试了多种方法来求解,其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想:
+ U; y" K5 H  ]. d# a" y一、模拟退火算法的起源
7 z3 P* r7 L! U" K+ e# E1)它受益于物理退火过程* |7 a2 ?  a$ P5 K: U0 R
  加温过程
  k3 w3 s2 n% U4 [1 S% X  等温过程
4 _. q" `- s8 w; S5 }) l4 D* Y  冷却(退火)过程
6 [* f1 e- K  M" _2)等温下热平衡过程可用Monte Carlo方法模拟,计算量大。
( [& `/ R" e0 a' E' n4 C: w! Z3)1953年,Metropolis提出重要性采样法,即以概率接受新状态,称Metropolis准则,计算量相对Monte Carlo方法显著减少。: D9 V# K  n( `+ O/ H

( M2 E0 ~! H! ?0 N4 @, `" S  w9 J6 E$ D4)1983年,Kirkpatrick等提出模拟退火算法,并将其应用于组合优化问题的求解。" ~2 \8 @# j" g
二、模拟退火的基本思想5 A& H6 `( ^/ A/ G: n# A9 D1 F
       它可以分解为解空间、目标函数和初始解三部分。 ' H! T8 \; T& \0 m, J' U, Z
三、模拟退火算法的流程
/ j# Z( h# ?: P* e: V. }4 O
2 p4 Z2 @6 F+ j& Y: S  J四、需注意因素
2 n% ^: K& g% a+ G, h$ Z6 b) i: B9 L1 P( a' V
+ b; i% g7 w4 k" |

9 j+ P1 U; I" ?5 c( K: F+ E8 P7 z# `9 L, a" L1 d
0 Y8 x' Z+ ?0 a

! ]4 B. ]' `& m/ D8 b- h4 [" N5 T( D$ U
: Q1 M, q. J' ~6 a9 Y
1 ]$ Q% o7 a+ O2 j4 K7 L" p' ]/ z4 c
五、本人的心得( h) H5 O+ ~0 C3 I/ [
      在使用模拟退火算法求解Sat问题时,遇到了几个问题,觉得有必要提出来探讨一下,这也是模拟退火算法需要注意的地方:
: b9 e  I" {! R' X1 i4 k      1)温度的设定及其变化函数;
' m- o" A, w  `8 v- y4 i: W      2)在每个温度值下,进行尝试的次数;
8 E: D1 T! q0 r      3)评估函数选取问题。% b7 A( H' e* J2 d/ S
     这三个问题我觉得需要经过不断的实验得出一个最优值,目前本人的研究及实验都很有限,得出这几个结论未必正确,如果有新的建议可以提出,谢谢。同时,由于本人目前还没有找到自认为比较合理的解决方案,所以具体算法及所列三个问题将在后期发布,有兴趣者可以留意。! x1 u2 I( X! R% E# {1 K. F
1 l% A- N$ _* `, o' G) x" [

; R4 [) _# \; A% G7 s2 C* k# G9 e9 G1 l& \5 X
1 A" s5 G' M- s

; [7 e) |9 g: b8 Z0 h
& N: F# D# }. U$ v5 `7 q




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