转（遗传算法）

guofuzi111

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

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

9 o  f- H9 E: U# {1 A- s; S, Q遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。
- o5 M- _. q, g# V, N! J8 [
5 [4 ^5 Q- U% `' J# L7 J3．2．1 遗传算法的基本概念
; D7 O- ]/ |8 J+ k
6 }% D- j! |# J遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

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

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

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

一、串(String)

# M6 z* j- `. d' _) y) M& k它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

8 ]  `2 Z* I5 r9 E二、群体(Population)

) D( W% O$ W* D# I个体的集合称为群体，串是群体的元素
) P' Y' R2 {0 l
0 \) p6 T. l) j$ F. F三、群体大小(Population Size)
: }) C; r- ^9 t  @$ {6 Z9 C4 N4 m
" l& e8 C% l+ Q在群体中个体的数量称为群体的大小。

四、基因(Gene)

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

五 、基因位置(Gene Position)
1 l& R! i7 K/ m8 ?1 x
0 Q! g. c/ r: t( L一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。

六、基因特征值(Gene Feature)

在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
* ]: i" p* C  ?
; c1 l6 J) f+ }2 J% I8 g1 R* F, w! \七、串结构空间SS
6 [3 @6 q3 ~4 c; E5 N* Z3 k4 b
& J0 ^2 B' Q, I  T  s在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

八、参数空间SP

这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。
! F* b3 R6 n) A; f  I+ w
  A- F3 `# d2 J7 J( }8 Q九、非线性

- U2 l3 w3 o2 N& M5 ]5 a& e它对应遗传学中的异位显性(Epistasis)
* ~9 f/ E. i/ [1 S9 k; ^, I
! z( {5 S# y7 h! l2 n十、适应度(Fitness)
, u$ d6 s5 `9 F. f2 S' p
表示某一个体对于环境的适应程度。
6 P( c. H. f3 k/ m) [
遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
3 E# `, c) a, I7 e& B
3．2．2遗传算法的原理
6 ?/ N& F& o  r4 c' y* ~+ v
遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
, k9 J5 `- l+ |) R/ H* Z' R+ ]# `
- @, J: d9 L# f一、遗传算法的目的

8 V6 W/ i8 e3 [# ?' w7 j9 G典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：

9 G# ~# l) R4 H! v4 P考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
9 P: t) q) f6 v- `! [2 m
bi∈{0,1}L        (3-84)
: g+ F. |; A# Y; [" r4 S  m
给定目标函数f，有f(bi)，并且
2 q7 A0 m( ~! [
0<F(BI)<∞< P>

8 [# l! p, B# F7 ^, ~8 Q同时

f(bi)≠f(bi+1)
- H. A6 P" f3 p% B% q% _: C
$ ^( l8 P  l: }求满足下式
  @" T4 n* R' f( G! }/ Z
max{f(bi)|bi∈{0,1}L}
% Y; y$ M1 q/ E6 g
- f' i$ G# f, H; ~$ H的bi。

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

, _0 M% \: X) q& f' q' a+ w8 Q. I8 E二、遗传算法的基本原理

长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
! Y. A% u1 J# j% Y5 d( o
4 h" r; M; g! {1 h4 A3 m1．选择(Selection)
# A: j8 q8 z: q6 M" ?0 \6 C( L
  q( l/ ^/ n" `6 B1 k* T3 K这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
% @# M4 O7 h& P; i  s" x7 {
$ s0 T2 u7 c) Z/ n# o% G8 ^- X2 ~( s+ F2．交叉(Crossover)
: |0 m7 {9 x7 r) r# M
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
+ Z* D; o" ^. t# f2 h
0 P, j  }) w: x  u4 M- C( }3．变异(Mutation)
: [, \" _% q8 G8 z3 o6 j
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。

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

choose an intial population

9 D/ p3 Z0 m' {0 T3 odetermine the fitness of each individual
1 L6 Y# w- u5 c8 w1 Y4 z
perform selection

! K, F  q: Y! k/ P, f- g& Z4 brepeat

    perform crossover

    perform mutation
/ i1 ]1 ^5 }' V* G
    determine the fitness of each individual

