转（遗传算法）

guofuzi111

生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
3 z7 v) U8 ?$ r
遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。

, j) Q6 t6 U5 G4 N遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。

1 G! s% c0 g6 U- m; m3．2．1 遗传算法的基本概念

遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。
( Y1 _$ S$ b, ]$ X! i% v
( E8 i& W3 h, c5 w. YDarwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。
) c6 d1 D. z+ P7 I) k1 ^1 _
Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
  y# Y7 R" v" _
. ]" Q$ ?: }* i# M1 |$ ^由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：

一、串(String)

% u8 t. p$ z+ D/ j% T- ^5 d4 C它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

二、群体(Population)
* n0 y/ f- y& l2 Y# I: r+ |
1 v$ U/ R, k; q+ I个体的集合称为群体，串是群体的元素

" R0 R; h+ X$ D0 {8 N! G8 k三、群体大小(Population Size)
( O: c: r( V3 ]* H- }
在群体中个体的数量称为群体的大小。
5 f" C: Z) k$ o: }6 ?* [$ G
6 S2 m6 x$ U3 ~四、基因(Gene)
  n$ g" j1 D) \* M2 H& n% h; ^2 B' T
基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
: y; y% i8 l4 m- r
五 、基因位置(Gene Position)

( G9 S1 l6 R2 Q2 ?% W0 u- ~/ f一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
( |' S1 V; t5 c9 c7 I& H
) d( V8 G9 \: h3 }六、基因特征值(Gene Feature)
0 ?) n$ n/ b- j* H3 l
在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

七、串结构空间SS

在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

八、参数空间SP

; k8 T3 L) D: P这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。
* i; G. ?3 ~; V" r/ s
1 n' A: }6 d' M. x7 Y5 A0 J九、非线性

它对应遗传学中的异位显性(Epistasis)

) j& i4 k; A( }" _$ e, o十、适应度(Fitness)
+ D$ ^8 ^! i# M7 r
表示某一个体对于环境的适应程度。

遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
; r) N; S4 J$ J8 q" Y4 p" j0 }
3．2．2遗传算法的原理

1 ~) Y- l# u9 e; u" D9 z0 T遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

一、遗传算法的目的
4 i5 a4 P' c; O& S! L
% p# w3 _1 J$ d& T典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
( u5 d3 ]; j( P% R! Z0 b
  |) Z1 X8 L  N4 |6 O8 a7 P考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
! i7 T: s) X! e6 w2 T
bi∈{0,1}L        (3-84)

