转（遗传算法）

guofuzi111

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

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

遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。
) e- P9 r. H1 _4 U. P, j
0 J" m) a+ T. A0 A" J+ \3．2．1 遗传算法的基本概念
, c: Q* o8 s0 Y9 ?* \
遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。
+ A0 i9 ~+ o2 O8 z4 J& m  R+ `
Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。
* ?5 Q/ R5 J6 {$ i5 o1 W
+ H* O  [- k1 Q5 o" Z% e% uMendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：
9 C! q* g4 C4 n& t2 Z. {
$ ?8 {- v1 ~5 L! I一、串(String)
- c( Q% y$ |. t7 {, b" k
& l( v, u  K/ P0 S' [它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

* v; B3 y0 {$ a; _( W二、群体(Population)
; Y6 E. r5 F# u" T' ~8 C: C
& P! f' k+ X$ u! D8 f( v个体的集合称为群体，串是群体的元素

三、群体大小(Population Size)

在群体中个体的数量称为群体的大小。
5 a4 Y; U1 U9 w9 w4 ?: D% z
四、基因(Gene)
0 ^) S! }$ c6 m$ p
基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

$ k* E8 n' z1 Y$ b$ k五 、基因位置(Gene Position)
3 P+ @$ v2 z  L8 P4 T7 c
一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
  b2 U$ Z  z9 o$ m6 e
( J1 Y9 e* V: o1 T' y/ ?: U5 j2 s; N六、基因特征值(Gene Feature)
6 {( }3 F$ Q7 ]9 @$ A$ i
在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

) C6 J; j6 ?! |# A0 z七、串结构空间SS
/ h1 `& s0 \* g- q. J
在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。
* r1 D' Y. w; J- \. v& `
八、参数空间SP

. G4 Q$ Z' F6 ?( Q: g这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。

九、非线性
4 A8 }, h8 D4 U; I3 I! g# p$ H
它对应遗传学中的异位显性(Epistasis)
$ r/ w; \' {6 Y8 X# i1 L6 i& h
十、适应度(Fitness)

- y; H. L/ s+ k表示某一个体对于环境的适应程度。
  F, [% U1 r9 F9 B+ B
& X. q& L3 V+ e1 \( V- T' H遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
0 h' ^2 ?/ N  o, w/ T( O
) m# [6 [9 p3 \& f, R/ Y3．2．2遗传算法的原理
8 R8 @1 H* X; }1 d
遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

一、遗传算法的目的

