转（遗传算法）

guofuzi111

生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
( |' y& N7 I0 L+ p
1 v! j3 X( M( Y7 u% N6 }5 m遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。

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

3．2．1 遗传算法的基本概念
: Z& W$ [, F" `1 {/ L/ e
遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

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

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

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：
# i' D3 i/ `- a* O: {3 b3 C* B
7 O( Y# w+ p- d1 j0 O+ }8 g7 E一、串(String)
' O4 x4 p/ h) p9 i
它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

5 W) q- C: l# ^2 ?% u8 o& y; q二、群体(Population)

$ E6 c' T9 D" Z; {1 l, q个体的集合称为群体，串是群体的元素

三、群体大小(Population Size)
1 f2 P4 `( U1 R( o6 v
' s. ]+ b) X# M0 b) b6 Z$ L在群体中个体的数量称为群体的大小。

四、基因(Gene)
' M% P9 Q9 e6 q/ e/ s+ l
) G) H8 p1 S& [基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
! j! H  {4 V% c3 B
8 _% w( o: h3 g$ j  x: P- s; l( J五 、基因位置(Gene Position)
" G5 J" ^+ f- D& e! b: h
一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。

* [" I4 C" u0 z+ \六、基因特征值(Gene Feature)
. u' |% v9 }7 G  P
在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

七、串结构空间SS
8 |, S! o% T) q6 f' U& M
/ m: n2 @9 e& d) A  q) x在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。
4 D. o* c) c& D: r0 v
: m3 ?5 ~7 r2 r/ Z/ }5 W! K八、参数空间SP
; V% c' p2 y$ Y' o* {2 |( g
+ b2 N* ~- d5 u  a5 e- G$ m这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。

7 o1 K4 j+ c+ N9 T& }& n九、非线性
$ k/ |. N! b0 l7 z) c" U
& x7 K, j' y6 ]2 L+ C8 P7 S. m它对应遗传学中的异位显性(Epistasis)
# ]9 m0 v% l/ @' [8 A
. @( E7 Y5 F/ i; r2 @0 |十、适应度(Fitness)
! B+ G# ^8 P3 m6 t( Q1 m6 Y: s
9 s- O: `2 }+ [/ D( d表示某一个体对于环境的适应程度。
" ?: X  w$ X  Y9 ~0 T* O" l
遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
1 o* u, k. i) M& g) Z# A: t, g. P
/ |+ d+ S# i; S  W3．2．2遗传算法的原理

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
) z9 F: W$ a* J- Z
: u4 Q. R1 o% V" |; A' U一、遗传算法的目的
. D3 i/ [) d( x# H2 p' o' @( I
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：

3 [2 @+ t  ]( V: j" E; C考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

bi∈{0,1}L        (3-84)
- d5 Q' a% d$ C0 y6 ]2 }
给定目标函数f，有f(bi)，并且
+ H1 m3 o0 {) q2 M" [
/ A. B5 R) b6 M+ R0<F(BI)<∞< P>

同时

f(bi)≠f(bi+1)
" ?- |' [; G: @; r( {- S" S9 W. R
求满足下式
" v+ }; k+ a8 ]! t1 m6 d
8 N" M* J1 Y9 W4 O+ ~max{f(bi)|bi∈{0,1}L}

的bi。
; \: O: s! A  y# s$ {6 R
1 ?6 l0 a5 x# z% P很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
* n& S; \" I2 M2 Y& D- w" _
二、遗传算法的基本原理

1 B5 a) k0 U9 J. E7 k: `' p长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
3 p3 T0 r9 B$ f8 K3 q
1．选择(Selection)

这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。

6 [2 I  t% W, s( G8 L2．交叉(Crossover)
, Q, n0 L: {& U
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
. G: `, x( _$ P6 {
3．变异(Mutation)
' q- B' x1 A8 K6 c% n8 C
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
- E2 A; l- [+ Y. n, ?1 I
. S  j( I+ p1 R7 T  u2 l# A/ x: p3 z+ m遗传算法的原理可以简要给出如下：

choose an intial population
/ r+ l0 w, m5 H5 ?. d6 {! I
determine the fitness of each individual

: B* T% c( S! rperform selection
3 p: p1 L4 h+ H, \! R- J; d
repeat

    perform crossover
: }9 G& F( L! i+ \6 p( M+ f
2 v. O# [- P% R    perform mutation

0 p2 h, k8 _6 ^0 \. Y, V+ C- H    determine the fitness of each individual

  J! H7 C! O: T  o9 \. ^    perform selection

; W( ~2 _: H0 `5 v0 Q0 U+ T" Guntil some stopping criterion applies
% {/ _5 ~$ b, Z; E, @, |
这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
三、遗传算法的步骤和意义
: J+ b, p. X8 S. I
1．初始化

% {: G6 k  ~& Q" Z选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
7 L0 U8 `# M$ t
( N+ Z0 \( _, `% l+ F通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
7 r" _! E4 ?0 C" M4 X
2．选择
) k& W5 O6 P& c: s
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
0 F& X# H1 a5 J2 h2 f# a3 A
给出目标函数f，则f(bi)称为个体bi的适应度。以


* I- b5 Z4 @. ^
为选中bi为下一代个体的次数。
8 n, i% t7 k5 O$ U) M- Y% H
显然．从式(3—86)可知：
! ?# G5 J# \- `6 s. g' g
* z% r3 @5 {$ e0 g$ l* @" c(1)适应度较高的个体，繁殖下一代的数目较多。

(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
% l3 I4 }3 a2 G8 N% U5 r
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

0 e3 q1 w* F  k  X. T3．交叉
" q: y2 V1 f5 y; b7 B. T* j$ X对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
( u3 r- y3 `! Z
( N  {0 I( W, j: f% x- h4 W9 H. d例如有个体

S1=100101
4 u' Y0 I: |- N$ p! D
3 @9 ]& S( r0 V. yS2=010111

! M3 C/ e$ L5 Y& X5 F( P选择它们的左边3位进行交叉操作，则有

S1=010101

- Q- v7 c9 _4 l& l0 iS2=100111
+ k) k+ S- l% Q  {3 Q: R  |. F& ]( E
9 S: U  p. x: r1 G一般而言，交 婊显譖。取值为0.25—0.75。
& ^) E. C7 H( F3 `4 v
4．变异
: W" R9 P, U7 Q
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
0 j9 p( c8 W# [5 [
例如有个体S＝101011。
/ l: k7 a3 w4 t' H
对其的第1，4位置的基因进行变异，则有

. F# {! O& Z6 q2 z( g/ M# Z- d9 R  bS'=001111
' y7 J, h. T8 R$ A" @; R
6 l+ q* o- ~2 e+ T0 L单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

4 T/ R& m3 w/ q( s) [5．全局最优收敛(Convergence to the global optimum)
! I2 _3 I. R: c# g' x  A* U
& Z0 x; [7 S+ G$ K# _% b" j当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
7 S3 n/ A: W" I" D8 e  f: z
图3—7中表示了遗传算法的执行过程。

$ B5 |0 c( t) _  z; v9 W4 W


图3-7 遗传算法原理
& o6 S4 x; T( G: K! a
- h& Z5 x7 K, @! L+ `# }3．2．3遗传算法的应用
- _! y* f- L5 K9 d0 B! M& B
4 X& B* K" F4 ?3 R/ J2 Y& f+ t% }遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

: H6 p8 X) c+ J; J4 [一、遗传算法的特点
  F% A' D4 ]' ]0 n( ]) X0 c
( Z/ W) M; K* X/ S1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

6 |0 n7 R3 R- Z4 z. _这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

  @0 |5 F: x9 K  e1 I2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

: N7 u$ O- K6 u' F6 Z# a' n由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

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

9 ?, A; m! O5 l$ z: g4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

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

& O) O# D" T: F6 u5．遗传算法具有隐含的并行性
0 Q2 H! j* X' d
遗传算法的基础理论是图式定理。它的有关内容如下：
4 X0 W2 E* t" C2 b3 |  c
(1)图式(Schema)概念
, L( F4 b, s2 N# Z& @+ Z9 E
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

. ]: b4 h" v. c. w7 S% s2 \+ O(2)图式的阶和长度
. o. Z" p( a7 U4 h7 i
图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
3 n( R2 }: e4 ~! n1 x" A
(3)Holland图式定理
8 N' _- O" \- u4 T  s& L& F
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

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

二、遗传算法的应用关键
- G* k3 Q% P' a3 V
8 H. `2 F% f; s+ v遗传算法在应用中最关键的问题有如下3个

+ ^8 w3 f. p0 E0 {; r1．串的编码方式
6 g/ M$ A# W7 i7 U" r. j, T
9 u, \* H) o" O6 K8 N" P, X这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
- F& e% q* {2 {& p5 t9 M  l, A; S
3 C5 {$ N/ @# ~; S3 J+ @2．适应函数的确定
# o7 J# X) I. f. p
* k) h# g4 Q9 g, w0 C5 L% a适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

5 G# _% w, G  f# d0 v3 E3 o3．遗传算法自身参数设定

遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
% z+ U) S3 [! l1 I$ S+ `  V
群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。

; i3 H) g1 E! u三、遗传算法在神经网络中的应用
" S3 E4 }6 T* i
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

; [4 @% e" E& u, J1 L+ k1．遗传算法在网络学习中的应用

在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

(1)学习规则的优化

% i0 e$ s1 z( C; T3 U1 a$ E) z# F" g用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
7 Y9 N4 G+ M* ]/ Z7 _
. |, Y: P7 _3 Z% Z(2)网络权系数的优化

; X; J" U% G8 A1 Z用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
5 T2 |: X+ _8 T* R3 x' ]$ R
2．遗传算法在网络设计中的应用
) K6 d" _: }. O4 k6 x; s
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
' T6 ~6 l; M! Q( v9 y
(1)直接编码法
7 W1 k% H& |6 _3 |, B
  o. X/ x6 t0 \7 z3 J" Z- I这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
6 A! u, k0 ]+ d' L/ Q
- A/ a) w4 r: Z+ s7 H5 d: \' H(2)参数化编码法

) M3 p, J% g: E1 @% Q; X% y参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法
! R$ g- b& D; ^# T/ x9 M, K# ?
0 p& P/ c9 m1 t- s, B这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。

3．遗传算法在网络分析中的应用
% Z$ H" ]6 q( c# T! S6 A! H' f
2 l: h8 n) L3 N) O1 U9 t0 b) ^; D4 V9 m遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
( ?& |' ^# C; b: |* d
; R( y* R' e# ~# c& P遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。

9 h' ^" N& N. x9 ?" }& B" K$ k% e三、遗传算法的步骤和意义
( o% y6 Z# @7 R+ |# M
' {9 l& v4 H; x6 ~1．初始化

8 I. G: |  J& X% @选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
* }9 `5 L, Y) ?0 `' U" U. o! V
" r( I& d% ^$ t; g通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

& f* G6 g; s& Y% I% _; ?2．选择
& P0 G2 |% \. r( L. H: @
/ @* G- H/ T3 Z, w+ b  {9 k根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

  ^4 U' C; C' ]8 i; n给出目标函数f，则f(bi)称为个体bi的适应度。以


- W- o' x- A0 W9 Y/ k4 d
为选中bi为下一代个体的次数。

- D( P, U- q0 [2 s* H  b4 M显然．从式(3—86)可知：
4 v+ `! y5 H1 ~: ]! M
/ V6 @0 X% @1 r3 ~: @! `(1)适应度较高的个体，繁殖下一代的数目较多。
, [4 k- |* }3 n" \' A
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
% W; g, J, j3 }7 D+ @! f& e( t# }
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
) s) F1 \2 E. c. ]5 T+ w) D
! o" H- H7 z0 v3．交叉
: t* Z4 r2 k: }9 Y3 m, d# q对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
/ Q& R1 [) S; p$ p0 d
- _/ F: V* ^5 U% _& [) q+ ^0 }2 v. W例如有个体

/ ?  \3 d2 G5 P- \# |: LS1=100101

S2=010111

) i- R: j7 e3 |, c选择它们的左边3位进行交叉操作，则有

S1=010101
/ {! @9 ?- \" }
S2=100111
) D2 i9 F* [: x0 y" y
1 {+ Y! D9 f2 h( H* D" P" p. D6 k一般而言，交 婊显譖。取值为0.25—0.75。
. z% U9 p- Z' K" O# G% s/ ^& t
, R- [0 G" R2 i# {/ g4．变异
) I6 W& k( }) C( z1 b: c
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
* g8 C" M7 [9 t
- @5 L  O  E! I0 r5 g6 Q( P例如有个体S＝101011。

对其的第1，4位置的基因进行变异，则有
5 M6 j# u: ~+ Q
S'=001111

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

. `9 W7 c! F/ S' l& A5．全局最优收敛(Convergence to the global optimum)

当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
* f7 P  f0 s2 f* g: H
% ~& y( e& z7 O2 M图3—7中表示了遗传算法的执行过程。
9 x* X; |4 b& d  Q6 T% V* j- V' o& r  ^

" B. p, s  Q# u
  A  y; ~! ]# Z+ p, x5 b
0 L. _: k- o& x% O! g( O) l* q图3-7 遗传算法原理
' j" w. {, Y; V& ]: _
. ~2 o$ C  D0 G! J: c3．2．3遗传算法的应用

- ^1 `1 H5 b7 W. b% o6 b$ ]* H遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
( N. A) s9 d* J. B
( M& x% {3 Z* v% p1 C! P; s. b  t一、遗传算法的特点
  X9 K8 P: w8 d, u: i
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

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

5 f% f0 m* p! J' k2 f+ z9 M2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

1 [  ?/ t' N9 W9 [$ \; T由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

( C) r2 x3 z) `; {2 a9 P3．遗传算法有极强的容错能力
+ y' K1 h' u, y5 Q, F
遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
' T) o0 Y; Z8 N( u# c- w" l
% Z. p% s* e. E1 @4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
( B8 q; E" c: C, B
5．遗传算法具有隐含的并行性

" n- p6 y- U7 `; P0 S遗传算法的基础理论是图式定理。它的有关内容如下：

8 z5 u6 O% g; F6 F(1)图式(Schema)概念

一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
5 R* y0 X2 T6 j, f
(2)图式的阶和长度
: M, P: R1 X  D) j7 N) k$ u5 ^9 L
图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
( V: R! L3 T2 i" {& i# b
; }; E# t& o& E' F(3)Holland图式定理
0 f! D; V0 @$ J/ p
6 j9 \3 q0 P8 f5 T; O) l7 d低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
. j  I, U5 |& T+ J) `" Y! n
遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

# {# W+ v* N( }+ k5 B; w二、遗传算法的应用关键
& n5 B2 _" V+ W# N& R
遗传算法在应用中最关键的问题有如下3个
" I# x8 ^: v" E, `6 t
) ]- h' Z, [; W9 v1．串的编码方式

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

. p5 n$ H4 ]" c0 E# L) }) j2．适应函数的确定

适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
& R1 O' N0 H  S# C
2 B7 `! u* C' `  i# z( K6 \: q% V' r! i3．遗传算法自身参数设定
! U' v8 X' J- g# W! i" V- h
遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
. j/ b/ Z) p) a8 D0 y' E# i
群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。

3 K3 h  B+ I# g* Y! C三、遗传算法在神经网络中的应用

遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
$ G  E3 \( U; ~& w* J1 e7 j
2 H' j, {+ ?( O  O( J1．遗传算法在网络学习中的应用
# W- \5 U% U* p$ Q* \; V
# z( ?# F* p8 L在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
3 ]' X) h, c, a# b- |8 A* L
- j% M' ?. h) r3 |7 f$ Q% Y# i0 |(1)学习规则的优化

用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
& q* c6 ^5 y" W% F
8 ^/ D+ J; w, {5 V/ q(2)网络权系数的优化

用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

" E( z0 R3 h0 p# J& D2．遗传算法在网络设计中的应用

用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
, Y6 E/ `7 D+ `# {9 n0 y
(1)直接编码法

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

(2)参数化编码法
) T% u2 y/ v' b4 q) k! V
. Y% x( c. a( t1 R0 _8 r6 n参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法
# O2 e" v9 [5 k9 D6 c
) q5 u- H5 M& T这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
* }3 x$ S- d% q
3．遗传算法在网络分析中的应用

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

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

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。