* ~& w4 x# j  ~/ [' m: ^: s    perform selection

% c7 h" D) l0 \' Y3 {9 d7 F& Xuntil some stopping criterion applies

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

  i' i/ C& ^$ l& m1．初始化
! q0 c" h' ~! `! G' Q0 g
选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
9 m1 \7 r4 p+ `& {0 R" |  E' ?8 x$ \
! o( O7 _, a2 B& p! U1 N通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
& @; l; D! X' o: v7 \/ n+ r( Q
5 T5 p1 g+ H: f# X2．选择

) j1 Q) B5 F+ L; h% f根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

给出目标函数f，则f(bi)称为个体bi的适应度。以
* j8 {- d; ^* @0 X! d( C  z$ ^
3 g) d1 d) K, l( ?' B
. e( V5 g) ?( B; A' Y+ t3 q3 ?0 ?
为选中bi为下一代个体的次数。

显然．从式(3—86)可知：
  Z+ U) g- D$ W$ \/ V2 k
  k" A/ f. L' @* ~6 x) [( D: Z(1)适应度较高的个体，繁殖下一代的数目较多。
, T- L+ f: V2 P; C
9 L2 Q2 p9 \) k) l(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
  W" a) H' s3 c  R5 c2 X9 m4 H
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

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

" S0 |, l- C+ p& R. g, j2 ~例如有个体

S1=100101

3 P& b: ^5 p5 j! hS2=010111
- Q5 B) o( f- Q9 s. J
选择它们的左边3位进行交叉操作，则有

S1=010101

% j0 h5 [/ G. [' i, G4 R+ P, LS2=100111

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

4．变异
: E$ l" V; y6 F, n' y( T. P2 |6 Y
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

! I+ E0 A' M3 ~$ g例如有个体S＝101011。
$ z, H3 ?* x5 T6 L, V5 P
对其的第1，4位置的基因进行变异，则有

8 j0 @0 A+ c' L  e/ {  j. @S'=001111

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

5．全局最优收敛(Convergence to the global optimum)
. l! v+ a4 \% ]% q! x
$ d. ^  k3 t! F, f' t当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
! I7 Q$ f" n' @! n! b
图3—7中表示了遗传算法的执行过程。


! B# x8 p8 p- p6 `

图3-7 遗传算法原理
. J) q2 b! }- b3 f3 s
3．2．3遗传算法的应用
7 @5 \! Z4 X- E1 M& L1 v5 S$ F
遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
# q1 P: o' f% E, C! z1 h
一、遗传算法的特点

0 p  s! K! J3 }! g! q1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
" z+ Y: f- \% v( @% d9 D" z
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

+ z. @3 q2 s( @1 v( B* ~2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
4 t- r7 O! r/ c$ J
: c4 N  u% J2 j: O8 J& h由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

3．遗传算法有极强的容错能力
8 X- Y1 E( U* t+ Y. p' N: I
  I1 e! G% d) U遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

0 g4 @) I3 Q6 H- @; e! o8 H4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
; E8 V5 w$ ^' k2 E( U$ u
5．遗传算法具有隐含的并行性

遗传算法的基础理论是图式定理。它的有关内容如下：
7 j6 V3 h8 x5 }: w
3 ~8 X5 N7 m4 v- j/ B(1)图式(Schema)概念

一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。
/ n- I6 Z- A1 a/ e3 R2 C, n, R( y
( X* v5 c7 d$ X# \0 @5 a, W(2)图式的阶和长度

: \1 o: H$ m8 S, n7 X% x图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
0 N/ B8 Y" w/ }( T2 n; B
(3)Holland图式定理
3 r" T7 T* F  A3 A# r1 y
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

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

, ?3 j! W7 q1 A2 w, X$ }二、遗传算法的应用关键
5 L# |6 K3 }% T' h/ i) X6 H/ D
( S$ T! c5 ]: @+ f3 q! }8 p遗传算法在应用中最关键的问题有如下3个

