请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
楼主: ebookSharing

[课件资源] 遗传算法(理论应用与软件实现附光盘)

  [复制链接]
字体大小: 正常 放大
aimaer_21        

0

主题

4

听众

45

积分

升级  42.11%

该用户从未签到

新人进步奖

发表于 2009-5-17 19:33 |显示全部楼层
|招呼Ta 关注Ta
回复

使用道具 举报

aimaer_21        

0

主题

4

听众

45

积分

升级  42.11%

该用户从未签到

新人进步奖

回复

使用道具 举报

csu        

4

主题

4

听众

235

积分

升级  67.5%

该用户从未签到

回复

使用道具 举报

hyip        

0

主题

4

听众

6

积分

升级  1.05%

该用户从未签到

新人进步奖

回复

使用道具 举报

zyqbnu        

1

主题

2

听众

287

积分

升级  93.5%

该用户从未签到

回复

使用道具 举报

扬帆呢 实名认证       

0

主题

4

听众

255

积分

升级  77.5%

  • TA的每日心情
    开心
    2015-1-19 12:02
  • 签到天数: 1 天

    [LV.1]初来乍到

    模拟退火算法简介' I0 |9 l1 |; n  _2 B

    : ~! y/ O! `) G, F9 g/ g: o* Q9 I, w+ V: P

    & [. g) Y! L  O9 g5 N$ A
    ; z! i% n- q2 X" d: h7 D, N
    & t- `" G1 ^' m" Z$ Q% \, N模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
    7 a( w. t4 x! t, p) N* e2 J& Q: o' V* |5 |* {7 F+ Q+ k+ V8 o  Z- P
    3.5.1 模拟退火算法的模型
    & `/ t8 s9 o" {$ V: |  @6 S5 d
    0 Q: N* b4 A1 H0 ?" c2 v5 q  模拟退火算法可以分解为解空间、目标函数和初始解三部分。 & ?5 }# h) o# L& _9 L

    6 W1 H) l" r9 |) r" q 模拟退火的基本思想: ( y; p# Z& i9 g/ ]

    , Q! f7 h& u: O9 x- g+ E  (1) 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点), 每个T值的迭代次数L
    / E) f9 `+ }( Y$ M& X! D7 P1 b4 H5 i9 p
      (2) 对k=1,……,L做第(3)至第6步:
    ' x$ _1 y: m* u$ G2 h# n
    / E; S7 B: `0 w  (3) 产生新解S′
    2 K8 h. d& U# |  d) O3 _8 ~) T9 h5 t  Z- K+ E# i$ V
      (4) 计算增量Δt′=C(S′)-C(S),其中C(S)为评价函数 - V! w0 M" A+ C( |+ Z  I
    7 Y- [& e1 ]6 h. {( q$ I
      (5) 若Δt′<0则接受S′作为新的当前解,否则以概率exp(-Δt′/T)接受S′作为新的当前解. : L# M" x1 F7 _/ o
    1 n! V5 ?9 X! b1 w  ~- Q- y* l
      (6) 如果满足终止条件则输出当前解作为最优解,结束程序。
    5 c' Y. B  `$ x/ m) P8 z5 {# U$ X6 {2 w: j
    终止条件通常取为连续若干个新解都没有被接受时终止算法。 + F( ]( D* \" ]5 c
    " |: b' R- c, M5 M1 |) s
      (7) T逐渐减少,且T->0,然后转第2步。 3 F" {; Q" k1 }, O# F
    0 S0 I/ F8 g. P
    算法对应动态演示图: - P, x& o' Y1 A  X

    / G" t' n/ N% z5 I3 L9 Y模拟退火算法新解的产生和接受可分为如下四个步骤:
    + ?. Z7 x% N3 b2 d
    ( {9 u+ w8 x* m  ?5 J2 v. U* N- ~  第一步是由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。
    . y* |1 O! W/ r) i; a3 U; }
      Y1 w. A) Z9 e1 F, B  第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。 9 r* E& {9 L/ Q' M! G+ J
    6 m: f" M2 q4 d( I4 ]; H2 \
      第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
    - k/ s2 _: ?8 Q6 z- |9 {4 x
    . W* a' b$ X: i  第四步是当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。   a* p$ n/ I) |. F, h7 Q
    , R) ?+ w& D: P. r
      模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。
    + Y- n! W6 |9 I) z$ s( K5 k: b
      B$ G* n4 D, Z! c6 v/ T, }# f, F
    0 y) ~' H. G; }" b3 V$ I6 I: Z( j+ P1 v
    3.5.2 模拟退火算法的简单应用
    6 k4 P" _8 u7 U  ]$ H
    8 A, F# Y' s+ O4 r  作为模拟退火算法应用,讨论货郎担问题(Travelling Salesman Problem,简记为TSP):设有n个城市,用数码1,…,n代表。城市i和城市j之间的距离为d(i,j) i, j=1,…,n.TSP问题是要找遍访每个域市恰好一次的一条回路,且其路径总长度为最短.。
      b0 _5 d' [0 q4 l( ~1 b  _4 O$ H- ^- j1 n# h
      求解TSP的模拟退火算法模型可描述如下:
    , r4 j  U( i: N4 s* p5 h: ]
    4 y4 Q! Z' n4 Y+ @4 j6 j' f2 G  解空间 解空间S是遍访每个城市恰好一次的所有回路,是{1,……,n}的所有循环排列的集合,S中的成员记为(w1,w2 ,……,wn),并记wn+1= w1。初始解可选为(1,……,n) . N' ?, c( o3 S0 b

    9 [) w9 {7 q% o( o; k  目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数:   u& l( E/ Q, S  E6 ?
    9 E7 U( j* z$ P- @8 q: ?+ P$ }

    5 Z) s% r0 B  h! y- A  |. p* g1 T6 Y) M# D
      我们要求此代价函数的最小值。
    " M  ]7 t& e& s0 U4 `% c. N- `3 `
      新解的产生 随机产生1和n之间的两相异数k和m,若k<m,则将
    * r" i) N. t* v* Z
      b3 g: q4 I* v7 C( r, z; {  (w1, w2 ,…,wk , wk+1 ,…,wm ,…,wn) 9 d7 I9 \, c3 H1 x' \/ ?; Q1 M

    ) K, F3 m- y0 ]7 ?  变为: 9 l) `/ k( k( h" ?7 \1 j) m3 P
    8 G1 {' j- X& r/ @3 w! c
      (w1, w2 ,…,wm , wm-1 ,…,wk+1 , wk ,…,wn).
    ; r% O2 ~0 q' X" j; \, U$ G. u, e( O# {6 L# |
      如果是k>m,则将
    . s# |( T+ C# ?/ n6 O0 D" w5 ~3 c4 |
      (w1, w2 ,…,wk , wk+1 ,…,wm ,…,wn)
    7 E# D5 _5 c* y* K9 Q$ e
    - e9 X& ^+ v  O  变为:
    1 N0 I6 G# K8 }: Z4 m3 X1 B
    5 N9 _6 L' H6 N) g" M* b/ ?! t  (wm, wm-1 ,…,w1 , wm+1 ,…,wk-1 ,wn , wn-1 ,…,wk).
    : @4 }' l* O$ Z& v# \# R% q0 c* \! _4 p( L% I
      上述变换方法可简单说成是“逆转中间或者逆转两端”。
    , m- R0 @% `: K7 ]6 ?' h% J
    ; h  {! F. @) [' H; e6 Z* B& N  也可以采用其他的变换方法,有些变换有独特的优越性,有时也将它们交替使用,得到一种更好方法。
    " t. Y$ s2 y* M# i2 v0 \5 K' L) j( w! B7 G+ \! Q: _* j$ C, m
      代价函数差 设将(w1, w2 ,……,wn)变换为(u1, u2 ,……,un), 则代价函数差为:   W4 r* c$ l3 ^/ E
      O- A6 C- T% x4 Y
    ) `' l7 ^* R5 i

    9 z( [9 ]7 n1 Q# C根据上述分析,可写出用模拟退火算法求解TSP问题的伪程序:
      M: [: d3 I% S, m
    & U2 V# n, c. U; \Procedure TSPSA: , w/ j* |9 u$ z: X8 B6 h
    * o) s' @( [% a2 l+ o& N
     begin
    + k; `" ~+ h6 q+ _+ m% T! Q* a8 f1 a( ^4 ?; s
      init-of-T; { T为初始温度} . S* c" k7 b1 z) e! a0 w
    - U% S% L. w- e- ]3 s8 o
      S={1,……,n}; {S为初始值}
    5 e9 i$ {% p$ I  O$ @7 ^# v" t* _- `+ s* A/ S- I
      termination=false;
    3 X: Y$ X1 {# r) s1 _" W. ~
    ) ?9 [3 `; {( m, b) u* p; c2 o  while termination=false
    : K, ^( X5 ]. v3 ~5 |- `
    5 @/ F+ \/ M1 ?& Z" k1 _7 \   begin
    : ^& m$ ~+ D# k" r! v
    4 N" k' b- a, \5 `5 ^+ Y    for i=1 to L do
    # l  Q$ o: m$ k+ d) _( v/ I$ m( |/ a) t& ~  \. W" m$ _
          begin 7 ^2 [( f# B$ r: z; S$ K/ [

    4 K2 q# m$ J7 F1 i        generate(S′form S); { 从当前回路S产生新回路S′} 4 u; _* n' ^1 O
    , d8 s% H6 M* r$ ~
            Δt:=f(S′))-f(S);{f(S)为路径总长}
    # L0 K: j) q- M& M5 ?' Z3 U8 f1 E6 n0 {" R$ j7 L$ l3 B) l* ~2 j0 v9 Y
            IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1]) $ {: H& S8 @6 E: @, Q) ~/ b' P

    ; ~+ t- _2 o3 ~; o, a- b        S=S′; / H* ^6 M0 K1 V6 c. a

    . n' D9 W, f# U2 ~        IF the-halt-condition-is-TRUE THEN . s, r" S6 l) I/ ]( p
    3 o% F( _; D' t4 K4 g" @) i
            termination=true; 5 @, n0 R( b: f! r
    2 e2 b- W1 r: A
          End;
    ; M! j6 X" X# D9 t4 H/ Z; x: ~; z3 Y4 K
        T_lower; % E- b, I, O0 A
    8 O8 h5 T5 ~7 @3 z7 e
       End;
    : \0 O/ a! g+ x
    3 l1 D1 E8 g( R* D+ x7 } End
    6 y( ^0 Q9 n, K& e/ y3 e2 a1 k6 I  F3 i
      模拟退火算法的应用很广泛,可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 4 x2 i% _* w1 Z) I% X* p. F
    . F8 h2 e$ L# m% W+ W

    ) Y5 G+ T, T6 G% ~3 W, `" l3 M" C! T! f
    3.5.3 模拟退火算法的参数控制问题
    7 K9 c) X  [; x% a. M: G7 w$ s# b1 h3 I- @8 W! R; [( J
      模拟退火算法的应用很广泛,可以求解NP完全问题,但其参数难以控制,其主要问题有以下三点: ; \) U" W% |$ y

    * Y3 H9 V9 u  k/ K, \  (1) 温度T的初始值设置问题。 7 j% g1 c6 U9 z% @, q, q. H
    3 v  v! q& b2 K( _) G0 I
      温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高,则搜索到全局最优解的可能性大,但因此要花费大量的计算时间;反之,则可节约计算时间,但全局搜索性能可能受到影响。实际应用过程中,初始温度一般需要依据实验结果进行若干次调整。 8 l  ]9 ]! w' |' g6 X. K3 y

    - E# e% F$ _" `( H) V  (2) 退火速度问题。
    % f5 v& |7 W6 f- U+ E0 y1 z* V0 K9 o! E
      模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间。实际应用中,要针对具体问题的性质和特征设置合理的退火平衡条件。
    / ?! B2 I  W$ _6 {9 y
    / c  ~! a  f: o' w+ N8 G  (3) 温度管理问题。 / O* s! U. U$ D# `" ^

    8 m: i5 C: F  S3 i  温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式: - G/ U7 L; ?- L/ v: R& H0 Y
    - v# W) j2 T7 s$ F0 K' I7 }& l
    : u! \8 ]( x0 N3 J

    " e: b% c( Q4 B( y. |9 jT(t+1)=k×T(t) ' D. m& E' J# _) H( M1 W4 f% V

    & c! Z* Y1 c2 E' l! Q) W7 }式中k为正的略小于1.00的常数,t为降温的次数
    / S+ o! ^+ U- `8 V) z' K: I复制代码
    回复

    使用道具 举报

    扬帆呢 实名认证       

    0

    主题

    4

    听众

    255

    积分

    升级  77.5%

  • TA的每日心情
    开心
    2015-1-19 12:02
  • 签到天数: 1 天

    [LV.1]初来乍到

    回复

    使用道具 举报

    扬帆呢 实名认证       

    0

    主题

    4

    听众

    255

    积分

    升级  77.5%

  • TA的每日心情
    开心
    2015-1-19 12:02
  • 签到天数: 1 天

    [LV.1]初来乍到

    回复

    使用道具 举报

    扬帆呢 实名认证       

    0

    主题

    4

    听众

    255

    积分

    升级  77.5%

  • TA的每日心情
    开心
    2015-1-19 12:02
  • 签到天数: 1 天

    [LV.1]初来乍到

    回复

    使用道具 举报

    shumo_bin        

    2

    主题

    5

    听众

    298

    积分

    升级  99%

  • TA的每日心情
    开心
    2013-8-30 13:45
  • 签到天数: 11 天

    [LV.3]偶尔看看II

    新人进步奖

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-29 14:11 , Processed in 0.685222 second(s), 101 queries .

    回顶部