转（遗传算法）

guofuzi111

生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
1 H1 a8 Q' b3 s/ |
6 J* s* e( r$ }' W/ [2 D  i! S遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。
9 ^& M! ]# D* d1 g  u2 P9 `" O
; S- B3 B8 F* t& c6 w遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。
/ S' F# w7 R. C7 j4 G) m5 x
3．2．1 遗传算法的基本概念
& f$ g/ U! A$ J7 U$ D  W
5 l( G2 ^: ?/ m: B+ ]遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

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

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

, O# K) _' Q! O9 U) y- A$ _3 {; S一、串(String)

& k# A% G  R" g1 M5 n& ^它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。
7 c0 D( w# ]6 r
二、群体(Population)
: s7 _& D; p& M: y
4 \1 _$ j9 j; c6 b# C个体的集合称为群体，串是群体的元素

三、群体大小(Population Size)

在群体中个体的数量称为群体的大小。
8 D* ?& c. H7 R+ F/ G3 X+ }1 u
四、基因(Gene)
& y, c4 B9 j) G; [4 |
基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

五 、基因位置(Gene Position)
, b  c! ~+ M% s
一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
* N5 _6 h7 F! K
5 f) R" m) |; h0 e, D+ b6 S- l六、基因特征值(Gene Feature)
! n- B. z  s! W' G
在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
6 X9 u  K8 _: D# `- I0 p8 f
七、串结构空间SS

& [& E% g+ q( m0 V* W8 v1 k在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。
: J! T2 k: K% `1 Y  q* F& z, F4 X
八、参数空间SP

这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。

九、非线性

  n- S7 o8 T+ r它对应遗传学中的异位显性(Epistasis)

十、适应度(Fitness)
2 s* W/ j( I8 k, P( A. [! W& W9 ~
表示某一个体对于环境的适应程度。
& r, z" f$ q' q
遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。
. o: @1 O4 _/ |0 V
3 Y; {$ v$ O. S  G( B  J1 B3．2．2遗传算法的原理

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
% W/ D1 }% ~, N
1 ?' N* c& {" s  L" k, R6 \一、遗传算法的目的
. C/ y% q% u# k
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：

& V5 o# q: p+ O+ _: H4 a( h; d考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

1 Z. s1 Z* d. c+ V/ wbi∈{0,1}L        (3-84)
+ q: w3 L5 G5 Q9 Z. j- T' _
: H- u/ F' Q& J; f, C/ D给定目标函数f，有f(bi)，并且
. ]  T0 \* L5 P6 g
3 {- ^# G& ]* F4 ^2 i0<F(BI)<∞< P>

同时
) W  N: S4 {5 U; [) ^. L
f(bi)≠f(bi+1)

求满足下式
- L6 L$ J0 E& q* Y, f( }0 R- m
max{f(bi)|bi∈{0,1}L}
" n( Q& I7 A3 N: D& a7 j! a4 f; U
的bi。
3 d; \7 V( c+ Y2 j6 b# w
很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。

二、遗传算法的基本原理

, l2 P5 N4 A' d+ |; {% v! ~& h长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
1 `8 O* ^3 z& H9 a$ D' J% T2 q
1．选择(Selection)

这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。

2．交叉(Crossover)
3 Y! F) M$ T  g- J3 D
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

3．变异(Mutation)

9 @# B& G& J, f; N- V. a这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。

遗传算法的原理可以简要给出如下：
; ^" m- S2 k' n  c0 M0 K
choose an intial population

! q, F/ K1 T* u5 [determine the fitness of each individual
  G* W1 A% G" }. h8 F  a5 n
perform selection

repeat

4 k# j7 F. ~& m- G( O: `4 S& J    perform crossover

    perform mutation
* A" S" {' a8 ]0 e; u% P
6 ~8 l; j9 R  ~    determine the fitness of each individual
0 ?$ \* b* {- w1 ^5 ]) P
- \7 G& D' O" _) e1 d- b8 F    perform selection

until some stopping criterion applies

这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
+ V' ?' t/ @/ e) ~# H( A三、遗传算法的步骤和意义

/ ~+ w6 o+ y2 {* C1．初始化

% M2 ^3 s* ^% Y0 }2 z" Y+ g选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
! e; X2 l" I# I% D# y( {; ^
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
7 G9 ~9 ]/ o/ u( t8 C- I1 @
7 d  _! T. E( ], I. u8 ]2．选择
: p$ S3 B3 ^9 T# p% P) U
+ }# u7 Y7 f) m. N9 G根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
) d% t4 @  |" B- H
给出目标函数f，则f(bi)称为个体bi的适应度。以
$ t3 |* M5 v4 H( r


为选中bi为下一代个体的次数。
. K( l6 W$ j- A* I3 o
显然．从式(3—86)可知：
9 i9 ~; V6 c- d5 ~4 {/ _
- m; V8 K! y1 L) o8 Y7 k7 z(1)适应度较高的个体，繁殖下一代的数目较多。
* E' M5 b3 c2 o1 m% E
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
  S: e3 F3 W6 l( O
' |2 G4 f/ x$ p' h; ~这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
! t& X( a4 @! }
1 }8 }0 n, k# @3 E% _" m7 ^, W3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

7 j" H* ^* P; {1 y' m$ w. `例如有个体
* k& l( F1 m/ l, o$ x& C+ ?" E
3 {1 d' F' ]: ]( w! \* f$ IS1=100101
, O! T% Q3 `% Q- a
9 T9 P! f% n# f0 e1 b: C) C/ {S2=010111
- h- f1 C4 j* n' y, D
3 N- c$ m& V+ V6 v选择它们的左边3位进行交叉操作，则有
2 P' a/ f! j: F3 }2 D
S1=010101
8 M4 ]0 q5 S  ~/ ?2 T
1 l' ~5 B3 s- e% j: z! QS2=100111

- i7 q# g8 J& @% I" H1 M' o一般而言，交 婊显譖。取值为0.25—0.75。
: m- ?6 [7 j6 w. x
4．变异

/ C* d1 y2 p" Z# u) s" ~: `3 X根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

例如有个体S＝101011。

1 l0 b; w; m; p# q  Y' b对其的第1，4位置的基因进行变异，则有

S'=001111

" X. E3 z" }) P8 d" ?  P! Q5 x单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
" O$ G5 f- F( f9 j3 t2 \6 ^' A
5．全局最优收敛(Convergence to the global optimum)

