QQ登录

只需要一步,快速开始

 注册地址  找回密码
楼主: ebookSharing
打印 上一主题 下一主题

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

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

0

主题

4

听众

45

积分

升级  42.11%

该用户从未签到

新人进步奖

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]初来乍到

    模拟退火算法简介
    7 Z* C% g2 z' s# Q" H( C' M1 y' V# w2 `% e
    3 `7 E) Y; H0 V0 c/ \* |/ P8 F
    ; {6 F3 q: r7 C9 `" O- Y' e
    8 \4 u  Z6 W7 F' G; p( a
    : r, ^8 b! s4 R3 T; h& K% t
    模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 0 w  j3 M5 A6 T5 X+ ~' z
    4 g4 y* ^4 y% D* I" d3 q  w
    3.5.1 模拟退火算法的模型 - k4 w7 r4 ~  y& l/ E/ P# \
    1 Q! l' v8 G: Z. Z3 R
      模拟退火算法可以分解为解空间、目标函数和初始解三部分。 * G7 k* r4 ~% C- e; x) ?
    ; a) }% S7 k" T) n/ R/ C
     模拟退火的基本思想:
    ' F* [( }: I0 G. _
    + B, ^5 N6 L% ]" R- f2 g0 }  (1) 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点), 每个T值的迭代次数L ; D9 y8 c+ E( v' T

    , `6 ^4 v1 U9 N( q+ G+ [8 `' \  (2) 对k=1,……,L做第(3)至第6步:
    3 {4 W# ~. L" d9 ~/ H- n
    3 w2 F, N' g; E8 {! h0 M  (3) 产生新解S′ 9 D; t9 o' v; Q/ q4 @& \

    9 w2 ]0 D% X8 n9 R' x' r) A  (4) 计算增量Δt′=C(S′)-C(S),其中C(S)为评价函数
    ) v+ B; P/ ^. N/ Q. _
    , o; r1 J. T. e1 e" Q/ ~; v  (5) 若Δt′<0则接受S′作为新的当前解,否则以概率exp(-Δt′/T)接受S′作为新的当前解.
    " I7 j0 |& L; ?7 M% d+ d1 Z! _- R: O" U2 }2 l" Z5 m2 [* g. P
      (6) 如果满足终止条件则输出当前解作为最优解,结束程序。
    6 Z6 q+ N* E6 H
    7 k# }# Y7 ^2 @8 ]2 Y4 P+ Z' }终止条件通常取为连续若干个新解都没有被接受时终止算法。 " A3 q  R, A* Y
    1 r" G* z4 g  Y& h& c5 `
      (7) T逐渐减少,且T->0,然后转第2步。 - j' H0 |' r4 ]3 I

    4 H) d$ K+ c0 r+ x/ Y% e算法对应动态演示图:
    * O9 D+ [* o+ _# u9 t- |9 r5 _
    1 j: p% x: P+ w6 N+ ~模拟退火算法新解的产生和接受可分为如下四个步骤: + d3 O6 |6 G; l1 k: w

    & @; @! J% F% X  W. X  第一步是由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。 ! z2 W# k3 y8 s
    & _7 p& D' H& l9 k, c$ S: [; g+ K
      第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。   W  H' n; K* j1 I: k

    - `  x( a  Z! V* O0 D% f, f  第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
    4 N/ h4 d0 ?+ m8 y, k5 k$ H+ S% ~; h. e
      第四步是当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。
    & c) }' s( K0 |$ [5 x% E& o; D
    - [$ p2 _4 |( ~/ M( L( D  模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。 $ z* T8 }8 ~( X8 n

    - t4 V) D' R1 K, ~7 H# r$ J! ^; b2 Y5 |: R
    * c6 B) Z4 U3 N3 F1 t% g$ M0 r5 K2 U+ A& \
    3.5.2 模拟退火算法的简单应用
    $ [+ G4 P# B" W5 r: |7 N- u6 ~) j1 b5 U9 I9 r8 p3 c
      作为模拟退火算法应用,讨论货郎担问题(Travelling Salesman Problem,简记为TSP):设有n个城市,用数码1,…,n代表。城市i和城市j之间的距离为d(i,j) i, j=1,…,n.TSP问题是要找遍访每个域市恰好一次的一条回路,且其路径总长度为最短.。
    ' p7 X; X! V: B+ t6 A+ j
    $ c- y9 G# a: o' O  求解TSP的模拟退火算法模型可描述如下:
    $ c) [) |: w7 O5 N' e- ^& L% o1 `8 k; {) k% v( ?2 k; m0 L9 E8 q
      解空间 解空间S是遍访每个城市恰好一次的所有回路,是{1,……,n}的所有循环排列的集合,S中的成员记为(w1,w2 ,……,wn),并记wn+1= w1。初始解可选为(1,……,n) " p5 v: b3 Q6 F, T
    6 d+ C( R: u& R; |
      目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数:
    % I- V5 t6 Z9 l! N% v% G1 Z. t& R9 m. N; y7 c/ S) g" O
    $ R0 `7 T' H6 k0 ~& d  S
    : G% b# q% b5 _/ x$ I% M
      我们要求此代价函数的最小值。
    ! y. I3 y' \. V" F! n) t% V" _4 Y( A$ Q
      新解的产生 随机产生1和n之间的两相异数k和m,若k<m,则将 . S+ a6 N/ A. h

    ( n5 C4 r, U- c) |; D  (w1, w2 ,…,wk , wk+1 ,…,wm ,…,wn)
    , K, z0 |1 O! q0 c3 f; o/ |3 l8 u
    5 T* b4 ?, x" h; q$ n  变为: 1 O' O9 G$ q* j; B3 Y3 g

    $ O# I7 R! o7 v3 q6 C0 r" p  (w1, w2 ,…,wm , wm-1 ,…,wk+1 , wk ,…,wn).
    1 _3 F3 e) T8 A% [9 i( E* _0 r7 v0 @/ D' n
      如果是k>m,则将
    9 X; I( R: {  G8 s& e/ q$ L% x% [& H
      (w1, w2 ,…,wk , wk+1 ,…,wm ,…,wn)
    0 D: [& ~' u: l, u. Q
    ! B, n' n9 S, v4 f( `. W- y  变为:
    ( J- s* I3 M) x
    3 M+ F: B0 k  Q/ f, h+ i  (wm, wm-1 ,…,w1 , wm+1 ,…,wk-1 ,wn , wn-1 ,…,wk).
    - M5 \* j* w6 D) R
    ) X% U6 S- C" `  上述变换方法可简单说成是“逆转中间或者逆转两端”。 . W7 t8 c% [0 }, h; q
    / ~* o6 J8 b1 E' A- x# c$ G2 Q
      也可以采用其他的变换方法,有些变换有独特的优越性,有时也将它们交替使用,得到一种更好方法。 ) y1 m( f6 ~$ d6 T
    & c8 w% n2 Y6 Q
      代价函数差 设将(w1, w2 ,……,wn)变换为(u1, u2 ,……,un), 则代价函数差为:
    + p" F- `; W4 y% M! a7 c; A; o/ u6 l7 p: U6 Q  ~1 J

    + [- V. ~  h; ]) I5 S( X7 u6 B! u
    / y. u, n0 M( a" O! D根据上述分析,可写出用模拟退火算法求解TSP问题的伪程序:
    # X2 e% m  D1 Q' Y9 D" P4 n1 X" W3 J
    Procedure TSPSA:
    - M! H: ^: E7 i9 z  {. v
    2 ~6 l  K  A% R1 Q5 Q" R6 g; C begin 1 j% n! \9 D2 z& P, S$ J6 b

    ( k# A5 E- l4 I/ w! n; i  f  init-of-T; { T为初始温度} 3 s8 T% [3 E; i0 m1 }; X
    , D6 T3 _. T, c
      S={1,……,n}; {S为初始值} " U. W! G0 y$ T% ~

    ; Q5 C9 R& F' h, W# g+ ]  termination=false;
    % [4 x: f+ ]+ {7 y  L( {- ]3 A  R7 J5 N( l5 O8 W
      while termination=false
    0 D$ s; y0 r  }$ A8 q, }/ W$ S8 R* H
       begin
    * O9 \- _' U0 m& E8 M6 I; I! f$ @! ~! Q7 N8 k2 M+ n8 ]% [
        for i=1 to L do
    ( w: T. a6 _5 m3 e" `
    % o# ~/ Z0 r' ^4 U      begin
    6 U+ ~  D# s9 L2 F) y4 `6 l& T2 B# ]) O% ^9 I0 R! i
            generate(S′form S); { 从当前回路S产生新回路S′}
    7 G0 G+ X* Y4 `9 T& h
    8 F7 v- w3 h; y. Q        Δt:=f(S′))-f(S);{f(S)为路径总长} * w( Y" I% K6 _$ @& Z
    ! O" ^6 j) H6 D& C* D
            IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1]) 3 D9 x& o* n7 G; P! z2 Y
    * o4 z6 {5 @' L, b( b  W# b1 s) n
            S=S′; 2 P7 h4 f% Y5 n( J5 ~; v$ [
    * P6 j3 r0 @9 t; N0 F4 d& ^
            IF the-halt-condition-is-TRUE THEN % F% V1 c, L+ I9 r, g
    & D$ w4 O4 G- I! I  S2 c
            termination=true; % @4 {4 `* [2 F1 h

    % m: C3 c) m! x8 V. y      End; 4 ]/ s, g9 k6 ?, u- O4 i" V/ W

    " p  X2 d& \& M. u0 @0 A" J5 s6 D    T_lower;   m8 G5 w5 t0 X# L" ]

    * c# Z2 @( C3 V# A1 ]7 }   End;
    + f! m3 h: `; |( l: B
    / C) g- }* O4 z% c" N End
    : G1 i& k$ `' U  i: h+ K" L5 z: Q' F% d
      模拟退火算法的应用很广泛,可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 ) T& u$ n! L8 E6 o: Y$ u  K. G
    % ~2 X. G- N3 u
    ! ?- x# _( a6 v% |

    . w2 i1 P3 L+ j0 f" a3.5.3 模拟退火算法的参数控制问题 ; b2 q# Y) `% ^# |
    + Y& s% ]1 C; I/ s
      模拟退火算法的应用很广泛,可以求解NP完全问题,但其参数难以控制,其主要问题有以下三点: $ i# t6 O* s' I2 T, f2 B+ x4 K
    . {. ^) G+ y* \1 j' Y3 k( D
      (1) 温度T的初始值设置问题。
    . ^# W" h8 E# O2 G' c# J$ L, I7 n) T4 T3 J# c- J! ?2 m  i- Z
      温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高,则搜索到全局最优解的可能性大,但因此要花费大量的计算时间;反之,则可节约计算时间,但全局搜索性能可能受到影响。实际应用过程中,初始温度一般需要依据实验结果进行若干次调整。
    . n2 x0 u2 ~* \8 U1 r8 G8 k3 o/ ^' Q) V+ Z! X0 n
      (2) 退火速度问题。 9 y1 e/ i8 x! Z' |* z. {
    % j2 ?: e3 D- q
      模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间。实际应用中,要针对具体问题的性质和特征设置合理的退火平衡条件。 # B- c; y' h& Q+ t" H
    $ L4 I/ c  j3 S1 p# ?5 e* H( y
      (3) 温度管理问题。 * N4 F7 G# K3 l0 [( v- r; {/ G
    ; N( ^( A/ `; s
      温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式:
    8 X' b* I8 {" D% o  h8 N4 A5 U! t( e9 T

    5 W8 T$ V# W5 ^. X4 y  T
    ; P' T) c% c* ]) b# @2 h3 M6 p: sT(t+1)=k×T(t)
    2 E  B( I5 |0 j/ G6 O! B+ L: Z6 ?
    + ]2 W' g. A7 _& b, I式中k为正的略小于1.00的常数,t为降温的次数
    2 i# B" B3 G) y  j# X( I& a复制代码
    回复

    使用道具 举报

    扬帆呢 实名认证       

    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, 2025-7-16 21:58 , Processed in 1.901105 second(s), 102 queries .

    回顶部