/ }7 ^% @3 N' `6 o0 } 4.兔子们知道一个兔的力量是渺小的。他们互相转告着,哪里的山已经找过,并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这 9 M9 G3 V+ r( g& z' }* r就是禁忌搜索。 - S# \5 |6 ^# e+ i( C& i ; H! q3 T+ J3 k. `# O6 ^
+ \) L" O# `8 s6 m: s
智能优化算法的概述 5 |) e1 O& o9 _! N/ H 4 v) m- p ~- R0 E/ c/ J3 f6 m
- B, V1 w" x9 o4 @1 F5 S
智能优化算法要解决的一般是最优化问题。最优化问题可以分为(1)求解一个函数中,使得函数值最小的自变量取值的函数优化问题和(2)在一个解空间里面,寻找最! Y# b1 h! i6 I( M& f3 w6 V
优解,使目标函数值最小的组合优化问题。典型的组合优化问题有:旅行商问题(Traveling $ ?& s$ n ^4 T( P7 F+ y
Salesman Problem,TSP),加工调度问题(Scheduling $ P8 _4 W% H, c% `, A7 {7 d p Q% w
Problem),0-1背包问题(Knapsack - V% T/ k$ j- `% \+ T- T
Problem),以及装箱问题(Bin Packing Problem)等。3 J7 V* b- }# b- A3 u, z
优化算法有很多,经典算法包括:有线性规划,动态规划等;改进型局部搜索算法包括爬山法,最速下降法等,本文介绍的模拟退火、遗传算法以及禁忌搜索称作指导性搜3 i$ F: b8 Q) E, Y4 r! M. G% T
索法。而神经网络,混沌搜索则属于系统动态演化方法。 % x; C. T& b9 [: g) A- v 1 F' {& ]$ {5 d7 I! E% D* N
5 H# X7 f/ K6 Y) ?. ~0 r
优化思想里面经常提到邻域函数,它的作用是指出如何由当前解得到一个(组)新解。其具体实现方式要根据具体问题分析来定。 : R9 g3 c6 s }' c+ j5 k ' Q6 b# _& d8 l* I/ ]3 k 9 I& r7 g: D, H* ?; s; z0 c0 d- M 一般而言,局部搜索就是基于贪婪思想利用邻域函数进行搜索,若找到一个比现有值更优的解就弃前者而取后者。但是,它一般只可以得到“局部极小解”,就是说,可能 ( D! l# u, X3 O" ~$ y这只兔子登“登泰山而小天下”,但是却没有找到珠穆朗玛峰。而模拟退火,遗传算法,禁忌搜索,神经网络等从不同的角度和策略实现了改进,取得较好的“全局最小解 ”。0 Y3 @# `* g5 l. z5 G+ d
! s% g, \( q! U; K: @# p4 f
* D% g$ T) g+ k- f2 \' k 模拟退火算法(Simulated Annealing,SA)6 w v2 { u z. r8 T" S" M
. k& a6 V3 o0 Q% e 6 ?8 v+ p7 C5 P2 e) F. z 模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热的时候,粒子间的布朗运动增强,到达一定强度后,固体物质转化为液态,这个时候再& T! e0 s( a$ J. S6 K3 l5 a
进行退火,粒子热运动减弱,并逐渐趋于有序,最后达到稳定。/ ~7 M j+ n) O; H) l$ k
0 V L5 o' m( S ! R# ~$ d4 x8 b6 X
模拟退火的解不再像局部搜索那样最后的结果依赖初始点。它引入了一个接受概率p。如果新的点(设为pn)的目标函数f(pn)更好,则p=1,表示选取新点;否 0 _% d+ v/ x% l( v% F' n7 s则,接受概率p是当前点(设为pc)的目标函数f(pc),新点的目标函数f(pn)以及另一个控制参数“温度”T的函数。也就是说,模拟退火没有像局部搜索那* M4 L3 T1 Y9 K( D0 ?9 G
样每次都贪婪地寻找比现在好的点,目标函数差一点的点也有可能接受进来。随着算法的执行,系统温度T逐渐降低,最后终止于某个低温,在该温度下,系统不再接受变3 T- h z' ?( x8 q* [/ H! J! E' m
化。 3 \2 ]7 M2 P' g5 @* W G ) k* U- B j2 E n9 G) ] & _3 m. _0 _; s4 l9 E
模拟退火的典型特征是除了接受目标函数的改进外,还接受一个衰减极限,当T较大时,接受较大的衰减,当T逐渐变小时,接受较小的衰减,当T为0时,就不再接受衰 / d& U; j) t% H5 C+ b减。这一特征意味着模拟退火与局部搜索相反,它能避开局部极小,并且还保持了局部搜索的通用性和简单性。 0 X: ^: N6 `* T4 [2 ~- x 在物理上,先加热,让分子间互相碰撞,变成无序状态,内能加大,然后降温,最后的分子次序反而会更有序,内能比没有加热前更小。就像那只兔子,它喝醉后,对比较 _5 G8 O! R1 @4 r; Y
近的山峰视而不见,迷迷糊糊地跳一大圈子,反而更有可能找到珠峰。 ! A' F0 [4 Z& ^, M7 r4 C4 ? 6 {; n7 m/ ^* b$ o: A- b
- L" N, b! y9 }: L# ~8 K b; f 值得注意的是,当T为0时,模拟退火就成为局部搜索的一个特例。 ; z( @$ z" R! V, a7 B& g/ O( l# G# Y " t9 X4 l/ {2 ?# M/ L/ W& g* ^) I 7 c0 W% j5 A. h( b# J% A 模拟退火的伪码表达: 8 O% q* k4 v. y( N- J- U procedure simulated annealing / W7 K" A% i+ ^% |9 S; z( A, b3 { begin + g, |3 F/ H; k$ c- ~$ d4 x t:=0; / q0 g( V+ }; ]# \* w- y
initialize temperature T 4 z; @6 Q& {( F9 t
select a current string vc at random; : x& `3 Q2 i: F% M9 Z: J
evaluate vc; 7 k: l3 T" ?7 R: S: l5 r
repeat 4 D% k$ G o* |: H1 X/ r4 x
repeat . U2 C* T- N2 z# V
select a new string vn in the neighborhood of vc; (1) 5 ^2 o6 q; s& I3 E; o. S4 | if f(vc) then vc:=vn; 0 c& E! h5 y& C! w
else if random [0,1] then vc:=vn; $ S0 B5 U, D+ F H6 f- M until (termination-condition) (3) 4 V/ i2 \* o3 y: Z T:=g(T,t); (4) , C( D% G2 ?" T+ Q# D7 Q8 q T:=t+1; ?$ T& V4 `# M until (stop-criterion) (5) 4 B, f' M6 L, x! a/ Y end; 4 R: P W6 F' G( e4 P( |9 j
# D; ~: W, v8 Q2 n, v8 E4 [ & ~5 u9 u$ r7 v: J) q
上面的程序中,关键的是(1)新状态产生函数,(2)新状态接受函数,(3)抽样稳定准则,(4)退温函数,(5)退火结束准则6 P' T; Y# C0 A N6 R2 r
(简称三函数两准则)是直接影响优化结果的主要环节。虽然实验结果证明初始值对于最后的结果没有影响,但是初温越高,得到高质量解的概率越大。所以,应该尽量选6 Z% L1 S9 B+ \$ }' R* S
取比较高的初温。: w! q4 M/ d1 O9 _7 b, q* A
& D/ [; @0 \" L& i4 ]- m ! C" c) H5 d% U3 z 4 M) O, x& `- P( u3 F
它们之间的联系也非常紧密,比如模拟退火和遗传算法为神经网络提供更优良的学习算法提供了思路。把它们有机地综合在一起,取长补短,性能将更加优良。 * L2 E, c0 M6 N$ \ 3 l& w" P% ]8 k" |
这几种智能算法有别于一般的按照图灵机进行精确计算的程序,尤其是人工神经网络,是对计算机模型的一种新的诠释,跳出了冯·诺依曼机的圈子,按照这种思想来设计 : h9 f5 W( m; s& D的计算机有着广阔的发展前景) s2 ?" [$ c3 u& o$ X
禁忌搜索算法(Tabu Search,TS) + x, m4 y! F1 e" E& g& s为了找到“全局最优解”,就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索,导致一叶障目,不见泰山。禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它(但不是完全隔绝),从而获得更多的搜索区间。兔子们找到了泰山,它们之中的一只就会留守在这里,其他的再去别的地方寻找。就这样,一大圈后,把找到的几个山峰一比较,珠穆朗玛峰脱颖而出。8 D, C) b9 m( L' T& f6 h
当兔子们再寻找的时候,一般地会有意识地避开泰山,因为他们知道,这里已经找过,并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表(tabu list)”的含义。那只留在泰山的兔子一般不会就安家在那里了,它会在一定时间后重新回到找最高峰的大军,因为这个时候已经有了许多新的消息,泰山毕竟也有一个不错的高度,需要重新考虑,这个归队时间,在禁忌搜索里面叫做“禁忌长度(tabu length)”;如果在搜索的过程中,留守泰山的兔子还没有归队,但是找到的地方全是华北平原等比较低的地方,兔子们就不得不再次考虑选中泰山,也就是说,当一个有兔子留守的地方优越性太突出,超过了“best to far”的状态,就可以不顾及有没有兔子留守,都把这个地方考虑进来,这就叫“特赦准则(aspiration criterion)”。这三个概念是禁忌搜索和一般搜索准则最不同的地方,算法的优化也关键在这里。! _" e) q3 K% Z! i3 B. f ^
伪码表达:5 E) w' \8 c0 @* k9 D5 W9 H
procedure tabu search;# q+ T3 z1 J# I& V2 U0 I! O5 H$ V
begin+ Y" }% ?2 y# A( `$ W; k9 b$ O
initialize a string vc at random,clear up the tabu list; / | d0 I, M4 r) u+ M: V: F/ O2 Ocur:=vc;( ]: a" v8 @+ y! n6 b" C
repeat7 Q ^/ w- l! ]1 h. V
select a new string vn in the neighborhood of vc; ( Z- S* m7 I, C( N& s6 W$ Kif va>best_to_far then {va is a string in the tabu list}$ R/ Z7 j$ U" p6 @+ c9 c: @$ N; ?
begin6 s$ ^! b8 j: \) m" Q) \
cur:=va;% T* \ e2 c( S! \% I
let va take place of the oldest string in the tabu list;$ U/ k, e+ S! k0 a) t7 G: e
best_to_far:=va;9 G0 E, h7 R& T2 f
end else5 r7 R' N3 f& G ~
begin7 v( M# r+ F, a. m, W% }+ F
cur:=vn; - v' g |* S7 \: W( u( W. f8 Qlet vn take place of the oldest string in the tabu list;8 m% [0 b/ P" M8 u' m+ E; [. u
end; 8 D/ ?6 ]9 i0 t' @6 h( puntil (termination-condition);1 p; P/ x& r* T( Z
end;" O' m/ F1 S% p3 u6 ^5 z! B
, B% s' l' u# `' _" _- v以上程序中有关键的几点:9 ~! `) T7 S2 w1 h
(1)禁忌对象:可以选取当前的值(cur)作为禁忌对象放进tabu list,也可以把和当然值在同一“等高线”上的都放进tabu list。$ I+ [; X5 s9 g8 @% \
(2)为了降低计算量,禁忌长度和禁忌表的集合不宜太大,但是禁忌长度太小容易循环搜索,禁忌表太小容易陷入“局部极优解”。 0 Y; O! F+ O7 j: A(3)上述程序段中对best_to_far的操作是直接赋值为最优的“解禁候选解”,但是有时候会出现没有大于best_to_far的,候选解也全部被禁的“死锁”状态,这个时候,就应该对候选解中最佳的进行解禁,以能够继续下去。 ) A7 f! h3 a3 o(4)终止准则:和模拟退火,遗传算法差不多,常用的有:给定一个迭代步数;设定与估计的最优解的距离小于某个范围时,就终止搜索;当与最优解的距离连续若干步保持不变时,终止搜索; ( _* t' T5 y8 W! {- U禁忌搜索是对人类思维过程本身的一种模拟,它通过对一些局部最优解的禁忌(也可以说是记忆)达到接纳一部分较差解,从而跳出局部搜索的目的。 r* _7 f7 e* J& p+ B; F人工神经网络(Artificial Neural Network,ANN) ! k. n' I9 I; k1 {- q神经网络从名字就知道是对人脑的模拟。它的神经元结构,它的构成与作用方式都是在模仿人脑,但是也仅仅是粗糙的模仿,远没有达到完美的地步。和冯·诺依曼机不同,神经网络计算非数字,非精确,高度并行,并且有自学习功能。 ; V, V2 ~0 I+ t8 s; F生命科学中,神经细胞一般称作神经元,它是整个神经结构的最基本单位。每个神经细胞就像一条胳膊,其中像手掌的地方含有细胞核,称作细胞体,像手指的称作树突,是信息的输入通路,像手臂的称作轴突,是信息的输出通路;神经元之间错综复杂地连在一起,互相之间传递信号,而传递的信号可以导致神经元电位的变化,一旦电位高出一定值,就会引起神经元的激发,此神经元就会通过轴突传出电信号。 ( s' b4 X* C: T7 O) g# Q8 }8 t# g而如果要用计算机模仿生物神经,就需要人工的神经网络有三个要素:(1)形式定义人工神经元;(2)给出人工神经元的连接方式,或者说给出网络结构;(3)给出人工神经元之间信号强度的定义。- V3 t7 w( H9 _% Z7 }
历史上第一个人工神经网络模型称作M-P模型,非常简单:3 z+ r+ x0 q% I1 z
其中, 表示神经元i在t时刻的状态,为1表示激发态,为0表示抑制态; 是神经元i和j之间的连接强度; 表示神经元i的阈值,超过这个值神经元才能激发。; d7 o* ]) w) B6 V( D
这个模型是最简单的神经元模型。但是功能已经非常强大:此模型的发明人McCulloch和Pitts已经证明,不考虑速度和实现的复杂性,它可以完成当前数字计算机的任何工作。 9 c- s+ q4 @8 ?2 ?: J以上这个M-P模型仅仅是一层的网络,如果从对一个平面进行分割的方面来考虑的话,M-P网络只能把一个平面分成个半平面,却不能够选取特定的一部分。而解决的办法就是“多层前向网路”。0 @" w/ b5 d: d( O+ o# w% } `4 N7 X) w2 D
图2 : U, W+ ?3 { m. L# Z, e, }图2 是多层前向网络的示意图。最下面的称作输入层,最上面一层称作输出层,任何一个中间层都接受来自前一层的所有输入,加工后传入后一层。每一层的神经元之间没有联系,输入输出层之间也没有直接联系,并且仅仅是单向联系,没有反馈。这样的网络被称作“多层前向网络”。数据在输入后,经过每一层的加权,最后输出结果。+ O7 R: y k( M, T k
图3 6 s2 v1 t) d0 c V# s如图3,用可覆盖面来说明多层网络的功能:单层网络只能把平面分成两部分,双层网络就可以分割任意凸域,多层网络则可以分割任意区域。* o% P7 K/ N: b8 u
为了让这种网络有合适的权值,必须给网络一定的激励,让它自己学习,调整。一种方法称作“向后传播算法(Back Propagation,BP)”,其基本思想是考察最后输出解和理想解的差异,调整权值,并把这种调整从输出层开始向后推演,经过中间层,达到输入层。; e# k. g. C0 A; R! L/ s9 A
可见,神经网络是通过学习来达到解决问题的目的,学习没有改变单个神经元的结构和工作方式,单个神经元的特性和要解决的问题之间也没有直接联系,这里学习的作用是根据神经元之间激励与抑制的关系,改变它们的作用强度。学习样本中的任何样品的信息都包含在网络的每个权值之中。 1 \( n7 _) D1 ]5 E/ Y' r: MBP算法中有考察输出解和理想解差异的过程,假设差距为w,则调整权值的目的就是为了使得w最小化。这就又包含了前文所说的“最小值”问题。一般的BP算法采用的是局部搜索,比如最速下降法,牛顿法等,当然如果想要得到全局最优解,可以采用模拟退火,遗传算法等。当前向网络采用模拟退火算法作为学习方法的时候,一般成为“波尔兹曼网络”,属于随机性神经网络。 8 i1 o) H; o7 G" p$ r0 v在学习BP算法学习的过程中,需要已经有一部分确定的值作为理想输出,这就好像中学生在学习的时候,有老师的监督。如果没有了监督,人工神经网络该怎么学习? : Y1 t. T1 f) x: p% n就像没有了宏观调控,自由的市场引入了竞争一样,有一种学习方法称作“无监督有竞争的学习”。在输入神经元i的若干个神经元之间开展竞争,竞争之后,只有一个神经元为1,其他均为0,而对于失败的神经元,调整使得向对竞争有利的方向移动,则最终也可能在一次竞争中胜利; % D& n5 q" ~: d人工神经网络还有反馈网络如Hopfield网络,它的神经元的信号传递方向是双向的,并且引入一个能量函数,通过神经元之间不断地相互影响,能量函数值不断下降,最后能给出一个能量比较低的解。这个思想和模拟退火差不多。 9 s% K& k) @9 p* x! }2 C' y ^4 N人工神经网络应用到算法上时,其正确率和速度与软件的实现联系不大,关键的是它自身的不断学习。这种思想已经和冯·诺依曼模型很不一样。7 {' u3 v7 k! W/ h* N- B
总结 $ ?) Q. I0 d# n* v+ o8 Z模拟退火,遗传算法,禁忌搜索,神经网络在解决全局最优解的问题上有着独到的优点,并且,它们有一个共同的特点:都是模拟了自然过程。模拟退火思路源于物理学中固体物质的退火过程,遗传算法借鉴了自然界优胜劣汰的进化思想,禁忌搜索模拟了人类有记忆过程的智力过程,神经网络更是直接模拟了人脑。% ~* _; j" c; ^/ c2 I* |
它们之间的联系也非常紧密,比如模拟退火和遗传算法为神经网络提供更优良的学习算法提供了思路。把它们有机地综合在一起,取长补短,性能将更加优良。 3 n% o" P. S' L这几种智能算法有别于一般的按照图灵机进行精确计算的程序,尤其是人工神经网络,是对计算机模型的一种新的诠释,跳出了冯·诺依曼机的圈子,按照这种思想来设计的计算机有着广阔的发展前景 & N( ]6 ?6 A+ j. |" V9 e$ j