转（遗传算法）

guofuzi111

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

' p6 M8 ~4 {) `, S6 b3．2．1 遗传算法的基本概念

5 l/ F9 @& f  g2 g/ _! i遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。
' L. Z8 k4 E" j- o  [! q, s
+ x4 O, ]# k  g; k: D3 V) zDarwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。

' l# |) c( K+ ?7 ?* qMendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
8 P) Y, W% g. a6 h$ J
由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：

% v# C4 e/ r/ L+ q) l" d; g7 a! y一、串(String)
  t, K  `3 @+ z' o0 m
它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

二、群体(Population)
1 V2 Q! J) Q/ }. |) w# K! p/ h* O/ o4 G
# {1 d- _& k& ~个体的集合称为群体，串是群体的元素
6 W! Z8 E" e, A
' u8 o( m7 s/ x4 i7 J& W8 @! o三、群体大小(Population Size)

在群体中个体的数量称为群体的大小。

四、基因(Gene)

5 c; I! r4 u0 X2 N3 z& X/ U基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
1 r2 n( O/ y( y. C
2 q7 J; L" _! |( ?5 H' X$ G# _五 、基因位置(Gene Position)
4 f# u, h% n* `3 T- O' p
  i8 t& j- g, H" N' s6 S& e1 I6 |一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
. F" y9 M$ Y8 F  h5 s
六、基因特征值(Gene Feature)

( T4 ]& `5 l6 Q( }& h在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
# l$ w' V& h1 J; b
, K# G9 F1 y1 w5 Q5 d, v七、串结构空间SS
1 W3 z- `% j' A7 a: |
在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

