转（遗传算法）

guofuzi111

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

4 [; `, u! f+ h  [1 Z3．2．1 遗传算法的基本概念
' Z3 G. f9 a/ G8 u0 N% v5 A
# D+ d; y' Z/ K1 a遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

+ H/ y6 f( q; M- G, ~4 L+ cDarwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。
  L, d' ?8 n* V6 ?
Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
% ^' n, O8 `1 T. s" q
0 f& }9 t' S( c; Y' E! v8 Y6 Y% ~1 K由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：

一、串(String)

它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。
' H6 @3 @2 h3 w1 q! B. q
二、群体(Population)

个体的集合称为群体，串是群体的元素
! ~' a7 @# H7 f. E! c% h, O
三、群体大小(Population Size)
1 \8 f) B# q/ }/ u! i, R" `' _
! S2 z1 O9 \9 {0 m( w5 _4 l$ X在群体中个体的数量称为群体的大小。
  Y: B$ T7 z$ ]2 O! N/ I
四、基因(Gene)
9 r( H9 b+ G9 n4 G
6 x$ V# }; P( D, d7 d基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
0 y1 |, q7 T: e+ _0 ~1 x5 I
$ ?9 R& s% _; D五 、基因位置(Gene Position)

+ P$ j$ N2 s2 ~" S- I一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
- F6 B. p8 q' m; a! c' G
4 @) X, c; L. a! b六、基因特征值(Gene Feature)

2 P* r: @. b+ s% M& w在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

七、串结构空间SS
) l4 G2 I- x0 N2 D3 T+ S2 J
在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

八、参数空间SP

这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。
8 z& f7 E. R5 M* y+ d9 ~6 S
7 z" _6 {* \& l* [九、非线性
4 o4 R# q9 W  H" \
它对应遗传学中的异位显性(Epistasis)

2 k/ L$ S, B3 u+ j* Y* h十、适应度(Fitness)

表示某一个体对于环境的适应程度。

% a1 T# Z, a' u- x遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。

, G  P0 t( _9 |3 [, ~3．2．2遗传算法的原理
; V7 P" P2 L' R+ l; H+ F  z
遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
& r  `! T6 W1 Q0 s; x2 ?
$ v5 c8 M) U- [; U/ q一、遗传算法的目的

% C- x8 _8 Z; X- w- a% i, c典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：

7 P  y) i+ T1 Z4 `, a) l2 s考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

bi∈{0,1}L        (3-84)

0 s) n: L2 \: E& Q给定目标函数f，有f(bi)，并且

3 ~/ B9 P: D! q0 ?# S, A0<F(BI)<∞< P>
! @- L3 \: h3 ^4 ^3 @4 y8 D
同时

f(bi)≠f(bi+1)
; b0 f! e* l8 C' I
+ D" e( b) n# }1 y$ Y" h求满足下式

, B- ?0 U- A9 t& ~max{f(bi)|bi∈{0,1}L}
+ g0 r. E; R8 B! K
的bi。

很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。

二、遗传算法的基本原理

长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
  c8 x+ v: T" V3 B
' y6 U& n, u+ {+ n' j. ^1．选择(Selection)
( J0 m5 h3 I, R* J) L7 V9 _
7 z, Q( E$ w4 o1 I这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
7 ^3 j2 U' p: }) U( E
* z. L) t4 [% d) z6 R2．交叉(Crossover)

这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
9 j/ z) W* X5 b4 w5 t/ E
  T) x  |& x" I) y; {3．变异(Mutation)
6 z- c: D& \3 \3 a
. L: A3 @) Z( ?9 Z; \5 _这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
2 M& d* d5 ]  O3 y* _$ b
遗传算法的原理可以简要给出如下：

- O1 U3 l' i4 U! Zchoose an intial population
* P3 w2 i! M  P. @1 r, H7 E
4 |6 K- s- A5 O: C, gdetermine the fitness of each individual

$ d9 k! x6 K$ ~: ]2 Nperform selection
$ b! G$ t+ X( C0 t+ P) j  Z% N
repeat

    perform crossover
$ s& |& {! j/ u. P
    perform mutation

& J& C8 o$ G3 R3 Y4 a8 n    determine the fitness of each individual

" z  I& Q6 C1 Y! b' b    perform selection
$ i3 M# P1 T1 g/ P- U
until some stopping criterion applies

4 A* \1 Z9 C+ }+ w3 W这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
& L- j" ?! C, \+ F% `1 f三、遗传算法的步骤和意义
. ^; ~. ^" [4 R
1．初始化
# t: {4 N! Z- Y$ ~
选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
1 R1 X5 t& \# Y$ a( {# h" [
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

9 E  p% W4 F; F: k  q; o6 ^2．选择
# n5 {& w7 v& Y' j3 R! |
  k* c8 a; t7 S1 V" B* `根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

给出目标函数f，则f(bi)称为个体bi的适应度。以
. `. O4 q1 U% m. J% B


4 ^* |9 j! _, c为选中bi为下一代个体的次数。
" ?' _& N! A% K
7 s, W, J. W# ~% n: C4 D显然．从式(3—86)可知：
( u# W5 q) h: q, q
(1)适应度较高的个体，繁殖下一代的数目较多。
3 v: `# ]$ x. M) E
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

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

