转（遗传算法）

guofuzi111

生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。

! G% C# M: }$ i" T3 u遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。
" l8 G/ A' H' ~: A
0 X/ q( {( X# ~+ B" n) ~: W- U( g遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。
' m# i3 p7 ^6 }) E5 ]
  H+ ]5 q/ C3 L8 ~3．2．1 遗传算法的基本概念

遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

" m1 [- G/ `/ a2 v4 R  `' ?. L$ a9 T  uDarwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。
  P4 Q* e3 J& z, F- B8 q
" O; p& V( ^0 D+ U1 x- mMendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：
: L) ?4 H( t; i* o. [
一、串(String)
8 m' M2 t( {) Y5 F# c
它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

二、群体(Population)

, z- Q" j. e( z# f个体的集合称为群体，串是群体的元素
; P& j7 {7 ^, W9 P% a8 F! K
! k+ _, i3 ^3 s! y. T* R! q三、群体大小(Population Size)
. O# S3 c& u( |" w4 d" s. i: }
在群体中个体的数量称为群体的大小。
2 a! u" L9 x; d/ @
: B6 b# j- u$ m- S/ \四、基因(Gene)

* N8 k$ l2 t8 v- a: n/ j2 Y基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
  w) V0 t, z& _
; m' N4 L* _: ?3 e& l1 w五 、基因位置(Gene Position)

1 D5 Z2 G/ y$ Y' C% T* Z- E一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
0 h; D: e) ?- w; l
六、基因特征值(Gene Feature)

在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

# ?* ~- i4 ?0 W/ ]  K( \七、串结构空间SS
: R4 P% Q- L5 o' g1 |: o3 m! r
在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

八、参数空间SP
, W8 Y* c% L- [1 W
这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。

) a" a2 W; N0 Q; {4 e* J九、非线性
- n$ [/ t1 O( x
它对应遗传学中的异位显性(Epistasis)
0 ]& \$ K. ~' `% A% J
" d0 Q  g- }) l8 E7 q# B# v十、适应度(Fitness)
5 D  ~% F7 G; E% @& T5 o& z; b
; J. E2 K) J* [$ R表示某一个体对于环境的适应程度。

遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。

+ ]  P& e6 Q% Q8 M' E3．2．2遗传算法的原理
4 J1 x4 f/ }0 n+ N- Z2 f1 N  o
遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

一、遗传算法的目的
1 O" c( q6 v8 L" ?8 Q% h& S8 V- \8 ^
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：

; P6 W% |# i- Y/ Z' }, o考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

bi∈{0,1}L        (3-84)
$ W; w+ G4 w1 \0 ]
8 B# E! l' i7 ]. s# A给定目标函数f，有f(bi)，并且
9 N" K  ]  B- w/ N2 F
" t+ F; Q) C. U  y0 a3 ~1 h0<F(BI)<∞< P>
; i9 K6 M3 M. K0 \: ~  J% k
0 Z. j) l! z  h8 F9 e1 F# R8 Z. D4 x8 j同时
( g9 ]$ I3 E$ Q7 v$ S0 Q* M
f(bi)≠f(bi+1)
( T' o3 V+ ^; p2 w4 e) ?
求满足下式
! Z5 f" @* Z1 M# c2 I1 K9 `) @
max{f(bi)|bi∈{0,1}L}

的bi。
3 A; f' n5 ~) [4 X
4 Z2 C2 K8 A3 H1 F6 l% Y+ }- I$ t很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。