( o! e4 t. k6 y6 A6 Q. c典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：

- o( S) h. o8 c1 D: g, o' U, p考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

+ T6 Q8 Q& I8 S' tbi∈{0,1}L        (3-84)
+ d- D  Z- U3 ~5 l* f3 q* m: K( \& v
给定目标函数f，有f(bi)，并且

" h7 I8 z% n3 }6 Z0<F(BI)<∞< P>
! s4 P! U& \9 b4 ~: O
9 f8 [0 V* b* W( ?! A. I: V同时
, ?8 }/ |3 G$ L
f(bi)≠f(bi+1)

求满足下式
: h% s" T9 E  l. V7 D0 `: C
max{f(bi)|bi∈{0,1}L}
* Z6 t4 @; S/ N5 \3 t9 I; C
的bi。

很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
7 X0 h  X! F$ m1 Q7 I
# `) J2 O2 p& g9 A/ D, J二、遗传算法的基本原理

长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
3 L( u8 p3 ^, E' h
. X% }( u* @+ F6 [1．选择(Selection)
) c" n) s4 V% C( h/ i
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
  U( U( F( {- J
' y6 k7 N/ Y0 t, Y2．交叉(Crossover)
( n' x: G; L5 d
- a( _7 d0 w  ]1 u# \; r  Y2 U* W这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

3．变异(Mutation)

这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。

遗传算法的原理可以简要给出如下：

% G8 V0 i! e6 @* z8 }choose an intial population
( `, z; Q  x. _+ T( u; H
; d7 U# O# x. m4 b8 _5 {. ]determine the fitness of each individual
' X- p( D- P- @1 O- W( o
perform selection

- b  L- p) c4 m$ k' a9 C6 G. @repeat
: Q+ g4 c% q2 F9 S& M
    perform crossover

    perform mutation

    determine the fitness of each individual
) M2 s6 d4 ]8 L1 s" Y7 f8 X
    perform selection

" n9 [  _/ p/ }until some stopping criterion applies
: o$ r& G# {! j- j8 L9 S
这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
5 j: \, ^- L) Z( u" x( S三、遗传算法的步骤和意义
/ M! _$ q& s& p- `$ ]) }2 Q5 f- u
1．初始化

! ^# n; a0 s# b4 S$ p8 r, P$ E选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
/ N& v8 ]  C4 f* }$ [, ]+ H
0 Z* L. D1 @& J$ `- T( K通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择

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

给出目标函数f，则f(bi)称为个体bi的适应度。以



为选中bi为下一代个体的次数。

) C4 R  m& }' @/ X) D显然．从式(3—86)可知：
. B1 y1 s  r/ I$ j. S7 d* z* R3 h
(1)适应度较高的个体，繁殖下一代的数目较多。

9 b/ B5 r' z% b# ^& s1 U(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
% W% z+ l1 [- N5 g# U
* r( [. C# x  a这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
7 H5 Z* j9 H; e# L% c
2 _7 X0 W+ q2 z3．交叉
3 _& \: ?' j) p7 u对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

$ G3 ?3 u7 I) X: ^6 y例如有个体
6 ~! @5 q# M# ?0 z
/ b* t: x5 d) C" \5 A- W  P9 |S1=100101
4 G9 y$ ^; k/ b$ B) Y' n/ {. K8 @
5 ?) `! t5 _; cS2=010111
6 r& @" Y' h# c; S5 g, z9 ?
选择它们的左边3位进行交叉操作，则有

) ]& K3 N9 K* K2 WS1=010101

S2=100111

一般而言，交 婊显譖。取值为0.25—0.75。
) ^: E' G5 y; \# _! d) Q- ^; m
$ \$ J1 r1 G5 C( k4．变异

$ M3 d% G/ f' e5 n: \$ m根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

) }$ e) o# T( s. H例如有个体S＝101011。

对其的第1，4位置的基因进行变异，则有
& v: N) `* \' U* n! Y
S'=001111

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

. h7 x- m- Q' {0 `6 e1 X5．全局最优收敛(Convergence to the global optimum)

当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
- n2 J' K% W) H$ n
* d& V1 ~2 Y3 a/ C, Q/ Z4 @6 s3 x图3—7中表示了遗传算法的执行过程。

% c: R  ?: c( X! |8 _/ d& Y9 H4 Q
9 }6 k8 t7 P7 q2 p$ K' q

- U# e# w, `2 G9 E图3-7 遗传算法原理

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

' @* K1 a% H  U6 d遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
* f+ u) s* ^/ m1 B
一、遗传算法的特点

$ O+ n, F- ^2 I# o# S4 h1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

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

2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
- F5 U+ n+ h  K) x: G$ e* g
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

