转（遗传算法）

guofuzi111

生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
/ Z# |* e% [: _) ?% a# a: U/ T
7 Z% r' o6 |, z' ?) M遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。
% o, A" u8 C4 L( i2 h* N* g
遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。

9 V. ?" [2 m7 D5 t. a* f% q* l3．2．1 遗传算法的基本概念

4 R1 \4 h$ _: z6 o9 e6 a! |! z  r遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。
. Z, A0 ~8 N, `% r* {1 f# y: M
Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。
$ O; C; J6 f9 v; ?
+ R4 A% S: q- M+ q+ g" P% zMendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
# [" q3 [! l: I! D* g( d. U9 j0 j
由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：
. Q, A% l1 d8 _
一、串(String)

它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

: p9 u0 F' ?2 e7 ?5 U& {# Z. x二、群体(Population)
; m% }0 k6 j5 `: a, P& M& y
+ @* Q$ t+ w, w( T个体的集合称为群体，串是群体的元素

三、群体大小(Population Size)

在群体中个体的数量称为群体的大小。

1 t% w6 B, Y( X1 ]8 W+ _四、基因(Gene)

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

五 、基因位置(Gene Position)
7 s& n) B+ t# Z% N' B: X
一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
/ O$ U. @1 v" f( [
+ ~8 T$ h* }: P: x) G' F4 q, Y六、基因特征值(Gene Feature)
( G. s& z3 `+ @6 g
  ~. W0 C2 y, Z. n在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
$ L+ z0 W. g: y
七、串结构空间SS
3 \3 y- e" _5 z- C. p8 M) A3 Y
) B* ?( u& R1 C' T在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。
# q# n7 a$ i7 g: W
八、参数空间SP

: v# u5 V% o+ ~4 f' c! }这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。

九、非线性

/ q/ `# I; j' b6 N4 e1 r- K+ g它对应遗传学中的异位显性(Epistasis)
  i2 `+ @7 ]: i  ~
十、适应度(Fitness)
) E# e& q  E# t5 M
表示某一个体对于环境的适应程度。
4 m9 o3 P- x8 y, ?' D1 T7 U
遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
& W, E- p: q! O) {  f0 f) r
. X8 l% C; C. d$ m! A1 {3．2．2遗传算法的原理
  R, v" e1 K3 @: U) k
7 n" t# ?3 C* G  t* _遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

一、遗传算法的目的
) }; c, d9 p& E3 w- r
4 _9 p  j8 n# f典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：

考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
- U, r+ \+ d6 O/ s
bi∈{0,1}L        (3-84)
% ^4 M: q& a( M# h. q; T6 M  F* t3 }
  Z# A" {7 r5 e  c$ i$ E% @& ]给定目标函数f，有f(bi)，并且
+ y( ~) W  M. p) `+ Q  J' R
5 e% \. I1 @! p4 B0<F(BI)<∞< P>
8 C* A+ A6 B# V( j# V- T2 T
. G! H" e' _' w同时

f(bi)≠f(bi+1)
8 ^- P2 U8 a+ ]; N
求满足下式
& l+ x% K. k* W
$ n, n+ x$ ?1 z, A2 K7 ~: ]9 g2 H( smax{f(bi)|bi∈{0,1}L}
6 L/ n4 \: T9 Y4 _2 x7 S
8 F  `+ r  v9 n1 ]的bi。
+ F$ U1 n/ s# v% X- f0 G, I5 Y9 l
' J5 G+ z; }, K2 O$ M6 c' h6 z很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
  s4 J' n9 t2 X: l& _
8 I& Y6 V$ i2 ^7 r/ {4 L7 F0 r二、遗传算法的基本原理

) p' O6 S: t4 a! A长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
6 I  X# B+ S& x4 s/ X1 y
1．选择(Selection)
# T6 u' t3 t0 ]! D% B
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。

2．交叉(Crossover)

' J" a1 M1 t2 f0 G# \& b这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

9 ?2 B% W& v; ^4 E) Y# M5 d' x+ O7 Q) f3．变异(Mutation)
6 h5 D' z" }* ]) B' i
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。

遗传算法的原理可以简要给出如下：
, L2 |5 w1 h  _7 U' z* ~
2 q) \7 k# v. k$ I" _5 V& Zchoose an intial population
- s: x# x5 G* i
determine the fitness of each individual
# s# y, v# C4 v
perform selection
; n& @! C) }3 j# f1 x
repeat
1 Y) ]  I6 l8 V) C1 `& Y& q
* e) ]: i: q, `* r    perform crossover

    perform mutation
8 y" t" k+ _% k" Q  u1 P
1 |' ?' @5 z1 c/ }% W    determine the fitness of each individual

' N, a5 s* Y' k) r, R' P4 c% V/ t0 W$ n' t    perform selection

6 z# g) l  F! P/ {until some stopping criterion applies

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

1．初始化

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

6 b# \; R7 T2 f$ w) ]. U5 p& _通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择
, h8 Q. u* \  z" c( E  l8 S  l
: o' i; _' C* `+ o% K根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

