转（遗传算法）

guofuzi111

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

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

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

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

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

- M/ o: L* `& N: U0 Y8 w7 B, d; VDarwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。

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

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

一、串(String)
0 ?& d; k( T" f+ n' z- T
1 x/ N+ n0 q+ W. S% D: u. E4 @' ^它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。
6 ^1 q9 w$ V: E/ K  _8 a
: D* p; U& G' W2 G2 m二、群体(Population)

0 e" x( c4 f  L. D  r6 g个体的集合称为群体，串是群体的元素
' q7 q9 J9 o  _+ h$ c2 U, r$ U
0 R; ~! R* g/ Z! F- T; ?' |  Z三、群体大小(Population Size)
; b4 Y# e  q: Q! l7 P7 U3 K
9 b' k6 j1 D" f在群体中个体的数量称为群体的大小。

四、基因(Gene)
0 r% c% z. G9 h
( n$ v8 u6 Q8 b# ~, U基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
6 U+ \; |$ W) {/ |2 |0 W
5 C! ]  ]1 Y% o6 ?' Y/ a五 、基因位置(Gene Position)
5 c: y6 }2 `/ D' X8 l8 c, \8 Z; c
6 G0 x7 C! |3 ^5 @0 ~+ w$ x一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
8 J7 K1 x7 j: r+ R1 U5 i/ u2 k
/ }7 u1 p4 Q) `+ Z+ z) |$ a3 D六、基因特征值(Gene Feature)

. h1 p" F/ E  K$ [' S2 a; _在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

$ N% o& B# n# c七、串结构空间SS
* U* l' t: m' N, b
- U+ g) S) I. v; V& E# T; c: ~在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。
% q/ T  s( n* m
/ J* [2 ^! Z( z( }$ m八、参数空间SP

这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。
0 M1 j3 `1 W1 K8 }4 C1 Q
九、非线性

