设为首页收藏本站|繁體中文 快速切换版块

 找回密码
 立即加入
搜索
查看: 1592|回复: 4

转(遗传算法)

 荐 [复制链接]
  • TA的每日心情
    慵懒
    2017-6-1 21:49
  • 签到天数: 6 天

    连续签到: 1 天

    [LV.2]偶尔看看I

    累计签到:6 天
    连续签到:1 天
    发表于 2012-6-7 10:01:22 | 显示全部楼层 |阅读模式

    马上加入,结交更多好友,共享更多资料,让你轻松玩转电力研学社区!

    您需要 登录 才可以下载或查看,没有账号?立即加入

    ×
    生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
    , }' O; A% [: y: y0 d  w
    ' |3 u" y7 m+ x* Y$ g  o- ]: w
    遗传算法的概念最早是由Bagley J.D在1967年提出的;而开始遗传算法的理论和方法的系统性研究的是1975年,这一开创性工作是由Michigan大学的J.H.Holland所实行。当时,其主要目的是说明自然和人工系统的自适应过程。
    5 U$ q1 U6 t' \0 I+ p, m4 @' M
    " h9 \$ `2 P3 _2 K2 f& M1 p: @
    遗传算法简称GA(Genetic Algorithm),在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中,现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样,都是对今后十年的计算技术有重大影响的关键技术”。3 M- {! g4 _: b6 L0 ]

    ' q+ B2 ]" Y( U3.2.1 遗传算法的基本概念/ c0 X$ @7 g! R7 z
    / ^. R9 }7 q/ g4 o8 ]; _
    遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。; [, R0 ]. Y3 J2 w9 L3 B
    . X# O) p, S, [7 m& e1 t9 I
    Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承,但后代又会产生一些异于父代的新变化。在环境变化时,只有那些熊适应环境的个体特征方能保留下来。
    - j# U/ t  i/ p+ o: }7 |# E7 H

    1 c7 q7 G. @: i+ w; {( p+ k& qMendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中,并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质;所以,每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰,适应性高的基因结构得以保存下来。1 _, y1 ]4 t4 X4 H1 R
    1 `- W. |+ i% J+ i
    由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法;故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下:% T  q( W& U' ?- t2 l& H3 G+ y

    & N9 W$ }! y) x一、串(String)
      q/ D4 Z1 T( C. g
    # K( M) ]4 N4 X+ B) Z$ n
    它是个体(Individual)的形式,在算法中为二进制串,并且对应于遗传学中的染色体(Chromosome)。
    . N, y+ M! ~; h6 W' }5 G6 }  u
    7 P4 V, p; O; X$ ^& Y. D. |$ }
    二、群体(Population) 4 a' q# V! q( [$ a; g
    , j& |! D' u/ G, ^
    个体的集合称为群体,串是群体的元素# r9 s- q2 I& x
    5 A- I: n* l' T# P) |
    三、群体大小(Population Size)
    0 y3 i& k8 c+ D4 Q0 k
    - A+ _1 w  l& W( I* f5 l
    在群体中个体的数量称为群体的大小。
    ! U; Q) [1 C. T" x1 r9 A7 c" [
    . u7 L6 j. E/ ]! E4 ~1 I& C; t$ L! H
    四、基因(Gene) # [( X% u$ z3 o, ^1 m  L  |

    " b" M. t/ |2 ]& d' I4 o基因是串中的元素,基因用于表示个体的特征。例如有一个串S=1011,则其中的1,0,1,1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。1 c, C! S: Q7 j$ q
    ( v; r6 c, D- u) e
    五 、基因位置(Gene Position)
    4 ~1 x, u& ~% ^- P4 i
    / x' c/ {3 Y8 w6 O4 r. K
    一个基因在串中的位置称为基因位置,有时也简称基因位。基因位置由串的左向右计算,例如在串S=1101中,0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。$ h* G  j& P$ m
    9 ~' R! |. ?6 H! ?7 Z
    六、基因特征值(Gene Feature) : g' w5 ^" x# P- A: j2 I

    0 t" U( C3 b$ U$ K8 P) R: n* ~0 R1 y3 O在用串表示整数时,基因的特征值与二进制数的权一致;例如在串S=1011中,基因位置3中的1,它的基因特征值为2;基因位置1中的1,它的基因特征值为8。
    % |6 Z( l" x' s1 Z- h5 B
    & k/ N$ l+ T* o7 w" @! @1 A4 O
    七、串结构空间SS . k7 R9 z. b7 v* c; E1 w
    " x/ Q* k; _$ G
    在串中,基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。  N( ^, y8 n# c" J
    : H7 _$ O6 e" g/ L: [4 l7 _0 E. [( ?
    八、参数空间SP 6 \7 B+ u6 N2 P$ F7 _( H

    " y2 V: ~: W! B/ j这是串空间在物理系统中的映射,它对应于遗传学中的表现型(Phenotype)的集合。
    ) H- o7 L0 o7 Z' l" T8 i4 i
    4 w& _3 @, W3 e/ w& n: K
    九、非线性6 k" o- J( N7 V* t: q
    # f- ~" D+ j* \# N- G
    它对应遗传学中的异位显性(Epistasis) + b: V' M- C8 B& u

    7 Q$ w. y, x$ B/ Z1 a+ Y% C十、适应度(Fitness)
    # Q6 \5 T/ w3 n# e  n
    7 e) Y$ _' X+ B5 s& J5 M: U
    表示某一个体对于环境的适应程度。; r, [% C2 H+ V

    ) q7 w0 m1 L* c) F遗传算法还有一些其它的概念,这些概念在介绍遗传算法的原理和执行过程时,再进行说明。; c2 t, L: x6 T! [6 n3 r0 H# z
      P7 t* H( o( g. P' |' V
    3.2.2遗传算法的原理6 m' U$ I! _5 R& u, H# ^

    ) U* E2 B% }8 h* ]: T4 z" {遗传算法GA把问题的解表示成“染色体”,在算法中也即是以二进制编码的串。并且,在执行遗传算法之前,给出一群“染色体”,也即是假设解。然后,把这些假设解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉,变异过程产生更适应环境的新一代“染色体”群。这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是问题的最优解。! t+ J5 b! Y: t( L8 u2 d' h

    & g* ?3 K, |0 g一、遗传算法的目的
    ! d9 G: K$ X! R% s( }

    2 W: `, P% y- ], v典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题:- c+ z& K1 n! f/ V
    & l! \2 p) S, [8 z0 O6 B9 U
    考虑对于一群长度为L的二进制编码bi,i=1,2,…,n;有
    2 g. g5 @% t! f" t8 `

    0 X* |- a8 W" fbi∈{0,1}L        (3-84)
    % r0 K' l. ~; z3 d  d
    1 m  q' l  T0 K% b5 |& Q2 x
    给定目标函数f,有f(bi),并且
    ; \8 f% I% r& a! i
    $ @8 A1 h5 J6 N( U  H/ U4 }2 q
    0<F(BI)<∞< P> ) ?- a5 y# F, m0 Q# S  c
    2 _9 t7 B9 h( ^
    同时) e( v1 _2 ^: V1 b* C3 C

      V3 H1 m  Q8 t1 p  }f(bi)≠f(bi+1)
    . C) ~. v2 h1 x( e; D( q2 l
    ) I) G  P0 l$ {( e; [
    求满足下式2 F3 X3 j% H; L1 w
    1 U* g, r6 _& o( H* r6 \1 N
    max{f(bi)|bi∈{0,1}L} ; O5 K& u- g1 Y2 q1 d
    ! e- p- v# D9 O' T' h
    的bi。
    8 H" _. {/ e/ N0 g0 @, e9 P

    0 U  E; k# J( ?' v+ n; y8 v很明显,遗传算法是一种最优化方法,它通过进化和遗传机理,从给出的原始解群中,不断进化产生新的解,最后收敛到一个特定的串bi处,即求出最优解。( S$ _! e# i  V
    9 w* }# v% a6 P& Q' H' x
    二、遗传算法的基本原理! C3 E) |, p" ]- W* h5 i

    % f7 s1 O. F& J" I0 x2 ^长度为L的n个二进制串bi(i=1,2,…,n)组成了遗传算法的初解群,也称为初始群体。在每个串中,每个二进制位就是个体染色体的基因。根据进化术语,对群体执行的操作有三种:* b' j' ]" k! g- j

    * Y) v3 L) q) q' o+ U9 E1.选择(Selection) $ @+ w+ \3 D3 i- m$ t; @6 y: j
    . u) f5 p- I! |) D2 ]9 w# k
    这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时,是根据个体对环境的适应度而决定其繁殖量的,故而有时也称为非均匀再生(differential reproduction)。& W% ^. l* [: ^- q# d
    7 W: b# q* F5 N) Y
    2.交叉(Crossover) 1 C0 m  k6 \! E# x

    ; ]/ f5 R0 Y: I2 Q" m3 J这是在选中用于繁殖下一代的个体中,对两个不同的个体的相同位置的基因进行交换,从而产生新的个体。
    $ T# p' {- X$ ]* G& ^

    % o7 R0 k2 {# Q( \  k. u% A3.变异(Mutation) 8 D* Y' o/ }0 a/ Q  ~# m; [3 J# Q

    ' S# g9 }, a2 E, L这是在选中的个体中,对个体中的某些基因执行异向转化。在串bi中,如果某位基因为1,产生变异时就是把它变成0;反亦反之。
    4 R: J. n; X; w/ A

    1 y% ]" s  G% a! d( H6 x8 Y* Y遗传算法的原理可以简要给出如下:
    , F$ E& G2 P" Z- L
    : r2 R7 P; ~2 ^. M3 |) T! b
    choose an intial population 6 J8 j! n0 X" e; \- A
    " h8 g5 l9 m9 t6 c
    determine the fitness of each individual # }, |; K0 W7 n6 }

    1 p  E- F1 F( H2 U4 qperform selection   x# o) s: o( T) W3 Z& y
    # n, K1 e, |4 v
    repeat
    , o; ^7 ~/ g8 V1 \

    7 U( f9 k& L/ V, C! P& o2 f, l    perform crossover
    * G% S+ z+ p( q. t% a2 U. V
    ' `/ D; l$ z! ?* c/ e7 H( k
        perform mutation
    ) i5 s2 y# y5 f
    4 j' a! S4 w/ l  ^8 R; G+ T/ P* u4 n0 q
        determine the fitness of each individual
    : K) \8 W4 _# {# m6 Z/ R" H
    / p% K. p1 O, g. ~- f
        perform selection
    . a& g& O7 {8 h0 T! K4 l) ?

    : f7 Y" |& r) r8 r( Puntil some stopping criterion applies
    / {" u0 Z) t8 ~. l% ~
    & N  k  a1 y; }, a* j
    这里所指的某种结束准则一般是指个体的适应度达到给定的阀值;或者个体的适应度的变化率为零。( g/ l4 u1 e8 l6 `2 i& {/ W
    三、遗传算法的步骤和意义, a3 Q  \1 L; r3 \% P& G% ^

    . M: ^' F# W) ]+ W) @; x8 o6 h1.初始化
    % y1 S0 Y& c8 J1 T

    1 s- y- {: B; k7 p" H; ]选择一个群体,即选择一个串或个体的集合bi,i=1,2,...n。这个初始的群体也就是问题假设解的集合。一般取n=30-160。) m& L, Q" i$ E* a0 t  Y2 T4 R
    ; H3 [: \% I+ N0 |1 H
    通常以随机方法产生串或个体的集合bi,i=1,2,...n。问题的最优解将通过这些初始假设解进化而求出。
    4 N1 G2 v) S6 \, M. ~  X% e8 r
    # @: R% ^+ Z& S5 q" j: a
    2.选择6 U, u- W3 u$ j  l

    : @; o6 }9 V$ U4 \) U6 ]7 @根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存,不适应者淘汰的自然法则。
    2 T; V/ v" [, G  w- n8 U
    5 S/ U/ p  g( T/ G" N- G7 ]
    给出目标函数f,则f(bi)称为个体bi的适应度。以" U" y. v* d, _3 H6 V

    , c; f. e  o' ?9 o7 w5 F  d, H/ \
    : Q& p; A0 D$ V! [8 F, H& {6 N: {. ? 6.2.ht40.gif 5 C0 w/ K( v0 C/ D! V; ~1 l: r
    为选中bi为下一代个体的次数。
    " p8 \  R7 i+ p$ g# c7 c, s
    * R; L: i/ z1 D$ z: I' V- y! Q
    显然.从式(3—86)可知:+ a; x# l/ y, A2 ]+ i* u2 @' H  Q; `9 Y
    ( f4 f8 J" K2 E4 t
    (1)适应度较高的个体,繁殖下一代的数目较多。
    ! {: N' \8 a- p" s3 Q

    6 _; M  j2 Y, S  d" q(2)适应度较小的个体,繁殖下一代的数目较少;甚至被淘汰。
    , ^3 f4 A- c" V5 u( ^! D
    - q# z7 @) m0 L  w: f
    这样,就产生了对环境适应能力较强的后代。对于问题求解角度来讲,就是选择出和最优解较接近的中间解。+ t/ b, a7 k9 n5 b* e7 @6 B
    ' J! q9 ~- b% u7 Q
    3.交叉
    9 q( q! F! I: z对于选中用于繁殖下一代的个体,随机地选择两个个体的相同位置,按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换;目的在于产生新的基因组合,也即产生新的个体。交叉时,可实行单点交叉或多点交叉。
    & g+ I% t* E# [4 N
    : P6 l, r+ z5 A; }1 [
    例如有个体
    " f4 U; i) ]2 b$ a

    ! H: U/ j, v% [S1=100101 , o7 P/ ~- g( L' n+ f7 _
    % }* n0 w* m2 m. S$ f
    S2=010111
    4 U/ e( O% l( b# b0 C$ I; F

    # G5 |% S: T# v! F选择它们的左边3位进行交叉操作,则有; J: ~; o, m7 l4 l! d

    4 p5 d1 F; D2 l4 Q, KS1=010101 ( Z! u0 A" v+ @/ M7 j- z' ?. E
    / o9 B' m; g% O: G
    S2=100111 9 U0 q6 W, {; _- c. l: s
    $ A) K+ I) T$ [+ ^& v
    一般而言,交 婊显譖。取值为0.25—0.75。9 E+ q! n5 U/ e4 c; d1 E8 n
    ( Z' W* m" K9 d# T
    4.变异5 [+ G5 ?2 w% a. ]

    % ?' ^* r4 ], T8 K( r1 j1 d根据生物遗传中基因变异的原理,以变异概率Pm对某些个体的某些位执行变异。在变异时,对执行变异的串的对应位求反,即把1变为0,把0变为1。变异概率Pm与生物变异极小的情况一致,所以,Pm的取值较小,一般取0.01-0.2。
    . K' n/ t! g  y' b6 Z$ I$ `1 K6 G

    & }; d! m+ s0 _4 o% F! ^# H9 g例如有个体S=101011。
    + Z: q* ^7 s' |2 I6 I% _: u& m  T

    + i) v5 |5 z, `% T3 i1 E对其的第1,4位置的基因进行变异,则有/ k* j) w+ D/ ?7 U5 J+ C0 |1 b

    9 P2 P' n  B: L/ S* p+ }S'=001111 9 u# e1 f1 W1 |2 y+ i: v, G
    # X4 |& H1 @& X
    单靠变异不能在求解中得到好处。但是,它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时,交叉是无法产生新的个体的,这时只能靠变异产生新的个体。也就是说,变异增加了全局优化的特质。
    0 H7 i- q/ e6 x+ C
    ' o9 P0 I6 f0 a, `
    5.全局最优收敛(Convergence to the global optimum)
    . m% L% x2 |; `( v3 v
    7 X4 T5 V4 w6 z/ r7 S, I) U
    当最优个体的适应度达到给定的阀值,或者最优个体的适应度和群体适应度不再上升时,则算法的迭代过程收敛、算法结束。否则,用经过选择、交叉、变异所得到的新一代群体取代上一代群体,并返回到第2步即选择操作处继续循环执行。
    1 x$ U) J2 M5 J4 O2 `  z& E, t8 E' C# ]
    6 V$ j0 y8 d# m" H4 R: C
    图3—7中表示了遗传算法的执行过程。4 U( W& Q- S+ k4 M
    2 w9 W: o- {+ G# Q- G* g! V

    1 U, M7 o; b) o0 k* \! L Genetic_Algorithm.gif + w) d+ X* x# _+ D8 {

    ' P, v3 |1 `" ~+ f: o# m图3-7 遗传算法原理) i8 d2 L2 O5 \" {& ^% H' r
    ' a$ P% I& W7 S6 ^, w- i
    3.2.3遗传算法的应用5 ]4 t6 Q$ W: S2 t2 U1 T/ V

    * U  R- r6 P! D- T) Y( v" a: J* U遗传算法在很多领域都得到应用;从神经网络研究的角度上考虑,最关心的是遗传算法在神经网络的应用。在遗传算法应用中,应先明确其特点和关键问题,才能对这种算法深入了解,灵活应用,以及进一步研究开发。
    # A$ K* g* H5 M1 u+ N$ x
    ! G( P0 N, ~9 R0 ]$ }/ }' ?
    一、遗传算法的特点2 T% M* s1 x) s! ~9 ^" O" J
    9 y6 Q* E, Z# p3 T  L( }9 h
    1.遗传算法从问题解的中集开始嫂索,而不是从单个解开始。, K* r6 i4 I+ `9 `- `9 g/ N
    + P% Q  `6 U1 ^- I( X
    这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的;容易误入局部最优解。遗传算法从串集开始搜索,复盖面大,利于全局择优。
    # e" E: t, j3 G1 l% Z
    ; D, L3 q1 h, T+ g8 Z8 {
    2.遗传算法求解时使用特定问题的信息极少,容易形成通用算法程序。" i* b3 B2 R7 |/ T
    . P( ^; j$ q3 `* H+ f* n
    由于遗传算法使用适应值这一信息进行搜索,并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息,故几乎可处理任何问题。" x  }& e' o0 E5 K. Q4 |

    - b: G( `- r$ j! l3.遗传算法有极强的容错能力" Y: E3 o/ R/ k  _1 h' J" G

    & |% y( |3 X6 E4 [8 p& N遗传算法的初始串集本身就带有大量与最优解甚远的信息;通过选择、交叉、变异操作能迅速排除与最优解相差极大的串;这是一个强烈的滤波过程;并且是一个并行滤波机制。故而,遗传算法有很高的容错能力。* H/ a  ]0 t+ ~* I0 ^
    : T: ~5 h; J1 F5 @6 @+ N" @
    4.遗传算法中的选择、交叉和变异都是随机操作,而不是确定的精确规则。
    2 u: w) a6 }+ f& g; l5 Z
    7 I9 I: v  b/ `- u# {# u2 L1 e
    这说明遗传算法是采用随机方法进行最优解搜索,选择体现了向最优解迫近,交叉体现了最优解的产生,变异体现了全局最优解的复盖。
    $ }7 B! S8 s& }5 p9 q
    . P' @' d" h# w4 v
    5.遗传算法具有隐含的并行性
    - G0 o" y( O; ?( T

    9 R& {. j' C4 H0 p+ @$ V* \4 U. H; X遗传算法的基础理论是图式定理。它的有关内容如下:; X2 W+ q3 ^7 P3 a4 S
    & c7 ]& F" p# W- w  C0 W
    (1)图式(Schema)概念
    $ O0 E  U  Y! P/ u7 _/ b, h8 z1 [
    - W4 ^/ Z5 P% U9 [. k. ~5 c! T
    一个基因串用符号集{0,1,*}表示,则称为一个因式;其中*可以是0或1。例如:H=1xx 0 x x是一个图式。
    7 n" Q9 u, u6 n* p! c" q
    , s, G- \9 k) ]
    (2)图式的阶和长度6 e3 Q- @  S- p0 d: J: d- ?  v
    5 C$ U; X0 M8 t" Y
    图式中0和1的个数称为图式的阶,并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度,并用δ(H)表示。对于图式H=1x x0x x,有0(H)=2,δ(H)=4。
    # Z1 j8 N+ }$ R* l
    3 |$ Q1 c2 L. J8 Y7 ^4 v
    (3)Holland图式定理
    , W  d2 Y: {- t+ V# F' Y6 {, ]
    : A1 `% q! W) W  q/ r3 r) r
    低阶,短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时,每代处理的图式数目为0(n3)。
    6 k7 u9 r( y: L1 N8 Q7 R" |0 ?* I

    # A0 s7 w4 ~1 s8 F: E遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
    , E6 M, T: S: [- x

    $ n3 w$ m1 W3 y/ h) ]% r二、遗传算法的应用关键
    # B' S  `8 @# u6 w0 P
    4 G+ h# R+ q7 T- T+ j( m; {! R
    遗传算法在应用中最关键的问题有如下3个
    0 T5 u2 @* D. N' d$ c# V2 l
    / T1 u/ ]' r* J$ Q& L
    1.串的编码方式
    , J) U; ?! R$ s; N- Y- g8 P. y

    - v7 G& Y! C! t  B! ^+ z1 z6 _( I这本质是问题编码。一般把问题的各种参数用二进制编码,构成子串;然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
    3 ~& m0 n$ }9 E3 q
    $ c1 k* J/ ^3 q) _& S6 o
    2.适应函数的确定; k2 h6 }) q8 y( O) h$ m# N

    ) w0 _  H: Z' p5 M/ X8 V适应函数(fitness function)也称对象函数(object function),这是问题求解品质的测量函数;往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数;但有时需要另行构造。
    7 L4 t7 Y* T4 q: g. x6 g8 {
    ! a0 O. m+ I$ L
    3.遗传算法自身参数设定: O5 C% \- f1 {( I( E

      d1 x/ g" p# ~$ k9 g) W( i遗传算法自身参数有3个,即群体大小n、交叉概率Pc和变异概率Pm。
    : |+ Q. _9 Q, c1 ~
    # R. X. m" j/ C, @* J
    群体大小n太小时难以求出最优解,太大则增长收敛时间。一般n=30-160。交叉概率Pc太小时难以向前搜索,太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构,太大使遗传算法成了单纯的随机搜索。一般取Pm=0.01—0.2。$ b" v4 I; y. K" h, B5 C
    3 g8 [1 a# p4 R% a
    三、遗传算法在神经网络中的应用
    5 a8 B4 J! C! N  C, z+ Y

    9 X. b8 d$ c4 f$ r1 B# h9 P遗传算法在神经网络中的应用主要反映在3个方面:网络的学习,网络的结构设计,网络的分析。  U% j4 s8 `/ L
    7 F. `: I- Z7 G; c
    1.遗传算法在网络学习中的应用
    " a+ b- I) ?# }' z
    5 D& f, N& w# Z* |5 w0 v
    在神经网络中,遗传算法可用于网络的学习。这时,它在两个方面起作用/ W% O6 W+ c; y. l
    ' K- p: U1 s( x4 c$ V, N2 x
    (1)学习规则的优化+ E+ D5 D6 W# E% j! u, {* x

    7 I# K8 W7 {; C6 l1 x5 j用遗传算法对神经网络学习规则实现自动优化,从而提高学习速率。
    . Q- O7 S2 Q. c/ A  M8 ]3 C$ I' c

    ! I- p) i! S# ~% G& n7 f(2)网络权系数的优化0 P9 g& J6 ]( |# g$ X
    & E2 D; L# L( y& j9 ^) B" c
    用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
    % `+ }& {* o' O
    9 r3 f9 k- o" V- ]( b$ k
    2.遗传算法在网络设计中的应用
    ( n; n# z9 Q; Z

    + q0 ~, p7 [/ B; P: C8 T# o用遗传算法设计一个优秀的神经网络结构,首先是要解决网络结构的编码问题;然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种:
    " Q4 O% |- G5 i8 P6 b+ U
    6 I2 ?' l  p4 e" j, M6 s) q5 T' [: _
    (1)直接编码法5 Q" Z  E0 R- L! F: J

    / Y% C) W+ T* D/ f这是把神经网络结构直接用二进制串表示,在遗传算法中,“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。+ W" R* o: {  l/ J9 X
    5 z# u- u' _7 o. {3 y' @* D( d
    (2)参数化编码法
    / O' }1 G8 y1 t. o6 @# q

    ( M9 [2 c0 J' `3 T参数化编码采用的编码较为抽象,编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析,然后产生网络的结构。
    2 W+ L# d* S' c( z
    # h5 v" t6 ~$ d. F% z
    (3)繁衍生长法
    3 F% [& o/ r, z! A

    4 S; ^4 X6 L% G这种方法不是在“染色体”中直接编码神经网络的结构,而是把一些简单的生长语法规则编码入“染色体”中;然后,由遗传算法对这些生长语法规则不断进行改变,最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
    ; e# j& u* f# g3 e
    ! w9 N+ D9 `& H
    3.遗传算法在网络分析中的应用& m5 ~3 z0 \8 V

    & t$ p8 Q! ^( W+ U; n; M1 _- Y遗传算法可用于分析神经网络。神经网络由于有分布存储等特点,一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析,性质分析,状态分析。$ c1 }* j& W% Y7 O! e
    ; \: A" U# {5 o2 r4 i: ?9 f7 C
    遗传算法虽然可以在多种领域都有实际应用,并且也展示了它潜力和宽广前景;但是,遗传算法还有大量的问题需要研究,目前也还有各种不足。首先,在变量多,取值范围大或无给定范围时,收敛速度下降;其次,可找到最优解附近,但无法精确确定最扰解位置;最后,遗传算法的参数选择尚未有定量方法。对遗传算法,还需要进一步研究其数学基础理论;还需要在理论上证明它与其它优化技术的优劣及原因;还需研究硬件化的遗传算法;以及遗传算法的通用编程和形式等。4 m- n5 c, w8 @2 Q
    . n/ A2 c$ H9 z& C

    1 l0 _" ?9 P# q" z: A
    三、遗传算法的步骤和意义
    " y, O3 \& k  J% g! H6 Z( ]' o

    ! M9 I: @( W4 i3 e& Z1.初始化
    / U. e+ J7 n, T
    ( j/ e2 c1 R7 ?0 x( ^* F2 D
    选择一个群体,即选择一个串或个体的集合bi,i=1,2,...n。这个初始的群体也就是问题假设解的集合。一般取n=30-160。
    ) c% C& r+ G& x2 K

      u. E1 l! S. h8 ?+ F4 v- q( o' P通常以随机方法产生串或个体的集合bi,i=1,2,...n。问题的最优解将通过这些初始假设解进化而求出。
    3 y. O; d+ i4 S% G

      ^4 Z* @/ E  ?2.选择
    7 L3 e. C4 S4 J2 F7 ^4 L+ U7 ~

    . x' i  P2 X4 |6 h( R. ~根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存,不适应者淘汰的自然法则。$ P& ?. ~7 i+ d" Y4 z

    * b% I6 |1 M. ]. e% s, z给出目标函数f,则f(bi)称为个体bi的适应度。以
    : [/ ?5 s2 x& c$ H

    ! @! F+ I/ c$ u) r1 N+ J$ Z- Z2 V! S8 K2 ^$ P) A

    4 N7 M6 V, I6 B8 U" b) v0 X" K- k" c为选中bi为下一代个体的次数。
    1 Y8 q% z& l$ J; w( s, p6 r

      B& v$ e" l; p; i2 Z7 c显然.从式(3—86)可知:
    ' h3 V, Y# B, G: w

    * I+ i9 p& g: V# S; X5 I(1)适应度较高的个体,繁殖下一代的数目较多。5 Q& {1 H/ O2 |9 J  H

    ' ?+ C7 d$ ^) J# \. F(2)适应度较小的个体,繁殖下一代的数目较少;甚至被淘汰。
    ; T1 W: ^0 b* r& C- x6 r* w

    " B: c( _  i; m! w! x这样,就产生了对环境适应能力较强的后代。对于问题求解角度来讲,就是选择出和最优解较接近的中间解。
    0 c" T/ K6 e- k  u, f" ]
    - E$ Y& \/ ^) u3 [; k
    3.交叉+ d! q3 ?6 W. t
    对于选中用于繁殖下一代的个体,随机地选择两个个体的相同位置,按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换;目的在于产生新的基因组合,也即产生新的个体。交叉时,可实行单点交叉或多点交叉。
    0 F+ Y' s5 u. W0 ^
    0 F) M+ C- j% E* v; N# M8 D; `- k0 o
    例如有个体: a* V! S+ \; d4 n9 P
    8 N6 o3 \; ~! S) e6 ^& {
    S1=100101
    5 O, B9 e, i4 q% L
    : c7 P) g4 e5 s- T$ M4 F
    S2=010111 , ~7 y  m& W9 A
    ! ]! I8 x' N3 j
    选择它们的左边3位进行交叉操作,则有
    $ I4 f1 f5 ~" k; N( ^3 B! ~4 z

    $ B6 O4 D. G5 [) K+ x& Y8 AS1=010101
    0 h$ a* L& w8 X  |7 i; e+ b
    : |0 N; D1 N! v, T
    S2=100111 $ i' c' P& v* i2 p3 `3 l

    - ^( e+ l' o4 L  Z& i9 t* t" w4 u+ _6 w一般而言,交 婊显譖。取值为0.25—0.75。
    1 k& x* F4 @& k" y& v
    * s% a) k1 V) j6 p. b& T, k
    4.变异7 ^3 U& ]' K4 D0 k& X
    6 E3 e4 V: T) n2 u# i! Z: I/ q2 }; G
    根据生物遗传中基因变异的原理,以变异概率Pm对某些个体的某些位执行变异。在变异时,对执行变异的串的对应位求反,即把1变为0,把0变为1。变异概率Pm与生物变异极小的情况一致,所以,Pm的取值较小,一般取0.01-0.2。
    " e, p" E/ X! K6 E

    & t8 `9 t( I3 G$ s' ~$ `例如有个体S=101011。; ]  T+ g* H- a; F8 a1 l

    / n7 ^1 L  p) L: T, P对其的第1,4位置的基因进行变异,则有8 |4 \# s5 M! c  L
    ' Q. l% Y! z7 T; L  \
    S'=001111 $ F  a) `' B) E# [% H
    ) I) B/ X9 G+ ~: \
    单靠变异不能在求解中得到好处。但是,它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时,交叉是无法产生新的个体的,这时只能靠变异产生新的个体。也就是说,变异增加了全局优化的特质。& K- \" }2 p* J
    + D/ l% ?* ?& O- C
    5.全局最优收敛(Convergence to the global optimum) " }6 E1 S# T/ L5 @7 G

    ) p" M# `+ }$ S1 _当最优个体的适应度达到给定的阀值,或者最优个体的适应度和群体适应度不再上升时,则算法的迭代过程收敛、算法结束。否则,用经过选择、交叉、变异所得到的新一代群体取代上一代群体,并返回到第2步即选择操作处继续循环执行。; [2 |6 d5 S0 P; ~1 @# n

    % J7 `! U1 D  L( z; x7 ^图3—7中表示了遗传算法的执行过程。
    * }. V- Y: V4 \  y% x! j. q" e! J4 \" p$ r1 T, F" N9 K

    / P! w$ k. t% t$ i' j9 U* s3 Q: m
    7 Y8 a2 s( m* s" t, E/ B
    7 G. z1 \  c" B6 p8 c. e% C图3-7 遗传算法原理
    + @. v; c: T# n. K6 ]0 X

    ( N  {% z1 P# X3.2.3遗传算法的应用9 m2 `/ W  N/ e+ y" e3 ]' b. b

    0 @! S0 p6 p0 t. X* d遗传算法在很多领域都得到应用;从神经网络研究的角度上考虑,最关心的是遗传算法在神经网络的应用。在遗传算法应用中,应先明确其特点和关键问题,才能对这种算法深入了解,灵活应用,以及进一步研究开发。8 ~* `5 |5 V4 f- P
    ; j  C% y3 x5 t3 m# k3 D
    一、遗传算法的特点
    , A& n& T! `$ Y1 ], q
    5 S5 K) W5 o- Y7 J
    1.遗传算法从问题解的中集开始嫂索,而不是从单个解开始。9 h4 i$ l1 G( G" V  D! i

    9 L; k, _$ ?, s( Y0 C这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的;容易误入局部最优解。遗传算法从串集开始搜索,复盖面大,利于全局择优。+ [9 V" b$ k$ I3 K, N

    $ F; f2 z: |2 q) J2 ^4 e2.遗传算法求解时使用特定问题的信息极少,容易形成通用算法程序。: L" T. ^+ L+ q  f. c) `

    , U+ h2 J9 a9 y0 z5 f) ]由于遗传算法使用适应值这一信息进行搜索,并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息,故几乎可处理任何问题。: J$ R8 F. c: `% T4 B  d, b
    # l5 Q0 H& H) C0 `! G
    3.遗传算法有极强的容错能力
    " K5 G7 l$ E( Q( y3 W$ M

    % k  h, f* O! g0 R遗传算法的初始串集本身就带有大量与最优解甚远的信息;通过选择、交叉、变异操作能迅速排除与最优解相差极大的串;这是一个强烈的滤波过程;并且是一个并行滤波机制。故而,遗传算法有很高的容错能力。7 R5 K) V/ @9 z2 X

    ! \7 W1 p- H' P7 j4.遗传算法中的选择、交叉和变异都是随机操作,而不是确定的精确规则。
    2 l9 a7 B& }% y) f/ k

    ( _; i! p6 S% @5 u- ~: J这说明遗传算法是采用随机方法进行最优解搜索,选择体现了向最优解迫近,交叉体现了最优解的产生,变异体现了全局最优解的复盖。
    % G: p+ |) }; n
    # m4 _4 R- L- N5 y$ `5 A# _
    5.遗传算法具有隐含的并行性
    ; W9 L" }4 c% u' I. B

    8 K& H  n3 z( G4 _7 s: l' h) U遗传算法的基础理论是图式定理。它的有关内容如下:: N" q3 p2 a) w# I

    1 m4 \2 y0 F' |5 U- d5 M(1)图式(Schema)概念* U* ~* K$ I* O# h' m6 z
    . i: p/ \' V+ g& @
    一个基因串用符号集{0,1,*}表示,则称为一个因式;其中*可以是0或1。例如:H=1xx 0 x x是一个图式。7 v/ f9 T7 |3 R& g$ {
    7 P3 f% L; y2 x6 _# n* o4 d
    (2)图式的阶和长度# V/ g; ~/ Q1 P' c0 J# f
    , D' Z$ W( l: _% K2 Y
    图式中0和1的个数称为图式的阶,并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度,并用δ(H)表示。对于图式H=1x x0x x,有0(H)=2,δ(H)=4。
    1 \( {3 P; F5 Y4 s: K

    - d' M2 q. Y% a: `0 X* r$ Y(3)Holland图式定理5 V1 ?' s" v, F" }" y6 G5 F
    2 D1 Q, h2 I6 U% F( q( G
    低阶,短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时,每代处理的图式数目为0(n3)。! ~2 S8 ?. t: C/ l' ~" t/ Z9 v# J3 X

    2 Z0 p8 l( G3 T* U' k9 I0 r1 t: {遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。% I' `0 ^* I5 z3 B- S; d
    2 O* x  z: q- p3 E# p; X
    二、遗传算法的应用关键
    " g7 H! J0 A2 T3 i4 V& _' N1 G# J3 z
    ! o! D% \; I  [9 j( j% D8 C
    遗传算法在应用中最关键的问题有如下3个
    / y5 w; f8 m; T- R8 f( j" j/ w8 h

    * P- D( f' O* i0 |3 p1.串的编码方式. C1 D  c3 ^. F

    8 T: {, j& S. U  v. Y% e, [这本质是问题编码。一般把问题的各种参数用二进制编码,构成子串;然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。6 X* R, ?* q9 u0 v' B

    ) Y, f2 m: M+ |7 Z; u6 H& s: I2.适应函数的确定. P( c4 i' G8 Z3 i/ k1 k5 J
    . |3 K0 R! p$ k$ L0 S5 m4 Q
    适应函数(fitness function)也称对象函数(object function),这是问题求解品质的测量函数;往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数;但有时需要另行构造。' J5 P, h0 `7 r6 B. X8 z9 ]0 ?. j- x
    ' z+ c7 f% O: O4 D0 a1 V
    3.遗传算法自身参数设定
    ' t. A4 ^, I7 u$ L0 p; |
    / U( j1 \! P- _% U- B
    遗传算法自身参数有3个,即群体大小n、交叉概率Pc和变异概率Pm。( F- K& c* S9 R9 \
    & x( K; C. w+ \6 ~" T$ d
    群体大小n太小时难以求出最优解,太大则增长收敛时间。一般n=30-160。交叉概率Pc太小时难以向前搜索,太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构,太大使遗传算法成了单纯的随机搜索。一般取Pm=0.01—0.2。! V  C# b8 t! Y0 \. E/ N- b" b
    # [9 C5 I$ M+ K  f
    三、遗传算法在神经网络中的应用
    * E+ }* T& |& ]# n3 A
    - d. L7 }1 n5 i
    遗传算法在神经网络中的应用主要反映在3个方面:网络的学习,网络的结构设计,网络的分析。
    ! O; y; Q4 B& x2 v2 `
    9 s- B  N/ t  k6 L. v0 F
    1.遗传算法在网络学习中的应用, u# C) ?6 [+ @6 D6 T) y

    ) j2 }- M8 g. r& b8 m( I& p2 `在神经网络中,遗传算法可用于网络的学习。这时,它在两个方面起作用
    / h/ \0 H  C( s0 f1 g9 N4 h& x; R

    0 y" S! ^. Y8 J  Q3 E0 d/ e(1)学习规则的优化
    $ ~3 E  w$ E7 J+ r; v- [: m: M, l
    / Z. {: A. F% p
    用遗传算法对神经网络学习规则实现自动优化,从而提高学习速率。- \1 a5 W! V6 x! W# D
    6 O- o; j0 Z, g! B7 ~
    (2)网络权系数的优化2 x7 _; a, i1 `
    2 R4 k$ B: Y% K
    用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
    0 c7 D( O) V! N

    ( ?& T5 v8 {! d$ W. ]2.遗传算法在网络设计中的应用2 ]$ h0 `) |- i4 ~2 j* a

    % ?, k+ l5 a, ^  [" W9 ^& L用遗传算法设计一个优秀的神经网络结构,首先是要解决网络结构的编码问题;然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种:/ M) n# C' z- ~" h7 @) ^9 T4 X8 E

    % R+ o! K3 E  q8 `; l$ T/ o' g(1)直接编码法
      p" R! `2 a/ G( E0 V

    4 D+ N: A8 [( i6 k# y这是把神经网络结构直接用二进制串表示,在遗传算法中,“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。/ z9 j: M* l) d/ v) k0 K' G% X
    : c4 s1 w3 [4 j. V* g& R: M4 i8 y
    (2)参数化编码法
    0 E+ _* S/ @7 g& \
    # i' d* u) Y" i7 O5 f
    参数化编码采用的编码较为抽象,编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析,然后产生网络的结构。
    ' P: w7 _0 ]6 J

    " Y" y7 @/ K, t* y, P(3)繁衍生长法
    " j, p8 F& {4 S% _+ ?1 e

    9 h" K% W2 X2 h3 D9 M% i这种方法不是在“染色体”中直接编码神经网络的结构,而是把一些简单的生长语法规则编码入“染色体”中;然后,由遗传算法对这些生长语法规则不断进行改变,最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。' d2 b8 K1 U( U& R) k* F
    * d9 k6 G( B* [! z  x6 X/ i
    3.遗传算法在网络分析中的应用
    : h( J$ R4 d6 U5 ~- b

    ) _3 n  H0 f7 m0 f' \$ I遗传算法可用于分析神经网络。神经网络由于有分布存储等特点,一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析,性质分析,状态分析。" z. ]# e4 c  W

    ( `' [6 y+ G1 L8 |遗传算法虽然可以在多种领域都有实际应用,并且也展示了它潜力和宽广前景;但是,遗传算法还有大量的问题需要研究,目前也还有各种不足。首先,在变量多,取值范围大或无给定范围时,收敛速度下降;其次,可找到最优解附近,但无法精确确定最扰解位置;最后,遗传算法的参数选择尚未有定量方法。对遗传算法,还需要进一步研究其数学基础理论;还需要在理论上证明它与其它优化技术的优劣及原因;还需研究硬件化的遗传算法;以及遗传算法的通用编程和形式等。
    2 e8 Y. n8 W1 d" D* b
    更多图片 小图 大图
    组图打开中,请稍候......
    "真诚赞赏,手留余香"
    还没有人打赏,支持一下
    楼主热帖
    帖文化:【文明发帖 和谐互动】 社区精神:【创新、交流、互助、共享】
  • TA的每日心情
    慵懒
    2017-6-1 21:49
  • 签到天数: 6 天

    连续签到: 1 天

    [LV.2]偶尔看看I

    累计签到:6 天
    连续签到:1 天
     楼主| 发表于 2012-6-7 10:03:10 | 显示全部楼层
    几乎可以处理任何问题。。。但是缺乏理论根据。“遗传算法虽然可以在多种领域都有实际应用,并且也展示了它潜力和宽广前景;但是,遗传算法还有大量的问题需要研究,目前也还有各种不足。首先,在变量多,取值范围大或无给定范围时,收敛速度下降;其次,可找到最优解附近,但无法精确确定最扰解位置;最后,遗传算法的参数选择尚未有定量方法。对遗传算法,还需要进一步研究其数学基础理论;还需要在理论上证明它与其它优化技术的优劣及原因;还需研究硬件化的遗传算法;以及遗传算法的通用编程和形式等。
    "真诚赞赏,手留余香"
    还没有人打赏,支持一下
    帖文化:【文明发帖 和谐互动】 社区精神:【创新、交流、互助、共享】
  • TA的每日心情
    开心
    2019-4-1 16:01
  • 签到天数: 1 天

    连续签到: 1 天

    [LV.1]初来乍到

    累计签到:1 天
    连续签到:1 天
    发表于 2012-6-7 10:48:31 | 显示全部楼层
    学习 学习了
    "真诚赞赏,手留余香"
    还没有人打赏,支持一下
    帖文化:【文明发帖 和谐互动】 社区精神:【创新、交流、互助、共享】
  • TA的每日心情
    愤怒
    2020-12-8 11:59
  • 签到天数: 105 天

    连续签到: 1 天

    [LV.6]常住居民II

    累计签到:223 天
    连续签到:1 天
    发表于 2012-6-7 14:58:45 | 显示全部楼层
    适合了解用。
    "真诚赞赏,手留余香"
    还没有人打赏,支持一下
    帖文化:【文明发帖 和谐互动】 社区精神:【创新、交流、互助、共享】

    该用户从未签到

    尚未签到

    发表于 2012-7-31 23:24:23 | 显示全部楼层
    希望提供代码。。
    "真诚赞赏,手留余香"
    还没有人打赏,支持一下
    帖文化:【文明发帖 和谐互动】 社区精神:【创新、交流、互助、共享】
    您需要登录后才可以回帖 登录 | 立即加入

    本版积分规则

    招聘斑竹

    小黑屋|手机版|APP下载(beta)|Archiver|电力研学网 ( 赣ICP备12000811号-1|赣公网安备36040302000210号 )|网站地图

    GMT+8, 2026-11-20 10:01

    Powered by Discuz! X3.5 Licensed

    © 2001-2026 Discuz! Team.

    快速回复 返回顶部 返回列表