给出目标函数f，则f(bi)称为个体bi的适应度。以
6 i7 a$ S( K! B8 G* b
6 R: E5 ?; Y, a% u, Q
1 i! R& {7 \2 c2 u% P7 e
为选中bi为下一代个体的次数。
& u+ m& }$ W+ V9 ~7 X4 Q4 q' j
显然．从式(3—86)可知：
  {5 i: y: [2 H5 E: H' r
(1)适应度较高的个体，繁殖下一代的数目较多。
1 ^# s* ?1 {+ k2 x
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

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

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

例如有个体
* i$ L) U0 Z' t$ ], m- w5 _0 T
: V& Y+ _* w9 MS1=100101

S2=010111

选择它们的左边3位进行交叉操作，则有
6 K  g0 c; t% _7 }' V/ @- J
S1=010101

/ o: d6 ^  t9 nS2=100111

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

4．变异
( v' C0 Z; i0 ^- @
2 K/ {- s; h+ M5 S根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
' _: {8 N' N7 ?$ _5 D# y2 \- H
/ S' S4 |  ?6 x1 Z$ X" O$ j+ a例如有个体S＝101011。

对其的第1，4位置的基因进行变异，则有
  Q, G) U- \$ y, ~7 o* h
S'=001111

单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

8 \$ I) N5 F2 v: H# g8 {5．全局最优收敛(Convergence to the global optimum)

当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
; i) x: U- }$ p9 [! i0 }! w8 X
图3—7中表示了遗传算法的执行过程。

2 T! h0 \# b; m


! @' ~/ c+ l  v2 g" G" Z图3-7 遗传算法原理
$ [4 L" F, z5 V1 w& ]$ d1 n# \
3．2．3遗传算法的应用

% ~; D8 [2 B0 f1 H* ?遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

一、遗传算法的特点
' J  O" S  v' T- W, l, Z5 \4 B
2 G8 b6 H- ?% b1 q1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
% N; T+ y4 T! }. x4 h
# Z. N4 M8 M" V# b! a* t# I- k- T" N这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
) s" n* Q  A3 \/ p- b8 n
! {- F% ?* ~, I) w4 S9 V由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