' E9 U3 J$ i8 Z/ Q% G: Z0 b* ^' f3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
; W. q  y: M& s" B
' O- n5 j3 K/ _6 y2 \$ @( A; p例如有个体
; [% m: G& m6 s
5 r: W, ~. C5 ^  ?S1=100101
! c( O' M& o4 R7 C- x) x8 E9 ^
S2=010111

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

$ S. {$ G0 V$ _1 x- E6 j( VS1=010101

S2=100111

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

4．变异
( B6 j; w7 P0 V1 P1 N% u( C
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
1 S/ u& t* R3 }* e. q) d
+ Y- ]$ m/ I4 Y2 T  b例如有个体S＝101011。

对其的第1，4位置的基因进行变异，则有
3 h' m& n8 }+ I( Y1 Q
+ J( e- v& r9 D& ]' Z$ F( CS'=001111

单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
. O3 B2 K$ B( i$ ~  O
5．全局最优收敛(Convergence to the global optimum)
4 q; L1 C, \2 d5 g
$ k: l6 H- l0 Y  D  K当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
! j! j: t6 J/ g- _
图3—7中表示了遗传算法的执行过程。
5 x0 m0 {- h8 g
; c6 r9 k+ o! M
# v* C0 p+ A* p, {# q! O

4 `4 d8 z5 K" \2 ^' ^图3-7 遗传算法原理
" `2 F/ t& Z7 l$ Y: M% Z7 C
3．2．3遗传算法的应用

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
# V8 K5 L* H& n' {0 I
一、遗传算法的特点
; q& m* U& ]# I2 X3 u( e
- R1 Y! C% N: k1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
  d1 v2 K- ?1 r% B
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
8 I9 {" b( {6 G) ^5 b
7 S: d* ?+ @1 e( U/ a, _! e  s由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

3．遗传算法有极强的容错能力
0 R$ ~0 K' Y4 h8 z7 D
* E; R# l3 b, r+ _遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
, \9 U7 W* j* e
4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

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

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

遗传算法的基础理论是图式定理。它的有关内容如下：

1 W& V7 M) G4 i# z  v$ V(1)图式(Schema)概念

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

(2)图式的阶和长度

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

(3)Holland图式定理
9 c8 l  C# k  b* x/ i2 @
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
" V, @: R/ n1 C  q8 c
# ~2 Y1 M- K, n5 Y* w; U遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
1 C5 e- ~/ w4 P) j1 U, u1 a
二、遗传算法的应用关键

4 g( W5 \. g0 s: j6 w遗传算法在应用中最关键的问题有如下3个
8 F1 o6 }* p8 a4 e
0 G& P( x8 J; r- V& G: X# \  y1．串的编码方式
: P. c/ X3 A/ m& D- g8 M$ H
" x8 K# U5 o5 }这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

2．适应函数的确定
4 e. T- l* n/ Z. _' _" J9 Q- ]
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

3．遗传算法自身参数设定
2 u& o9 Z6 C% c6 {4 }5 i1 O! o5 V3 o1 y: b
遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
2 E+ P- y! J/ x; T! X6 |; l: P) L
) I1 _$ [) j; M群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。

三、遗传算法在神经网络中的应用

遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
, N7 _; H+ f5 [4 E0 a5 z3 i
1 }0 |. X8 k- R1．遗传算法在网络学习中的应用

. l) G! d2 _" k6 i: t在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

2 o& o/ K# {$ h  C; m(1)学习规则的优化
+ y0 n  F7 `/ Y. N  y! C
用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
" _, M) `# G# n! B7 Y; N/ @! C
: F- N- o- o  L  a# j( Y4 c(2)网络权系数的优化
/ `6 ~" t& `# A& \" C
5 X! \3 g- J( _+ x用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
9 l( C; r3 Y$ h% p' Y
2．遗传算法在网络设计中的应用

& v* m6 F: {  d4 R# [, q用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
" }3 O! g! M7 k- K9 E
(1)直接编码法
  J% m- Q9 b( z: ]* D- P, u
这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

4 Y' s5 `6 L: S(2)参数化编码法
5 b0 o* g0 |) s; Q; z
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

. z: R* W$ B( `' K5 ]" l(3)繁衍生长法

这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
" S% s% R  T1 H# Y$ M2 n& h" v/ b6 h: t
3．遗传算法在网络分析中的应用

  D1 @0 l8 i) g遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
6 m& B0 \. |7 @+ A- ]
3 o0 e9 v1 m: l, ~# a4 S遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
1 H& ~- f7 c: g4 l% v8 S. \% ]

三、遗传算法的步骤和意义
3 b) K& H# h$ _  g- |" P
9 g6 }, u) q2 y. `/ W% h1 V1．初始化
$ A& t2 p8 e, `; K
选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
  f& {4 Y  O2 i0 P# l. ~- M+ Q
* m0 e! N4 t! x- t  @( o9 o4 U通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
5 Y8 j8 S9 C) K. P/ R0 R
2．选择
8 e  V$ G+ w6 `+ S5 {
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

  B& {# ?; [$ J1 \3 m( w% ?- X给出目标函数f，则f(bi)称为个体bi的适应度。以

& x* g, q! O1 C$ S
, A  ~6 I& g# B* h- p3 t
4 L' r. o9 H5 j- X3 M0 q) t# g为选中bi为下一代个体的次数。

' ]7 L" m; h* \0 F, B5 M! L显然．从式(3—86)可知：

(1)适应度较高的个体，繁殖下一代的数目较多。
! Q' Y' J0 q! N, ^0 s! E
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
+ _" z! o7 R1 v
" u0 Y& n$ B9 R$ ?) ~$ j, L这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

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

例如有个体

S1=100101

S2=010111

$ i: K) y! H# t. I选择它们的左边3位进行交叉操作，则有

9 T5 r; N) c* [S1=010101
: @9 e# X) o3 W7 s; N  t+ [, B* l- L- B
S2=100111
; Y" c2 U; t& C2 k$ w5 p( h  x& h: z
一般而言，交 婊显譖。取值为0.25—0.75。
( z9 R# \. Q8 t. n" P
3 D, E: |& E% q4 O3 e4．变异
; j' E2 E2 f5 @  @. v& ^
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
5 x" ]7 ^, D1 Z' k* \% |3 ]5 H5 _
例如有个体S＝101011。
; _- R7 H) ^$ f: B2 B: q
对其的第1，4位置的基因进行变异，则有
' L9 @4 _' J' J
S'=001111
, W* V' T. @" O$ w' |  O" P/ P8 _
/ X3 `1 n& d+ d  R0 K4 Q8 }单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

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

& h- O  T3 f3 T当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
0 Y. a. h: @7 j1 _' y3 \
图3—7中表示了遗传算法的执行过程。

/ H8 ]. a  G- a  D' B

# ~! j* [+ h8 m" Q
图3-7 遗传算法原理

( X2 v9 J, f* R* U1 _. ~: l- c3．2．3遗传算法的应用

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

( g& u6 m* N' l: C1 L( o! C4 S一、遗传算法的特点
* i/ }& P! M; E$ I1 x8 U9 P: j
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
: T0 Y& V" E% u2 @9 u; j
, R/ }' c; L( ^8 i8 u这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
4 c+ E  w" I8 t# t3 P" T" R& a
2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

; D/ |2 R7 \: }. ~. j! b由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

3．遗传算法有极强的容错能力
) ]8 ?3 ?% R5 K6 R' y
9 V! D& R1 K" e- e遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
  n! a( v  _1 ^
  L* R6 H; k1 n6 k, F这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

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

遗传算法的基础理论是图式定理。它的有关内容如下：

(1)图式(Schema)概念

4 K' I2 w4 O" e1 L, \一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

' {$ j3 p2 F  Y6 P/ D' V( n(2)图式的阶和长度

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

(3)Holland图式定理

低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
5 l! ^% [: w5 p1 ~0 W
5 s* D) Y7 w% u5 V遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

- x; s5 q: O7 x: f3 u2 E# @二、遗传算法的应用关键

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

# J3 X9 _3 c+ ?& [7 T* n1．串的编码方式

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

4 C) d- r0 q; q* k# m+ B2．适应函数的确定
1 l4 q0 x  b0 q" t( p) Q- ?( N
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
3 A8 d& W7 }4 d1 b6 L3 B
3．遗传算法自身参数设定

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

群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
1 ^( G+ P! @3 {6 E0 \$ z9 N$ ]( s
三、遗传算法在神经网络中的应用
2 J8 l' \6 f6 Z; p7 b* {7 C1 r/ T
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
0 J! J5 \- `  F: o5 Q" x  ]
1．遗传算法在网络学习中的应用

# ~& l8 Z" q* t在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
7 \& H; W, B- G
1 T5 R& g& D( k+ x, g1 ~1 t6 l(1)学习规则的优化
8 s/ i; A- p; x
9 L; Q. _& `5 W: M! w7 q' g5 Q/ `用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

(2)网络权系数的优化
4 a) h5 r4 {3 T! b
用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

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

+ V) d# E" ?* I0 v/ a. D4 p用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
, q  W; _) d! b/ x. Z  |
(1)直接编码法
: A5 |) k5 W8 R& N
这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

(2)参数化编码法
( F+ w5 C& q& M8 R1 C4 A+ I
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
) v6 q8 B- Z; P; u
/ K' _' s4 O# B2 j+ x) N(3)繁衍生长法

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

2 p/ i& Y) Q" a: k3．遗传算法在网络分析中的应用
* b4 Q' z" S  t& Q2 D( s8 ]
$ H% S5 y2 M. C3 |遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
8 O8 t4 n7 D+ a: `7 N$ C
( L7 T* a7 R: A# `) H2 l2 h遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
  h" \' t& \$ P3 G5 E4 f

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。