' I$ r* p4 J  P# T4 G! A二、遗传算法的基本原理
3 y6 U6 s; A& |6 v  \! B4 `8 e
长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：

6 B0 |9 X5 W, M1．选择(Selection)
$ e& `! F- {1 M1 [+ X
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。

7 b3 k* B- k* G5 N5 T2．交叉(Crossover)

这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

3．变异(Mutation)
2 z- V& p" ?" ]+ C& p
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。

1 X* l5 Z3 E  Q9 ^0 _遗传算法的原理可以简要给出如下：
. g! V( K& ?5 W7 |& J2 `4 k( G
choose an intial population
* G! v0 x8 R2 C' H# X/ b
7 \4 W' f9 Y5 j& M; [- qdetermine the fitness of each individual

0 d* T! k6 H' l0 W/ L- Hperform selection

repeat
  c- q+ x  \3 ^+ o; z& [
    perform crossover

9 b7 _: b& j6 l; s( _9 E% l% T8 h    perform mutation

    determine the fitness of each individual

    perform selection

; B( T' {" x2 w. f, G5 s, Iuntil some stopping criterion applies
5 P1 ?0 k4 M; d! m. ?9 r8 k
这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
+ g0 k& X% s: T# K- T三、遗传算法的步骤和意义

, E! w" l5 J8 V5 i$ D1．初始化
8 k; a( Y) A$ G2 F! j8 W2 Y/ }* X
选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。

通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
( G+ z" `: y; B- e' G0 p* T1 d
2．选择
3 s" T# R! S4 K) z8 @! e4 c! Q$ G
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

给出目标函数f，则f(bi)称为个体bi的适应度。以
5 G# v+ M; R+ j& E2 s. ~+ O& x- h

* q9 e% H9 u( D1 D
为选中bi为下一代个体的次数。
2 D" {, \" _  n6 j3 L
1 G& }/ f# T2 H: |( ?2 _, z显然．从式(3—86)可知：
; t2 W/ ?' d$ ?2 J9 t
(1)适应度较高的个体，繁殖下一代的数目较多。
) d% W, H! [" @( c3 Y/ a
9 k0 v0 w  c1 [5 |- h9 R/ M& U(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

3．交叉
4 e+ j. P" F% c. ~0 r) M对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

例如有个体

5 Q' E" K9 A. P9 h% V7 m/ `S1=100101
- f1 m3 m+ g, o# W* b
: H$ ~% r2 _- e) f! pS2=010111

选择它们的左边3位进行交叉操作，则有
; \7 J3 ~% z) o' r# m7 ]" ?
S1=010101

S2=100111

一般而言，交 婊显譖。取值为0.25—0.75。
  R0 M6 @+ Y# |0 ~# v, {: Z4 G/ E
% ]2 }6 H$ [& V/ n4．变异

根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
3 f- _3 i0 S$ C5 _
例如有个体S＝101011。

对其的第1，4位置的基因进行变异，则有
$ `) Y! g4 E- i2 }, D$ h
7 x, x0 |; _& R( K4 Z  ~S'=001111

, k/ y: C8 L7 B( O+ D/ J2 d0 _9 h8 Y单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

5．全局最优收敛(Convergence to the global optimum)
0 o, a1 t# ?7 y; C: w8 u
: ]. r+ Z4 r+ |' `& e当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
( K- Y: I/ Q% s/ d3 b( J5 h
( \( D( `9 B  m图3—7中表示了遗传算法的执行过程。

0 I1 z' Q9 ]% l# t) H* K

* E+ y4 o% F9 d2 v
0 v& v& J  Q6 H1 B- a图3-7 遗传算法原理
8 e+ D4 l# O+ B1 e9 J0 {! ]! x
3．2．3遗传算法的应用

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
5 v, }1 O1 H9 }5 @
6 @/ }; Q  H$ P9 E$ `一、遗传算法的特点
8 A1 v6 }+ ?; D* K
8 ?& d2 A9 C( A1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
$ S9 Y$ Q/ R- [1 F# l
4 K/ `$ s8 }" r1 X5 u2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
) ^% ]; W' u6 ?4 q9 l
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
0 K3 S& d/ w) B9 f% J+ d$ v9 x
3．遗传算法有极强的容错能力
* d4 \# t, I/ T* }3 x, K- R
5 }+ O1 \; Y7 L) O- d' c, D遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
; l8 p  r1 c+ D0 ]5 M% N: Y/ E
4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

& I5 X/ M$ r6 F  K& \2 y这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
: ?  V/ t% `; I3 x
5．遗传算法具有隐含的并行性
8 R4 r$ z' O! O$ ^+ c4 C; m: d
% C& M7 j4 X& @- E& V遗传算法的基础理论是图式定理。它的有关内容如下：
- X5 K% b' K, N" e
(1)图式(Schema)概念
7 j8 z3 C  O  @, u8 s
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

) E- z- W. J; g2 V' I6 l. @(2)图式的阶和长度

图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。

(3)Holland图式定理
8 P% Z: D& q+ n8 {6 ~
. y) l$ Z' X8 |  t# U& Z# k; ]低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
! Q  Q' O! K  L" w
遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

, J' p3 O7 g8 W% Q( _; N二、遗传算法的应用关键
" x, D* i' l+ O. e5 C; r
3 i; Y" F6 h7 q遗传算法在应用中最关键的问题有如下3个
! M1 M* I) q2 z2 n& H8 M3 O
1．串的编码方式
( |8 C( F3 {5 t* }) q+ e- F
; V; n! d3 N: h# w. j这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
0 E! A/ C& K( C4 J. u/ x  y, @
/ w7 h; q, ^0 |3 R; M3 v$ ?( ?2．适应函数的确定
- K- j0 T, t( v
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
" ~$ Y: U& h5 h  A# A8 w
4 v1 T; t6 g: R! a# X# ^# |7 p! A3．遗传算法自身参数设定

遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
, ~+ [" z( H, I+ {
群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
, p; i6 ]  [. h0 E: l  Z1 c
8 U9 c" p+ c' {: J4 z1 O3 E4 f三、遗传算法在神经网络中的应用
8 _  b$ L) w+ c3 }  r/ h5 x
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

1．遗传算法在网络学习中的应用
/ T2 g( C+ F8 i7 \& x( Q- F
/ ^# k# O" Y" Q7 `5 E* A在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

5 ?9 j$ O4 z9 g  y(1)学习规则的优化

# a0 L6 ]  Y! v3 A1 E/ y用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

) p5 T! P4 \! W$ Q( s3 E  t& M(2)网络权系数的优化

+ g  G# B% |4 I( \: y8 n用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

$ s, g% N& ^9 o! d* V# @2．遗传算法在网络设计中的应用
( F. u5 Q  e& |4 \
5 K/ [. ^! Q( f; H) V1 P用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
+ T% \& W$ p  S) i# |$ D6 ~  V3 L# s3 n
8 L3 _+ B* a* m0 J. t" T(1)直接编码法
! ~, z( I9 \3 T( o: h) W
+ q: y+ O* \% Y& n) M" F+ J# _这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

(2)参数化编码法

参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法

这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。

" `9 ]# x- V' w1 y3．遗传算法在网络分析中的应用

* j: S7 {6 Z; M* r遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
' r" n2 [% G/ a& n, ^  n
- c& O7 ^; v* ]' C' ~遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
% _! i! j  H. [. G
+ {- {) A+ v( C- A! o& }% [

三、遗传算法的步骤和意义

" v9 i4 K! W, S  v1．初始化

选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。

通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择
, L& t# U6 Q( o) y& b: Z
9 U0 y, Q0 @* {根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
- V" Z4 n$ l5 T+ E
给出目标函数f，则f(bi)称为个体bi的适应度。以
6 u2 e- V7 [9 K5 Z+ ^
% k# P6 |6 @' R' q8 k" O/ [
8 U4 W3 f+ I) x; O) f+ R. `
- O$ d& h) G3 q1 n- \为选中bi为下一代个体的次数。

, X9 |2 D$ m, W8 U+ S) a显然．从式(3—86)可知：

) t; |+ {/ _# I2 b+ Y- N% S7 e4 p( ?(1)适应度较高的个体，繁殖下一代的数目较多。

" |1 R' N+ c" c! o$ `(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
, g: b* m% }4 I; x4 Y$ q
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
+ s, L8 B0 k9 U
3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

例如有个体

7 B% N; f$ W2 iS1=100101
1 r5 E) ~1 x% q
S2=010111

# K; W  h& Z$ c$ w选择它们的左边3位进行交叉操作，则有
7 b# G7 Y+ Y% o) I/ o' d
S1=010101

S2=100111
' @# f  H- d! L
  C- ~+ _" i7 z- q+ Z一般而言，交 婊显譖。取值为0.25—0.75。

- j1 q8 b- V: a. ~4．变异

根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
9 A& K4 P& G$ V3 k
例如有个体S＝101011。

; i- S6 L6 v/ g* P" n5 L3 K: N对其的第1，4位置的基因进行变异，则有
, P( `( t6 J/ w4 Z
4 s8 z, h3 z- v  a; bS'=001111
; M% G9 P/ L1 _6 J! w+ j- [
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

3 D' S$ ]; A) @" x5．全局最优收敛(Convergence to the global optimum)
0 B: z* Y8 J0 y7 r: C( ^- Q
* g. Z) S) x6 ?1 q当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
& z1 Z, [- f" c: x. f
图3—7中表示了遗传算法的执行过程。
7 G& T; Y6 n, r# g1 y: W" g( ]
3 i) @& T( ]" V; G  `! q

5 B  o8 [; r1 y# k$ }
0 }7 T+ a) _" ~8 b图3-7 遗传算法原理

3．2．3遗传算法的应用
6 R' _/ G' e* }: ~( ?7 Z
7 J' ?6 l6 |. E# d9 l遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

一、遗传算法的特点

1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
7 S$ u2 E/ Z" i- w2 @. C* l
3 k  u/ @+ `4 r! {7 {5 f+ u; `这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
0 N# G: \. E4 Z  l3 ^
# `' b3 O3 O( D( ]2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
) H4 x+ T: H  s6 N5 @" \
2 U  Z* J8 b- X$ q4 C: G由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
7 o1 n3 o& z2 |
3．遗传算法有极强的容错能力
% v/ I! `% k* O" P8 A
遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
7 k- R0 O. u* O* ^$ F
0 y/ D& t( N2 D0 R/ {& G' H4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
  g( H+ x- Z' A9 h+ a( X
+ T" D, a( k4 A, ^9 C; |这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

9 W0 |( D% a/ T+ X# M1 q5．遗传算法具有隐含的并行性
3 p  C5 K8 ]9 R" {" R8 Y
遗传算法的基础理论是图式定理。它的有关内容如下：

(1)图式(Schema)概念

一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

(2)图式的阶和长度
# c& F% u/ f. B4 _6 I, s$ a
图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
0 g2 h  G- _2 b- t) H! F. n  Q
(3)Holland图式定理
  x8 x# _6 Y1 l+ R
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

3 a' N4 l0 `) N9 ~$ P, @. u2 A, m遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

' B2 b1 X4 q+ q8 W/ F二、遗传算法的应用关键

9 H/ _' q$ ]7 r/ a) u- E) u遗传算法在应用中最关键的问题有如下3个

1．串的编码方式

+ E+ Z" r/ s, f9 l2 M% E这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
, L2 A: ~5 |* F/ m# {; f
( V; r3 U: e$ c6 r$ i6 M4 Z, t2．适应函数的确定

适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

0 \  l' r! b/ \3．遗传算法自身参数设定

遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
4 Y( Q% W) M- Q7 g
三、遗传算法在神经网络中的应用

  ~4 v1 \  O9 r遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

  @& {% B2 X3 P) T% W9 Q$ `  ?1．遗传算法在网络学习中的应用

1 n. e  D+ ?2 y+ e( ^2 h; [在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
) K- q/ b5 a, \" R7 ?# \: i- I% c8 E
(1)学习规则的优化

用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
5 w7 n. N- ?- G+ r1 O
(2)网络权系数的优化
/ C  D5 Q) H/ C" a
用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
- P9 t+ s, m! ?
6 l1 J8 X6 H7 M' q+ A& D* A* l7 d2．遗传算法在网络设计中的应用
% H3 f& G; e+ _% [' K
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：

. N/ W) r; G9 Q. t. I! O2 j(1)直接编码法

这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
* I1 I0 E, v* J
(2)参数化编码法
9 {1 b$ u2 B0 @6 J
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

+ E) N* l" n: ~4 X1 i: i5 t(3)繁衍生长法

这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。

3．遗传算法在网络分析中的应用

遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
" v0 t& E( g" X6 F" ^! Q
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
! D0 i* r8 L; g! c2 f0 Q  m2 `

guofuzi111

几乎可以处理任何问题。。。但是缺乏理论根据。“遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。