3．遗传算法有极强的容错能力
1 }0 u1 D* [6 x" W% B7 I
( p) _8 [) g# g& B8 N2 k遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
" n8 M' Z7 N$ D
4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
' S: R8 r/ ]9 ]4 J9 T# z! j$ h6 R9 i
. k; \. C" e6 m. t. `5 [  b4 U这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
3 V7 C  k; P3 c: X; @4 w5 ^3 z! q' R
5．遗传算法具有隐含的并行性

, ^0 l9 w+ }& ~2 L2 B# a遗传算法的基础理论是图式定理。它的有关内容如下：
* e/ A' A& m& z5 q/ k6 H' g
# n+ C6 h& X* Q3 y& l5 U, T(1)图式(Schema)概念
  ~9 f5 V, F: B" ?( U3 X, q
) c9 N$ O: i( c* B( G+ A+ v一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

(2)图式的阶和长度
3 L" g8 s# |/ N: r+ B  V: O
( b: t& K& H7 f/ k( r+ v) j图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。

(3)Holland图式定理
. Q) I* A- K" `- Z' s$ m
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

* B) r  h# d' r& n$ m2 T/ a遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
- t2 k( F) P# `
二、遗传算法的应用关键
5 @9 b* C7 D* T8 j: m/ A2 B- P
遗传算法在应用中最关键的问题有如下3个

' D+ G2 i9 G# j  K0 e! g- e  V1．串的编码方式
" a! C# `. E8 N* x6 ]
/ b% U8 z. Z0 R5 h这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
* m7 `2 y0 D9 q9 J* I8 ~5 j3 Q
& E& W+ j5 u( K9 H2．适应函数的确定
, e, W& y0 x! h" F
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
, \/ {1 L1 A0 i9 H
. v! n/ x7 [) a6 M9 g! s8 M2 e3．遗传算法自身参数设定
" p: u5 V& ~0 e- U) [6 ?
遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

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

" ]2 z6 g- G  A* S" A/ C7 f- W三、遗传算法在神经网络中的应用
+ b/ a3 {3 G0 V- l. C$ s
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

* s) L1 }' l$ V$ T. E- w5 ?8 T1．遗传算法在网络学习中的应用
. V. e+ J# i" C2 u1 ]( L+ M! Q( E; k
4 [! W! \* l' }$ ~3 b0 A' r在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
8 z% Q: M1 e( G/ J0 O. E
. ?( V' `+ e) }% h(1)学习规则的优化
- f! {& g3 m1 x3 w6 x( N
用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
: q- B# _) X6 r$ m& n5 g
(2)网络权系数的优化
- w- u4 F$ Y" i& L
用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

  x; B% a% Q" s+ _% ^. t5 [2．遗传算法在网络设计中的应用

' P- J& ]' l! H3 z) s, G( t用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：

(1)直接编码法
7 Y6 ], K: Z' I# K7 a
这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

(2)参数化编码法
2 q# U5 a. F/ X* U1 {8 c
& B( d& @+ H" p( q$ k6 \; ]参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

. p& h* ~5 w! c+ j(3)繁衍生长法
7 F2 K( m/ s' J- \, ], |
这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。

3．遗传算法在网络分析中的应用
" Z+ f% j2 g) H0 b! e
% W' ~# P, U/ r! H3 \$ \/ R遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
. Y% H5 |% ^! ^0 S( v7 c- o
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
7 F  V+ C* L# ?  t& X; r. t
8 \8 ]; Z5 T* I; p/ y* G: ]

三、遗传算法的步骤和意义
( Q: A7 |. A+ C- O$ v
1．初始化

" }* [2 w# B5 K. v) m; N选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
+ m& S& v+ F- v3 r
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
, h8 `% Y: n  [0 q9 P
5 @, q6 _4 i- m8 D2．选择

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

给出目标函数f，则f(bi)称为个体bi的适应度。以



  n  |/ G1 B! T, w' d' }# b为选中bi为下一代个体的次数。

显然．从式(3—86)可知：
' f4 L3 C0 _$ C( b' @$ J' X
# _6 ?$ J( [0 Q(1)适应度较高的个体，繁殖下一代的数目较多。
6 b0 w1 U, O. z: X% [; B
! w' b: e3 X6 J9 ](2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

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

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

例如有个体
$ _- A, @- C4 u$ c/ ~
S1=100101

S2=010111
1 h: K' s- S1 Y& _
选择它们的左边3位进行交叉操作，则有

S1=010101

' P3 P1 A  v) p9 V1 j8 BS2=100111
/ S$ l  Y0 ~3 U5 C' Y9 }
9 H( ?0 U4 P2 X4 c. z& D7 k一般而言，交 婊显譖。取值为0.25—0.75。
4 |9 r: C, @+ S
  u2 L' G% }- ?9 Z/ t, a4．变异

根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
8 J4 G: q5 h- d
例如有个体S＝101011。
" H- X1 Y  B2 Q. `1 X, w0 i$ q
2 m8 G4 G. b+ y" @# ~7 b8 [/ d对其的第1，4位置的基因进行变异，则有

S'=001111
6 G" R1 [! g; Q( g
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
: Q# V7 t# {- S% c% d' J6 @8 z$ n
3 _  y) v5 D6 C( u5．全局最优收敛(Convergence to the global optimum)

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

图3—7中表示了遗传算法的执行过程。
+ J! u6 e4 u' a3 E


7 d3 h* C0 [* b/ A  B& j
6 L2 {* P4 b+ Q4 d% C* X图3-7 遗传算法原理
- J. g1 O+ n, |5 f. h& }# u+ C
% R1 u  Q# y" h* [$ W9 k3．2．3遗传算法的应用

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

一、遗传算法的特点

1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

0 S4 H7 e/ W  D% T; Q% i* t这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

, U- ^- E) ^" u; e- B* U2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
# Q6 C) l& r% w( z" f$ Z
; ^! a$ @* V9 r( g; i3．遗传算法有极强的容错能力
$ y+ R2 d& p" {
遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

* M) a" ]7 a. R- P3 R0 f- _& s+ h) o4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

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

5．遗传算法具有隐含的并行性
6 N5 V# G/ S% N6 R
遗传算法的基础理论是图式定理。它的有关内容如下：

# l. A  S& m  {* a2 J' T: t(1)图式(Schema)概念
: p: Y4 U3 r9 _+ `% ^# @* u1 m
: m1 S7 j$ F4 @+ G  ^7 z一个基因串用符号集{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。
5 t0 j# Y+ e) \4 }
+ @3 o1 p* r; l2 o0 N* j4 j(3)Holland图式定理

% X/ v/ S+ w% f# N& o/ {  X' P低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
% g9 e1 ~2 {; U
二、遗传算法的应用关键

& o3 u) y* ^" e) T, K- {遗传算法在应用中最关键的问题有如下3个

" u; t( B1 Z7 t( e1 R8 b1．串的编码方式
0 J( ^: |2 u# n) \8 l+ W
2 `" F2 j" n# C  o  E  p$ d这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
& X' I9 p8 {/ C( g, u& [
2．适应函数的确定
# P: S! g2 A9 P+ i; K6 s
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

, A0 z: D0 g2 i* {7 k) [& u: ]" k3 c3．遗传算法自身参数设定
% E  |$ R' m; w* U2 ^$ K# l
9 S2 W3 K5 q2 d& g遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
+ q$ ~* k0 @, O* F* m
群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。

三、遗传算法在神经网络中的应用
9 [' T3 A/ @' B
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

1 n6 F  c% r) U2 E" ^! V4 o1．遗传算法在网络学习中的应用
3 A1 [& u/ k0 e% i+ Y/ e! y& e
在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

7 x* X/ l; ?4 r0 f1 }" c; |(1)学习规则的优化

& ]: ^- y+ T5 H  ]  i& j, c# E用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
- I) X$ ]7 Z, i0 Q
! \1 W5 s! I5 I1 O. h(2)网络权系数的优化
/ w  i$ }) \9 P% _: G8 M; N
. T$ K: C& l! F) n5 y5 ~7 `& d用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
! A2 o! F: D4 ~2 g* c2 X% ^
2．遗传算法在网络设计中的应用
) }% @3 y0 S- b9 l+ j8 t& ?# S8 F
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
  d9 Y+ ]+ I: Y' S3 ?- Q3 I: o; O/ ^
3 u5 \" }& n, A" _8 B(1)直接编码法
3 X2 }0 K* E! f3 l  ?, y7 N
这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

9 v+ @: Q$ d) j5 t( x8 {# D! l(2)参数化编码法
5 i8 E* ]3 t& C) g
, A' _7 H  E9 u4 |  y+ Q参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
' j/ [; w! I2 R# }$ D
(3)繁衍生长法

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

3．遗传算法在网络分析中的应用
7 D& H% f3 ?  J" l
遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
5 Y- W- B, W* c+ @7 q. R7 t
8 r4 A1 k/ l  J5 D6 o遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
' r) N+ `! }" ^# \; ?! y

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。