八、参数空间SP
# W- i8 K' H# y7 j$ N# o4 z# _
这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。
( J4 R: |7 {; a4 @: P
九、非线性
$ ?( j/ b* n6 Q/ A7 `7 a4 L8 O& b
& n% n2 A) `7 o# |- ?" O它对应遗传学中的异位显性(Epistasis)

十、适应度(Fitness)

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

遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
1 F  Q9 k" Q" n; t, r0 V" P
; e2 U% w, @9 `$ G% N7 w# A) J3．2．2遗传算法的原理

6 `" W, R3 n) C- q7 Z遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

$ Z! w( e: I$ c, _; a4 y一、遗传算法的目的
9 M% |5 {, g/ N. ~* O2 S4 G
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
$ f4 E5 b" V) l) Z* B
考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
7 S9 u: x; w; p2 }6 ^. y
bi∈{0,1}L        (3-84)
: b# j, w7 e5 b. d: y+ Q. p& R: z, G. c
0 w6 D' u6 a2 }! ?% Z* a$ g- a7 W给定目标函数f，有f(bi)，并且

0<F(BI)<∞< P>

同时
0 G0 b) L, q: }' @
f(bi)≠f(bi+1)
# F7 }' {, j7 I% t& C
求满足下式
  f! N4 H  t5 J7 b( E
$ \3 s- ~' `- p# G- J) Amax{f(bi)|bi∈{0,1}L}

的bi。

很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
/ N: t. p% o+ [# v. @
* S4 e4 O' o5 |' [二、遗传算法的基本原理

, _; z6 ^7 Z" l+ q" p, B长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：

1．选择(Selection)
0 @4 }0 s3 u5 f0 {& \
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
( C. C3 A, H! @0 Y" _" d3 f
: w7 \* E9 {) c  l5 U- ?- r2．交叉(Crossover)

这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
5 F) ~* q9 j0 H$ Y' |
3．变异(Mutation)

这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
; i% h3 T7 c4 K
遗传算法的原理可以简要给出如下：

choose an intial population
: j# W$ k- L# L, x6 L7 w7 |+ T
determine the fitness of each individual
( M+ E* X6 X* ^0 ~% N' f' i+ k
9 f7 `3 y! Y, |perform selection

repeat
. C3 c4 U2 m* u2 d: C4 |
    perform crossover

% ?+ Y" p+ e5 E: ~% q8 Y    perform mutation
% ]) Y& z5 x% ]5 h: W  v+ u& p
! I( j3 J9 o4 B" z  S4 Y# h    determine the fitness of each individual

" M. c, j0 t6 ^* |    perform selection

until some stopping criterion applies

; u! [2 E0 ^1 i+ I& d% x) s这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
" ?. X4 G1 e- Z/ b. H- E三、遗传算法的步骤和意义

, b6 G9 y5 P7 M& h/ Q1．初始化

6 c- ?- W& }% `( h7 M* j选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。

通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
2 x% T1 A" B. d- j( r
2．选择
" {+ k& H+ _: w0 @+ e
3 }. |% W4 ]  F2 A根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
# P% O- O+ {$ F3 x, M- \# x
" [2 `( o. L+ t7 u! f+ F# A1 y给出目标函数f，则f(bi)称为个体bi的适应度。以
! K5 y' H, |6 ?4 h: [0 N! N! c, E* r
# L2 c. _9 |1 c( Z: i
3 J. @: @' B  L* L- p6 v
- M) U8 t1 U; g& a) h+ D2 W为选中bi为下一代个体的次数。

2 d1 C( ~0 ]/ L- Z3 o显然．从式(3—86)可知：

6 @, L& o0 f/ y" f, N" _(1)适应度较高的个体，繁殖下一代的数目较多。
) P' N" K4 F* T+ ^9 u
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
8 n" O, ?) J, U& v' `0 g" K- l- K8 [+ ]
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

! A; E* F- P3 M. B8 y& R! n4 T3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
: U+ M$ c, {. `3 x7 u
* G; S0 e) D, d  W7 R! k例如有个体

S1=100101

& {8 Z' Z5 v& r5 qS2=010111

+ s0 _6 ?/ k/ x# D$ B6 [( U选择它们的左边3位进行交叉操作，则有
! l* ~- _: u) D  b. [2 F
S1=010101
4 \4 ?6 M: |9 B; y& y4 k, V. @
) H( f4 S9 L- \, E& _S2=100111
' t: J0 N6 h) _7 r1 K  A4 s
一般而言，交 婊显譖。取值为0.25—0.75。

4．变异
" O2 i) l) o9 J
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

9 k2 h' X/ O6 r( T3 ]2 v例如有个体S＝101011。
4 T' W3 w: E7 w7 s) S  M
1 F* _! n/ N/ n对其的第1，4位置的基因进行变异，则有
4 [& M3 p" F6 l) ~0 V: ?
) i& {1 C' e; i5 P+ s1 FS'=001111
8 l$ L( V8 Y: b* |; n# n
5 z9 H+ H- `" h单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

5．全局最优收敛(Convergence to the global optimum)
: l7 z1 S5 P5 q- `: Q5 {/ @7 f( l
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
( ~# N& \; i' \) A
+ x; m" p6 B9 U0 w5 }图3—7中表示了遗传算法的执行过程。

" J1 p0 p1 e3 X8 E  j- V7 c


图3-7 遗传算法原理

2 w9 B. F, c6 i3．2．3遗传算法的应用
: ?/ G; D6 q+ Z+ F
, J$ z8 R! b- v遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

" [2 ^6 c* M( i/ A5 i一、遗传算法的特点

5 z. V" n2 y* ?0 P! G1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
! I( K; u% Q2 i7 I
0 c0 a3 H$ U- h' {$ ~这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
" b) @1 [: Z. |' b
2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
# {8 w) e0 E+ e
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
/ }  Z) f( V% W2 w) U
3．遗传算法有极强的容错能力
, x- D  c) P8 c5 u1 p$ D
+ Z6 M* O2 X, w* y. h: U: ?" E遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
; s3 H' {, s# j8 I+ M
, Y# B5 O4 }. v1 h+ |# {4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
* }1 h+ ?3 O% k7 Y
; S9 {* t  u7 `2 }8 V: g这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

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

5 A6 I7 ?0 G' A# C. p8 z8 s# v% E遗传算法的基础理论是图式定理。它的有关内容如下：
, c& Q; O! f* ~" a8 g0 f% P3 q
; g/ e- e, K, S) O. \(1)图式(Schema)概念

+ y4 X& Q9 B3 r/ u. S一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

) z/ g/ u: D4 j% f  O(2)图式的阶和长度
" Q7 @1 K- }. {8 p5 z! r. L
! y0 G: L# L1 u  o+ x4 l8 Q图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
) I$ \. c* I7 ^; j6 G2 Y4 [
(3)Holland图式定理
+ ~. a& D* E5 H7 g$ b( ?% i
. T3 U/ d' ]0 H& n2 i( R低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

2 |1 r# `4 y8 k8 ?遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

二、遗传算法的应用关键

* Z; B9 H9 G, a- d4 K遗传算法在应用中最关键的问题有如下3个
9 j' ~+ y! j2 P: e8 b, v
3 \5 Y% g  V2 u2 x' b! J( P2 m8 h1．串的编码方式
& [" H7 y: x7 l( [: x1 K" M) c
这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

2．适应函数的确定

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

/ ~! r( F& h# `3．遗传算法自身参数设定
9 K- F& s1 X9 x, {
- ?) l  H( I0 T0 T# ~. N遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

  q; y+ n  I# d) i群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
. b, k; J1 `2 [  y$ G) C9 G
三、遗传算法在神经网络中的应用
2 [4 C8 m: D/ {/ N6 `3 H: O
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

4 O6 X: t% x; b( c  U& @1．遗传算法在网络学习中的应用

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

(1)学习规则的优化

用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

1 t3 |' x, ^& I7 J8 M. Y# b" I4 e1 C(2)网络权系数的优化

+ d1 y7 |; [: |2 L  U用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

4 W0 O$ t, J0 O$ f/ Z2．遗传算法在网络设计中的应用
, Q$ L& E+ O" k% \" Z$ O# C
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
! I- I, C6 R' Q
(1)直接编码法

( A2 q* E  |* C: J" Z9 W0 A( P. m- c这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
1 C/ J; ?! Y, @7 [( w1 r* S
" Y/ C7 o. g& ^, ]+ [& D(2)参数化编码法
" H% ^' r9 R9 i; \) ~
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法

/ y5 ~" b( w- Q" S3 x这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
- a" p2 [  w+ p3 m5 p9 [
3．遗传算法在网络分析中的应用

5 s0 O7 N" A5 |7 \4 s9 t, n  E4 D遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
& C; j. }0 t" P$ a& L& X
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
! Q( I3 P5 f+ L  o' A- E
: }$ u. F3 `0 X; P) S3 j/ m

三、遗传算法的步骤和意义
) Q' m$ N& K9 \! d- t
1．初始化
% ]" o; K6 ~# k4 p1 L2 J) V
, y: Z+ ?9 i- h* a0 B选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
1 ?9 O1 F* m4 ~8 H  D$ K) ^& J- p3 O
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择

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

: K, _, c) ~0 m# m: V" \$ J& ^7 U给出目标函数f，则f(bi)称为个体bi的适应度。以


% e3 g9 |7 S, X7 ?# Y
为选中bi为下一代个体的次数。

显然．从式(3—86)可知：

5 f) d+ L' U5 Y" e(1)适应度较高的个体，繁殖下一代的数目较多。
! J1 L% R4 y: A2 B
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
$ l& U. A$ j3 e  ?
3．交叉
/ U1 J) s. @5 r# [对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
  V0 g/ Y) @2 Q1 q% q1 k  g
例如有个体

1 v9 V# T$ K& u& p* kS1=100101
3 D0 W, q' e6 B. x7 E
S2=010111

选择它们的左边3位进行交叉操作，则有
! ^9 O+ z- l/ B5 d* P
S1=010101

S2=100111

; C' b3 n( V- n4 |2 K一般而言，交 婊显譖。取值为0.25—0.75。

4．变异
( u( r1 Z7 S7 P# p- E% q9 X0 ^
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
' J- [) X: t, l) k% s5 \
" a! f2 }+ Y. [) I% Z例如有个体S＝101011。
2 k8 `$ @0 W) L8 e' x
对其的第1，4位置的基因进行变异，则有
) i4 O3 f3 Y1 W9 l
S'=001111

% e8 p7 M! n' c单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
$ t5 w9 H1 `) a. Z7 Q- q
: Q* `$ Q6 A2 _( Y) w5 s2 H5．全局最优收敛(Convergence to the global optimum)

当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。

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




图3-7 遗传算法原理
3 _  |2 s; h5 q# ~
3 ]8 c# l/ a: }$ Z5 @3．2．3遗传算法的应用
/ y# F1 R  J) k6 g3 ~: r- g# Z
遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

7 m2 Q1 ~; T# t! ]4 z  O一、遗传算法的特点
- X8 q/ I, H$ T% D& T! Z3 _# P& H
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
" |6 v- d  P: H0 \, W& _3 @
  Z! `0 m5 C9 @% b) f9 }这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
0 x4 D; }6 j# v: F+ \2 ~' ]/ ^" t
2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
2 h* v3 W, }: X5 s. N
3．遗传算法有极强的容错能力

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

9 Q1 c  f6 C9 H+ t' U4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
  _! L$ ^3 X8 G' T, H
* r) T- x* T! F5 x- ]3 }, F这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
' d& X+ ]# @. E4 n6 b* ?6 O
) y5 `  o, u( b; U: b( P5．遗传算法具有隐含的并行性
1 r! g: B" v. s3 X: `9 v5 J  l; ~
0 v/ ~0 }/ Y. y遗传算法的基础理论是图式定理。它的有关内容如下：

- T$ @) h, X) w4 c(1)图式(Schema)概念
1 n' V* J, e/ n" |
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
( a: b( `; s; V: e# p, h2 g
' u6 M  \% k. B3 X2 e(2)图式的阶和长度

图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
/ C" T% r8 g4 T. y7 m8 g
(3)Holland图式定理

6 @( Y( a  U$ M9 S# a) s低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
* @% R7 v; R0 n" G4 [- p
遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

二、遗传算法的应用关键
9 ?2 ^( t2 w7 M9 I2 S) ?8 z' n- p
8 q& K( F" p! L+ R遗传算法在应用中最关键的问题有如下3个
% w1 C9 f( C% J+ P1 e
1．串的编码方式
" j; m! K+ I% n4 C* Y( J( c
这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

2．适应函数的确定

; f: k, ]' ~) n3 U适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
4 N: m5 ?& A5 Q  k2 L  |
3．遗传算法自身参数设定
: ]' |+ K; J. [5 R' n
遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

* }) z3 \- K  v群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
1 \1 L2 Z! t& C& I# K
三、遗传算法在神经网络中的应用

  {7 l4 Q) Q( y9 a遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
! @1 D" [0 V+ h: @
1．遗传算法在网络学习中的应用

" D. P. w$ H  U4 @1 x- P在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

(1)学习规则的优化

( V. {3 O+ Y4 b8 K, V用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

(2)网络权系数的优化

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

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

用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
) y- T5 ]# g5 s" E5 j+ e9 {7 P/ |! Y4 R
(1)直接编码法

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

(2)参数化编码法

, t6 @1 W  D5 I8 |" Y参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
: K5 v% _1 P( u3 w- Y/ j
(3)繁衍生长法

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

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

遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
! E3 g' X% d" Q! ^0 S, F8 L8 C
' x: p' H# s; z- x" H( q$ s5 S& Q/ z遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。