转（遗传算法）

guofuzi111

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

遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。
( p% X' l- D! M6 I  g# @* d
遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。
& x4 n3 H6 t" B5 ~7 L9 s* H1 G
3．2．1 遗传算法的基本概念
7 k4 ?; n9 @. ~; g4 b5 Z! g- X
2 S, o% |; f8 A; U" Z% H8 P遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

, E, D' z2 F9 C- x3 U+ |Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。
4 f, T4 \% p, P
+ g& D2 [* \& x1 T# A: a) C/ |Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
; |6 O6 q2 r: U$ f" k, V' |
由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：

# W# |& {5 T8 X+ U+ f+ W一、串(String)

它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。
" r8 E4 I3 c4 a
& A1 [7 b* @# V' n5 V- q二、群体(Population)
/ P7 V5 [! P% V; ?# ?( J8 F
个体的集合称为群体，串是群体的元素
! C' r4 D' F8 ?
: i/ F  J/ P' w( d/ X三、群体大小(Population Size)
0 \8 _/ e5 u1 l, R! Q  R
在群体中个体的数量称为群体的大小。
# Y7 `" L; r' N% K9 j
) R" F. P& L0 d# i" [, M8 I" M四、基因(Gene)

基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

五 、基因位置(Gene Position)
6 E" n) c/ i: D) F
一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。

六、基因特征值(Gene Feature)
/ d7 `  [2 U5 Y0 T9 _
在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
7 K( X( c; [, c8 C4 v6 `( z
七、串结构空间SS

$ I4 i5 d5 c7 m9 [- o/ e在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。
( U4 Q# |9 }6 L4 G7 ~" ^$ r' |9 B
" }1 v7 t7 Q& T( T' Z八、参数空间SP
8 B3 ]3 O8 A6 Z+ q& [: |
, J6 i9 A4 p8 S$ A3 [9 a, u: {这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。

九、非线性

它对应遗传学中的异位显性(Epistasis)

) {1 A# K  C; o" Q! q3 [+ ~9 o十、适应度(Fitness)
5 v& e: t' Q6 ]6 N
/ \/ K% A' g0 B" v0 G* }表示某一个体对于环境的适应程度。
3 q( x9 @1 {4 O$ i
遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。

3．2．2遗传算法的原理
$ B4 l, D7 e& g7 A9 H
+ e9 A. F" N% }) I遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
( ^! U/ Y( ~: H
一、遗传算法的目的
1 K& }/ M7 X+ R; _
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
# r7 q3 e, q8 \& b6 T
考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

. O% D; w- k* v" d4 I) Q$ I& Zbi∈{0,1}L        (3-84)

给定目标函数f，有f(bi)，并且

+ }0 B& n  E  h: A0 ~0<F(BI)<∞< P>

: A: d  F  y9 k( L  q6 \2 Y2 f同时

f(bi)≠f(bi+1)
% J6 g9 s: Q* d7 x) \
* q$ p" J% L6 w! ~+ [求满足下式

max{f(bi)|bi∈{0,1}L}

: a$ J+ w- \+ T" }的bi。

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

二、遗传算法的基本原理

9 w; W/ h; B/ I7 P; K' o/ m长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
9 F" D! K0 D8 t
1．选择(Selection)
* S( D/ m9 [6 \' H8 J5 G, G( i! f
5 ?# R, S. v' F; c这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。

+ ~+ d+ |9 j# g( D" a, n% d$ A0 h2．交叉(Crossover)

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

3．变异(Mutation)
" |3 C9 j2 T& p
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
) }  X6 i0 r% v) x$ h, ^9 Y7 B4 ]
遗传算法的原理可以简要给出如下：

choose an intial population

6 h0 @- U! r" Y+ k. Vdetermine the fitness of each individual
" S" L$ |0 s+ ?. Q
" |/ x( o6 o* n: ~perform selection

repeat

( R3 c5 }% V* W& S+ K5 m    perform crossover
" [" {7 L7 Q/ L  T$ n/ V6 o% {
$ J% e, e7 J: k    perform mutation

    determine the fitness of each individual

    perform selection

- {+ q6 k/ X$ g. r& J# h  tuntil some stopping criterion applies

4 |  j9 Y! t- [( J3 j这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
三、遗传算法的步骤和意义

" j; B+ T3 P0 J) ?: g' Y1．初始化
* f8 ^% t2 ~8 D# y. T$ Y$ S
: c  C7 M/ h; K: Y选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
9 |* A6 ]& R& x$ k5 Q
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择

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

3 `4 p8 q* U! c7 L给出目标函数f，则f(bi)称为个体bi的适应度。以
( D2 O2 B6 W! h9 l

$ x( g8 ]9 ], Z2 i2 K" ~% }# k1 _$ Q
  s; N* v! _4 T# ]; w3 a) o; i为选中bi为下一代个体的次数。

显然．从式(3—86)可知：
( e' {2 {7 a8 z- L
: q: |8 \, l/ A- x  M: p; A: m% m(1)适应度较高的个体，繁殖下一代的数目较多。
1 |) k# k! y+ P& j; S
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
* Z1 O  {& X; r- i0 h) O
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

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

4 I# e/ O, P+ `+ ^1 u. {4 k例如有个体
, Q5 V: W! T# h' ?* C+ p4 T
S1=100101
& i2 u1 C, b+ ?$ ~4 u
S2=010111

2 c( ?% w, j7 s. s4 p选择它们的左边3位进行交叉操作，则有

: r- H1 |: z6 b7 I& NS1=010101

S2=100111
9 d4 i0 z9 z$ B/ v% B6 a* }4 a
一般而言，交 婊显譖。取值为0.25—0.75。

5 a, _- K( U+ ~1 V0 L8 _4．变异

根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
; J3 _9 G, v$ ]3 Z3 T
例如有个体S＝101011。
' j% P: Y9 A3 F+ [) G
% E" y, E$ _! s对其的第1，4位置的基因进行变异，则有

S'=001111

单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
4 s- r5 E# ^( o, L
5．全局最优收敛(Convergence to the global optimum)

. ]' I# y8 B  W  y: t4 k+ p. d2 ?+ [) \当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。

图3—7中表示了遗传算法的执行过程。


8 z, ^- Z5 E( M. [! @

- B, e/ k. v8 T' v, E: I3 h, k图3-7 遗传算法原理
* x0 t6 O3 Q3 o  Q9 I
3．2．3遗传算法的应用
7 w4 v* E- w- Y1 S# w2 m/ M
0 n$ z* l6 k8 x/ j6 o1 t1 \3 k- n遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

! I5 s2 G3 d( _" h2 T一、遗传算法的特点
. A; H* j# i. F
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

) j5 I* }, _7 |& v这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
4 c! N9 {) m. N$ e2 P2 N3 A
2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
  `6 M. S- T4 t
3．遗传算法有极强的容错能力
9 V) }8 z6 q$ Q# I9 z
1 _) J' O5 ~- b  b3 S7 M) [1 o遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
7 J' U; |5 n1 r0 O& \
9 ~2 S6 S+ F- R3 B) `4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
3 E' P' m: d$ E3 E, H; S
' S9 X2 z$ ?7 B) q这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

5．遗传算法具有隐含的并行性
7 s' l7 d, v/ H& O
遗传算法的基础理论是图式定理。它的有关内容如下：
  H2 G5 k/ T$ t4 z, J, G. f( o
/ r# m7 h; n& l(1)图式(Schema)概念
6 ]! i! i3 H2 C0 S2 m" ^
* `  M% z  G5 m一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

(2)图式的阶和长度
* v! j0 j& p( u, g9 O) U( ~
图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。

/ ?7 z- B" ]. r8 R+ V/ N(3)Holland图式定理

0 Q5 \" o8 `3 j5 g低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
7 H2 Z5 I7 n0 S' r4 H$ \
2 o9 T0 [0 G& v) p# d遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
+ q. t8 W& w* A% J* s( I3 T  X
; a1 X: \0 P6 }! f- x二、遗传算法的应用关键

* i( q$ c2 v2 A+ t% K遗传算法在应用中最关键的问题有如下3个
$ D- ?# b$ O* E  q( m
1．串的编码方式
0 V7 F% S* M' O# M; z' t
( r  B# I) v/ n6 F: `6 B这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
8 R. r# S" P5 I7 S6 q
2．适应函数的确定
# K. H  t3 w3 |" @) a* Y+ x4 g! o
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

6 ~6 Q; q$ P' n+ Q2 E6 t" D, F8 e, M3．遗传算法自身参数设定

遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
, ^, p5 [8 T/ P
, W! ^9 `6 Z. ~3 _; A群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
# D5 c, v) `0 q8 g4 @5 r. K) x
( c; o3 n. W$ l! |- X: N- _三、遗传算法在神经网络中的应用

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

# _/ G2 a( w! C" Y! `+ ~1．遗传算法在网络学习中的应用
5 Z8 T# u, V' R' f: e- N
在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
4 z+ F* ]- J; v
(1)学习规则的优化
$ r: j4 Z+ j5 @1 ?" r/ v6 v: S
" t# C4 E% u; {4 U& O用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

" ?1 R8 N9 f! G) f1 E(2)网络权系数的优化

5 I$ o5 Y; a, v+ T. G( F4 |: P用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
2 g7 P7 _9 C- g' s+ f$ D
2 B! S8 l, d1 |. E3 m' \5 q  {/ m# o- c! r2．遗传算法在网络设计中的应用

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

& e3 P. t6 I: y3 o2 X(1)直接编码法

+ N/ C- j1 `- S/ w; E' F3 Q这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

1 H) w6 C7 I' v6 D5 S& \(2)参数化编码法
0 G4 v( q$ S4 F: F. s
3 a* z+ i6 v$ d0 C$ _4 k参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法

这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
) X0 V8 m1 x; o* y, o  M. _  w/ c
3．遗传算法在网络分析中的应用
- h$ i1 w, }4 D0 I/ d! N; T
遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

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

三、遗传算法的步骤和意义

1．初始化

6 }% B! A0 `0 m' n- P) _+ [选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
) z* M1 c8 f. f$ w" F9 s' r2 z) E
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择

' Y! W% `  f, W4 b4 z: s% {根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

给出目标函数f，则f(bi)称为个体bi的适应度。以
2 f1 n" W' q, s* Z7 u' h  A
" l9 Z0 U8 }% F3 {; Q% s/ T

6 x4 n) D1 `0 ^% O为选中bi为下一代个体的次数。
* B: }! q) j0 |* w6 Y8 S) q
! i# U7 o. t, l9 G# e! j; Z) }显然．从式(3—86)可知：

(1)适应度较高的个体，繁殖下一代的数目较多。
) r+ ?& n0 ^6 w( T* X6 n  p. H
# |3 o3 `/ w5 L5 P& D# ~% d1 V(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

5 d4 i9 R% S9 d4 O8 q5 ?这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
! K! W% s; @0 }+ t  A: G
* Z3 ^1 H1 ~# E2 b  M$ p* }/ N+ ?3．交叉
# |8 j' ?/ m8 d9 I- q& R, H; V对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
6 c, ~  D+ e) E6 U5 W1 i9 s, F* s
0 D0 _4 |( W2 s( U例如有个体

S1=100101

S2=010111
4 ^8 `! q, i* C7 P
* p0 }; {2 `& q- }) W选择它们的左边3位进行交叉操作，则有

5 z6 I% ^8 `; W% F, C+ US1=010101

& X! S) }( r/ \1 A2 vS2=100111
) z$ V: o9 y! z" N, R; G1 W3 q
9 z; O# L0 j7 `) f- l' |' }一般而言，交 婊显譖。取值为0.25—0.75。
, }& f: t) H% {4 `3 C
* Y* X% p% o' Y- H) u2 ]4．变异

根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
; H3 ~0 l/ C# Q7 i, F" M+ x
2 i. m3 t* \! i例如有个体S＝101011。
! j* B; \" Y2 ?; I! ?+ K' e
$ u- \( h8 p: a2 Q0 l  u对其的第1，4位置的基因进行变异，则有
, J% a1 i4 d# k
* b' A1 S9 X3 X4 u4 ^+ G; D7 ]S'=001111
( }, o4 g0 g* b; [; N# \- n5 Y
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

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

9 w, r/ G* g7 }+ b- |) n+ E当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
$ h. k; N) q; D: B
图3—7中表示了遗传算法的执行过程。
4 N0 {4 H( n* o8 D% g* R
" W5 k* H1 v( y4 B$ \% B
" r7 ~" O5 z' Z5 }

图3-7 遗传算法原理

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

* D5 P7 w9 N; H8 \& N0 h1 S' l遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
* v2 W7 V8 t8 r* \3 Z; r
一、遗传算法的特点
0 x4 `) z" w* K9 Q5 h2 _
# `% a' w' N/ t& t7 y4 l0 e' L1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

' j9 P7 s1 c/ @5 Q- A3 i这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
; n+ l2 h5 t: Z% d% g6 d4 p
: E6 ~4 H6 d% f2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

. n4 u: ?& G8 |: A# r5 g由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

. `! H' R" y0 p4 n: c" q3．遗传算法有极强的容错能力

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

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

4 d# O5 N, M0 v! a. e: n  Z这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

0 n* p# a- G9 t5．遗传算法具有隐含的并行性

8 V- ^/ }6 g2 J& `& o3 l遗传算法的基础理论是图式定理。它的有关内容如下：

5 v( @; h9 z" Y(1)图式(Schema)概念
2 i+ j9 _8 S6 a/ Q9 k3 d+ R/ y
5 o1 @$ A% R* Y# _+ a( _( g; J一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
( G& L( a2 P7 A& Y& h9 e) `
3 W7 F1 i" C& Q7 v(2)图式的阶和长度
, o. b: F; ]/ s% a( w
图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
7 j3 h# O& p0 f/ @( ?) [1 h2 |  I
(3)Holland图式定理
7 V- e' D2 q5 s: P/ z
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
. U0 d8 e  ~! L. ^2 O  W! l0 x
" K3 V6 ?# B( v4 u二、遗传算法的应用关键
) u9 t5 X/ P8 d; Q" Z6 w/ J
遗传算法在应用中最关键的问题有如下3个
" o. w$ W  o2 a1 Y& @  I
1．串的编码方式
' q0 P) |1 t  _7 _
这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
- {( c8 }3 @- U& [7 x
2．适应函数的确定

' d0 Y' M/ }/ d8 g$ H: R% e& A适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

4 e) y6 T  K  ~2 v: Q8 U; B3．遗传算法自身参数设定
+ b: e# D/ Y" A
遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
  P5 }3 b# h( V; ]" s+ ^+ G
三、遗传算法在神经网络中的应用
# A8 C8 ?& |' L" L0 Z( h* K
: ^: T9 Z! C) [. a! k: C, b遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

1．遗传算法在网络学习中的应用
* H4 s) z. a& F5 ~8 l& E7 q  A2 M
在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

$ B0 r3 V1 A! Y' K6 I0 t- `/ z(1)学习规则的优化
( \: G- W4 W; Y/ u: K; ~# t
. E9 A" i* h7 D; I* S+ Y用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
5 t8 |' q" {  j/ N! y
) e$ i' Y/ _" ^  w' ^(2)网络权系数的优化
3 G. i; J, ~& \( x) s0 o
) s" Q; J. k, U0 x用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

2．遗传算法在网络设计中的应用
  m% E* V# C- g  O
2 a: B% v  }+ D# l; O* y5 T用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
: [  C  [, c7 f0 T5 k
(1)直接编码法
  G% H3 H# C! z; J" [( G
: ~: r. O# r( L2 d8 I: I这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
. e* L% G8 T$ o  j+ Y( p
5 P% K0 M! i7 P+ o' X(2)参数化编码法
' o9 ?, H3 N" R/ L% i) \) [9 K7 b
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
& O+ P1 ~; k6 T! U% R
(3)繁衍生长法

1 z& O, B2 l& _3 C' X这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
( g  L! |( m. e$ _. I$ J: @
3．遗传算法在网络分析中的应用

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

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

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。