4 J2 n) Z4 y$ j  {, Y: ?( M它对应遗传学中的异位显性(Epistasis)

十、适应度(Fitness)

7 D, t3 R9 }$ ^* P; p+ N表示某一个体对于环境的适应程度。
" s; q7 \& d* D+ q2 Y4 l
遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
( v2 i9 R% J& v
3．2．2遗传算法的原理

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
0 L! Z: Z8 }# H/ x; z
! w1 @  w# P2 o5 Y8 P3 T. y+ F一、遗传算法的目的
& N9 p5 n' O2 @/ u
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
" j( V8 x' Z& ^8 {6 r6 `6 r, S2 @
考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

, N- P. e3 B* K; y2 Y+ B' X0 Zbi∈{0,1}L        (3-84)

% o% K7 k1 O3 T& E( F给定目标函数f，有f(bi)，并且
* {  v  {# [0 R) j; g
% X1 ^8 V3 k$ _: w# Q0<F(BI)<∞< P>
+ K) L' M% [$ E5 a
同时

f(bi)≠f(bi+1)
  c. X' R9 q; H( j
求满足下式

- d" @$ `/ Y4 z8 r' v2 ~max{f(bi)|bi∈{0,1}L}
  v) O7 [% t; T9 q! c
9 ?0 L3 h+ O* D# e3 f的bi。

很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
  r; P2 n) S1 o2 r& Y1 K
; Z+ X( C2 \$ g0 |1 m  o8 _二、遗传算法的基本原理

4 {7 M# _5 e  w- I' R; E6 z- u长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：

: k% c9 F( `$ C: o9 i1．选择(Selection)
+ x, J4 f+ W3 a  k7 z! [; M" p! A
  E% F# T+ O3 r$ j& b- b9 T这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。

7 R+ D% h- ^$ c* o; I$ A2．交叉(Crossover)

, C  K2 b7 w) e# X6 X" L( S( ^这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
6 v  X- ~, ~: W" s
3．变异(Mutation)
' M& B2 V% c$ Y/ ~4 u
8 _7 W' o8 ^5 X9 ?, v8 t这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。

遗传算法的原理可以简要给出如下：
  k4 }/ n& N% L- G9 ^- w
choose an intial population
6 u6 i5 ]+ C# r( h5 T
  N- r1 h$ s! X9 ^6 Fdetermine the fitness of each individual
  s+ s2 |  v( x+ @' f' h
5 M+ O. ~6 o9 e1 J1 b( q/ r& N4 k8 Hperform selection

0 A$ h2 [: n6 t! Z- a) Prepeat

    perform crossover

    perform mutation
7 E! K' @* [) W2 b' k: a/ U
    determine the fitness of each individual
+ F$ `% I( f+ A
( ^# k) U: c6 n$ j& k- U    perform selection

, t5 k% p% v( b2 X4 t$ O, Uuntil some stopping criterion applies
+ T  v6 Q* W# t" I4 U2 a
, j* M1 S+ L- g' X0 I% D这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
) b  Q& W/ ?6 ?, G9 L9 Q6 _三、遗传算法的步骤和意义

1 q3 V1 [( i: d% T( C' ^, u* p, P/ {9 A1．初始化

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

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

2．选择
3 y6 }+ n2 n& _! y4 Y
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

. `- y. m* C) |6 U* D给出目标函数f，则f(bi)称为个体bi的适应度。以
9 C6 ]3 X( L: L3 _# ?; F
- \" N) @0 L  o' y
+ T% W: b* V. k$ Z& x' f# i
为选中bi为下一代个体的次数。
# X+ W9 E. U! k3 ^9 x. b
显然．从式(3—86)可知：

6 d% N+ T- z9 |0 U(1)适应度较高的个体，繁殖下一代的数目较多。
0 m) }% ]4 U; S+ x& \9 g9 K7 E
% g9 j! k1 y8 ^6 }- J# Z6 z(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
. o1 d# {3 N- Y$ D# ]
8 ~' `) M1 p) v) T$ q这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

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

$ v8 e# W* h. m9 d3 ^8 [( x0 r例如有个体
6 R! n4 e5 `! s. A$ ~+ Q+ m
S1=100101
- j3 J" f" m" l4 W
S2=010111
; B+ ~" Q! K4 n2 r$ ^: P
2 K. F: A. A: k8 ]3 L  C& f! O选择它们的左边3位进行交叉操作，则有

% U. l7 i! N0 vS1=010101

S2=100111

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

! b1 N9 v7 X' ?, u( _/ f0 p4．变异

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

例如有个体S＝101011。
/ I% t) L& \" Y
4 x! J) t4 }1 r! O4 f. K对其的第1，4位置的基因进行变异，则有
7 W, d  Q  D" L
S'=001111

; N1 y+ E4 k/ U; t) z, ?, Q! j单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
" c2 P. }# E- u/ L8 `' }
, P" X* h; p6 z5．全局最优收敛(Convergence to the global optimum)

当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
* k& d% T+ X. h  z0 W
; |. ^# g; O7 G8 i. x4 F# w1 d& d图3—7中表示了遗传算法的执行过程。
  {8 y$ r+ ^+ S* j7 |3 v

, e# @2 a# ~& ]+ h, r8 B  S
! e. a9 Q" S, Z" ~) G0 c9 a
图3-7 遗传算法原理
9 \' `( V8 e7 b7 L* r# C3 k3 t
3．2．3遗传算法的应用
. Q' J# f5 R$ N/ A/ m6 ^
7 n7 ^- N5 X" |' M7 u+ G) Z: o遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

$ C" v' @6 H* [! l一、遗传算法的特点

1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
5 i4 c8 o+ Q! L$ D) m
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
3 Q7 \+ P+ i" \1 x0 {
2 c, V' C: v7 B% y( N2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
2 P2 k8 h, T, K2 b1 z, u
3．遗传算法有极强的容错能力

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

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

这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
9 V& K- \& z# p+ e9 T% f/ f, w
  e+ o8 c! j3 ?0 \5．遗传算法具有隐含的并行性
5 r8 H4 V' e  z- r1 V
遗传算法的基础理论是图式定理。它的有关内容如下：
8 E7 Y, e  m6 `% Q- U
(1)图式(Schema)概念

7 ]( M6 N: s# v  R  G% F1 s一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
$ k2 n- V' p/ }9 s; S# ]
/ a1 E, F8 n2 ~) ~" x& ?  ](2)图式的阶和长度

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

& ^: r* V$ z" p! R3 L% q6 \+ V7 b(3)Holland图式定理
$ y! ?% C+ r, s& z5 j
5 S4 m" n  A4 x# T' `1 M& v低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

" }+ K; w* d2 q- e遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

" X6 f# s& l: k# f二、遗传算法的应用关键

遗传算法在应用中最关键的问题有如下3个
. \; [. O2 U+ @" y3 H* d: L' `
1．串的编码方式
9 w  W9 X6 u# |6 W
  ]& `4 v* N3 V3 n7 `1 c0 D这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
1 g; h8 m" u$ _) C- d( M- p) m
) h- x8 `0 }8 @) Y8 V2．适应函数的确定
, M8 t6 P* k7 {- R; }) S# U+ ?
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
: l/ F; [5 d( O; n3 P
3．遗传算法自身参数设定

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

; M2 T- K- W; a) g三、遗传算法在神经网络中的应用
& t* q# |9 f+ q6 |4 R
" `& x9 W: m/ L遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
# t) w6 G' d( D. k- Z
1．遗传算法在网络学习中的应用

在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
" h+ k2 R7 c4 ~& L( `
7 A9 k  j5 v3 A& x; \5 ^. F; h(1)学习规则的优化
" F5 b" N( L8 M. @8 t( n/ u& i( o
% X# G' p2 e. f' I用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
- Q* q+ \# c! H: l) N) @
(2)网络权系数的优化
( d6 c4 j3 b1 T% D, m  l
& N! S3 [7 \+ J2 H8 \用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

$ n9 C% I* ^0 g4 \" I( ^" @2．遗传算法在网络设计中的应用
9 l1 G- O- N! Z& F9 Q( O
' ]4 i  `# x9 {用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
; J2 f+ g6 b+ Q0 E. E
7 p% q% A) k# {% M; g: ?' p(1)直接编码法
/ z& Y& a, }+ _0 s
2 q7 U( `" ~( _. N/ ]' V( ?% d" _这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
( F, G) C. A) X" o4 |
$ N! Y5 G( U. D" r7 G+ r" l3 P(2)参数化编码法
, K  P+ S3 @3 g4 X) d( M- `
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
, D; X; u; u5 [$ y/ q
% d+ Q  l$ g) ~" W5 T) [* W(3)繁衍生长法
) s' @$ I( [3 w, n4 z0 T
这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
5 R2 U/ r3 N3 T# _$ V
3．遗传算法在网络分析中的应用
% l4 A5 X+ P; \; a1 F
0 w& K* m+ V  W' J2 [遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

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

/ k' u5 f: ?% `+ K

- O% l. U( b9 }( i6 Q! s) y三、遗传算法的步骤和意义

  Q2 I$ A: p' b4 H( r8 P7 L1．初始化

选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
- q) H, C' z! }; a# ^
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

+ }+ B' m: j6 `. S2．选择
( Z, x) ~6 k: B1 }
& W+ ]! Y( m5 ^" ~6 C: w根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
5 b6 K  l  g0 T2 m! x2 P
给出目标函数f，则f(bi)称为个体bi的适应度。以



7 b( k1 ~4 I* K0 r7 \5 ?/ ~$ t为选中bi为下一代个体的次数。

, H; a& G+ `* v( |; `( H+ K8 c显然．从式(3—86)可知：
4 U  Y" e( M: |. i9 q* Q' j' L
(1)适应度较高的个体，繁殖下一代的数目较多。

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

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

3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
! f: \# ?' {" u/ C* T! j6 W
- {' X2 g0 |# x: {* L& A: P例如有个体

" w+ }- S! ?3 g+ e: m8 f: N+ x' ^S1=100101
  X  e: H& b% j( R) y" {
S2=010111

: D9 A. P" P6 v6 e/ R; J选择它们的左边3位进行交叉操作，则有
& Y& `+ C" f8 p! f  e0 V( W7 f2 W4 M
S1=010101

) z& c9 p! P% E: C' Y- l2 [( e, uS2=100111
: e- G3 F) b6 E0 Y% T5 S/ H9 z* ~
一般而言，交 婊显譖。取值为0.25—0.75。

# C" ]4 O7 [% S4．变异

0 ~; v4 X( \3 |# x1 g- f" i7 W根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

例如有个体S＝101011。
$ U7 S0 J& u. J8 q) a/ u
1 ^: q9 J1 K& Z对其的第1，4位置的基因进行变异，则有
) c( l$ J6 w; b' L  C$ D
1 V1 p7 }$ P/ r5 e5 }9 g! X- a+ s; pS'=001111
" A* }7 l' ^4 j" ~1 Q
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
7 W9 S: {1 R) d7 N  S
4 Z. I" E3 ^1 T3 c( p. N# |9 l: w- C5．全局最优收敛(Convergence to the global optimum)
) {1 G- \) l# I/ W5 H( q7 L
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
; D/ H) m- Q8 p
4 {0 r5 E9 N8 ]% L5 I7 h! e' O5 o$ @图3—7中表示了遗传算法的执行过程。


# O/ O) i7 u! I. R0 r
3 u, Z5 X- R, m' P8 M
  \9 m+ v5 a) v3 [8 U& Z" w; s9 t图3-7 遗传算法原理

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

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
+ U$ R/ ^, {# b( b
+ N2 a% z8 [; r2 D  l+ i3 _3 x一、遗传算法的特点

1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
( H. `' b8 x; @6 }/ U0 x$ s
0 N# j6 v0 n. }3 j8 U这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

6 a! F$ @3 W0 T6 G& s. d  n2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
" ~1 x. |$ x+ T# S
- ~! H6 E! @' ~7 n" R* X由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
7 W( _6 T  ^2 I1 p) a5 y
3．遗传算法有极强的容错能力
: @6 D& g0 x& j$ N" l  X+ E
. A6 _4 F3 q8 ?/ a遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

' T; u2 b5 n; x3 }* n4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
9 Z' g2 N( z" W! J- t
这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

/ g9 F( I: i, t7 _6 p0 r( R3 ^5．遗传算法具有隐含的并行性
7 P$ s! }" n; e( r0 S6 n3 p+ |
遗传算法的基础理论是图式定理。它的有关内容如下：

: s7 w, [+ E. t! z+ W4 D(1)图式(Schema)概念
! K7 V$ i' D  Y# d! q* R
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

(2)图式的阶和长度

图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
8 s; M0 f& F2 Z3 K' C) w
; k5 W+ @  t* N3 u(3)Holland图式定理

低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
- E. l5 ^; ~' c1 A3 R/ p
! C) \, t  Q% f! |) A# c- T遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
- g0 f2 W/ F7 c2 a& h1 A1 v; x8 r) n1 K
二、遗传算法的应用关键

4 `; Z9 V5 v$ R6 R  J& ~, ?遗传算法在应用中最关键的问题有如下3个
8 h0 D7 n% ~8 M6 X
1．串的编码方式
: M' X4 e5 D0 |: r6 u
这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

, c- i# B0 @6 D+ e1 C2．适应函数的确定

1 X  M7 Q; `& {$ T8 O! Y适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

3．遗传算法自身参数设定

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

/ f# o. ?1 ~7 _$ j! u% a" p" I三、遗传算法在神经网络中的应用
3 i- B5 X8 o4 @1 D* n
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

. p- S- b9 f" X/ ?/ e$ p3 O0 v3 @1．遗传算法在网络学习中的应用
, |2 K8 f% B/ x9 x
, ?3 e3 k  D* k: ~4 P9 N% Q1 n在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
' g% q* `6 c) L) G: P
(1)学习规则的优化
# S! x! g  u# p' |6 @0 g& Q. u
) n! s! b" W/ I# c用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

# W; ]3 H3 |% l. z( t3 t(2)网络权系数的优化
9 e; }- e4 m: \6 A) z
用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
6 S: V' X3 r) X0 N7 c+ c8 E7 y4 Q
2 l8 s" _5 i! w$ P* P, N2．遗传算法在网络设计中的应用
/ N( O* h4 {7 ?, c7 q& v
! g# Z5 K1 ?+ A& d用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
" F8 c, ^/ e7 J; |2 _4 w
* m0 c1 \* r( V- n& ?/ `(1)直接编码法
5 n. I; C  K) n+ A
这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

7 ?5 Z9 j  U1 `(2)参数化编码法

2 k/ g9 q2 ?4 a/ d参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法

这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
. h) W, D) _8 h1 B& |' w
" ^1 y! s/ x  O+ y0 f# W3．遗传算法在网络分析中的应用
2 i* I9 d$ i  @! H% x9 J
3 {, Q7 X" @1 y8 ]" I遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

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

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。