- 在线时间
- 60 小时
- 最后登录
- 2017-2-18
- 注册时间
- 2011-5-31
- 听众数
- 5
- 收听数
- 0
- 能力
- 0 分
- 体力
- 807 点
- 威望
- 0 点
- 阅读权限
- 30
- 积分
- 288
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 136
- 主题
- 8
- 精华
- 0
- 分享
- 0
- 好友
- 4
升级   94% TA的每日心情 | 怒 2012-2-25 00:11 |
|---|
签到天数: 95 天 [LV.6]常住居民II
 |
一. 爬山算法 ( Hill Climbing ). |$ [) D& \3 A. ?& C8 P
5 m4 ^5 `( N+ S" x8 a% e
介绍模拟退火前,先介绍爬山算法。爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。7 [( w/ n6 u5 q- D) q
; _; M- }' Y& Q8 I! e2 R/ l; Y 爬山算法实现很简单,其主要缺点是会陷入局部最优解,而不一定能搜索到全局最优解。如图1所示:假设C点为当前解,爬山算法搜索到A点这个局部最优解就会停止搜索,因为在A点无论向那个方向小幅度移动都不能得到更优的解。
3 S- _# m7 X1 c8 `. d6 j ![]()
6 S( `9 Y( o; K: l- H4 ]
# r O/ E3 \9 c: k2 Q7 [二. 模拟退火(SA,Simulated Annealing)思想
& T" p$ H0 @* V* ?2 j7 P y
! I( o) T8 H( c, }. T. ^ 爬山法是完完全全的贪心法,每次都鼠目寸光的选择一个当前最优解,因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法,但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。以图1为例,模拟退火算法在搜索到局部最优解A后,会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点,于是就跳出了局部最大值A。
, t, k9 O0 }4 U6 E4 G; v. P) j& X& e6 l% c1 y$ S; q
模拟退火算法描述:" M; F& ?: V: Z% s
; B: P: N% B7 P, E, j 若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解),则总是接受该移动' k5 @7 [2 v, q4 l
9 j$ o2 s9 E2 d0 \) [" [ Z 若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差),则以一定的概率接受移动,而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定)
i1 {' c0 D O5 T& z; V. O
8 W0 Q3 C3 P! m S) [1 i( K 这里的“一定的概率”的计算参考了金属冶炼的退火过程,这也是模拟退火算法名称的由来。
' ^0 F+ I$ O9 V. J' H" H5 j; v! P' v/ t
根据热力学的原理,在温度为T时,出现能量差为dE的降温的概率为P(dE),表示为:
) v c' X H$ k3 O& M' e
- b. v9 S9 K7 p8 n6 i* V P(dE) = exp( dE/(kT) )1 R& f& r. u9 H) @+ {1 a
, Y5 ~/ S+ m" }& T4 m
其中k是一个常数,exp表示自然指数,且dE<0。这条公式说白了就是:温度越高,出现一次能量差为dE的降温的概率就越大;温度越低,则出现降温的概率就越小。又由于dE总是小于0(否则就不叫退火了),因此dE/kT < 0 ,所以P(dE)的函数取值范围是(0,1) 。! k1 X. c6 U$ y
. Q* W+ R: h; b6 `0 ?( u" m
随着温度T的降低,P(dE)会逐渐降低。
8 C. |8 S/ A3 F1 Z+ @: b* C# Z
- D' C: `0 i p6 u. N Y' M- h- H 我们将一次向较差解的移动看做一次温度跳变过程,我们以概率P(dE)来接受这样的移动。- F p1 P5 X; x
. i+ z2 A4 K! w
关于爬山算法与模拟退火,有一个有趣的比喻:
! R: L- O+ Q. D6 m* Q s! I# f
7 i: M9 ?' y) { s5 d4 q. h1 Y 爬山算法:兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法,它不能保证局部最优值就是全局最优值。$ R* I; T4 p/ d3 d7 D5 m2 A, q
7 N5 t2 T' ~6 L; c" k% [
模拟退火:兔子喝醉了。它随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,它渐渐清醒了并朝最高方向跳去。这就是模拟退火。 |
zan
|