, ^+ c) @5 s# o4 R0 f% M3．遗传算法有极强的容错能力
1 u8 S; Y: w1 w
0 g% A8 S3 U5 d7 ?% i+ o+ g0 w! \  V遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
; a. b3 U" L* Z- b( z
. \& i8 b9 v* V$ x' ^4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
$ N# w7 D/ T6 |- J. ?( L  I+ W3 t6 V
. Q* |4 P" m+ E7 u, L! I2 c: c这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
0 {  u" w7 ~' G
4 y0 D" D' x6 x+ I7 v5．遗传算法具有隐含的并行性
% @4 N5 B5 w/ i; d% R1 O
& q6 C8 T7 b9 @遗传算法的基础理论是图式定理。它的有关内容如下：
( Q. {4 E" R7 G
(1)图式(Schema)概念

: ?) B; x$ |5 ^; V一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

4 I; y4 T3 a( u2 S& w(2)图式的阶和长度

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

4 {/ u# C6 d5 s0 U: t2 x% n5 R(3)Holland图式定理

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

1 `* l" B0 V* d( N; \) l遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
% i" T  a: w8 ^0 I2 |1 J( Q# n
' _4 E* L) ^! s9 Y- L1 z5 h  _二、遗传算法的应用关键

+ ?& v  @0 t& v7 ]; _遗传算法在应用中最关键的问题有如下3个

- Q" ]% ?! y* d# b/ a7 f7 S  `1．串的编码方式

7 H( \# i# U$ z这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
4 p2 X; x* ^0 {8 Q% x0 I; H  v
! l  l: _( E+ U* l7 F2．适应函数的确定

) k1 ]3 Y7 ~" T2 @适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
, ?- f5 z# _3 g% J$ J6 B6 I
3．遗传算法自身参数设定

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

  c1 K" t# W5 O' _9 z8 _6 }群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。

三、遗传算法在神经网络中的应用
5 F* _3 |5 v3 ?' c! a5 ^5 w! a
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

) Y& f4 ^+ Y6 d& l/ l1．遗传算法在网络学习中的应用
! R8 p' t2 V# U( t1 n4 ?1 k
+ p0 d3 f3 g8 G% j! T在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

(1)学习规则的优化
9 C- z+ E# f4 A, @
用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
0 Q9 ~1 i$ S7 r
* ]2 ?$ x  _' [: `(2)网络权系数的优化

/ x! R) V* \2 k7 \1 v+ X用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

2 ]* X; t  ?0 B. k. [2．遗传算法在网络设计中的应用

用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
; z  ]1 b0 {5 R( R* k
4 A$ b" ~( i( G* E7 u* h(1)直接编码法

' H+ Z: c% @$ N. `这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
* r$ E, h$ n( B3 I; f0 [$ a& N7 q
" H- j/ L' f. z0 @2 R(2)参数化编码法
; s8 a% U# r& L! ^& E6 B" f
2 v0 Z( Y. n+ w参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
8 \; ]  |0 ^$ N6 `6 q6 s/ _! u
- m: j3 G& j8 x# k) p( q(3)繁衍生长法

" E% z2 [, F2 B1 Z9 ?这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
- r" Y5 D9 p' l2 _* z1 C1 \
3．遗传算法在网络分析中的应用
" T) _4 v2 h8 Q' S
# p6 ^* B8 z5 D- S/ {遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

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

$ T4 L+ S( U* ]  u; }三、遗传算法的步骤和意义
; y/ k8 V: u% P) K
1．初始化
% s1 H4 P; |  x" r3 s4 m
选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
; ^+ W: y) |' E* n$ x
6 W" w: [, g# p# [: e6 m; x* r通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
( ]5 p$ v1 l3 p( {* u3 r2 F
2．选择

7 N3 \- }3 @  u7 K* A, G根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

给出目标函数f，则f(bi)称为个体bi的适应度。以


4 U6 w. s6 D, v
, ^: Z9 v) s9 R7 f/ b- W为选中bi为下一代个体的次数。

显然．从式(3—86)可知：
) W5 A; c0 s) Q8 n1 \, q$ p
(1)适应度较高的个体，繁殖下一代的数目较多。
: h9 _1 _4 y4 d( ?0 L. O/ A
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
% |5 T8 {3 J1 z1 W6 k" \# P
+ Q7 B, E* W- J" K, l3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

例如有个体

S1=100101

S2=010111
/ A7 X8 s$ E1 }: ~8 e, K# t
, B# b# z* h, N选择它们的左边3位进行交叉操作，则有
$ G! f+ @' i4 g* a: ~
4 C# o2 t4 U. v  N7 D3 }S1=010101

- J5 O/ }$ C. j/ q; I: [) nS2=100111

: V, Q7 d4 K& Z" s7 J4 K8 c3 W一般而言，交 婊显譖。取值为0.25—0.75。

" O+ o2 g- D# X2 @0 ?7 S4．变异
$ L: f- u+ ]) z8 _
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
, |2 h) x. ~' L6 I: K& Y
例如有个体S＝101011。
% k4 N5 C8 W, G; _6 j3 T
对其的第1，4位置的基因进行变异，则有

S'=001111
: X  v! I. y+ d
* {& p9 L, L' u2 F单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

5．全局最优收敛(Convergence to the global optimum)
; |. e* p) N' ?" v* U
& q0 d. s) L% ?2 G/ j2 e# e当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
' o5 u( R/ i$ T9 D. ?: ]. v% F
# o4 E, S8 M1 _图3—7中表示了遗传算法的执行过程。
$ p: F/ y1 I4 e5 Z: Z, L
1 b: V# x+ I* P# o3 r/ Y# I


图3-7 遗传算法原理

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

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
# @% O" l' G9 y; c% u" @: w
9 \  K8 `. i; Z+ z一、遗传算法的特点
# j; [. [, }' y; [
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

; {( X# h  w+ f: w+ Y这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
0 A. x7 y- r# L0 P9 ~
4 s, D' v9 q1 n' F5 N+ O/ y由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

8 N2 E" `1 G+ p9 _  p1 a. R. k, R3．遗传算法有极强的容错能力

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

4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

5．遗传算法具有隐含的并行性
% J. H  d0 M6 i1 y+ f! k  d+ t
遗传算法的基础理论是图式定理。它的有关内容如下：
+ ^/ q( G, j0 p  {
$ C% g  H: p: f5 L9 m  \(1)图式(Schema)概念
* H0 P4 V( E: V+ |6 G6 J1 D, ]
8 X0 _4 M  ^* W0 J5 i4 A一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

7 ?' Y; U2 s6 W% b! g4 ^9 J2 w8 v(2)图式的阶和长度
9 J5 k9 Z2 c& K; J& M
  l9 W. {: |0 v* d- q; J  m4 j/ z图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。

- Y; S  g0 V! w" j( ^8 Z, K6 q4 U(3)Holland图式定理
+ |+ h, B/ g; s3 c" \- H
, ~0 S+ w4 Q1 O; ]% {2 s, O低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
# x; I: d' O, P2 h
二、遗传算法的应用关键

遗传算法在应用中最关键的问题有如下3个
' m# `! d4 K/ q: Y/ e
1．串的编码方式

+ }9 \/ }1 `$ R: O# p- Y这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
, o" M' k& E! b& F: ^" X
6 Q# C9 K. e' F5 S2．适应函数的确定
7 Y8 ]  h+ D9 x+ D
9 l9 J1 }& g& c5 B( b: b9 T适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
9 T+ ]: |: b8 g" }3 P
3．遗传算法自身参数设定
  x' Q7 g; X( K$ D# a8 E
" r0 A8 h$ W- A) \" c, q遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

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

8 C2 n6 h* S3 W! ^* r三、遗传算法在神经网络中的应用
+ C9 j2 ~& J: f! X; V# F- y
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
' p- v( e  n; n
1．遗传算法在网络学习中的应用

在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
- a, w# P' j- b4 D
; h2 @  e7 ?+ s% G6 `(1)学习规则的优化
9 k" }. K3 A" T( i) L" m" m
用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

" p) g9 Z( d% Q3 a(2)网络权系数的优化

  H  W, S6 }" E' G  H用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

2．遗传算法在网络设计中的应用
% K7 `$ o+ ~% L! l  `
' _5 T& w1 e1 k7 H9 h# e1 b用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：

(1)直接编码法

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

. X4 m, n% F0 f8 s: K( u! n0 U( }(2)参数化编码法
3 E4 l' H% M# t( D0 j
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法
4 `" V, W* u, j2 \) b
这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
& x6 L4 M6 B  ^0 F0 a3 C8 t
+ B$ A9 z- k0 S  L+ N3．遗传算法在网络分析中的应用
" _$ O  v* k' l' N& q! m
( \; A+ A3 O+ e遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

* S5 R: o6 P( L) c遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
$ h2 [7 ~2 e$ p$ q7 r/ ~5 r5 d

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。