1．串的编码方式
0 ^5 R. R4 A. F$ |. R( d& F8 H! j' R
1 f5 D8 J8 |. A# C1 d这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
  ^0 m$ t* ^' A( s* r
2．适应函数的确定

7 I% Z# c& z3 a5 ]& `适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
( O7 G- k# L; t5 t' j$ h. B
' \5 d& o$ [$ F% O! r! F" p3．遗传算法自身参数设定

遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
5 _/ y' ?# g9 F4 A2 [( }7 g
4 K2 S( a# u2 k+ }4 ^# Y群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
+ q8 E5 s$ Z+ C3 y+ K
三、遗传算法在神经网络中的应用

遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
9 b3 u! X8 R# l
; p+ ?( _, t) z7 S1 b1．遗传算法在网络学习中的应用
4 _( @' J+ @( v9 A: E
在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
( z7 t# y8 `8 ~7 t: S* I  K
(1)学习规则的优化
: }2 O& _- G. l: P7 h
- O, H- {. y5 z# q2 a! \* Y用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
4 R7 a' Q7 D" U+ d, Z( Z
(2)网络权系数的优化

; \( o2 V# p7 f: F2 F用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
% ~& n  n& D6 ^2 c
5 P6 z* O4 H: u2．遗传算法在网络设计中的应用
! Z! b; j: A8 r8 T
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
1 a$ g+ [8 f; J; V7 u& Z
(1)直接编码法

这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
; Y0 E  ~4 b" b+ w* Q' }# i) Y
(2)参数化编码法

, x% Y; ], R; `参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
3 J. Y  k( t; q: O+ m- [5 t' `" d6 T
+ ~3 Y- S. k* i5 I/ v+ a(3)繁衍生长法
, M, c' t. F# C7 ~6 n  V
这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
2 a6 V+ o* e7 ~0 S- a
3．遗传算法在网络分析中的应用
1 s# L+ W/ u0 C) `
. s' \7 ~" S8 S, b2 Q% h遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
7 [% x3 ]" D* l1 ~5 S6 Z; t
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
" ]0 g0 O) W- ^8 G! I

" f6 |( o: d0 @# Y: F6 |三、遗传算法的步骤和意义

  e% f3 [) O# X$ b1 a( [1 h1．初始化

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

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

2．选择
8 Y- _& j; F$ f
' A* M, B  W) U8 t* l根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

% `8 `4 _; B7 M, b  n给出目标函数f，则f(bi)称为个体bi的适应度。以


7 X% ~1 W# j  H) Z5 r) w1 X
为选中bi为下一代个体的次数。

7 y/ j" S6 A/ y5 j7 Z: x& i7 t# y显然．从式(3—86)可知：
3 W0 n# k3 K: ^% _% |, ^7 U
(1)适应度较高的个体，繁殖下一代的数目较多。

, a4 m6 A2 r; }1 p(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
, H& T8 B- M1 J& F3 N
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
! j8 ~  U( u, p  x2 Q
6 {5 e3 i' s* u" t例如有个体
* O/ n& x0 [  Y: P+ N- V% O
/ V, A9 J1 |* q% s2 sS1=100101
5 b. H, E2 |" |$ F- N- L( E
  U0 f& Q5 G9 c  E6 GS2=010111

6 y2 ], T1 `* _* o& _5 D选择它们的左边3位进行交叉操作，则有

0 y  y" C0 C- e! {4 V$ x2 cS1=010101

S2=100111
( w' f( x5 t# E& |' Z' j
一般而言，交 婊显譖。取值为0.25—0.75。
7 ]0 V8 d3 K3 u  D  b
/ p, |6 p  ~  J6 w0 `4．变异

1 w0 f9 b+ l- }1 a* m& e! e, c7 I( X根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

6 X6 l5 u& _  p* s. E例如有个体S＝101011。
3 M& |- r8 T! }  H3 ]
对其的第1，4位置的基因进行变异，则有
$ ], n2 T$ O$ m# X9 q3 o" Z& R
. \& e: I- i/ `; x- [2 nS'=001111
: f% ^! |' ?0 \$ G5 S
6 s$ Y, w0 h' b单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

: k9 L3 ~0 S4 ?1 G( @5．全局最优收敛(Convergence to the global optimum)

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

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


4 {9 B; J0 k- j9 J5 a! k  D
: `# m! e- x# ?# M* }- c
2 w1 J) r; C$ R$ W+ L图3-7 遗传算法原理

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

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
! l* o8 ~2 |" I/ s
: }% w) A! W0 D1 i* j; O! t) c一、遗传算法的特点

1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
# T9 B, g7 V  ?+ G  ?9 y1 {
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
0 L) t! a- ]& l. ~5 @7 D: P
. q. f0 B) L5 [- x$ P2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
& F2 T4 d" c5 k& l; B% }
: a0 j* O/ O( E2 p4 i由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

" u; W. k3 }  \3．遗传算法有极强的容错能力

' D0 Z$ k# _8 U0 N8 D6 D7 n4 Q8 \" ~遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
: n* d& m2 f& r' |5 W' U( B
4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
5 e! i% A- p3 u
% Q1 u  z& t: x# T5．遗传算法具有隐含的并行性

' \( @  H" O( A/ t遗传算法的基础理论是图式定理。它的有关内容如下：
" K; k& _* Y* V- @3 y1 A: a5 N
  a! V) c5 ?1 O- s; b  O1 q! Q+ ](1)图式(Schema)概念
1 S0 Y! L2 P# V
0 b0 q0 q+ \- y+ F- c. g1 [% z4 i一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

(2)图式的阶和长度
) Q/ D$ b1 i; A3 v% \/ n' m
7 {" ?! j8 f% q3 N3 c% h图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
1 D, Y2 T: B; U
(3)Holland图式定理
3 f% K( j! b, ^8 ~# m: s
6 a/ R. ~+ Z# x, f1 f0 z6 y低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
8 D" l. k& {9 m) |2 m3 C8 x
# w) U# ^2 B9 K3 \8 _遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

二、遗传算法的应用关键

遗传算法在应用中最关键的问题有如下3个

1．串的编码方式

  G  k3 [. r" y2 d2 S. n这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
) Q1 C1 L! T. e6 O1 r3 L
2．适应函数的确定
( E; I' h7 u# S0 j, [
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

5 Z) H$ X  a- B! ]$ x4 l3．遗传算法自身参数设定

& Z. [9 B- O" t, O2 H. y4 }# Z% a% a遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
; ~* I7 y. t8 m; \! Y$ j" Q% O$ Y
群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。

/ [; `1 f. N0 ~, H8 z三、遗传算法在神经网络中的应用

5 g, d- X1 y- \6 M5 C: i遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

$ X& z, v: Y# c. _! Y3 M1．遗传算法在网络学习中的应用

9 m; U' @( I8 _: A6 b% \在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
0 E( Y! ~: o6 k4 x# U
7 P! x* F% R3 p8 H" |0 E. x(1)学习规则的优化

用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
2 b8 e( i, C5 V6 P. ?! e% e8 A
  O6 E: g0 S8 q  L7 i(2)网络权系数的优化

5 S8 U+ Z( W* ?! G用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
1 L" `, G# V+ i/ |7 |1 m! Z7 I4 t
2．遗传算法在网络设计中的应用

3 K5 `+ g1 S, m3 l! s4 j- m用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：

(1)直接编码法
5 O1 h7 J% o3 e: F. P! V
) B8 b( h, f) F" G9 e& S" a+ Y这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

(2)参数化编码法

( O; Q3 s* _9 z/ A$ p; j2 D参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
6 s! t1 R! V- h1 p8 v. t( U5 W+ T9 V
% w7 a  C2 b. V(3)繁衍生长法

0 f- k- `% l7 L! o/ _这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
3 u/ w2 K- t+ |9 _) R/ `
& x8 b) o. z  b" p4 l' D3．遗传算法在网络分析中的应用
: ^$ ]1 s& H7 H/ J  |
% Q) ^/ z+ U! t$ r0 z/ z% X3 t遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
' h' P3 ?2 C( I# _
; V% s1 ]5 Z2 o. f遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。