当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
4 M4 c% X+ l5 R6 }2 I
图3—7中表示了遗传算法的执行过程。

; @0 c2 f# R. m! p3 i


! K: w$ O$ r; J' n0 X% T# L图3-7 遗传算法原理

/ [# Q) I# Z4 R5 ?, @5 s& o  `& P3．2．3遗传算法的应用

  r# @, V) d5 V* _" s/ G9 s8 i6 a遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
1 ~+ ]; H$ }7 J9 i8 F0 g, J
一、遗传算法的特点

' m* ~0 ^' }. N0 U8 e! i; d" f1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

0 n) N5 }6 {1 @5 [) m这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

" ~( z( P' b" a: d( r+ `由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

, r" S  e' S, j, n3．遗传算法有极强的容错能力
; W* \) |1 r6 Y& b5 E# z
: @8 Y5 l! A7 V  L* C遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
0 i+ @% P, h+ w& T4 Q, c. F6 J; z  y
0 ~3 U+ r5 r. \) _# M- h4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
3 F. R5 G9 o1 e
5．遗传算法具有隐含的并行性
4 g/ }; |2 R0 i7 R
- Y$ b% o' Y- ~% r& G$ ]遗传算法的基础理论是图式定理。它的有关内容如下：

(1)图式(Schema)概念
' k5 F4 O, {0 }  X0 @
1 X# q3 d3 ]2 v- e8 G一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

(2)图式的阶和长度
: h0 q  _# d5 R$ ?3 d& H" s
# z6 O) o2 Y: \图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。

4 ^4 I4 C1 D- t' a: j* Y(3)Holland图式定理

# P& S/ l# X2 Q# n$ @4 b  ]低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
. }8 Y2 O. n$ J- j0 Y# O
遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
- _; S- {  l; g
二、遗传算法的应用关键

7 B+ k9 R: O, `; Q: Y+ [' p% |# T遗传算法在应用中最关键的问题有如下3个
# ?+ z. {# Y! u5 B
# T& |5 w3 V# Z/ a: |. x/ l1．串的编码方式

这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
3 U5 V# I6 q# @
2．适应函数的确定

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

/ y$ S) j5 P6 {- h2 F+ N3．遗传算法自身参数设定
& M. m0 }) d8 c  m* i+ A
! N' A5 R5 c  ]% Q! |- Q7 y遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
6 m& v. ~8 t1 y4 ~1 l; u; p& ~
8 Q, M, J2 Q  X1 Z群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
2 {  ~* z" m' B# |. P& I# }* t) x
! w% f7 @: S+ R  X三、遗传算法在神经网络中的应用

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

1．遗传算法在网络学习中的应用

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

/ I& Y* x7 T" r# u  Z(1)学习规则的优化

9 f. c- b, i5 q6 [1 p% T0 G用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

(2)网络权系数的优化

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

8 c4 Y5 k0 J8 l, o2．遗传算法在网络设计中的应用

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

(1)直接编码法

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

2 ?. u" z; j5 t7 ~6 Z, p(2)参数化编码法
  h' N* D3 x5 ~" i. G
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
1 ^7 k) X' H9 }! u. b, ~+ E% Y0 s4 P
(3)繁衍生长法

这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
* n1 J4 g# b  M& [' @; `; w8 n4 `6 [
% E  G: `. C5 Y% s8 _+ F3．遗传算法在网络分析中的应用
& g1 q4 M$ c( b: ^0 p6 }8 `
遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
; P9 \1 }  ~  ?; i, r9 n5 I3 Y
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。

三、遗传算法的步骤和意义
1 I; p2 g# J* C7 i- o5 r
1．初始化
# l" j; A9 [( D2 n4 h; ^
% e8 K; i4 k, Z选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。

: Y; b" X; v! V" Y1 V: \通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
% l, I$ G) t. \! [7 h
2．选择

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

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

, g0 @$ p$ P' g' v" F. F

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

: W0 ^- u/ I) v5 U" }显然．从式(3—86)可知：

