转（遗传算法）

guofuzi111

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

' a7 ]' w) J2 B8 |3．2．1 遗传算法的基本概念

3 T" V. A5 I: x1 j4 Z2 c' K0 I5 A遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

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

Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
+ J+ ]* x+ P9 s0 a
由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：
8 Y( Q/ a$ d. [1 b
一、串(String)
+ g! N, o: i0 ?7 N
! a0 W' w/ T: Q! o& Q2 M! O+ ]- R  N% v它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。
; `1 D* j- H# @. y: {
二、群体(Population)
/ i8 }2 E3 s9 }8 I: Y/ P4 I
个体的集合称为群体，串是群体的元素
$ Z$ n/ h8 L1 ^1 U$ {$ o
三、群体大小(Population Size)
! s" ?% ^1 B( C8 ~5 ^
在群体中个体的数量称为群体的大小。
; \5 r6 g+ w* E5 w: x& b
& l2 R1 V! E4 w* B四、基因(Gene)
1 [, G3 S# E. u4 G: V. ~/ _) C
3 _0 h5 R4 Q! @' y3 N+ ^基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
! r$ t" U, o8 U2 K2 H8 M
五 、基因位置(Gene Position)
! H9 M3 r8 q- p' ]+ t! j
+ Y) b: Q  b, X9 {2 d" {" m7 M0 i一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
9 ]- w3 B7 j8 Z
. [( Z, \2 l$ c' s  J& U' M+ {六、基因特征值(Gene Feature)

1 h9 B, a- r4 q' m1 V在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

七、串结构空间SS
  ]1 Q) Y9 W* U- A
在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

八、参数空间SP

: e- q4 a# Z4 w: U这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。

9 V$ Z+ t2 \8 x2 r! B6 b/ r九、非线性

: b3 J$ y- R% y/ ?- r, C) [它对应遗传学中的异位显性(Epistasis)
; i0 k7 v" T+ l& b  w, M
9 x+ b( B5 i2 m. }十、适应度(Fitness)

表示某一个体对于环境的适应程度。
$ D  T6 d/ K: t2 W- m" P- X4 r+ X
" K/ W" ~1 m6 f/ W遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
4 Z. J$ |- z5 q( F6 i
- h7 d( x/ x! i" [) @4 r  x; {3．2．2遗传算法的原理

- O. g  `4 G3 H6 ~6 v; O8 q遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
9 h- J/ @6 Z- U4 p$ r& G
一、遗传算法的目的
& T. o$ S0 e+ W* K. e2 c
; n0 q. T1 v. b8 G典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
; N& M7 n9 I" @
. ?1 d3 V- o# g! q) G& l; Z2 V考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
4 l/ Z( L/ @3 M8 W9 P3 c, N) E
% z1 N7 O& u, r9 ?3 ?- y/ Ybi∈{0,1}L        (3-84)

给定目标函数f，有f(bi)，并且
) M% l9 U' @! ]% ~
0<F(BI)<∞< P>

0 A  ?: j( T( s& o% x0 L同时

f(bi)≠f(bi+1)

求满足下式
! F- Y) q( h$ X) ~9 m
% E$ c. O4 K8 b+ N; X2 smax{f(bi)|bi∈{0,1}L}
& R3 e0 N- a9 t! s
, Y  ?5 `% M" y的bi。
3 v$ [; o$ f  d$ Y1 h8 D" A/ c
# ^3 L. ^$ \+ [* x( x) v' F5 Y很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。

二、遗传算法的基本原理
; O6 u* w. g* T$ _
长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
* ^7 X& q: N# W" U) e2 j
+ Q( U1 T+ B7 |4 [; O/ ^  h$ E! m1．选择(Selection)

这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
& V7 n* D! ~6 l% s$ K) W8 J/ V
5 x  w  {9 v) T" O) y2．交叉(Crossover)
7 p* {3 b; ^' b# ?% z. O2 a+ d
9 |$ {6 _( }+ x- H/ L这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

6 Z& c& F# U/ i5 u, p* I' Y$ ?6 n" b3．变异(Mutation)
/ ]5 l7 r2 k8 L6 M$ K
6 i: y3 v1 r+ X  ], z# S6 e, U+ P这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
! m; v# B) }' H% Y, m% h
遗传算法的原理可以简要给出如下：
5 M# @2 f" P- M
) p6 B0 @& D; y1 Echoose an intial population

% L! l, ~1 M7 r( g9 u# Ldetermine the fitness of each individual
& t+ r1 ~; a1 F
perform selection
7 q' q9 F* E! F% _, N
repeat

, u0 v7 u; a4 _, r3 V, V    perform crossover

9 B, B( T1 k/ `1 G2 P+ Q+ l    perform mutation
( E" Q1 e  _. j6 O
$ |7 P8 p/ K  U. D    determine the fitness of each individual
8 t' J( G8 y3 E- U
    perform selection

3 G# ^8 c" S( runtil some stopping criterion applies

这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
三、遗传算法的步骤和意义
2 k- E5 b: c7 Q  j  P" M& }# l
1．初始化

3 X0 E' j! j6 _/ K. k, h5 a选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
' o( s+ q- C. p' j. H
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择
3 b' Z5 s9 w, B1 m) ~% u( D
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

8 F4 B1 L( e6 y给出目标函数f，则f(bi)称为个体bi的适应度。以
% T) q* ^( l0 n7 Z9 W: J7 B( D


* p* k" S. O) o: Y$ G2 J为选中bi为下一代个体的次数。

显然．从式(3—86)可知：
. ]& {2 p# Y7 f' V' z8 z
(1)适应度较高的个体，繁殖下一代的数目较多。
2 h( s* c5 G# F+ {) O8 K
. {, p  e. |2 @7 A(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

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

3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
$ O+ C, w! B/ K) t- d4 B7 W
8 b# a) A- d: {. V+ X* b% {例如有个体
5 o; |+ a, j8 c: S0 Y; |
S1=100101
" s) ]) G: K2 V+ X, T( Z  S% o2 z7 ]
' m3 I, C# o! Q% b$ L! }S2=010111
, B- \( ^& H6 `( g; K
选择它们的左边3位进行交叉操作，则有

+ |/ p& o* V+ IS1=010101
% f1 T0 |! r8 M
S2=100111
( b4 ]3 I8 w* n" e
一般而言，交 婊显譖。取值为0.25—0.75。

6 }& z; x5 Z  S4．变异
1 h5 x6 p' }# S7 S
+ o3 @7 m( E$ P4 P7 J根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

4 ~3 o" }1 M5 `6 X  t7 O例如有个体S＝101011。
, |4 {3 I: I, o3 Q) j& o3 W
对其的第1，4位置的基因进行变异，则有

* K7 D# H8 y, A: M* W+ ES'=001111
' G( K/ n2 R+ [# m
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
5 \+ S' F1 L( @+ o
" A# H0 B. p$ ?) Q5．全局最优收敛(Convergence to the global optimum)
/ p  P- Q% B; C" Y: x/ p
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。

图3—7中表示了遗传算法的执行过程。
7 v* l0 W( C) b  q
+ l! u: M) w5 Q+ Q

# }! {$ t/ C  K
  o. _( t% r% A$ y图3-7 遗传算法原理

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

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
$ z# \+ Y% R- A! n) w
4 X- U6 r2 v3 Z7 ?2 J0 z5 S一、遗传算法的特点
& p5 g# b4 f* v* f8 X  q
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

4 w2 M; \' o) c) ^- b8 E7 ]这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
7 d$ d, \: S  H' ^
+ ^" m7 ~0 V7 J& d由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
$ H* K0 e9 b+ y! S: u! i" S
8 c! X# W& V# [( q0 S& {0 g3．遗传算法有极强的容错能力

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

4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
- p% p# a8 }3 S8 T3 i
这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
2 t2 P% n$ `  Z' v
* d5 h) L3 m" K+ D, E! x4 X  Y( D5．遗传算法具有隐含的并行性

  g3 w. V$ t" q1 ]6 n5 J遗传算法的基础理论是图式定理。它的有关内容如下：

(1)图式(Schema)概念
; y3 Y; F+ x, b  E7 s
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
& p' Y" m* ^/ W: |1 k* _
. M, U# |$ t/ {5 s8 \- P(2)图式的阶和长度
0 v( n/ Z$ |8 i! \
% Y6 k8 t. {" J图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
, L0 N) F) i5 V, E0 T
! F( [4 W& J$ U# W, @(3)Holland图式定理

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

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

二、遗传算法的应用关键
! u4 ]6 c, e+ M7 n/ v
7 V/ R# f. ^8 K! g+ ^3 |遗传算法在应用中最关键的问题有如下3个
* ?3 T( r4 k" i( I3 K2 W4 U# l; h
* X2 K6 w% i. c/ o+ E. M6 t1．串的编码方式
; Y! o; X4 ?) ]; ]& Z
. g; `4 |, \3 q8 E这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

* E( }" N; T: ?2 P  `2．适应函数的确定

' h3 D4 a/ v' Z7 [2 i+ t3 }2 I/ @适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

& I# _' [0 @9 m( q3．遗传算法自身参数设定
0 M: y3 T( o0 y. y4 O
0 ?- _& ^" l% l! A+ C! c1 [7 u遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

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

三、遗传算法在神经网络中的应用
' Z( s+ t$ H: U5 E
1 ^+ c/ w3 F8 g/ p7 h/ N遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
# N/ J- b* Z! _1 L
1．遗传算法在网络学习中的应用

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

(1)学习规则的优化
/ B" k9 k% Y3 O3 r
( {) t* e% z/ q( {: e用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

(2)网络权系数的优化

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

( O; `% Q" q' s2．遗传算法在网络设计中的应用

用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
& v( R9 B9 c7 o2 t7 {7 w5 k
(1)直接编码法

这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
# ]4 X2 ~" F5 G
/ w: E6 C9 Y. u0 M  D6 t(2)参数化编码法
; J* c- F0 @* t" ~
0 ]8 u2 P- |5 ^4 \参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

0 L/ h" X# f4 t1 B. ~0 J% _% n/ W(3)繁衍生长法

% O5 i* ?6 @  c2 b这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
% M6 N' f* |; j9 p& ~, G0 F
3 q0 Q2 F' }4 b) ?$ x) Q3．遗传算法在网络分析中的应用
: H3 ^9 _) T1 ]1 W
遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
4 n; u' O+ L& G2 y
1 ]9 @2 s; ^" W4 Y遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。

, H: s/ p8 H+ \% ^6 l0 D8 V三、遗传算法的步骤和意义

1．初始化
  ^1 ~& F- d. q" e+ @, [* b
) t9 e/ B: w9 N# _选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
3 q/ n: @0 [- l; T  P; @: _
) k* }# E! W' k) T8 }8 H通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择
1 Q) g0 c  N& s7 }9 s9 K' i
# p' r" o* h; i- R- O根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

  X6 t  k/ r( }* o3 K给出目标函数f，则f(bi)称为个体bi的适应度。以
) {' j2 j- X* E$ j& ]# m

. v7 I9 `7 K7 I
为选中bi为下一代个体的次数。

, c# Z- Y$ {: Q9 }$ d; I  {显然．从式(3—86)可知：
9 o; H# d' W8 C" X* b: h, k" Y
& C, v& F: T( Y  N) p(1)适应度较高的个体，繁殖下一代的数目较多。
% A( G) W' V) r8 Z2 E0 H
# g% v, N$ A$ T3 f7 I# ~(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
6 t/ ^* x. J3 a: Z3 c
: g5 b+ X5 G3 l( Z# N7 m) G这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
2 c5 [1 {% r1 X* {  u4 T
; a& w0 f2 z7 q9 M3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

% d. ?8 J$ P$ w+ A例如有个体
6 I4 M5 S: B4 W
S1=100101
" w" @6 c  ?: @. ?5 E8 V
S2=010111
4 b1 ~+ F" M$ n, H+ r) ^6 e
选择它们的左边3位进行交叉操作，则有

S1=010101

S2=100111
3 ^, L( `* F* n/ p$ X- ^
一般而言，交 婊显譖。取值为0.25—0.75。

/ _% N  [5 n  ]8 h8 u# M# C5 ^, W4．变异
0 a& z0 F1 P/ p& d( m8 Y
4 B; C; Q9 o9 B0 Z6 J, S, S根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

例如有个体S＝101011。

对其的第1，4位置的基因进行变异，则有

* `0 ?; R; N& s% L) D2 QS'=001111
( S8 h$ z0 R' V7 u
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

5．全局最优收敛(Convergence to the global optimum)
, j  u7 O2 q8 d4 U
( M3 Q+ k. |. r8 p  l当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。

0 |/ D; q, m6 q& F' [/ |图3—7中表示了遗传算法的执行过程。


4 z$ ]/ T: y& {* _6 S

图3-7 遗传算法原理
% t* ]0 @! P" q5 l; W& |
3．2．3遗传算法的应用

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
" s8 X- L1 }7 k  \
) S: ^  x: K8 ~: [! h* \- Y一、遗传算法的特点
# d* }* I' l8 n
0 x4 l* e+ J" _' w1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
% ^  J; g/ F* f/ T# O4 z
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
$ P* t9 [' I4 [* y0 R  c
2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
1 j/ X, D  ?4 r" r% j/ w
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
9 P6 w" |; n; b$ Q6 Q
4 c2 c: }3 C; d9 s) g/ f3．遗传算法有极强的容错能力

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

% C/ ~( a6 S5 {8 ~$ s" B4 D$ A4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
! I% w2 F; d9 s/ o2 W9 y1 R0 l
7 F' v: j( e- {+ s' z+ ]4 ], n- I+ U这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

. ?( P6 b! R9 V- b' g  P* v/ n5．遗传算法具有隐含的并行性
! G  K+ @# {6 z  Z
遗传算法的基础理论是图式定理。它的有关内容如下：
1 M1 r5 ?8 X: P$ ~8 B# [
(1)图式(Schema)概念
( T) j. S3 m! V9 p. ^7 R
2 {% U/ n5 W  `" N) l1 B; e7 o一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
; P9 w4 T7 t0 M# f2 D
(2)图式的阶和长度
2 C" c1 s, X& C& A/ s+ E. J! J
图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。

& b' \7 h$ E$ ]1 B+ U(3)Holland图式定理
3 W, B9 F# q* r5 _! Z, w
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

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

二、遗传算法的应用关键

遗传算法在应用中最关键的问题有如下3个
& a+ E, V, u( {  y& A
5 N7 r2 w+ h. [1．串的编码方式

" @0 `0 }7 h. F& ~$ c. ~5 E+ q. [' _这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

) g, v, |5 h0 `+ @  C; P7 g' y5 G6 x2．适应函数的确定

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

3．遗传算法自身参数设定
7 Y, O5 k; ~$ a' C7 }; P9 V7 n
: y+ `% K/ D8 s遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
7 r2 n. N( ~* h/ R9 {# Y$ Z5 F
三、遗传算法在神经网络中的应用

遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
# p& p1 M0 W4 C1 `* ^5 A) }
1．遗传算法在网络学习中的应用

4 s# ~" j% z/ M& B在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

2 M: H8 b7 q; M! ^4 ^% ]4 j(1)学习规则的优化
2 }5 K( {. f( G) o' g8 X6 d  X
& W4 @! w& D- A用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
! N+ [, e4 U; C* x$ o
(2)网络权系数的优化

$ Y" F: {# e& J9 a9 ?' Y用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

. [: J! k+ h5 j+ k, [7 L2．遗传算法在网络设计中的应用
) A% P( k& c3 O- p
! F3 V# ?9 c  z9 K用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：

1 r4 C. m# g( d) l7 W. r& q(1)直接编码法

这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
4 Z" E2 M- e% [1 Y4 [2 i
(2)参数化编码法

参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
" Z) t( C& a3 X: h3 d% \
(3)繁衍生长法
4 J; x2 o% K) {7 p: i, X+ q
. g% T2 S  U7 y, }: L这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。

3．遗传算法在网络分析中的应用

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

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

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。