* f. B+ ]3 A6 F2 I q0 d 1 [7 G: e% `+ @) H. X* F0 g
“物竞天择,适者生存”,是进化论的基本思想。遗传算法就是模拟自然界想做的事。遗传算法可以很好地用于优化问题,若把它看作对自然过程高度理想化的模拟,更能 * B; Q. M; ]( S0 F3 v! c% Q* a显出它本身的优雅——虽然生存竞争是残酷的。0 a* T6 U( O+ s
: A# f( _; M! u5 v) Y
! s! |1 O+ I# a Z' o; O( H# @
遗传算法以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码 $ d, n0 y. G* I6 T' a、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。! W# f' m+ w- V2 L: n2 q
作为一种新的全局优化搜索算法,遗传算法以其简单通用、健壮性强、适于并行处理以及高效、实用等显著特点,在各个领域得到了广泛应用,取得了良好效果,并逐渐成 3 D" m' k. b7 O( p; d& Z为重要的智能算法之一。 g# G9 n, |3 U" b" h ; l: Q- N" y8 X# `4 Y" v; A ; b: ]" T4 y* Z1 O* f 遗传算法的伪码: u, U) ]: [; O + L7 \. m. T( j+ q 3 Z/ E; k- Y F# G- A. E
procedure genetic algorithm 7 r- u. A" l. C$ T1 w0 v, Q8 L) m
begin / m2 F2 k3 p: g. d5 W
initialize a group and evaluate the fitness value ; (1)6 j* E, N U" K- C' |/ i- @4 B, ~. q
while not convergent (2) 6 k4 m2 q: z7 l begin % {2 }# y/ V% ]2 O" ~6 M" p# U
select; (3) ' [4 f9 ?0 H$ f; h0 ~ if random[0,1] crossover; (4) ! T% J! D! b9 R1 u; M2 S if random (0,1) mutation; (5) . T6 N9 w& g1 A# H: m$ s end; ' V, ^7 o% O# C; | end : S: E7 H5 a& W) L 上述程序中有五个重要的环节:# h7 T9 ^ a5 O" F h
(1)编码和初始群体的生成:GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据,这些串结构数据的不同组合便构成了不同的点。然后随机产$ l% N1 p, N; m! e5 Y! h
生N个初始串结构数据,每个串结构数据称为一个个体,2 w" F' T5 |! j( F! z" X/ l; {6 T
N个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。1 F, |7 C% _8 i
0 \8 ^6 q; d2 w - E2 a4 u' V9 a' u$ D3 h: @
比如,旅行商问题中,可以把商人走过的路径进行编码,也可以对整个图矩阵进行编码。编码方式依赖于问题怎样描述比较好解决。初始群体也应该选取适当,如果选取的& \% [+ l9 k! W3 c2 k5 o% X- N
过小则杂交优势不明显,算法性能很差(数量上占了优势的老鼠进化能力比老虎强),群体选取太大则计算量太大。$ l3 V) _) y/ T/ W9 g% u0 M: b
% r8 L" n- v5 g/ c6 z( o+ U- S
! L* X: A- L, [, y2 D; e (2)检查算法收敛准则是否满足,控制算法是否结束。可以采用判断与最优解的适配度或者定一个迭代次数来达到。 : g" w3 v8 [& \5 @ : z9 u9 o" Z( V! q* l & z" i/ G% x8 m: h U2 k+ b (3)适应性值评估检测和选择:适应性函数表明个体或解的优劣性,在程序的开始也应该评价适应性,以便和以后的做比较。不同的问题,适应性函数的定义方式也不同" y( A+ ^: H- R) c
。根据适应性的好坏,进行选择。选择的目的是为了从当前群体中选出优良的个体,使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想,进行 $ _( p+ m* Z }5 ]4 V) G0 V9 ^( Q选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。. g+ j) ~, {9 R A" E1 _
2 G7 M! g, c- m, Z 4 K7 k, X% U3 X, i
(4)杂交:按照杂交概率(pc)进行杂交。杂交操作是遗传算法中最主要的遗传操作。通过杂交操作可以得到新一代个体,新个体组合了其父辈个体的特性。杂交体现 7 }( U* n" g# l! i" i; D了信息交换的思想。" I$ C- Z) | k# Q$ u! k$ V4 [, c
. L! D, r- s) [2 l2 t) Z7 s 3 h3 x9 E+ z/ N1 v% ~/ }( k 可以选定一个点对染色体串进行互换,插入,逆序等杂交,也可以随机选取几个点杂交。杂交概率如果太大,种群更新快,但是高适应性的个体很容易被淹没,概率小了搜 - G4 |9 B y; o* }索会停滞。/ U+ y( ^: Y1 d; l8 D! @+ g! w2 {* T
6 s; c5 C) K. S" L* J
( ]3 f; Q# [4 W$ ]4 P7 }/ [ (5)变异:按照变异概率(pm)进行变异。变异首先在群体中随机选择一个个体,对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样, GA中变异发生的概率很低。变异为新个体的产生提供了机会。 * C1 |3 A2 i" k5 t7 Z, Y! p 2 {" o# H- J* W$ E6 o5 S 6 ?( a4 l/ R1 h) _' l4 {& {
变异可以防止有效基因的缺损造成的进化停滞。比较低的变异概率就已经可以让基因不断变更,太大了会陷入随机搜索。想一下,生物界每一代都和上一代差距很大,会是 " f' s- W- f% o% B" A怎样的可怕情形。 [/ Q5 K& }" H P: t6 L * N. P$ I: M+ w) s/ s h7 M
- c2 J. o. `, r" i& H& Y8 F: m 就像自然界的变异适和任何物种一样,对变量进行了编码的遗传算法没有考虑函数本身是否可导,是否连续等性质,所以适用性很强;并且,它开始就对一个种群进行操作" _/ n1 T4 w$ J2 p1 y
,隐含了并行性,也容易找到“全局最优解”。 2 n4 A+ f3 u) _$ ~- Y O * w0 L( j: u) h4 p! A3 h( X 2 X; E9 p) a# { 禁忌搜索算法(Tabu Search,TS) 5 v) g7 g i* y3 g $ [1 [) O- Z% L* r9 V( o
. t7 T+ \6 F- g' J* Q4 w! h
为了找到“全局最优解”,就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索,导致一叶障目,不见泰山。禁忌搜索就是0 B/ ?3 I4 I/ m. S
对于找到的一部分局部最优解,有意识地避开它(但不是完全隔绝),从而获得更多的搜索区间。兔子们找到了泰山,它们之中的一只就会留守在这里,其他的再去别的地4 J. |7 o$ f/ m' {% s
方寻找。就这样,一大圈后,把找到的几个山峰一比较,珠穆朗玛峰脱颖而出。 2 }/ D1 G* u& u0 z( G( s) V# R 0 b# x8 U+ |& Z7 Q2 M $ ]- {3 H; q- e 当兔子们再寻找的时候,一般地会有意识地避开泰山,因为他们知道,这里已经找过,并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表(tabu ; h) y2 l* s. i9 o$ u. J$ R( X( ~1 o
list)”的含义。那只留在泰山的兔子一般不会就安家在那里了,它会在一定时间后重新回到找最高峰的大军,因为这个时候已经有了许多新的消息,泰山毕竟也有一5 `5 C# m/ o) N5 g" c
个不错的高度,需要重新考虑,这个归队时间,在禁忌搜索里面叫做“禁忌长度(tabu j! V- ?! b: A! |3 G' x1 c$ H
length)”;如果在搜索的过程中,留守泰山的兔子还没有归队,但是找到的地方全是华北平原等比较低的地方,兔子们就不得不再次考虑选中泰山,也就是说,当$ o/ S2 u9 v1 w* a$ F! g: K
一个有兔子留守的地方优越性太突出,超过了“best . z3 ?* I5 x9 f% P: c+ P( [
to ; g" O0 g1 ^% s
far”的状态,就可以不顾及有没有兔子留守,都把这个地方考虑进来,这就叫“特赦准则(aspiration . P; A. a7 ]9 O N! ^, e' E' ~ criterion)”。这三个概念是禁忌搜索和一般搜索准则最不同的地方,算法的优化也关键在这里。/ _$ e M6 S# I3 T
1 a' Y0 u" a+ o, i+ i2 T: U / [% Q3 Z; e6 m3 b! x' l2 t' j4 o 伪码表达:1 R' L" M7 V7 W
procedure tabu search; ( g5 q h( `, S$ [ S" p' ]5 m( x7 _
begin " F. q, E$ h2 P& O! H initialize a string vc at random,clear up the tabu list; : y) {0 q; C* r1 C7 M2 K7 Y cur:=vc; ) l0 v: V4 t6 B6 n
repeat ) Q& u6 K+ n! {3 t8 M
select a new string vn in the neighborhood of vc; 9 ]1 k8 r. ^$ L# q3 G& k if va>best_to_far then {va is a string in the tabu list} ' X0 ~5 \9 g# R& u8 V7 M% c begin 2 h: C4 H( h& e
cur:=va; - r8 Q4 H, F6 }5 y) o let va take place of the oldest string in the tabu list; , Q1 j7 A4 Y- b; R" H$ }" @. N3 R
best_to_far:=va; X$ g9 x0 z# P7 c5 t end else 6 q5 E- U* m# _' b begin 5 y$ ]2 ]) D) z0 v5 N
cur:=vn; " B' b- h- D- N5 \ let vn take place of the oldest string in the tabu list; 5 A1 P; x6 C; p( `# } end; $ o0 M/ o7 m: U' \5 Z2 ]; V until (termination-condition); ! O1 E0 n' Z( C; H end; ) A8 x% y; [5 j4 b0 K& T8 C* e+ h
8 J' g6 @8 t2 S9 ^1 r( X$ v+ B # V; n" A& O0 n/ ]& L5 u9 k
以上程序中有关键的几点: % f7 i5 f0 S% E, y- m6 |1 q! z6 e (1)禁忌对象:可以选取当前的值(cur)作为禁忌对象放进tabu J/ E8 E5 U- ~. V( P0 T5 A
list,也可以把和当然值在同一“等高线”上的都放进tabu 0 f7 m7 E% T1 `; c list。 " q7 x7 ?2 ]1 [* r# |- V (2)为了降低计算量,禁忌长度和禁忌表的集合不宜太大,但是禁忌长度太小容易循环搜索,禁忌表太小容易陷入“局部极优解”。 & X" ?, Y& h# Q( a ( j Z& I, j, y% n 5 ]* Y V- c" b& E, I (3)上述程序段中对best_to_far的操作是直接赋值为最优的“解禁候选解”,但是有时候会出现没有大于best_to_far的,候选解也全部被禁的 “死锁”状态,这个时候,就应该对候选解中最佳的进行解禁,以能够继续下去。1 H! @" g! r5 h" T: {- k
3 c- v! _2 E$ K# W4 e
1 [0 q( J8 m8 b- F. E (4)终止准则:和模拟退火,遗传算法差不多,常用的有:给定一个迭代步数;设定与估计的最优解的距离小于某个范围时,就终止搜索;当与最优解的距离连续若干步 # t" n& m% h" N& ~0 t9 e# Q保持不变时,终止搜索;! P( b4 l ~: e/ h; V
' \: p* S1 d& m
5 t7 `* J$ \8 o
禁忌搜索是对人类思维过程本身的一种模拟,它通过对一些局部最优解的禁忌(也可以说是记忆)达到接纳一部分较差解,从而跳出局部搜索的目的。 0 s' F/ F: D' i% e, w' } ! i" k; E# S7 Y! ]) V3 A / a$ F1 `8 G+ r, s+ E6 ^
人工神经网络(Artificial Neural Network,ANN) ' k- k6 S$ |4 c. m3 u3 Q' R s5 E5 e: N0 _7 L/ }
9 a9 J& Y( \, G$ T 神经网络从名字就知道是对人脑的模拟。它的神经元结构,它的构成与作用方式都是在模仿人脑,但是也仅仅是粗糙的模仿,远没有达到完美的地步。和冯·诺依曼机不同 / J5 t7 Z! ?1 `2 i5 l: Y,神经网络计算非数字,非精确,高度并行,并且有自学习功能。 5 Y! y2 K! }4 c4 y8 x+ g& V 7 x S% _( \0 l6 W) F 6 q; c# T! [0 h, Z3 M 生命科学中,神经细胞一般称作神经元,它是整个神经结构的最基本单位。每个神经细胞就像一条胳膊,其中像手掌的地方含有细胞核,称作细胞体,像手指的称作树突,& Y3 R+ J* Q; C; x
是信息的输入通路,像手臂的称作轴突,是信息的输出通路;神经元之间错综复杂地连在一起,互相之间传递信号,而传递的信号可以导致神经元电位的变化,一旦电位高! I: I% e% D. Y9 m
出一定值,就会引起神经元的激发,此神经元就会通过轴突传出电信号。 : f; ?, ?, c5 E - \$ u/ o9 W! ]: Q* e' Z( W 7 w1 @9 ?% F. M( k6 G& Y8 e
而如果要用计算机模仿生物神经,就需要人工的神经网络有三个要素:(1)形式定义人工神经元;(2)给出人工神经元的连接方式,或者说给出网络结构;(3)给出3 ?- \ i0 p3 g+ g# B: H) [( L% p! Y
人工神经元之间信号强度的定义。' Y0 {- A0 S/ x6 d/ [
9 J- S+ e! J! T - ~8 c- X5 n s0 ~. {# F* y( w
历史上第一个人工神经网络模型称作M-P模型,非常简单: , s8 f( f5 R4 ^: G% C2 A* c ! v$ D: c( o$ l( z+ m7 o* X
* U( Y( n, o$ l. r0 S' ]0 u6 _
其中, ) }3 }2 F0 s& x8 J1 ?! s! B, ? 表示神经元i在t时刻的状态,为1表示激发态,为0表示抑制态; $ z; @# A+ m8 D: w0 m4 Y 是神经元i和j之间的连接强度; ( |7 T. i) |- `5 G 表示神经元i的阈值,超过这个值神经元才能激发。) ?- C2 e+ o7 `! K3 c: \
这个模型是最简单的神经元模型。但是功能已经非常强大:此模型的发明人McCulloch和Pitts已经证明,不考虑速度和实现的复杂性,它可以完成当前数字* g L* x L7 m1 {. g
计算机的任何工作。 # d, O- e8 A, _! P" _ 7 J" o. g2 L& c2 P- N/ H. g
7 d& B1 o, Z: M: |. s4 F2 X4 G
以上这个M-P模型仅仅是一层的网络,如果从对一个平面进行分割的方面来考虑的话,M-P网络只能把一个平面分成个半平面,却不能够选取特定的一部分。而解决的6 N3 k% Z2 ^4 Q+ G: b
办法就是“多层前向网路”。' r3 J9 E4 u! |
& ?( k9 X- l1 s2 |% _* j: ?! f
6 \1 T, N& V4 a1 k 图2 3 v- G* q, m9 \9 g2 h8 N7 C v 图2是多层前向网络的示意图。最下面的5 I4 t! ^2 n, j' w1 E F8 \
称作输入层,最上面一层称作输出层,任何一个中间层都接受来自前一层的所有输入,加工后传入后一层。每一层的神经元之间没有联系,输入输出层之间也没有直接联系 5 t. O# @" B5 _/ p& M9 O,并且仅仅是单向联系,没有反馈。这样的网络被称作“多层前向网络”。数据在输入后,经过每一层的加权,最后输出结果。 & G1 b3 o3 U: Z' c6 W) j1 n& F+ D. C6 h " Z; y- |" d9 k6 r8 Z : K: w0 \% x1 r
图3 ' h6 ]9 V& Q j4 M! d
如图3,用可覆盖面来说明多层网络的功能:单层网络只能把平面分成两部分,双层网络就可以分割任意凸域,多层网络则可以分割任意区域。& \8 q% I7 G) C
为了让这种网络有合适的权值,必须给网络一定的激励,让它自己学习,调整。一种方法称作“向后传播算法(Back * \" |7 p6 O4 I5 b* H Propagation,BP)”,其基本思想是考察最后输出解和理想解的差异,调整权值,并把这种调整从输出层开始向后推演,经过中间层,达到输入层。- @( C# w2 p8 p# _
+ r. {# d6 {& Z5 E 6 m" g4 j* S/ N
可见,神经网络是通过学习来达到解决问题的目的,学习没有改变单个神经元的结构和工作方式,单个神经元的特性和要解决的问题之间也没有直接联系,这里学习的作用 / o: B$ e [& c3 j" Z( h; K9 v$ Q是根据神经元之间激励与抑制的关系,改变它们的作用强度。学习样本中的任何样品的信息都包含在网络的每个权值之中。 . i1 z" t" B' R, F4 ]$ Y9 j( l5 l . l2 H' i5 F5 e: N S% E! s( V* X
+ w# e2 \- ~, `
BP算法中有考察输出解和理想解差异的过程,假设差距为w,则调整权值的目的就是为了使得w最小化。这就又包含了前文所说的“最小值”问题。一般的BP算法采用( ?" x' L5 ~6 X# @0 z) Z# I
的是局部搜索,比如最速下降法,牛顿法等,当然如果想要得到全局最优解,可以采用模拟退火,遗传算法等。当前向网络采用模拟退火算法作为学习方法的时候,一般成6 C! I" \' W) c; x
为“波尔兹曼网络”,属于随机性神经网络。- w! ?$ }5 c6 F0 q" G, z( n* A
1 n, ?# E7 y' K3 I9 y- H5 t4 l# s, l
( R2 d) H7 G5 }
在学习BP算法学习的过程中,需要已经有一部分确定的值作为理想输出,这就好像中学生在学习的时候,有老师的监督。如果没有了监督,人工神经网络该怎么学习? & r7 N ?) d. {' w) `, R : J7 q, O3 f% R1 J1 Y8 q" x W / @" ]. w5 t+ e ?3 X3 Y
就像没有了宏观调控,自由的市场引入了竞争一样,有一种学习方法称作“无监督有竞争的学习”。在输入神经元i的若干个神经元之间开展竞争,竞争之后,只有一个神; Q, {; A% S# M; I
经元为1,其他均为0,而对于失败的神经元,调整使得向对竞争有利的方向移动,则最终也可能在一次竞争中胜利;8 h9 L3 T* [0 e
3 W+ F' E1 o; E + H" ^, E& K3 x- H
人工神经网络还有反馈网络如Hopfield网络,它的神经元的信号传递方向是双向的,并且引入一个能量函数,通过神经元之间不断地相互影响,能量函数值不断下 ; Q, ]1 g7 B3 W# U. o3 z降,最后能给出一个能量比较低的解。这个思想和模拟退火差不多。 * r7 w/ F& s+ e. \$ F$ j ) C& t4 j* X* n2 L5 p" f& c! E1 J
6 C A8 N' @$ {" { 人工神经网络应用到算法上时,其正确率和速度与软件的实现联系不大,关键的是它自身的不断学习。这种思想已经和冯·诺依曼模型很不一样。3 B0 \3 \( z& L; \! X* b+ @
5 }3 h) a$ I3 Q" q0 ] 7 _9 ?# g" f, }+ S4 r0 K 总结 . G1 M. K- I$ c# ` 模拟退火,遗传算法,禁忌搜索,神经网络在解决全局最优解的问题上有着独到的优点,并且,它们有一个共同的特点:都是模拟了自然过程。模拟退火思路源于物理学中 7 K) s% b- f. a. S/ r固体物质的退火过程,遗传算法借鉴了自然界优胜劣汰的进化思想,禁忌搜索模拟了人类有记忆过程的智力过程,神经网络更是直接模拟了人脑。5 E6 x7 P! r J+ b! i
; H: Z% c% _* @" A' n$ q
" t9 |& e* r$ Z. O0 D ; o: }, t+ t% k& ]( a" ]
它们之间的联系也非常紧密,比如模拟退火和遗传算法为神经网络提供更优良的学习算法提供了思路。把它们有机地综合在一起,取长补短,性能将更加优良。 O# y* [$ D& Q, U b" B# H
- L, p' f. |* b 这几种智能算法有别于一般的按照图灵机进行精确计算的程序,尤其是人工神经网络,是对计算机模型的一种新的诠释,跳出了冯·诺依曼机的圈子,按照这种思想来设计7 k# q5 [ v! P% M8 T
的计算机有着广阔的发展前景$ s4 M8 h. m. I+ L& G3 T6 b
禁忌搜索算法(Tabu Search,TS)5 G6 s. b4 V7 f0 y, }/ k2 P! P
为了找到“全局最优解”,就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索,导致一叶障目,不见泰山。禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它(但不是完全隔绝),从而获得更多的搜索区间。兔子们找到了泰山,它们之中的一只就会留守在这里,其他的再去别的地方寻找。就这样,一大圈后,把找到的几个山峰一比较,珠穆朗玛峰脱颖而出。 $ O; w: g ]9 \: C# \当兔子们再寻找的时候,一般地会有意识地避开泰山,因为他们知道,这里已经找过,并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表(tabu list)”的含义。那只留在泰山的兔子一般不会就安家在那里了,它会在一定时间后重新回到找最高峰的大军,因为这个时候已经有了许多新的消息,泰山毕竟也有一个不错的高度,需要重新考虑,这个归队时间,在禁忌搜索里面叫做“禁忌长度(tabu length)”;如果在搜索的过程中,留守泰山的兔子还没有归队,但是找到的地方全是华北平原等比较低的地方,兔子们就不得不再次考虑选中泰山,也就是说,当一个有兔子留守的地方优越性太突出,超过了“best to far”的状态,就可以不顾及有没有兔子留守,都把这个地方考虑进来,这就叫“特赦准则(aspiration criterion)”。这三个概念是禁忌搜索和一般搜索准则最不同的地方,算法的优化也关键在这里。 ) l7 [, R, X- B9 t伪码表达:+ M- v2 V9 Y! r3 w) l% p
procedure tabu search; ) E. P' V: ^0 J) c7 f% Ibegin + ]) }: G9 u& K: s' s* W6 Q* o- h9 _initialize a string vc at random,clear up the tabu list; 7 @( r. h! i u8 T6 y8 Lcur:=vc;' N0 d, y! R) ^2 ~
repeat( g& }/ v0 N K! S- Z
select a new string vn in the neighborhood of vc; & ]$ `- h' p# `9 }$ o. |6 o. Uif va>best_to_far then {va is a string in the tabu list}# x' `" `% n, Y1 T }) `4 Y
begin9 U0 O+ L# E2 {+ U% Z: J
cur:=va;' p7 f2 S3 w! c" v; r- @* f
let va take place of the oldest string in the tabu list;% [, W! u. ^) J6 |. s, ~! u
best_to_far:=va;# I0 W/ H6 ~( ~4 ?: r5 M
end else % ?. k J0 Y! K6 \& ~begin# f* k2 x# x$ t
cur:=vn;- L! q* A6 S' Z3 r: A! E* F) N
let vn take place of the oldest string in the tabu list; * g5 j) Y8 p2 |4 D+ N4 _# Gend;- X% u1 i0 P1 `9 I$ G
until (termination-condition); w0 }( B0 t! y% c2 G; wend; # Q+ a" \: \: E5 { : p7 ~" `8 p1 f" J以上程序中有关键的几点: 3 g6 F+ _9 M+ Q/ Z(1)禁忌对象:可以选取当前的值(cur)作为禁忌对象放进tabu list,也可以把和当然值在同一“等高线”上的都放进tabu list。/ C- k% N1 W3 @) b7 \
(2)为了降低计算量,禁忌长度和禁忌表的集合不宜太大,但是禁忌长度太小容易循环搜索,禁忌表太小容易陷入“局部极优解”。# I' T( P4 l( h* d' Q2 }# m: J
(3)上述程序段中对best_to_far的操作是直接赋值为最优的“解禁候选解”,但是有时候会出现没有大于best_to_far的,候选解也全部被禁的“死锁”状态,这个时候,就应该对候选解中最佳的进行解禁,以能够继续下去。" w, m' `. T# K7 t$ s
(4)终止准则:和模拟退火,遗传算法差不多,常用的有:给定一个迭代步数;设定与估计的最优解的距离小于某个范围时,就终止搜索;当与最优解的距离连续若干步保持不变时,终止搜索;2 h- e5 v% _7 l) h8 m
禁忌搜索是对人类思维过程本身的一种模拟,它通过对一些局部最优解的禁忌(也可以说是记忆)达到接纳一部分较差解,从而跳出局部搜索的目的。6 v$ R" i% V& Q9 y. ?, r: O0 k
人工神经网络(Artificial Neural Network,ANN) $ j* t! V( l+ P) A神经网络从名字就知道是对人脑的模拟。它的神经元结构,它的构成与作用方式都是在模仿人脑,但是也仅仅是粗糙的模仿,远没有达到完美的地步。和冯·诺依曼机不同,神经网络计算非数字,非精确,高度并行,并且有自学习功能。4 y: N0 _' L4 }$ x* e
生命科学中,神经细胞一般称作神经元,它是整个神经结构的最基本单位。每个神经细胞就像一条胳膊,其中像手掌的地方含有细胞核,称作细胞体,像手指的称作树突,是信息的输入通路,像手臂的称作轴突,是信息的输出通路;神经元之间错综复杂地连在一起,互相之间传递信号,而传递的信号可以导致神经元电位的变化,一旦电位高出一定值,就会引起神经元的激发,此神经元就会通过轴突传出电信号。 9 \2 ]0 Q9 p$ J4 k而如果要用计算机模仿生物神经,就需要人工的神经网络有三个要素:(1)形式定义人工神经元;(2)给出人工神经元的连接方式,或者说给出网络结构;(3)给出人工神经元之间信号强度的定义。. N* _6 g, O6 ?* h/ o' g, U- M
历史上第一个人工神经网络模型称作M-P模型,非常简单: 3 W1 \$ r4 D0 J" B其中, 表示神经元i在t时刻的状态,为1表示激发态,为0表示抑制态; 是神经元i和j之间的连接强度; 表示神经元i的阈值,超过这个值神经元才能激发。 ; p' f0 \: N6 e7 r这个模型是最简单的神经元模型。但是功能已经非常强大:此模型的发明人McCulloch和Pitts已经证明,不考虑速度和实现的复杂性,它可以完成当前数字计算机的任何工作。 : K: V6 q' F! Q7 O2 z. S以上这个M-P模型仅仅是一层的网络,如果从对一个平面进行分割的方面来考虑的话,M-P网络只能把一个平面分成个半平面,却不能够选取特定的一部分。而解决的办法就是“多层前向网路”。 6 ?6 U9 H m* X" G, ]4 Y7 ^图2 2 r1 ^: }6 X* T, Z图2 是多层前向网络的示意图。最下面的称作输入层,最上面一层称作输出层,任何一个中间层都接受来自前一层的所有输入,加工后传入后一层。每一层的神经元之间没有联系,输入输出层之间也没有直接联系,并且仅仅是单向联系,没有反馈。这样的网络被称作“多层前向网络”。数据在输入后,经过每一层的加权,最后输出结果。 6 a" x. |! d5 x6 U2 D7 w图3 5 z& {, \$ t- B5 S& N; z如图3,用可覆盖面来说明多层网络的功能:单层网络只能把平面分成两部分,双层网络就可以分割任意凸域,多层网络则可以分割任意区域。 W; \& q+ S- \! G9 B6 G为了让这种网络有合适的权值,必须给网络一定的激励,让它自己学习,调整。一种方法称作“向后传播算法(Back Propagation,BP)”,其基本思想是考察最后输出解和理想解的差异,调整权值,并把这种调整从输出层开始向后推演,经过中间层,达到输入层。1 H2 z! h! N4 e8 g/ r }
可见,神经网络是通过学习来达到解决问题的目的,学习没有改变单个神经元的结构和工作方式,单个神经元的特性和要解决的问题之间也没有直接联系,这里学习的作用是根据神经元之间激励与抑制的关系,改变它们的作用强度。学习样本中的任何样品的信息都包含在网络的每个权值之中。 . k9 o8 V9 Z( m! d# w1 oBP算法中有考察输出解和理想解差异的过程,假设差距为w,则调整权值的目的就是为了使得w最小化。这就又包含了前文所说的“最小值”问题。一般的BP算法采用的是局部搜索,比如最速下降法,牛顿法等,当然如果想要得到全局最优解,可以采用模拟退火,遗传算法等。当前向网络采用模拟退火算法作为学习方法的时候,一般成为“波尔兹曼网络”,属于随机性神经网络。 1 H( S3 ~1 Y9 t6 a( E在学习BP算法学习的过程中,需要已经有一部分确定的值作为理想输出,这就好像中学生在学习的时候,有老师的监督。如果没有了监督,人工神经网络该怎么学习?0 L: _" f! |$ X7 a: I
就像没有了宏观调控,自由的市场引入了竞争一样,有一种学习方法称作“无监督有竞争的学习”。在输入神经元i的若干个神经元之间开展竞争,竞争之后,只有一个神经元为1,其他均为0,而对于失败的神经元,调整使得向对竞争有利的方向移动,则最终也可能在一次竞争中胜利; " S7 x( s+ M+ \/ M( s2 M8 V9 y+ p人工神经网络还有反馈网络如Hopfield网络,它的神经元的信号传递方向是双向的,并且引入一个能量函数,通过神经元之间不断地相互影响,能量函数值不断下降,最后能给出一个能量比较低的解。这个思想和模拟退火差不多。8 H" ~# ~2 S; O' f
人工神经网络应用到算法上时,其正确率和速度与软件的实现联系不大,关键的是它自身的不断学习。这种思想已经和冯·诺依曼模型很不一样。+ |( }- e: j$ w& p$ K" [4 e; g
总结% R" F1 u$ ?+ s/ A6 Z& m2 o
模拟退火,遗传算法,禁忌搜索,神经网络在解决全局最优解的问题上有着独到的优点,并且,它们有一个共同的特点:都是模拟了自然过程。模拟退火思路源于物理学中固体物质的退火过程,遗传算法借鉴了自然界优胜劣汰的进化思想,禁忌搜索模拟了人类有记忆过程的智力过程,神经网络更是直接模拟了人脑。 0 s8 Z/ U; i/ {; N( c5 \! N它们之间的联系也非常紧密,比如模拟退火和遗传算法为神经网络提供更优良的学习算法提供了思路。把它们有机地综合在一起,取长补短,性能将更加优良。3 i2 [" ]3 x5 `
这几种智能算法有别于一般的按照图灵机进行精确计算的程序,尤其是人工神经网络,是对计算机模型的一种新的诠释,跳出了冯·诺依曼机的圈子,按照这种思想来设计的计算机有着广阔的发展前景 # g5 C7 y6 {9 n7 f& f3 e+ ]