2 @" t; r" ]' l+ z: x( g给定目标函数f，有f(bi)，并且
- D' V# n7 f: e4 i  T
6 u7 n$ g0 Y/ c: D9 i8 T. L0<F(BI)<∞< P>

) l# `: Y4 n8 s5 o7 L7 y: K同时
) z, s; `9 Z& I' g+ W9 C1 X. B: A  K
: Z) J" P6 G8 U! c* A0 u3 Ff(bi)≠f(bi+1)
1 E* q, U' k* N: C
求满足下式
; Y- W1 x+ w0 [
" c1 g1 r, n4 P& E3 Tmax{f(bi)|bi∈{0,1}L}
) @, U  s4 T7 q6 h3 O
( X# V& B9 T$ j5 }  Z; B" {的bi。
: C) ^& b8 U9 \9 \8 E5 o
很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。

二、遗传算法的基本原理

长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：

1．选择(Selection)

+ k, {, d6 F+ Q- l; J这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
7 F5 q5 O- A- \0 M
% @3 g; J. Z5 x2 g4 N5 m2．交叉(Crossover)

这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
0 w# ~- I) H) ~9 k& ?% S! A
3．变异(Mutation)

3 J( N0 U/ P- b( O- r* y4 n这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
, t  s- L0 g- x4 y1 Y! X) R  T
遗传算法的原理可以简要给出如下：

+ @5 x: \% o0 Ichoose an intial population
2 H1 y- t- R! |7 f" B$ i3 K, Z
determine the fitness of each individual
4 ]( T( d5 ?, N" r" }' @, M; v, r
perform selection

7 J6 ]6 _  i; m0 O& Frepeat

    perform crossover

; b1 l: P7 t% r( W8 Z    perform mutation
5 [, J- J& W8 F$ V
) }0 [1 q$ A! b! ^1 j, ^    determine the fitness of each individual
( g. V+ y  l* s) O& \! N& ^+ l
( f8 Y8 o& C8 o+ u    perform selection
4 a* `- X- X( v2 r+ b
- h0 [6 Q* G/ K0 Y+ Iuntil some stopping criterion applies

这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
三、遗传算法的步骤和意义

% f' ^3 O9 {. x8 }1 O, r1．初始化

选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
& P# n! @' l7 l2 B9 Y6 F. b
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
0 \  p9 ~  b$ z& s! X
9 f" c9 ]$ b; q2．选择

7 U. U6 r5 H9 r4 Q3 _: }/ X根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
/ l( j( X% O; u
给出目标函数f，则f(bi)称为个体bi的适应度。以


. {( Q. [" g/ N' U6 ^
9 m5 b2 m1 @$ ]为选中bi为下一代个体的次数。

显然．从式(3—86)可知：
' ?5 X3 X5 @3 ?7 F) K0 J1 y2 w
' S% e* n* t3 U1 v. ?(1)适应度较高的个体，繁殖下一代的数目较多。

(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

% h  Q. g0 k1 a( `7 f/ z. _这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

3．交叉
3 {2 ]1 n) m$ Z$ w- j0 N8 a对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

+ W% u* J7 b% S# F% Z  O* P" P例如有个体
7 u  }# k. ^4 G8 N7 k
S1=100101
( ?: b$ {; S8 G6 M& \9 Q
" ^  ]- `3 x9 `7 \' ^# ^1 p3 SS2=010111

' E/ e% n3 `% _: h选择它们的左边3位进行交叉操作，则有
# C6 l4 B/ J6 O) X! X4 k/ `" x3 T
  |$ r2 l( C7 bS1=010101

4 U6 r7 H  @! P8 WS2=100111
* G6 T7 n) |+ }0 s  `
一般而言，交 婊显譖。取值为0.25—0.75。

* u5 Z3 U0 I0 ~0 n0 U4．变异
9 S# p' _$ `+ i
: ?5 i0 X4 x( _/ `" j根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
; o1 e$ n6 n) s2 ?, m
例如有个体S＝101011。
& u  A7 H8 A! X1 x. n3 @! i! O
/ d; L: |5 _( j对其的第1，4位置的基因进行变异，则有

+ ^# x4 f1 O" o( }5 VS'=001111

单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
: h3 P' ]4 Y7 O' x0 f" a
5．全局最优收敛(Convergence to the global optimum)
) B- S6 e: R% B* r% k% C
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
( L( v6 A# e7 F
) }- j$ c* ^/ O$ s  l% p, F: G图3—7中表示了遗传算法的执行过程。
1 R  {/ q8 _2 c8 z" }$ ^( A

  B' c3 t0 `! @: ~; Q
1 m$ L# e# x. u5 i/ w) }5 T; D
图3-7 遗传算法原理

3．2．3遗传算法的应用

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
! O+ F1 i3 O( C9 p% o
一、遗传算法的特点

4 w+ g5 D4 k) B' E1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
7 F" p& {6 N. N/ J/ y6 j
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
/ E3 W' Z" Y0 [0 y1 y* e
2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
& ^5 Z% Y+ R& _' Z/ b& g
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

; U' t* S5 _5 p3．遗传算法有极强的容错能力

遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
, A" K) S3 T$ X/ q2 _
; f4 [1 N0 ?0 ~: s4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

% H- ]+ Y% c  W这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
4 N+ ~" T( e5 y. J- M. K5 s. d+ A  x+ ^
6 P6 ], {# y0 {( m+ A5．遗传算法具有隐含的并行性
( |* \3 J8 S) f3 y% X9 d; P
遗传算法的基础理论是图式定理。它的有关内容如下：

(1)图式(Schema)概念

一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
* I0 q. e- L* V5 [+ Q: _  u0 R
(2)图式的阶和长度

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

(3)Holland图式定理
, c2 L+ @" b9 @" s4 M% g
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
# A" R8 D* K: S5 _, ~# w, @
, s( S% F5 h% {! l遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

/ f% d* L6 N! X$ M! D0 b二、遗传算法的应用关键

遗传算法在应用中最关键的问题有如下3个

1．串的编码方式

这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

9 N  {, h) s$ |0 z9 D, p2．适应函数的确定

0 y& \" G) s6 }- R' b1 z6 s& `适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
# e' w8 ]7 J# R% B1 M  Q% o
) L, ]4 ?( c/ F8 c# ]* U3 ?3．遗传算法自身参数设定

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

4 Y+ M* h0 Z% y6 a  S4 k+ [群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
1 p+ q* c, o( \. x
3 R* v& [$ H7 q3 s, l- }) z0 S7 n  [三、遗传算法在神经网络中的应用
( Z! p- f* I& @3 |8 R
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
' r6 Q! h+ X1 u2 H/ _/ p6 z
) S. a& I/ t! ]4 G. k- A1．遗传算法在网络学习中的应用

% Y. Z2 r, H4 X- p$ ?5 B在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
# l! x) k% ?: l4 X, d$ z/ w$ k
6 o( S- k5 M9 O- s) D(1)学习规则的优化

用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
  I: n, C. W5 {5 s* A$ E
) ^/ J8 b0 U' p(2)网络权系数的优化

- t- x' w) e" O( x0 A& F% f用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
3 q; G: \2 J+ _
; r4 T; X8 A- L) ^2．遗传算法在网络设计中的应用
! _+ V8 `, ]% f9 {1 Z" U
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：

(1)直接编码法

: q1 ^# l1 r6 T这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

(2)参数化编码法

* R" n1 @6 @, Y7 ^7 C参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
! m7 d! n/ {* B$ R5 r0 E
(3)繁衍生长法

: X* z) I) \/ s( a1 K: ?, F这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
8 p0 B2 q4 v2 n1 t2 `# G6 \# K+ f
3．遗传算法在网络分析中的应用
: G- D7 k9 _: ]/ F
# |/ P! t: b. x" N1 @+ Z遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

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

+ D, B- v1 w0 n: N  ~8 |" p三、遗传算法的步骤和意义
; N$ u4 T+ n0 A  q
1．初始化
. R' |3 F" [* N) d  v
5 I0 O( A1 v& |+ u  j8 `% \选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。

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

; S) m$ Q' [1 S8 h& @2．选择

根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

, i- o6 ~* ^3 u3 E. N给出目标函数f，则f(bi)称为个体bi的适应度。以
" h% c6 ]3 o3 w8 S  j' T
0 _# G4 D$ T7 N5 a

为选中bi为下一代个体的次数。
& G- X; [3 l# @& ?- T
显然．从式(3—86)可知：
. l6 G8 }; y! Z7 \+ y/ j
" ^* a+ |! V0 q2 _1 |& p(1)适应度较高的个体，繁殖下一代的数目较多。
( M. O0 _& y) _# T! T
# B4 t" O  y9 i' J( z# K5 _(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
2 o% _# ?2 ^0 _2 y2 V4 l
8 l# G9 k5 O# P4 k2 x- E3 A- o这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
6 p+ `7 k0 @. V- Y) k
# Z% s" s5 c3 d- \4 F  I3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
) c! H: B6 m3 m6 v* U% t& |- z
4 {- E% U7 s6 S/ u3 {例如有个体
+ x; T8 u+ K) L( A
6 R, F& n6 g* H) i/ xS1=100101
1 k' `+ h0 ^  ?2 ?$ A0 j  E2 t
S2=010111
, f- E: }5 v" }" Y1 w9 p' L
3 P2 j; ~& K7 Y4 v; w! e$ v选择它们的左边3位进行交叉操作，则有
/ }: `0 W5 E1 m( B* w
% y% j# N+ K4 L' RS1=010101
4 L8 {, ^, i, k! u; Y9 d% Y
2 B( T; D5 j( q& c' _: tS2=100111

4 k$ E+ p  i0 X# g一般而言，交 婊显譖。取值为0.25—0.75。

6 f! U7 G- b$ N4．变异

! {3 }6 f. I- j  [- Z+ u1 a5 C根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

2 y7 D9 p9 _6 r( o' f9 T1 _. X$ s% f例如有个体S＝101011。

7 A2 p( {1 J- ~9 \9 p对其的第1，4位置的基因进行变异，则有
* S6 ~8 a5 C! K' Q8 ~8 y4 U
S'=001111
8 U3 b$ q0 ~: B/ @( \2 E5 E: \
. r7 m, Q# l- r1 t9 }单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
3 p9 ?( H3 k; a0 p9 E! |
) h  c  ?! _. _$ X5 ]! @3 L8 z  e5．全局最优收敛(Convergence to the global optimum)
& z; l9 M  V0 I. X5 f
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。

# R. W+ s. F! Q图3—7中表示了遗传算法的执行过程。
2 l' H$ z, Z4 h/ c" R8 }
- {1 h  O$ \5 \/ o" P$ q
6 B3 Q+ f+ i8 M+ U
6 N: D( x7 H  D; W( ^$ n' e
图3-7 遗传算法原理

% N8 N* B3 H; \" _" C9 x7 y, R8 x3．2．3遗传算法的应用

( J) b! w0 p% C# |2 J. [遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

( {+ `8 _1 h7 r一、遗传算法的特点

( n. \- b& w7 O/ I1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

% {2 t* W. D9 T3 N5 j4 |这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

- I4 X& w" k* m  [: Q2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
9 A7 N- t9 l* j
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

3．遗传算法有极强的容错能力

( j! c# r/ f' J2 R4 T遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

# {* G3 C; B6 F2 k4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
4 E0 R% w" M! q% }* ?- E, V& V
( f. Q( k: i  j6 i2 e! k$ |3 x7 i& t这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

: C9 M/ O1 M7 u6 D3 T, Q% S9 }5．遗传算法具有隐含的并行性

遗传算法的基础理论是图式定理。它的有关内容如下：
- r* _* [, s  ~, l% v7 E$ w" b( L- J
(1)图式(Schema)概念
) V9 o/ ^9 p2 S% I
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
) G8 @7 t( b7 f: }# _0 ]2 F
(2)图式的阶和长度

图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
( V$ O( f; E4 b2 [( w
6 P, r, Q! R! `( j+ G! p(3)Holland图式定理

7 d  P6 P  A/ b# |低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
' R3 y& `/ l) u2 i) t
2 D9 b% h# W1 k6 i" g二、遗传算法的应用关键

  t* N- z5 ^  c, Z遗传算法在应用中最关键的问题有如下3个

1．串的编码方式
$ `+ X% |. j: F! r; ^" U, q& {9 l
& L8 R: G) b' ^6 n; ]" ~这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
( U0 K9 ?/ a2 \
# j- t1 S$ f+ [2．适应函数的确定

适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
7 o% ?! _# a6 c: q2 z  ]
. P# z# b3 l7 B  d3．遗传算法自身参数设定
* {0 U2 h, k( U
& [* K7 ~( l0 G  i遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

1 t4 L/ a+ R- y3 M( S群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
* C9 ~7 R1 o: D' Q4 J+ a8 s  M2 y5 T
三、遗传算法在神经网络中的应用
: j+ k8 Q' H+ I) u# m; V0 X
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
! D7 Y% L! Y8 A
1．遗传算法在网络学习中的应用
% P: _( H: j( S, c# ?. J
在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
6 H$ `( B% i* P% k# p
(1)学习规则的优化

用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
! u; E+ ?: T  y) ^1 O
(2)网络权系数的优化
& J. v6 i, ?# f7 u
2 {% K/ i! d$ u) _1 W用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

2．遗传算法在网络设计中的应用
# w& V& _) }- D: N- m7 Q
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
0 t- ^! U# W6 G' E& x% P) X% x
(1)直接编码法

这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

(2)参数化编码法

3 |) f! x7 b. @' h! A7 o参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

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

5 r7 z2 l! C& |+ U3．遗传算法在网络分析中的应用

" k: k8 o- W' h6 F/ @遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

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

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。