转（遗传算法）

guofuzi111

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

遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。

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

3．2．1 遗传算法的基本概念

* T4 W& U* t' Z! C% m遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。
2 T) n- A  _+ o' ?
Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。
7 B( A, O+ B% @7 F! g
Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
0 R5 z$ r7 U) G. A; i/ M
# x- X- P8 c( B) M! u由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：
& E3 G( A9 W+ L; p
1 {0 ?7 H/ ]( ]8 m* l+ D0 O一、串(String)
+ D4 p+ }, ^# x$ }
它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

/ F# C1 z7 o, b9 C* Y* Z3 G! U. R二、群体(Population)
3 d5 B+ L& j+ h8 b
" I% I2 p' u) u( u3 _个体的集合称为群体，串是群体的元素
  z/ Z7 I0 C" W+ X  O
+ R( x+ V: z6 {三、群体大小(Population Size)
4 L1 z3 r' ?# ~/ z7 H
/ d5 [/ i0 _. @- k" O% N- v在群体中个体的数量称为群体的大小。
' N1 I1 R- u, {% @( s5 _7 e% m: u
( c3 h+ W2 B4 @) j四、基因(Gene)

9 \0 v9 ^: A) P基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

五 、基因位置(Gene Position)
$ M8 t( z9 ^, a. G9 t
2 c/ X5 p* _7 S* E一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。

& @( }5 K. H- c  ]5 Q3 M  S- M六、基因特征值(Gene Feature)
! ^( P; q! v! z: I, P
7 c% r  a6 G! l* Y% b* F在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
( `0 C) B# d# C4 I: p. \- C
' p! ?5 I6 V; b七、串结构空间SS
! O( C9 w) Z- N& @( R
在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

八、参数空间SP
2 L: T) W8 u  X9 a1 @1 O
这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。
9 o+ }+ P" ^' N+ s4 X6 M  @
九、非线性

它对应遗传学中的异位显性(Epistasis)
/ }  v7 Y+ ~$ e1 O4 g% [( m
9 J% c% F; T' [& u* z十、适应度(Fitness)
4 y& q8 ]/ e  y0 W
表示某一个体对于环境的适应程度。

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

: w; V* i% d' s7 [5 L3．2．2遗传算法的原理
) N4 H- \0 k- G6 B' o3 I
9 I; I) K) n4 {! i& ]% m遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

, r. z6 w, g, k( T) k一、遗传算法的目的
1 z; d' Y9 B3 `/ O" S' ]( V
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
3 r/ f* q5 |6 ~2 I1 u
考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

bi∈{0,1}L        (3-84)
$ c- v) f2 p3 x. L
给定目标函数f，有f(bi)，并且

0<F(BI)<∞< P>
- e+ T2 V2 T" K& [" ?6 z
. F) `  c- D- V; {# H" Y同时
& h3 V' p) S3 ?* Y! {" q6 y
4 e5 M4 P4 y6 F  uf(bi)≠f(bi+1)

% C  P, Y3 p, w5 C. U8 U求满足下式
7 B: p. h  \) j  {- P; b7 [  ?
max{f(bi)|bi∈{0,1}L}
, G. Y- c. i7 l
+ Y) C4 a7 y8 k: D2 S5 t) j! N的bi。

* Q1 h! T% J5 P5 e- w" m很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
% ^/ b! }  s7 k" \: _5 N$ F3 a
0 S9 K& h( l! r! A/ w1 x9 P1 |0 H4 l二、遗传算法的基本原理
% S- z" M0 F/ w, _& [. A
长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：

1．选择(Selection)

4 i# }( a$ J6 y3 m; a- k1 H这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
! W+ y8 D+ r9 T3 }  K
2．交叉(Crossover)
& ~9 Q  H6 v8 D
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

4 \6 i6 U, `/ q  x5 i) g$ D3．变异(Mutation)
& j2 j8 g7 ~' S+ N5 f/ N! @3 _! ]
& H7 E/ ?4 z# T6 p) J这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
/ |) I, w; m: Q: p; ?- c1 [" }
$ J' B0 u, h& m  y* l" j遗传算法的原理可以简要给出如下：

& d/ Z; V3 U+ z; ?& schoose an intial population

: [. p1 a9 _8 x# X5 O& c% adetermine the fitness of each individual

perform selection

repeat
9 ^& y$ `3 \2 L2 @
8 K( B& m! q1 ^$ G0 r2 D, \% N1 O    perform crossover

    perform mutation
% F" o. B# ?3 _; d4 @& I. r
    determine the fitness of each individual
$ ^* J5 W2 _) {/ `
, g; c/ u0 T. Z8 Z: K4 s8 Z0 _9 ~    perform selection
6 F1 t( p0 u: v- f  A- u
until some stopping criterion applies
9 @) y! ?/ h  U* P+ q
% @9 M, n* r3 u6 }. U+ l这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
& U2 a; ~' S5 {) u三、遗传算法的步骤和意义
( `6 o( P0 k( B
1．初始化
( Q7 t: y3 {) P2 y9 v( ]. i1 a
0 u1 i; B! H7 d, h; K, S1 |, A2 R选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
/ _+ a9 g" V' d* l* \" H
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择

: h! p+ Q5 r' }4 G$ v: B根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
, g/ F+ C" w7 O$ b7 v: p
( F$ W( `* ?' |% N给出目标函数f，则f(bi)称为个体bi的适应度。以

& S' W. j8 R" ^, {  E& h* `$ [& F
! F; P; s" l8 z# }' S  t
为选中bi为下一代个体的次数。
9 C1 ?' j* H* J9 M
显然．从式(3—86)可知：
. d* Z1 \$ x0 z6 I4 L
(1)适应度较高的个体，繁殖下一代的数目较多。

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

% \& G; v+ s( J# Y4 z1 W这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
9 O/ m7 k: v7 v$ V
3．交叉
, {# x. ]( y% _6 g1 W- i. M" e对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

, |4 i% h/ L% b例如有个体
  w* L- z  }/ e* p0 m6 y: z2 B
  W2 E& s9 a7 P' E6 R+ `( Z% AS1=100101

S2=010111

- I% j" _- A2 R% ~2 F( ]. X6 l选择它们的左边3位进行交叉操作，则有
$ y2 M; k+ t& n' T
, c  f6 M8 ^  q) l, N: E* e" \# m' QS1=010101
+ k0 S# U$ V/ s/ L8 v; g
S2=100111

" g* w, w4 d) d0 N8 Z一般而言，交 婊显譖。取值为0.25—0.75。

4．变异

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

例如有个体S＝101011。
* I4 ?0 t" U5 ?9 E+ m
对其的第1，4位置的基因进行变异，则有
8 W' j: H) c- a8 g5 H8 e8 u
" o9 g5 b) f/ E2 U0 |+ }S'=001111
; }* ~3 b1 O1 o$ I2 k
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

5．全局最优收敛(Convergence to the global optimum)

当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
$ Q# b" B8 }$ s. d
  |$ Y) O2 r( \* ~$ u图3—7中表示了遗传算法的执行过程。
% c% k8 H& |9 P$ y2 f3 P
) _  P& D% \. M! n* h+ t( q
3 o7 O. e8 o* F7 k4 m

图3-7 遗传算法原理

3．2．3遗传算法的应用
. V& Q4 U; {% e5 u6 ]: R0 u( O$ z6 C
遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

一、遗传算法的特点
7 g! B6 J# z9 ]+ i- `6 }
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
: @! @. a- p4 `5 o6 N. E
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
5 Y5 ^$ ~8 e% @; U2 K, C3 Y
) l# e% H* t  F+ a  N, R2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

  B; u% A# u; `" J由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
9 R. B. H/ [" M
3．遗传算法有极强的容错能力

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

4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
8 D) R9 R4 G, H+ t
6 x1 p6 s! d) I. E  Q( v/ S这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

5．遗传算法具有隐含的并行性

% y' W* E; h# e7 H0 V; @" u2 ~遗传算法的基础理论是图式定理。它的有关内容如下：

2 O4 ?, i* Q+ n& D(1)图式(Schema)概念
. {" O3 f: d& X# N8 D" A
) Q4 V- ~. n4 X8 j5 H( D一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

2 ?' B3 M) Q: a: h! Y(2)图式的阶和长度

+ E" l4 p  ^8 x- d- I8 [图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
, ~; s0 v& I8 J% p( Z
(3)Holland图式定理

& Q# z' i  b! @% T5 y! m低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
' o6 b  }& J7 d# I7 d4 D$ D
* Y  W% N- r( s1 w  ]; a9 E3 S二、遗传算法的应用关键
" ^3 \/ E1 m3 A. d2 a
遗传算法在应用中最关键的问题有如下3个
5 J3 j9 a) F$ M" r/ ~$ a5 j
1．串的编码方式
5 C( R+ c5 o  g, [3 {
, ]0 _3 F( Q! J- z这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
& }7 [- `+ H6 m: Y, P9 b
2．适应函数的确定
+ h' F# b. j- d8 D+ W
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
/ X* [0 b: R# J
3．遗传算法自身参数设定

遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
: H2 ~+ R$ l/ f0 s) t
群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
7 k5 w2 P9 D0 X6 {, `0 d" C/ R3 y' B# n
三、遗传算法在神经网络中的应用

- C8 F! {8 ?, e; g2 g/ c遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

1．遗传算法在网络学习中的应用

2 A- `0 a: T8 Q0 D在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

(1)学习规则的优化

# a  d, I9 L) ?# Q( b用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
- d% I1 j, x; M- j2 Y
(2)网络权系数的优化

用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
  K# ~/ g0 D9 H# T- L
2．遗传算法在网络设计中的应用

用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
  k1 `  T7 ~, f0 J
(1)直接编码法
3 F! R& A% j3 V- c& e$ C% Z
. l7 Z' J& g, x0 p& N; h! r8 B这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
1 p! l3 L/ X- ?7 H: g
- P, Q/ v6 W+ X% o+ X1 q(2)参数化编码法
: r$ b3 @- U6 l; l
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法

这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
' r) t( s0 R7 y9 t- d% |* s6 ]
1 d; b2 J5 d# K2 ~3．遗传算法在网络分析中的应用

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

, g5 V* f7 N! S  d

三、遗传算法的步骤和意义
$ @' M% B/ S4 D! L
2 d' U, t9 w& F. H9 ~% p1．初始化
4 v) P% [* s9 E: }' Y; ^
. h' p! I8 W6 Z; s- |选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。

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

' p! Q3 j. f% P* m# ?2．选择
$ S* S% O6 Y! n6 t
3 E" |; I# F8 W9 K: s' v根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
- I) {" b5 L" ~: D
5 ?6 x5 A& t! Z1 P: l给出目标函数f，则f(bi)称为个体bi的适应度。以



4 I% P4 i% D% W* q7 Z为选中bi为下一代个体的次数。
- Y9 X3 t! U2 K
3 }% y! O. x* L9 [- d显然．从式(3—86)可知：
4 E" ^( |: j0 c3 j3 A
* d  }( ?2 K% s! u" O+ Z9 L! M. s(1)适应度较高的个体，繁殖下一代的数目较多。

(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
. t7 O: U/ S% x# `( G# r- A/ z4 V* @
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
* m, M& }+ C' b# \8 N4 g
, J" A. w$ o2 }3．交叉
& e1 Z+ V: h% n& M# u6 b对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
! G: R2 l: \8 F% h: Z. h
例如有个体

S1=100101

S2=010111
! c+ p) H5 F* Q2 w7 [
- a& d2 g. H1 l/ @9 @选择它们的左边3位进行交叉操作，则有

" T0 r# R9 i- ?/ ~& f, mS1=010101
8 O( k/ f7 l, f* x& i3 r
S2=100111

一般而言，交 婊显譖。取值为0.25—0.75。

4．变异

  K2 c$ c& e4 J  R0 K根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
4 F- w) x$ O- F) O. v* Z& s, u4 g
! h- g6 n% B- @- u% S例如有个体S＝101011。
$ V: [4 l+ L0 g/ S
对其的第1，4位置的基因进行变异，则有
7 i  Y% K: x$ ^! X
1 f: M" |4 Q( OS'=001111
) L) H+ Z  W+ e8 ^  F: @
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

( H5 W  N7 ^' a7 I9 m5．全局最优收敛(Convergence to the global optimum)
; K7 l0 \7 ~+ j1 p
) R2 [/ e: l: |- Z4 U- F7 H当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
) @. z; P7 g9 z/ j- r
, G  a7 O2 X2 D7 [图3—7中表示了遗传算法的执行过程。
& i% W; i- \5 g



9 d+ T" h2 v9 R8 h  W图3-7 遗传算法原理

! Q1 b/ f  X6 j0 h4 i7 w' t3．2．3遗传算法的应用
& l7 a2 p" |. k* [6 L" Z
* r" J9 Q; e6 M; a遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

一、遗传算法的特点
2 [2 f+ p' y; r
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

1 O, p! T5 I9 @7 \3 e3 F: P! @3 j这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
9 A9 a% v. \4 p% m2 M% t3 ]
0 I3 |* N/ ?! `8 d; x2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
0 ~# S1 j' v9 L, A- l$ }8 W. g
3．遗传算法有极强的容错能力
5 ?' K  d5 U. k; `# V' {
遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

8 w& M$ K$ {/ D& C3 \( N: ~: b- n4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
- X# D% j  ]3 \# m
4 P' V0 P/ |8 l3 w" C. N/ x& b+ @这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

* A3 B9 t. w9 x6 R5．遗传算法具有隐含的并行性
' M  l* U) H' g4 m
遗传算法的基础理论是图式定理。它的有关内容如下：
9 Z9 s) E' R' f9 @7 m5 Y+ @9 `
(1)图式(Schema)概念
* F6 ?% v* S4 h3 H6 q
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

: y% l2 z* r5 i! u9 N+ s(2)图式的阶和长度

, q( `! ?0 n; @( o图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
8 i6 Q- H3 L+ @+ r& y3 A( J+ _
7 e  x9 M) U6 h! D6 `+ D, l" s7 P(3)Holland图式定理

  U* t2 {( C3 H% D8 x# w* C低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

( d8 i- l) r; C2 B/ d% H二、遗传算法的应用关键

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

1．串的编码方式

# @0 b. ?1 V5 x) G这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
7 {- Q6 A3 I6 }
2．适应函数的确定

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

3．遗传算法自身参数设定
, Y1 j, j- x" l2 R$ [
& b3 T! ^3 h4 V  k! H' @, H7 z遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
- B, o  h/ x( n8 r/ X% P" g9 n) N5 ?
( E: a( \' r" L0 u! a# I5 @群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。

三、遗传算法在神经网络中的应用
$ H+ I3 M; G& g0 [9 [% @
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
- N) q) G6 N+ Q6 R6 V6 _% g/ N" V
- A8 C7 y; J4 b0 h: P0 _1．遗传算法在网络学习中的应用

在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
6 D* m8 _, N! }% R3 H
(1)学习规则的优化
' q0 `$ T  ~6 k, Y" X
用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

(2)网络权系数的优化
* K' n% z2 }5 W8 \: E. B
2 L1 @3 B3 \7 M/ l* z用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
' A) _( @" w6 X/ \8 {1 d
2．遗传算法在网络设计中的应用
% z4 i7 A* A' x+ j) ~
2 J8 i0 z9 _5 v: H8 G用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
) M- F( ?8 j7 T" Z* A# C$ ~9 S
1 x; y- x* u- n* q0 D' C  \1 L(1)直接编码法

9 d% F' P( m$ Q: a# N这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

(2)参数化编码法
& n( b0 ~& I: B" s
! i5 `+ i: Y8 G1 Q5 I- P( u- {参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
$ T6 d8 U2 x$ j: @( v9 V
(3)繁衍生长法
. C8 h5 U" y, L: ]7 a
这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。

, }% Y/ I& I1 P9 T2 F+ }4 Y$ p- O3．遗传算法在网络分析中的应用
! J, s/ w# e2 u8 K7 G6 U. ~
遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
+ c, c) U7 F! j
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。