8 R, J. C& e+ p(1)适应度较高的个体，繁殖下一代的数目较多。
, `/ [; o7 [& o( `/ Q1 {; t  s
! D0 d) t4 ]1 i* m(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

8 _. g  P) e4 ^0 n$ E# L! @, J6 M这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
; c5 l5 R- I. B
3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

例如有个体
) C& A: v3 X1 i" E
  \# H+ D( p' cS1=100101

8 f6 ]4 }/ \5 K- P- f1 V7 ~1 K/ wS2=010111
. w5 O2 x+ a" x1 R+ k& {
( t. i! B+ @6 m2 S: s3 T选择它们的左边3位进行交叉操作，则有

S1=010101

. ^- P3 ^0 J2 x! P& N# M& PS2=100111

* i6 L4 t" j4 E3 y一般而言，交 婊显譖。取值为0.25—0.75。

/ Y4 S& |& n' \' x4 n- i: e4．变异

根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
; \8 m& P) K# P9 X
例如有个体S＝101011。

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

5 u' w7 b) h- h3 Z' g# \S'=001111
+ J% t& u2 ^+ Q1 A  A3 {8 `3 ]
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
- B" t. t6 O9 k/ D7 Q
5．全局最优收敛(Convergence to the global optimum)
, n, J7 s* a$ c! W, P* m. ]- ?( c
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
$ X( M( \! P& \7 b! y
0 [  N- K9 v3 {+ W0 e' @" b( Z$ b图3—7中表示了遗传算法的执行过程。

. _) A% T9 [  X
- b0 Z6 w8 c, q; V- G

) f! }, `: `0 W' x* Z图3-7 遗传算法原理
, m( |4 h  ?+ t. @& D9 Y5 X( T
3．2．3遗传算法的应用
  X" b3 F/ N0 I- t7 m
遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
4 L& L  w: N1 Y* _' H% m) A( v
一、遗传算法的特点
6 W. c, ~  x1 T% X2 H% p4 \) {
' j; {2 o# r1 N; D& o; J1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
4 @8 n, I; ~4 ~5 C. ~6 A4 C- j- m
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
; u& N- j8 L' w- h2 f: y9 J" P* b
2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

3 c0 {/ D" v8 [% Z由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
) c- W- u6 p! s+ h! _
1 s8 l; K- d' l: \3 G3．遗传算法有极强的容错能力
1 O7 t( o) c5 g0 ~& j8 o
. O! D& j5 s; d7 B6 f& A8 X$ q9 j遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

+ O3 Q7 p8 M; u6 Q( r0 o4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

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

1 I2 Q8 O  A' X: I: R5．遗传算法具有隐含的并行性
' T9 F; U% s2 I; d! H
* w- {  x6 t( o1 s+ f! r* Q遗传算法的基础理论是图式定理。它的有关内容如下：

. R6 Q' C9 \' w/ D1 [0 ]. W' M(1)图式(Schema)概念
. `+ o( C! \- S: y
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。

(2)图式的阶和长度
% p8 u2 x; N4 p+ Q3 m' n
- U$ D: ~* X5 |$ V. n4 z% V图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
& i! _& V5 ], a, F5 \; R" o
(3)Holland图式定理

; l2 h/ e2 o- w4 U低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

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

二、遗传算法的应用关键

遗传算法在应用中最关键的问题有如下3个
2 n8 s+ ]) L5 A, `& o1 k: ]+ W
) l. N( v& [0 b$ E( o1 X- y1．串的编码方式

+ c8 }! C( d6 `5 P9 d这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
. L, {4 x4 G! g, g" r5 \5 z  Y
; w% Q4 U+ _8 e/ B2．适应函数的确定

0 @6 R) C% \6 |. T# K适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
- j' ~  {+ p& c- h0 d; {7 s
/ ]% |1 Q4 j0 M. u* _3．遗传算法自身参数设定
9 Z8 P. d* m1 T
: j0 v0 c; {6 ^遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
' I' h  K7 K$ [6 z) g4 S
三、遗传算法在神经网络中的应用
6 |5 q& f' Y8 z. N* p$ B
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
9 s6 g9 h( E9 q8 W& H8 q. Q$ k* p, H
& q$ U: r, J' |5 ?1．遗传算法在网络学习中的应用
( k  a1 R: }: Z& `2 L; Q3 D% |6 K
在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

(1)学习规则的优化
6 a& J" R0 l% H2 P
用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

% X. t* m% H3 U; p9 t(2)网络权系数的优化
3 P. y  S/ B; ]8 U
1 T  i. f# g3 G用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
2 b% ^, g4 Q" f1 V: S/ L
2．遗传算法在网络设计中的应用

; L' J5 B* h2 y/ }/ P6 X用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：

(1)直接编码法

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

8 ]- H9 n- E# S+ ~(2)参数化编码法

参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法
) j1 [/ p: m6 [: J
. O$ O6 D/ i/ |8 y- D0 G4 K这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
4 F1 h$ |( A% u' k2 q
3．遗传算法在网络分析中的应用
. I% d5 _( a1 b9 {9 J
遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
" |* j$ c# h& o
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
  D9 H1 n) E) f# D$ L) K/ X

guofuzi111

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

lijunjason

学习 学习了

mingyu

适合了解用。

cxxa

希望提供代码。。