转（遗传算法）

guofuzi111

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

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

遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。
2 _. x$ t  M& A! ^( X9 r+ i+ }
! }' N( C' B3 Z6 Z7 l9 ]! T3．2．1 遗传算法的基本概念

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

; O  V4 t' O  K8 l+ Z2 ?  w6 XDarwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。

Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。

- h3 X2 ?- j5 X7 Z3 K由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：

" S( s' W; Q& `; U6 X. ?$ w( S一、串(String)

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

* ~3 v0 v% b3 |: z* L# M二、群体(Population)

个体的集合称为群体，串是群体的元素
, _7 ^+ L9 {. K  k6 j
三、群体大小(Population Size)

在群体中个体的数量称为群体的大小。
/ _1 B- T0 A6 F: X9 g
0 G8 ?% w5 l1 {5 r四、基因(Gene)

9 z1 w8 E* e' w" W. b基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
0 C6 R6 \; @2 z6 T; h: ?
5 I: G0 p6 G, |* F( G+ l6 {' z五 、基因位置(Gene Position)

一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。

  V- f9 M( f$ j六、基因特征值(Gene Feature)
2 Q# J% F4 k3 @! W4 t4 X, }
在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
" \' w( ~: J$ R) v
七、串结构空间SS
, P/ t; S: Z' L: v
- x1 _. }$ u" B. E. F: D在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。
* p# l) Q3 q0 h3 J# g9 d( a
八、参数空间SP
$ A6 }7 l, Y. Q2 M
这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。
7 _# j5 ]  y! Y6 {5 b& r
九、非线性
" k. |2 ?/ @( w# {
它对应遗传学中的异位显性(Epistasis)
2 [, F1 v0 B* L4 k! l+ W6 U8 f
十、适应度(Fitness)

表示某一个体对于环境的适应程度。
3 {2 ~: K! p6 s
遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
+ Y% x& R9 p0 H* _. s8 U
3．2．2遗传算法的原理
) H5 {! t- O. c% N+ [
遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

一、遗传算法的目的

* e) L; g8 p8 R4 N% J  |典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
& Q- t; @+ n$ [/ P& _( y, c9 ]
. b/ T- h; A& f  I6 _考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
- T# U6 t4 Q+ J, U
$ B' t3 B5 I. {8 ~# W3 m2 R4 q( `bi∈{0,1}L        (3-84)

, T5 i; Z! F3 {/ X' @/ x给定目标函数f，有f(bi)，并且
# N- ~9 _) Y. d. x& X, X: J
1 D% }1 k7 C. \/ ]2 c( a; |7 o0<F(BI)<∞< P>

( o5 K' y/ D7 j6 E同时

f(bi)≠f(bi+1)

求满足下式
" `& H% J: E. I/ J
max{f(bi)|bi∈{0,1}L}

7 z! M/ Z- Y% ~5 E2 _的bi。

6 M2 t# f, C# T很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
4 V8 [5 ]8 L) W: ^4 t
二、遗传算法的基本原理

/ a; I" n. F/ x8 q  m  |长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
' j) k; u' R" `6 q% a4 o. U8 F/ L: [
4 K5 N  L$ @2 j* ~. R9 t) Y0 v1．选择(Selection)
8 ?- n7 N. C1 |5 D3 ]# P9 _# n
0 {- K) m! u( L+ o9 w2 w) Z这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
/ C# |% |- ^' K7 q
2．交叉(Crossover)

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

+ s; H" V- R, R* F: G5 h( a3．变异(Mutation)

这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
5 V3 \2 C- Y! d! i- R
遗传算法的原理可以简要给出如下：
$ P3 V: h% R, E/ w. b
4 \: K1 P5 x& m" t" H3 W" ?choose an intial population
7 L! Y5 o! S1 s; F9 |9 R6 p! a( x
determine the fitness of each individual
2 Z9 S1 L3 _# g+ }
8 M( u( u0 ?" J- r: J  G5 m$ wperform selection

% P+ E% t$ O/ N; I  @1 l- `$ Hrepeat

& V, t  r! x' B3 T+ I( _$ t5 l    perform crossover
# u# \/ Q6 r+ s! v8 m! ~4 D' B
    perform mutation

    determine the fitness of each individual

+ `5 P4 k; y: @0 ]- R    perform selection

until some stopping criterion applies

2 ?1 K) F* s3 X4 z6 L. P$ \这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
3 e8 l$ Y9 k5 u/ e& `三、遗传算法的步骤和意义

1．初始化

选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
/ ]( u+ F0 E1 R* ~, x) Y
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择

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

* Z# h" K+ m) x6 E1 S* j8 m给出目标函数f，则f(bi)称为个体bi的适应度。以
  I$ p" o6 ]6 L- E" [
6 \  f* }8 J6 D- h

4 O% c+ C% |6 p& e) @9 p% @为选中bi为下一代个体的次数。

) K& x8 \7 o& i+ I& m0 J0 j4 J显然．从式(3—86)可知：
) |, ]2 r$ M% n, I% V# L. |5 A: G
(1)适应度较高的个体，繁殖下一代的数目较多。
7 _" b3 i" c% ?. m$ E; h: _3 t
! E% ^& w) J3 K' I* Z(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
# Y- L. n4 }) D# h7 V8 v4 d  T
3 R" E. o# w# X4 t5 M" U这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
, [- L& w5 O% u0 u3 U
# C" z( w' g, M: L& N1 i. @' x3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

例如有个体

S1=100101
7 F( X! n+ Y  ~" W# c" L
7 s: w" x+ _3 G8 _7 v  {S2=010111
2 a( K$ [4 s1 _, L2 i
选择它们的左边3位进行交叉操作，则有

S1=010101

S2=100111
. V+ E; _2 q1 r2 Y  o
一般而言，交 婊显譖。取值为0.25—0.75。
6 X1 f  Q) Y0 l& l- y2 }: q4 f2 b5 S
+ i; S3 W( L; O: h4．变异

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

例如有个体S＝101011。
) E# G& ?; p( h( h& A
6 J. w1 v, |- i- X( B  }对其的第1，4位置的基因进行变异，则有

# z- U5 B" q) i/ ?& `8 JS'=001111

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

5．全局最优收敛(Convergence to the global optimum)
( |8 P& R; O: l1 h5 _: c  |& X
2 Z9 z) C5 y! M0 j- W当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
2 o& s& F0 t+ c
/ \+ E# B8 U' i$ D' F图3—7中表示了遗传算法的执行过程。
8 q, c6 Y% k. M% H
/ Z8 Y! u( s3 k6 m: j


图3-7 遗传算法原理
& [' _/ @; Y5 X! g: V3 S
3．2．3遗传算法的应用
+ ]3 y4 v: H+ a3 v* o: d7 |
  J% }& R. ?4 X  x3 ?; e遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

: U  Z* r( Y4 U  P$ j7 {8 g/ k) O一、遗传算法的特点

( T! _9 |2 R) K- J+ l, a, o1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
' w1 r& C! v. \& _/ ~
( L/ A) E' [) t$ p$ U* x5 R+ k2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
, X7 D* s% j& G0 p! \
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
2 C. B' j* J& Y3 n
, j* n3 x8 o, B& ]3．遗传算法有极强的容错能力
' s. E9 H' k# a* v- v
3 F/ [! {' l( p: O6 C+ ^% w* ^遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

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

1 @( I& |$ b! m0 E9 e5 q) K这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

5．遗传算法具有隐含的并行性
9 d+ O! D$ y$ M" H. W
/ E3 P( O* j  ?& w+ ?+ ]遗传算法的基础理论是图式定理。它的有关内容如下：

(1)图式(Schema)概念

- f' _2 ]$ o( S$ x( _$ I一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

(2)图式的阶和长度

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

# y" j; Z$ P' N6 o/ |(3)Holland图式定理
1 T( q1 Z# Z5 D5 V. ~& R
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
3 [# \# ?2 x2 o9 @( u! P
7 ?7 N7 |2 B! o" x) I0 D% o9 X) T遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

' _7 A- [( f; N1 @: ?# f$ |0 x& H二、遗传算法的应用关键

. f. n3 Y- Y9 _2 l9 R/ B$ u遗传算法在应用中最关键的问题有如下3个

+ ~  b- S  Y) m' H; [1．串的编码方式
( E5 j5 C( b6 \5 A( X* _$ @% E
) ]7 m2 b" D3 L" i" o3 ?' X这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

2．适应函数的确定

适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
/ S4 L  ]. Z) W% s# S
0 j- D4 n' C0 `& o3．遗传算法自身参数设定
$ B8 D/ \0 u3 }  @/ K% h- V
. P; Y) j3 o% N- H) Y遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
) ^; V) N  i2 A7 I" }
群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。

0 [7 j3 \( Z% I6 g6 k# N$ L三、遗传算法在神经网络中的应用

遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
9 G8 f3 ^' \3 u5 E2 U/ _
5 @8 I: k7 C, H3 l+ n/ g1．遗传算法在网络学习中的应用

在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
8 l8 h; H  G, D9 g; T9 x# |5 w
+ T( @/ f& C) p/ K(1)学习规则的优化

用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

$ q& w" B( ~  K. _(2)网络权系数的优化

5 W' N6 a! w7 \( O用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
0 I0 t0 j( l! ~, L
2．遗传算法在网络设计中的应用

' m9 [. F1 ]0 s; e% K) Z用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
( U8 T: `" C; J2 i0 ?* M6 d
(1)直接编码法
( ]/ M" f/ Y0 L
! z8 I, f+ |5 Q  m7 H这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
, ^# Z6 c4 C; Y
(2)参数化编码法

" i6 t9 L( I4 `7 A7 |6 [参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
2 }! d3 Y2 B" a4 F8 i
(3)繁衍生长法
/ ]! E' z& W3 d0 p+ r
& q- W; O/ c7 o7 x! C这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。

. \8 Y+ Q) o4 D/ v  s% W, [3．遗传算法在网络分析中的应用
2 a% x& R) k% M( g
' o# H& o! k0 @! r: d遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

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

& {  y, u& @2 r三、遗传算法的步骤和意义
3 {2 t; h2 K3 f! Y# {* S
1．初始化
- I: X# q: ?6 i$ r6 H' g, z! p, B
0 `3 ], o/ h0 U0 z: y选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
/ _: k/ X+ i9 @$ D) b
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

5 q6 k! x: W( B3 V% j' B2．选择
" g( N, m5 W$ n; f) W, l
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

! m/ _: h6 ^* C$ I2 R; p2 [给出目标函数f，则f(bi)称为个体bi的适应度。以
6 b+ k0 D$ t) r$ {- ^; H
5 @+ Q2 X/ h* [: A+ }
7 Y8 V3 o) M6 X) v! x
为选中bi为下一代个体的次数。

$ c# r% {% [) e' X/ c! S显然．从式(3—86)可知：

. \# ]% G$ Y# Z(1)适应度较高的个体，繁殖下一代的数目较多。
/ @* C. ]& J7 ~" g
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
2 m1 h1 M4 c6 Z; N" H1 {6 R
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
/ S- T4 P5 A( t9 V5 ]& y4 t
例如有个体

0 `' A+ {1 i4 V) v/ Q4 PS1=100101

S2=010111

选择它们的左边3位进行交叉操作，则有

) H# x3 a6 ]8 T8 k0 C5 v& qS1=010101

0 P5 g1 g% Y1 \; i, E: IS2=100111

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

8 @. |+ Y; }+ t+ i& ?7 B6 [4．变异
. v5 y* Z- L1 d4 j1 h  |
4 r9 @6 |8 c6 u- T7 O# p8 N根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
1 {& W4 P" t5 b
例如有个体S＝101011。
$ N0 S/ p  t3 m$ P3 k1 G9 X
对其的第1，4位置的基因进行变异，则有
/ F  ?0 w1 b- y4 ?, |' `% {
9 g5 e# W/ p' i& ]& iS'=001111
+ Z0 t2 r; Q% w/ ^
7 \; o8 \; `+ l; |4 C  n6 f5 r单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
, F( D* J( k5 l7 z8 e
( t' x1 i6 D4 X) _# f5．全局最优收敛(Convergence to the global optimum)

3 g5 n; H7 l( P# h" G3 m( w当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。

图3—7中表示了遗传算法的执行过程。
& A; Q, m4 q* y4 C8 K+ O1 c* D( t
& U4 U# m: D  a+ w4 P
5 W5 F/ T% S! ]" I% j  m5 g6 R$ _" G8 Y# R

图3-7 遗传算法原理

3．2．3遗传算法的应用
& e5 c) V6 v8 V% m1 |
遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
, a# ^6 E9 Z. q9 g
  `' ?5 A; W3 f一、遗传算法的特点

4 l+ N% P1 ^+ a: e0 ^9 \2 M1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
+ Q; z" M0 e8 C# y
9 [5 L  q9 o$ o这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
. q4 m1 Y  K; w( }3 K# {3 z# q
7 Z4 B4 u  b1 h5 U由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

7 G5 P8 N+ y4 L4 D! r2 M# U, T  ?3．遗传算法有极强的容错能力
9 T! Y  [2 U( |
3 [# ^. }# Y8 H' Z" b遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
& m' f& u. N3 D
4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
- H- j( ?( R2 g+ ]- }
4 y$ m  b4 K' O/ R+ U/ ~! s这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

5．遗传算法具有隐含的并行性
% S. `/ j+ E" t: d
$ C5 I; e; b* g' R( e( o遗传算法的基础理论是图式定理。它的有关内容如下：
% [/ n/ L$ z& S( N& k/ T
(1)图式(Schema)概念

5 L9 F3 |4 ^/ }+ {* A/ C2 C* P一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
: i# r1 t7 ^3 d4 B+ R. p# a( l
. Y& I. q  i0 f0 Q  [; }/ c# ~; o/ j(2)图式的阶和长度
9 N  \; ^  w: y6 I* R
图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。

(3)Holland图式定理

: g, b, Q7 D9 k9 L0 e9 T6 \4 p低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

9 L( e& _" }6 D) M1 ~( ~  a遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

8 P& u; X  M4 N: G8 d* h  L二、遗传算法的应用关键
- X8 ~$ ]; z" Z
遗传算法在应用中最关键的问题有如下3个
* ~, _7 }+ `) k- G- X% i4 G4 R
* \$ \& B! z; f9 S# w1．串的编码方式
) Y. k, R5 H5 p& I
这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
# Y$ c0 g- d$ V- |, ]3 V
2．适应函数的确定

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

3．遗传算法自身参数设定
% ?5 T0 ~$ P& u) O! i: a3 _
  V, e6 r; v+ l2 x) }- w" K遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

' G% P  E& u  n( a! Y群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
. x9 T4 _  m7 o2 k" j+ W- Q
2 ~3 b! P7 @; G( Z) y, `三、遗传算法在神经网络中的应用

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

  ^2 O% a( {  ]+ [2 t1．遗传算法在网络学习中的应用
& i5 P7 A6 L" y3 l6 \
在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
5 ?9 ]* ~! S3 `$ s! s! y
(1)学习规则的优化
) _7 ^. T9 ]! F1 P4 M
+ Z& D1 Z9 b5 [1 ]9 X$ I! K用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

4 u  s) e. p" [# H7 F1 H(2)网络权系数的优化
" j# \9 R; K4 [! ?% [5 Y9 @% f" e
用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

2．遗传算法在网络设计中的应用

用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：

  B* `- }2 M0 }4 s" |/ D(1)直接编码法

8 w7 k" `. z* y! W8 }# m这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

% E- Q" o) b4 R6 g$ G(2)参数化编码法

7 t. L! b) t- c1 v参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
  l  J* P5 l2 A( g0 e0 n# I
(3)繁衍生长法
; n# Z1 I" |- q4 d+ Q# h
0 }" _- Q2 ~1 m; d这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
1 ]# g7 z. ^% H* G- ]' m
3．遗传算法在网络分析中的应用

遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

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

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。