TA的每日心情 慵懒 2017-6-1 21:49
签到天数: 6 天
连续签到: 1 天
[LV.2]偶尔看看I
累计签到:6 天 连续签到:1 天
马上加入,结交更多好友,共享更多资料,让你轻松玩转电力研学社区!
您需要 登录 才可以下载或查看,没有账号?立即加入
×
生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
, }' O; A% [: y: y0 d w ' |3 u" y7 m+ x* Y$ g o- ]: w
遗传算法的概念最早是由 Bagley J.D 在 1967 年提出的;而开始遗传算法的理论和方法的系统性研究的是 1975 年,这一开创性工作是由 Michigan 大学的 J.H.Holland 所实行。当时,其主要目的是说明自然和人工系统的自适应过程。
5 U$ q1 U6 t' \0 I+ p, m4 @' M " h9 \$ `2 P3 _2 K2 f& M1 p: @
遗传算法简称 GA(Genetic Algorithm) ,在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中,现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样,都是对今后十年的计算技术有重大影响的关键技术”。 3 M- {! g4 _: b6 L0 ]
' q+ B2 ]" Y( U 3 . 2 . 1 遗传算法的基本概念 / c0 X$ @7 g! R7 z
/ ^. R9 }7 q/ g4 o8 ]; _
遗传算法的基本思想是基于 Darwin 进化论和 Mendel 的遗传学说的。 ; [, R0 ]. Y3 J2 w9 L3 B
. X# O) p, S, [7 m& e1 t9 I
Darwin 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承,但后代又会产生一些异于父代的新变化。在环境变化时,只有那些熊适应环境的个体特征方能保留下来。
- j# U/ t i/ p+ o: }7 |# E7 H
1 c7 q7 G. @: i+ w; {( p+ k& q Mendel 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中,并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质;所以,每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰,适应性高的基因结构得以保存下来。 1 _, y1 ]4 t4 X4 H1 R
1 `- W. |+ i% J+ i
由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法;故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下: % T q( W& U' ?- t2 l& H3 G+ y
& N9 W$ }! y) x 一、串 (String)
q/ D4 Z1 T( C. g # K( M) ]4 N4 X+ B) Z$ n
它是个体 (Individual) 的形式,在算法中为二进制串,并且对应于遗传学中的染色体 (Chromosome) 。
. N, y+ M! ~; h6 W' }5 G6 } u 7 P4 V, p; O; X$ ^& Y. D. |$ }
二、群体 (Population) 4 a' q# V! q( [$ a; g
, j& |! D' u/ G, ^
个体的集合称为群体,串是群体的元素 # r9 s- q2 I& x
5 A- I: n* l' T# P) |
三、群体大小 (Population Size)
0 y3 i& k8 c+ D4 Q0 k - A+ _1 w l& W( I* f5 l
在群体中个体的数量称为群体的大小。
! U; Q) [1 C. T" x1 r9 A7 c" [ . u7 L6 j. E/ ]! E4 ~1 I& C; t$ L! H
四、基因 (Gene) # [( X% u$ z3 o, ^1 m L |
" b" M. t/ |2 ]& d' I4 o 基因是串中的元素,基因用于表示个体的特征。例如有一个串 S = 1011 ,则其中的 1 , 0 , 1 , 1 这 4 个元素分别称为基因。它们的值称为等位基因 (Alletes) 。 1 c, C! S: Q7 j$ q
( v; r6 c, D- u) e
五 、基因位置 (Gene Position)
4 ~1 x, u& ~% ^- P4 i / x' c/ {3 Y8 w6 O4 r. K
一个基因在串中的位置称为基因位置,有时也简称基因位。基因位置由串的左向右计算,例如在串 S = 1101 中, 0 的基因位置是 3 。基因位置对应于遗传学中的地点 (Locus) 。 $ h* G j& P$ m
9 ~' R! |. ?6 H! ?7 Z
六、基因特征值 (Gene Feature) : g' w5 ^" x# P- A: j2 I
0 t" U( C3 b$ U$ K8 P) R: n* ~0 R1 y3 O 在用串表示整数时,基因的特征值与二进制数的权一致;例如在串 S=1011 中,基因位置 3 中的 1 ,它的基因特征值为 2 ;基因位置 1 中的 1 ,它的基因特征值为 8 。
% |6 Z( l" x' s1 Z- h5 B & k/ N$ l+ T* o7 w" @! @1 A4 O
七、串结构空间 SS . k7 R9 z. b7 v* c; E1 w
" x/ Q* k; _$ G
在串中,基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型 (Genotype) 的集合。 N( ^, y8 n# c" J
: H7 _$ O6 e" g/ L: [4 l7 _0 E. [( ?
八、参数空间 SP 6 \7 B+ u6 N2 P$ F7 _( H
" y2 V: ~: W! B/ j 这是串空间在物理系统中的映射,它对应于遗传学中的表现型 (Phenotype) 的集合。
) H- o7 L0 o7 Z' l" T8 i4 i 4 w& _3 @, W3 e/ w& n: K
九、非线性 6 k" o- J( N7 V* t: q
# f- ~" D+ j* \# N- G
它对应遗传学中的异位显性 (Epistasis) + b: V' M- C8 B& u
7 Q$ w. y, x$ B/ Z1 a+ Y% C 十、适应度 (Fitness)
# Q6 \5 T/ w3 n# e n 7 e) Y$ _' X+ B5 s& J5 M: U
表示某一个体对于环境的适应程度。 ; r, [% C2 H+ V
) q7 w0 m1 L* c) F 遗传算法还有一些其它的概念,这些概念在介绍遗传算法的原理和执行过程时,再进行说明。 ; c2 t, L: x6 T! [6 n3 r0 H# z
P7 t* H( o( g. P' |' V
3 . 2 . 2 遗传算法的原理 6 m' U$ I! _5 R& u, H# ^
) U* E2 B% }8 h* ]: T4 z" { 遗传算法 GA 把问题的解表示成“染色体”,在算法中也即是以二进制编码的串。并且,在执行遗传算法之前,给出一群“染色体”,也即是假设解。然后,把这些假设解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉,变异过程产生更适应环境的新一代“染色体”群。这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是问题的最优解。 ! t+ J5 b! Y: t( L8 u2 d' h
& g* ?3 K, |0 g 一、遗传算法的目的
! d9 G: K$ X! R% s( }
2 W: `, P% y- ], v 典型的遗传算法 CGA(Canonical Genetic Algorithm) 通常用于解决下面这一类的静态最优化问题: - c+ z& K1 n! f/ V
& l! \2 p) S, [8 z0 O6 B9 U
考虑对于一群长度为 L 的二进制编码 bi , i = 1 , 2 ,…, n ;有
2 g. g5 @% t! f" t8 `
0 X* |- a8 W" f bi ∈ {0,1}L (3-84)
% r0 K' l. ~; z3 d d 1 m q' l T0 K% b5 |& Q2 x
给定目标函数 f ,有 f(bi) ,并且
; \8 f% I% r& a! i $ @8 A1 h5 J6 N( U H/ U4 }2 q
0<F(BI)< ∞ < P> ) ?- a5 y# F, m0 Q# S c
2 _9 t7 B9 h( ^
同时 ) e( v1 _2 ^: V1 b* C3 C
V3 H1 m Q8 t1 p } f(bi) ≠ f(bi+1)
. C) ~. v2 h1 x( e; D( q2 l ) I) G P0 l$ {( e; [
求满足下式 2 F3 X3 j% H; L1 w
1 U* g, r6 _& o( H* r6 \1 N
max{f(bi)|bi ∈ {0,1}L} ; O5 K& u- g1 Y2 q1 d
! e- p- v# D9 O' T' h
的 bi 。
8 H" _. {/ e/ N0 g0 @, e9 P
0 U E; k# J( ?' v+ n; y8 v 很明显,遗传算法是一种最优化方法,它通过进化和遗传机理,从给出的原始解群中,不断进化产生新的解,最后收敛到一个特定的串 bi 处,即求出最优解。 ( S$ _! e# i V
9 w* }# v% a6 P& Q' H' x
二、遗传算法的基本原理 ! C3 E) |, p" ]- W* h5 i
% f7 s1 O. F& J" I0 x2 ^ 长度为 L 的 n 个二进制串 bi(i = 1 , 2 ,…, n) 组成了遗传算法的初解群,也称为初始群体。在每个串中,每个二进制位就是个体染色体的基因。根据进化术语,对群体执行的操作有三种: * b' j' ]" k! g- j
* Y) v3 L) q) q' o+ U9 E 1 .选择 (Selection) $ @+ w+ \3 D3 i- m$ t; @6 y: j
. u) f5 p- I! |) D2 ]9 w# k
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生 (Reproduction) 。由于在选择用于繁殖下一代的个体时,是根据个体对环境的适应度而决定其繁殖量的,故而有时也称为非均匀再生 (differential reproduction) 。 & W% ^. l* [: ^- q# d
7 W: b# q* F5 N) Y
2 .交叉 (Crossover) 1 C0 m k6 \! E# x
; ]/ f5 R0 Y: I2 Q" m3 J 这是在选中用于繁殖下一代的个体中,对两个不同的个体的相同位置的基因进行交换,从而产生新的个体。
$ T# p' {- X$ ]* G& ^
% o7 R0 k2 {# Q( \ k. u% A 3 .变异 (Mutation) 8 D* Y' o/ }0 a/ Q ~# m; [3 J# Q
' S# g9 }, a2 E, L 这是在选中的个体中,对个体中的某些基因执行异向转化。在串 bi 中,如果某位基因为 1 ,产生变异时就是把它变成 0 ;反亦反之。
4 R: J. n; X; w/ A
1 y% ]" s G% a! d( H6 x8 Y* Y 遗传算法的原理可以简要给出如下:
, F$ E& G2 P" Z- L : r2 R7 P; ~2 ^. M3 |) T! b
choose an intial population 6 J8 j! n0 X" e; \- A
" h8 g5 l9 m9 t6 c
determine the fitness of each individual # }, |; K0 W7 n6 }
1 p E- F1 F( H2 U4 q perform selection x# o) s: o( T) W3 Z& y
# n, K1 e, |4 v
repeat
, o; ^7 ~/ g8 V1 \
7 U( f9 k& L/ V, C! P& o2 f, l perform crossover
* G% S+ z+ p( q. t% a2 U. V ' `/ D; l$ z! ?* c/ e7 H( k
perform mutation
) i5 s2 y# y5 f 4 j' a! S4 w/ l ^8 R; G+ T/ P* u4 n0 q
determine the fitness of each individual
: K) \8 W4 _# {# m6 Z/ R" H / p% K. p1 O, g. ~- f
perform selection
. a& g& O7 {8 h0 T! K4 l) ?
: f7 Y" |& r) r8 r( P until some stopping criterion applies
/ {" u0 Z) t8 ~. l% ~ & N k a1 y; }, a* j
这里所指的某种结束准则一般是指个体的适应度达到给定的阀值;或者个体的适应度的变化率为零。( g/ l4 u1 e8 l6 `2 i& {/ W
三、遗传算法的步骤和意义 , a3 Q \1 L; r3 \% P& G% ^
. M: ^' F# W) ]+ W) @; x8 o6 h 1 .初始化
% y1 S0 Y& c8 J1 T
1 s- y- {: B; k7 p" H; ] 选择一个群体,即选择一个串或个体的集合 bi , i=1 , 2 , ...n 。这个初始的群体也就是问题假设解的集合。一般取 n = 30-160 。 ) m& L, Q" i$ E* a0 t Y2 T4 R
; H3 [: \% I+ N0 |1 H
通常以随机方法产生串或个体的集合 bi,i = 1 , 2 , ...n 。问题的最优解将通过这些初始假设解进化而求出。
4 N1 G2 v) S6 \, M. ~ X% e8 r # @: R% ^+ Z& S5 q" j: a
2 .选择 6 U, u- W3 u$ j l
: @; o6 }9 V$ U4 \) U6 ]7 @ 根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存,不适应者淘汰的自然法则。
2 T; V/ v" [, G w- n8 U 5 S/ U/ p g( T/ G" N- G7 ]
给出目标函数 f ,则 f(bi) 称为个体 bi 的适应度。以 " U" y. v* d, _3 H6 V
, c; f. e o' ?9 o7 w5 F d, H/ \
: Q& p; A0 D$ V! [8 F, H& {6 N: {. ?
5 C0 w/ K( v0 C/ D! V; ~1 l: r
为选中 bi 为下一代个体的次数。
" p8 \ R7 i+ p$ g# c7 c, s * R; L: i/ z1 D$ z: I' V- y! Q
显然.从式 (3 — 86) 可知: + a; x# l/ y, A2 ]+ i* u2 @' H Q; `9 Y
( f4 f8 J" K2 E4 t
(1) 适应度较高的个体,繁殖下一代的数目较多。
! {: N' \8 a- p" s3 Q
6 _; M j2 Y, S d" q (2) 适应度较小的个体,繁殖下一代的数目较少;甚至被淘汰。
, ^3 f4 A- c" V5 u( ^! D - q# z7 @) m0 L w: f
这样,就产生了对环境适应能力较强的后代。对于问题求解角度来讲,就是选择出和最优解较接近的中间解。 + t/ b, a7 k9 n5 b* e7 @6 B
' J! q9 ~- b% u7 Q
3 .交叉
9 q( q! F! I: z 对于选中用于繁殖下一代的个体,随机地选择两个个体的相同位置,按交叉概率 P 。在选中的位置实行交换。这个过程反映了随机信息交换;目的在于产生新的基因组合,也即产生新的个体。交叉时,可实行单点交叉或多点交叉。
& g+ I% t* E# [4 N : P6 l, r+ z5 A; }1 [
例如有个体
" f4 U; i) ]2 b$ a
! H: U/ j, v% [ S1=100101 , o7 P/ ~- g( L' n+ f7 _
% }* n0 w* m2 m. S$ f
S2=010111
4 U/ e( O% l( b# b0 C$ I; F
# G5 |% S: T# v! F 选择它们的左边 3 位进行交叉操作,则有 ; J: ~; o, m7 l4 l! d
4 p5 d1 F; D2 l4 Q, K S1=010101 ( Z! u0 A" v+ @/ M7 j- z' ?. E
/ o9 B' m; g% O: G
S2=100111 9 U0 q6 W, {; _- c. l: s
$ A) K+ I) T$ [+ ^& v
一般而言,交 婊显譖。取值为 0.25 — 0.75 。 9 E+ q! n5 U/ e4 c; d1 E8 n
( Z' W* m" K9 d# T
4 .变异 5 [+ G5 ?2 w% a. ]
% ?' ^* r4 ], T8 K( r1 j1 d 根据生物遗传中基因变异的原理,以变异概率 Pm 对某些个体的某些位执行变异。在变异时,对执行变异的串的对应位求反,即把 1 变为 0 ,把 0 变为 1 。变异概率 Pm 与生物变异极小的情况一致,所以, Pm 的取值较小,一般取 0.01-0.2 。
. K' n/ t! g y' b6 Z$ I$ `1 K6 G
& }; d! m+ s0 _4 o% F! ^# H9 g 例如有个体 S = 101011 。
+ Z: q* ^7 s' |2 I6 I% _: u& m T
+ i) v5 |5 z, `% T3 i1 E 对其的第 1 , 4 位置的基因进行变异,则有 / k* j) w+ D/ ?7 U5 J+ C0 |1 b
9 P2 P' n B: L/ S* p+ } S'=001111 9 u# e1 f1 W1 |2 y+ i: v, G
# X4 |& H1 @& X
单靠变异不能在求解中得到好处。但是,它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时,交叉是无法产生新的个体的,这时只能靠变异产生新的个体。也就是说,变异增加了全局优化的特质。
0 H7 i- q/ e6 x+ C ' o9 P0 I6 f0 a, `
5 .全局最优收敛 (Convergence to the global optimum)
. m% L% x2 |; `( v3 v 7 X4 T5 V4 w6 z/ r7 S, I) U
当最优个体的适应度达到给定的阀值,或者最优个体的适应度和群体适应度不再上升时,则算法的迭代过程收敛、算法结束。否则,用经过选择、交叉、变异所得到的新一代群体取代上一代群体,并返回到第 2 步即选择操作处继续循环执行。
1 x$ U) J2 M5 J4 O2 ` z& E, t8 E' C# ] 6 V$ j0 y8 d# m" H4 R: C
图 3 — 7 中表示了遗传算法的执行过程。 4 U( W& Q- S+ k4 M
2 w9 W: o- {+ G# Q- G* g! V
1 U, M7 o; b) o0 k* \! L
+ w) d+ X* x# _+ D8 {
' P, v3 |1 `" ~+ f: o# m 图 3-7 遗传算法原理 ) i8 d2 L2 O5 \" {& ^% H' r
' a$ P% I& W7 S6 ^, w- i
3 . 2 . 3 遗传算法的应用 5 ]4 t6 Q$ W: S2 t2 U1 T/ V
* U R- r6 P! D- T) Y( v" a: J* U 遗传算法在很多领域都得到应用;从神经网络研究的角度上考虑,最关心的是遗传算法在神经网络的应用。在遗传算法应用中,应先明确其特点和关键问题,才能对这种算法深入了解,灵活应用,以及进一步研究开发。
# A$ K* g* H5 M1 u+ N$ x ! G( P0 N, ~9 R0 ]$ }/ }' ?
一、遗传算法的特点 2 T% M* s1 x) s! ~9 ^" O" J
9 y6 Q* E, Z# p3 T L( }9 h
1 .遗传算法从问题解的中集开始嫂索,而不是从单个解开始。 , K* r6 i4 I+ `9 `- `9 g/ N
+ P% Q `6 U1 ^- I( X
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的;容易误入局部最优解。遗传算法从串集开始搜索,复盖面大,利于全局择优。
# e" E: t, j3 G1 l% Z ; D, L3 q1 h, T+ g8 Z8 {
2 .遗传算法求解时使用特定问题的信息极少,容易形成通用算法程序。 " i* b3 B2 R7 |/ T
. P( ^; j$ q3 `* H+ f* n
由于遗传算法使用适应值这一信息进行搜索,并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息,故几乎可处理任何问题。 " x }& e' o0 E5 K. Q4 |
- b: G( `- r$ j! l 3 .遗传算法有极强的容错能力 " Y: E3 o/ R/ k _1 h' J" G
& |% y( |3 X6 E4 [8 p& N 遗传算法的初始串集本身就带有大量与最优解甚远的信息;通过选择、交叉、变异操作能迅速排除与最优解相差极大的串;这是一个强烈的滤波过程;并且是一个并行滤波机制。故而,遗传算法有很高的容错能力。 * H/ a ]0 t+ ~* I0 ^
: T: ~5 h; J1 F5 @6 @+ N" @
4 .遗传算法中的选择、交叉和变异都是随机操作,而不是确定的精确规则。
2 u: w) a6 }+ f& g; l5 Z 7 I9 I: v b/ `- u# {# u2 L1 e
这说明遗传算法是采用随机方法进行最优解搜索,选择体现了向最优解迫近,交叉体现了最优解的产生,变异体现了全局最优解的复盖。
$ }7 B! S8 s& }5 p9 q . P' @' d" h# w4 v
5 .遗传算法具有隐含的并行性
- G0 o" y( O; ?( T
9 R& {. j' C4 H0 p+ @$ V* \4 U. H; X 遗传算法的基础理论是图式定理。它的有关内容如下: ; X2 W+ q3 ^7 P3 a4 S
& c7 ]& F" p# W- w C0 W
(1) 图式 (Schema) 概念
$ O0 E U Y! P/ u7 _/ b, h8 z1 [ - W4 ^/ Z5 P% U9 [. k. ~5 c! T
一个基因串用符号集 {0 , 1 , *} 表示,则称为一个因式;其中 * 可以是 0 或 1 。例如: H=1xx 0 x x 是一个图式。
7 n" Q9 u, u6 n* p! c" q , s, G- \9 k) ]
(2) 图式的阶和长度 6 e3 Q- @ S- p0 d: J: d- ? v
5 C$ U; X0 M8 t" Y
图式中 0 和 1 的个数称为图式的阶,并用 0(H) 表示。图式中第 1 位数字和最后位数字间的距离称为图式的长度,并用δ (H) 表示。对于图式 H = 1x x0x x ,有 0(H) = 2 ,δ (H) = 4 。
# Z1 j8 N+ }$ R* l 3 |$ Q1 c2 L. J8 Y7 ^4 v
(3)Holland 图式定理
, W d2 Y: {- t+ V# F' Y6 {, ] : A1 `% q! W) W q/ r3 r) r
低阶,短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为 n 时,每代处理的图式数目为 0(n3) 。
6 k7 u9 r( y: L1 N8 Q7 R" |0 ?* I
# A0 s7 w4 ~1 s8 F: E 遗传算法这种处理能力称为隐含并行性 (Implicit Parallelism) 。它说明遗传算法其内在具有并行处理的特质。
, E6 M, T: S: [- x
$ n3 w$ m1 W3 y/ h) ]% r 二、遗传算法的应用关键
# B' S `8 @# u6 w0 P 4 G+ h# R+ q7 T- T+ j( m; {! R
遗传算法在应用中最关键的问题有如下 3 个
0 T5 u2 @* D. N' d$ c# V2 l / T1 u/ ]' r* J$ Q& L
1 .串的编码方式
, J) U; ?! R$ s; N- Y- g8 P. y
- v7 G& Y! C! t B! ^+ z1 z6 _( I 这本质是问题编码。一般把问题的各种参数用二进制编码,构成子串;然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
3 ~& m0 n$ }9 E3 q $ c1 k* J/ ^3 q) _& S6 o
2 .适应函数的确定 ; k2 h6 }) q8 y( O) h$ m# N
) w0 _ H: Z' p5 M/ X8 V 适应函数 (fitness function) 也称对象函数 (object function) ,这是问题求解品质的测量函数;往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数;但有时需要另行构造。
7 L4 t7 Y* T4 q: g. x6 g8 { ! a0 O. m+ I$ L
3 .遗传算法自身参数设定 : O5 C% \- f1 {( I( E
d1 x/ g" p# ~$ k9 g) W( i 遗传算法自身参数有 3 个,即群体大小 n 、交叉概率 Pc 和变异概率 Pm 。
: |+ Q. _9 Q, c1 ~ # R. X. m" j/ C, @* J
群体大小 n 太小时难以求出最优解,太大则增长收敛时间。一般 n = 30-160 。交叉概率 Pc 太小时难以向前搜索,太大则容易破坏高适应值的结构。一般取 Pc=0.25-0.75 。变异概率 Pm 太小时难以产生新的基因结构,太大使遗传算法成了单纯的随机搜索。一般取 Pm = 0 . 01 — 0 . 2 。 $ b" v4 I; y. K" h, B5 C
3 g8 [1 a# p4 R% a
三、遗传算法在神经网络中的应用
5 a8 B4 J! C! N C, z+ Y
9 X. b8 d$ c4 f$ r1 B# h9 P 遗传算法在神经网络中的应用主要反映在 3 个方面:网络的学习,网络的结构设计,网络的分析。 U% j4 s8 `/ L
7 F. `: I- Z7 G; c
1 .遗传算法在网络学习中的应用
" a+ b- I) ?# }' z 5 D& f, N& w# Z* |5 w0 v
在神经网络中,遗传算法可用于网络的学习。这时,它在两个方面起作用 / W% O6 W+ c; y. l
' K- p: U1 s( x4 c$ V, N2 x
(1) 学习规则的优化 + E+ D5 D6 W# E% j! u, {* x
7 I# K8 W7 {; C6 l1 x5 j 用遗传算法对神经网络学习规则实现自动优化,从而提高学习速率。
. Q- O7 S2 Q. c/ A M8 ]3 C$ I' c
! I- p) i! S# ~% G& n7 f (2) 网络权系数的优化 0 P9 g& J6 ]( |# g$ X
& E2 D; L# L( y& j9 ^) B" c
用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
% `+ }& {* o' O 9 r3 f9 k- o" V- ]( b$ k
2 .遗传算法在网络设计中的应用
( n; n# z9 Q; Z
+ q0 ~, p7 [/ B; P: C8 T# o 用遗传算法设计一个优秀的神经网络结构,首先是要解决网络结构的编码问题;然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列 3 种:
" Q4 O% |- G5 i8 P6 b+ U 6 I2 ?' l p4 e" j, M6 s) q5 T' [: _
(1) 直接编码法 5 Q" Z E0 R- L! F: J
/ Y% C) W+ T* D/ f 这是把神经网络结构直接用二进制串表示,在遗传算法中,“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。 + W" R* o: { l/ J9 X
5 z# u- u' _7 o. {3 y' @* D( d
(2) 参数化编码法
/ O' }1 G8 y1 t. o6 @# q
( M9 [2 c0 J' `3 T 参数化编码采用的编码较为抽象,编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析,然后产生网络的结构。
2 W+ L# d* S' c( z # h5 v" t6 ~$ d. F% z
(3) 繁衍生长法
3 F% [& o/ r, z! A
4 S; ^4 X6 L% G 这种方法不是在“染色体”中直接编码神经网络的结构,而是把一些简单的生长语法规则编码入“染色体”中;然后,由遗传算法对这些生长语法规则不断进行改变,最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
; e# j& u* f# g3 e ! w9 N+ D9 `& H
3 .遗传算法在网络分析中的应用 & m5 ~3 z0 \8 V
& t$ p8 Q! ^( W+ U; n; M1 _- Y 遗传算法可用于分析神经网络。神经网络由于有分布存储等特点,一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析,性质分析,状态分析。 $ c1 }* j& W% Y7 O! e
; \: A" U# {5 o2 r4 i: ?9 f7 C
遗传算法虽然可以在多种领域都有实际应用,并且也展示了它潜力和宽广前景;但是,遗传算法还有大量的问题需要研究,目前也还有各种不足。首先,在变量多,取值范围大或无给定范围时,收敛速度下降;其次,可找到最优解附近,但无法精确确定最扰解位置;最后,遗传算法的参数选择尚未有定量方法。对遗传算法,还需要进一步研究其数学基础理论;还需要在理论上证明它与其它优化技术的优劣及原因;还需研究硬件化的遗传算法;以及遗传算法的通用编程和形式等。 4 m- n5 c, w8 @2 Q
. n/ A2 c$ H9 z& C
1 l0 _" ?9 P# q" z: A
三、遗传算法的步骤和意义
" y, O3 \& k J% g! H6 Z( ]' o
! M9 I: @( W4 i3 e& Z 1 .初始化
/ U. e+ J7 n, T ( j/ e2 c1 R7 ?0 x( ^* F2 D
选择一个群体,即选择一个串或个体的集合 bi , i=1 , 2 , ...n 。这个初始的群体也就是问题假设解的集合。一般取 n = 30-160 。
) c% C& r+ G& x2 K
u. E1 l! S. h8 ?+ F4 v- q( o' P 通常以随机方法产生串或个体的集合 bi,i = 1 , 2 , ...n 。问题的最优解将通过这些初始假设解进化而求出。
3 y. O; d+ i4 S% G
^4 Z* @/ E ? 2 .选择
7 L3 e. C4 S4 J2 F7 ^4 L+ U7 ~
. x' i P2 X4 |6 h( R. ~ 根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存,不适应者淘汰的自然法则。 $ P& ?. ~7 i+ d" Y4 z
* b% I6 |1 M. ]. e% s, z 给出目标函数 f ,则 f(bi) 称为个体 bi 的适应度。以
: [/ ?5 s2 x& c$ H
! @! F+ I/ c$ u) r1 N+ J$ Z- Z 2 V! S8 K2 ^$ P) A
4 N7 M6 V, I6 B8 U" b) v0 X" K- k" c 为选中 bi 为下一代个体的次数。
1 Y8 q% z& l$ J; w( s, p6 r
B& v$ e" l; p; i2 Z7 c 显然.从式 (3 — 86) 可知:
' h3 V, Y# B, G: w
* I+ i9 p& g: V# S; X5 I (1) 适应度较高的个体,繁殖下一代的数目较多。 5 Q& {1 H/ O2 |9 J H
' ?+ C7 d$ ^) J# \. F (2) 适应度较小的个体,繁殖下一代的数目较少;甚至被淘汰。
; T1 W: ^0 b* r& C- x6 r* w
" B: c( _ i; m! w! x 这样,就产生了对环境适应能力较强的后代。对于问题求解角度来讲,就是选择出和最优解较接近的中间解。
0 c" T/ K6 e- k u, f" ] - E$ Y& \/ ^) u3 [; k
3 .交叉 + d! q3 ?6 W. t
对于选中用于繁殖下一代的个体,随机地选择两个个体的相同位置,按交叉概率 P 。在选中的位置实行交换。这个过程反映了随机信息交换;目的在于产生新的基因组合,也即产生新的个体。交叉时,可实行单点交叉或多点交叉。
0 F+ Y' s5 u. W0 ^ 0 F) M+ C- j% E* v; N# M8 D; `- k0 o
例如有个体 : a* V! S+ \; d4 n9 P
8 N6 o3 \; ~! S) e6 ^& {
S1=100101
5 O, B9 e, i4 q% L : c7 P) g4 e5 s- T$ M4 F
S2=010111 , ~7 y m& W9 A
! ]! I8 x' N3 j
选择它们的左边 3 位进行交叉操作,则有
$ I4 f1 f5 ~" k; N( ^3 B! ~4 z
$ B6 O4 D. G5 [) K+ x& Y8 A S1=010101
0 h$ a* L& w8 X |7 i; e+ b : |0 N; D1 N! v, T
S2=100111 $ i' c' P& v* i2 p3 `3 l
- ^( e+ l' o4 L Z& i9 t* t" w4 u+ _6 w 一般而言,交 婊显譖。取值为 0.25 — 0.75 。
1 k& x* F4 @& k" y& v * s% a) k1 V) j6 p. b& T, k
4 .变异 7 ^3 U& ]' K4 D0 k& X
6 E3 e4 V: T) n2 u# i! Z: I/ q2 }; G
根据生物遗传中基因变异的原理,以变异概率 Pm 对某些个体的某些位执行变异。在变异时,对执行变异的串的对应位求反,即把 1 变为 0 ,把 0 变为 1 。变异概率 Pm 与生物变异极小的情况一致,所以, Pm 的取值较小,一般取 0.01-0.2 。
" e, p" E/ X! K6 E
& t8 `9 t( I3 G$ s' ~$ ` 例如有个体 S = 101011 。 ; ] T+ g* H- a; F8 a1 l
/ n7 ^1 L p) L: T, P 对其的第 1 , 4 位置的基因进行变异,则有 8 |4 \# s5 M! c L
' Q. l% Y! z7 T; L \
S'=001111 $ F a) `' B) E# [% H
) I) B/ X9 G+ ~: \
单靠变异不能在求解中得到好处。但是,它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时,交叉是无法产生新的个体的,这时只能靠变异产生新的个体。也就是说,变异增加了全局优化的特质。 & K- \" }2 p* J
+ D/ l% ?* ?& O- C
5 .全局最优收敛 (Convergence to the global optimum) " }6 E1 S# T/ L5 @7 G
) p" M# `+ }$ S1 _ 当最优个体的适应度达到给定的阀值,或者最优个体的适应度和群体适应度不再上升时,则算法的迭代过程收敛、算法结束。否则,用经过选择、交叉、变异所得到的新一代群体取代上一代群体,并返回到第 2 步即选择操作处继续循环执行。 ; [2 |6 d5 S0 P; ~1 @# n
% J7 `! U1 D L( z; x7 ^ 图 3 — 7 中表示了遗传算法的执行过程。
* }. V- Y: V4 \ y% x! j . q" e! J4 \" p$ r1 T, F" N9 K
/ P! w$ k. t% t$ i' j9 U* s3 Q: m
7 Y8 a2 s( m* s" t, E/ B
7 G. z1 \ c" B6 p8 c. e% C 图 3-7 遗传算法原理
+ @. v; c: T# n. K6 ]0 X
( N {% z1 P# X 3 . 2 . 3 遗传算法的应用 9 m2 `/ W N/ e+ y" e3 ]' b. b
0 @! S0 p6 p0 t. X* d 遗传算法在很多领域都得到应用;从神经网络研究的角度上考虑,最关心的是遗传算法在神经网络的应用。在遗传算法应用中,应先明确其特点和关键问题,才能对这种算法深入了解,灵活应用,以及进一步研究开发。 8 ~* `5 |5 V4 f- P
; j C% y3 x5 t3 m# k3 D
一、遗传算法的特点
, A& n& T! `$ Y1 ], q 5 S5 K) W5 o- Y7 J
1 .遗传算法从问题解的中集开始嫂索,而不是从单个解开始。 9 h4 i$ l1 G( G" V D! i
9 L; k, _$ ?, s( Y0 C 这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的;容易误入局部最优解。遗传算法从串集开始搜索,复盖面大,利于全局择优。 + [9 V" b$ k$ I3 K, N
$ F; f2 z: |2 q) J2 ^4 e 2 .遗传算法求解时使用特定问题的信息极少,容易形成通用算法程序。 : L" T. ^+ L+ q f. c) `
, U+ h2 J9 a9 y0 z5 f) ] 由于遗传算法使用适应值这一信息进行搜索,并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息,故几乎可处理任何问题。 : J$ R8 F. c: `% T4 B d, b
# l5 Q0 H& H) C0 `! G
3 .遗传算法有极强的容错能力
" K5 G7 l$ E( Q( y3 W$ M
% k h, f* O! g0 R 遗传算法的初始串集本身就带有大量与最优解甚远的信息;通过选择、交叉、变异操作能迅速排除与最优解相差极大的串;这是一个强烈的滤波过程;并且是一个并行滤波机制。故而,遗传算法有很高的容错能力。 7 R5 K) V/ @9 z2 X
! \7 W1 p- H' P7 j 4 .遗传算法中的选择、交叉和变异都是随机操作,而不是确定的精确规则。
2 l9 a7 B& }% y) f/ k
( _; i! p6 S% @5 u- ~: J 这说明遗传算法是采用随机方法进行最优解搜索,选择体现了向最优解迫近,交叉体现了最优解的产生,变异体现了全局最优解的复盖。
% G: p+ |) }; n # m4 _4 R- L- N5 y$ `5 A# _
5 .遗传算法具有隐含的并行性
; W9 L" }4 c% u' I. B
8 K& H n3 z( G4 _7 s: l' h) U 遗传算法的基础理论是图式定理。它的有关内容如下: : N" q3 p2 a) w# I
1 m4 \2 y0 F' |5 U- d5 M (1) 图式 (Schema) 概念 * U* ~* K$ I* O# h' m6 z
. i: p/ \' V+ g& @
一个基因串用符号集 {0 , 1 , *} 表示,则称为一个因式;其中 * 可以是 0 或 1 。例如: H=1xx 0 x x 是一个图式。 7 v/ f9 T7 |3 R& g$ {
7 P3 f% L; y2 x6 _# n* o4 d
(2) 图式的阶和长度 # V/ g; ~/ Q1 P' c0 J# f
, D' Z$ W( l: _% K2 Y
图式中 0 和 1 的个数称为图式的阶,并用 0(H) 表示。图式中第 1 位数字和最后位数字间的距离称为图式的长度,并用δ (H) 表示。对于图式 H = 1x x0x x ,有 0(H) = 2 ,δ (H) = 4 。
1 \( {3 P; F5 Y4 s: K
- d' M2 q. Y% a: `0 X* r$ Y (3)Holland 图式定理 5 V1 ?' s" v, F" }" y6 G5 F
2 D1 Q, h2 I6 U% F( q( G
低阶,短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为 n 时,每代处理的图式数目为 0(n3) 。 ! ~2 S8 ?. t: C/ l' ~" t/ Z9 v# J3 X
2 Z0 p8 l( G3 T* U' k9 I0 r1 t: { 遗传算法这种处理能力称为隐含并行性 (Implicit Parallelism) 。它说明遗传算法其内在具有并行处理的特质。 % I' `0 ^* I5 z3 B- S; d
2 O* x z: q- p3 E# p; X
二、遗传算法的应用关键
" g7 H! J0 A2 T3 i4 V& _' N1 G# J3 z ! o! D% \; I [9 j( j% D8 C
遗传算法在应用中最关键的问题有如下 3 个
/ y5 w; f8 m; T- R8 f( j" j/ w8 h
* P- D( f' O* i0 |3 p 1 .串的编码方式 . C1 D c3 ^. F
8 T: {, j& S. U v. Y% e, [ 这本质是问题编码。一般把问题的各种参数用二进制编码,构成子串;然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。 6 X* R, ?* q9 u0 v' B
) Y, f2 m: M+ |7 Z; u6 H& s: I 2 .适应函数的确定 . P( c4 i' G8 Z3 i/ k1 k5 J
. |3 K0 R! p$ k$ L0 S5 m4 Q
适应函数 (fitness function) 也称对象函数 (object function) ,这是问题求解品质的测量函数;往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数;但有时需要另行构造。 ' J5 P, h0 `7 r6 B. X8 z9 ]0 ?. j- x
' z+ c7 f% O: O4 D0 a1 V
3 .遗传算法自身参数设定
' t. A4 ^, I7 u$ L0 p; | / U( j1 \! P- _% U- B
遗传算法自身参数有 3 个,即群体大小 n 、交叉概率 Pc 和变异概率 Pm 。 ( F- K& c* S9 R9 \
& x( K; C. w+ \6 ~" T$ d
群体大小 n 太小时难以求出最优解,太大则增长收敛时间。一般 n = 30-160 。交叉概率 Pc 太小时难以向前搜索,太大则容易破坏高适应值的结构。一般取 Pc=0.25-0.75 。变异概率 Pm 太小时难以产生新的基因结构,太大使遗传算法成了单纯的随机搜索。一般取 Pm = 0 . 01 — 0 . 2 。 ! V C# b8 t! Y0 \. E/ N- b" b
# [9 C5 I$ M+ K f
三、遗传算法在神经网络中的应用
* E+ }* T& |& ]# n3 A - d. L7 }1 n5 i
遗传算法在神经网络中的应用主要反映在 3 个方面:网络的学习,网络的结构设计,网络的分析。
! O; y; Q4 B& x2 v2 ` 9 s- B N/ t k6 L. v0 F
1 .遗传算法在网络学习中的应用 , u# C) ?6 [+ @6 D6 T) y
) j2 }- M8 g. r& b8 m( I& p2 ` 在神经网络中,遗传算法可用于网络的学习。这时,它在两个方面起作用
/ h/ \0 H C( s0 f1 g9 N4 h& x; R
0 y" S! ^. Y8 J Q3 E0 d/ e (1) 学习规则的优化
$ ~3 E w$ E7 J+ r; v- [: m: M, l / Z. {: A. F% p
用遗传算法对神经网络学习规则实现自动优化,从而提高学习速率。 - \1 a5 W! V6 x! W# D
6 O- o; j0 Z, g! B7 ~
(2) 网络权系数的优化 2 x7 _; a, i1 `
2 R4 k$ B: Y% K
用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
0 c7 D( O) V! N
( ?& T5 v8 {! d$ W. ] 2 .遗传算法在网络设计中的应用 2 ]$ h0 `) |- i4 ~2 j* a
% ?, k+ l5 a, ^ [" W9 ^& L 用遗传算法设计一个优秀的神经网络结构,首先是要解决网络结构的编码问题;然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列 3 种: / M) n# C' z- ~" h7 @) ^9 T4 X8 E
% R+ o! K3 E q8 `; l$ T/ o' g (1) 直接编码法
p" R! `2 a/ G( E0 V
4 D+ N: A8 [( i6 k# y 这是把神经网络结构直接用二进制串表示,在遗传算法中,“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。 / z9 j: M* l) d/ v) k0 K' G% X
: c4 s1 w3 [4 j. V* g& R: M4 i8 y
(2) 参数化编码法
0 E+ _* S/ @7 g& \ # i' d* u) Y" i7 O5 f
参数化编码采用的编码较为抽象,编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析,然后产生网络的结构。
' P: w7 _0 ]6 J
" Y" y7 @/ K, t* y, P (3) 繁衍生长法
" j, p8 F& {4 S% _+ ?1 e
9 h" K% W2 X2 h3 D9 M% i 这种方法不是在“染色体”中直接编码神经网络的结构,而是把一些简单的生长语法规则编码入“染色体”中;然后,由遗传算法对这些生长语法规则不断进行改变,最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。 ' d2 b8 K1 U( U& R) k* F
* d9 k6 G( B* [! z x6 X/ i
3 .遗传算法在网络分析中的应用
: h( J$ R4 d6 U5 ~- b
) _3 n H0 f7 m0 f' \$ I 遗传算法可用于分析神经网络。神经网络由于有分布存储等特点,一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析,性质分析,状态分析。 " z. ]# e4 c W
( `' [6 y+ G1 L8 | 遗传算法虽然可以在多种领域都有实际应用,并且也展示了它潜力和宽广前景;但是,遗传算法还有大量的问题需要研究,目前也还有各种不足。首先,在变量多,取值范围大或无给定范围时,收敛速度下降;其次,可找到最优解附近,但无法精确确定最扰解位置;最后,遗传算法的参数选择尚未有定量方法。对遗传算法,还需要进一步研究其数学基础理论;还需要在理论上证明它与其它优化技术的优劣及原因;还需研究硬件化的遗传算法;以及遗传算法的通用编程和形式等。
2 e8 Y. n8 W1 d" D* b
楼主热帖