再上一篇: 第 4 章  模拟退火和随机机
上一篇:4. 2  模拟退火
主页
下一篇:4. 4  习题
再下一篇: 第 5 章  均 场 退 火
文章列表

4. 3  随机机

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

随机霍氏网是一个最基本的波尔兹曼机。以基于热动力学中的艾星(Ising)模型的转移概率代替麦绰泼里斯准则,可将模拟退火应用于离散霍氏网就得到波尔兹曼机。在随机机系列中,高斯机是最通用的。用它可得到波尔兹曼机和柯西(Cauchy)机。

4.3.1  波尔兹曼机

考虑图3.1所示的双极霍氏网,回想

1

E(S) = - sisjwij - siIi (4.29)

2∑∑ ∑

i j≠i i

翻转一个神经元的状态,从si到- si,所引起的能量变化为

ΔE(i)= E(s1,s2,…, - si,…,sN) - E(s1,s2,…,si,…,sN)

= Δsi SiE

(4.30)

= Δsi - ∑wijsi- Ii

j≠i

= 2siui

依据艾星模型,接受这一从si到- si转移的概率为

P(si→- si) = 1 = 1 (4.31)

ΔE(i) 2siui

T T

1+ e 1+ e

其中T 是退火过程的温度。图4.4示出了(4.31)式所给出的接受概率。可见转移到低能状态的概率比转移到高能状态的要大。在高温下状态转移极易实现。而在温度到达零点时,转移到一个具有较高能量状态成为不可能发生的事情。因此,神经元i状态翻转的概率为

从- 1到1: 1 = P(ui) (4.32)

2ui

- T

1+ e

1

从1到- 1: = 1- P(u)i (4.33)

2ui

1+ eT

#第35页-

图4.4  波尔兹曼机在不同温度下的接受概率

用下式给出的随机激活函数取代图3.1中确定性的非线性函数,可以方便地获取随机霍氏网:

1 以概率P(ui)

ζ(ui) = - 1 以概率1- P(ui) (4.34)用ui代替2ui,(4.30)~(4.34)式可以用类似的方式运用于二值网。可以证明,尽管转移概率不同,稳态分布没有变化,且仍为波尔兹曼分布((4.2)式)。证明过程与4.2节给出的类似。随机霍氏网(波尔兹曼机)可泛化为神经元任意互连的网络,而这些神经元又可进一步划分为可见的和隐含的两类。所有随机霍氏网的神经元都是可见的。隐含的神经元与网络的输入或输出没有直接联系。可见神经元又可划分为输出神经元和输入神经元两类。在霍氏网被用作联想式存储器时,权值由训练获得。类似地,波尔兹曼机应用于联想式存储器或有教师的学习等问题时,它的权值也可由训练得到。

组合优化问题不但可被映射到霍氏网的框架上加以解决,它们也可被表述为二值规划问题[3]。回顾 并定义下列变量:

TSP

S l {sXi∈{0,1}©¦ ,i= 1,2,…,N}, (4.35)其中

sXi= 1  如果城市X 在旅程中处于第i个位置 (4.36)

0  其它

由此,TSP 可被表述为求取使下列代价函数最小的旅程。

f(S)©S¦∈S = ∑∑∑∑wXiYjsXisYj (4.37)

X Y i j

其约束条件为

∑sXi= 1且∑sXi= 1," X,i= 1,2,…,N (4.38)

X i

其中

dXY 若j = (i+ 1)modN

wXiYj = 其它 (4.39)

0

在波尔兹曼机上实现上面表述时,每个变量都用一个神经元实现,并通过引入约束重新定义权值。其目的是找到波尔兹曼机的一个构形(状态),使如下一致性函数(consensusfunction)取得最大值。

#第36页-

C(S)©S¦∈S = ∑∑∑∑wXiYjsXisYj (4.40)

X Y i j

其中

> max{dXA+ dXB©¦ ≠B}  若X = Y且i= j

wXiYj = - dXY 若X ≠Y且j = (i+ 1)modN

< - min{wXiXi,wYjYj} 若(X = Y且i≠j) 或(X ≠Y且i= j)

(4.41)这个一致性函数与代价函数十分相像,不过(4.38)式给出的代价函数约束条件已被吸收到(4.41)式给出的一致性函数的权值中去了。代价函数的最小化因而也等价于一致性函数的最大化。可以证明波尔兹曼机的一致性函数是可行的。也就是说,一致性函数的所有局部最大值都对应于有效的旅程,满足(4.38)式。这一函数也是保序的,亦即

f(S(k)) > f (S(l)) C(S(k)) < C(S(l)) 对于S(k),S(l) ∈S 和k≠l (4.42)与随机霍氏网使能量最小不同的是,这一波尔兹曼机使一致性最大。因此,在对这一模型采用模拟退火时,接受一个从S(- )到S(+ )的状态转移的概率为

接受概率= 1 (4.43)

- ΔC

1+ e T

其中 = ( (+ ))- ( (- ))。当 →0时,基本上不可能转换到一个一致性较小的状态。

ΔC C S C S T

接受概率看上去是图4.4中曲线沿y 轴的翻转。

4.3.2  高斯机

与波尔兹曼机的推导相似,高斯机[12]可由连续霍氏网(图3.3)获得。高斯机的动态特性与连续霍氏网的类似,只不过在每个神经元处加入了一个随机变量,从而有

si= sgmTi,β(ui) (4.44)

dui= wijsj + Ii+ η (4.45)

dt ∑

j≠i

其中η是一个均值为零的高斯随机变量。它的标准差为σ= cT,其中c是一个常数,T 是温度(与模拟退火有关的控制参数)。加入随机扰动的目的是使网络能够跳出局部最小值。

实现高斯机的步骤可以归纳如下:

(1) 初始化。

① 设si= v,其中v是一个分布于- 1与1之间的小随机数。

N N

② 设T0 为起始温度。

③ 定义退火流程。阿其雅玛(Akiyama)等采用了如下降温函数:

Tk = T0 (4.46)

1+ k

cT

其中Tk 是第k个温度,而CT 是一个常数。

#第37页-

(2) 在每个温度处重复下列步骤直至达到热平衡①:

① 随机选择一个在此次扫描中尚未被更新的神经元。

② 计算

u+ = u- + Δt wijsj- + Ii+ η (4.47)

j≠i

其中Δt 通常是一个很小的数值。

③ + = β( i+ )。阿其雅玛等[12]采用了

s sgm k u

βk = β0 (4.48)

1+ k

其中β0是β的初始值,cβ是个常数。注意,当k→∞时,Sigmoid函数的值接近硬限器。开始时神经元的值聚集在0附近,随着退火过程的推进,它们逐渐接近并稳定在1或- 1附近。这一使Sigmoid函数变陡的机制被称为函数的锐化。

(3) 降低温度,并重复步骤(2)直到温度到达零点。

+

上述的u 是一个随机过程。如果采用瞬时激活和硬限器(即除去图3.3中的积分器并使用硬限函数),则高斯机的动态过程为

ui= ∑wijsj + Ii+ η且si= sgn(ui) (4.49)

j≠i

因此可得

P(si= 1) = P(ui≥1)= fu(λ)dλ

0 i

(λ- u)2

- i

∞ 2

1 2σ

ui

= e dλ

0 2πσu

i (4.50)

ui 2

- λ

σ 2

ui 1

= e dλ

- ∞ 2π

ui

= Φ σu

其中fu(・)是ui的概率分布函数,ui和σu分别是ui的均值和标准差,Φ(・)是累积高斯

i i

分布函数。注意Φ(・)具有类似于Sigmoid函数的特性,因此选择一个适当的c可使高斯机接近波尔兹曼机(见习题4.5)。

4.3.3  柯西机

柯西机,亦称快速模拟退火[155][156],也可容易地由高斯机得到。只需将高斯机中的高斯随机变量(白噪声)用柯西随机变量(有色噪声)取代即可。这一替换增加了网络接受一个代价变大转移的可能性,因而增强了它跳出局部最小值的能力。另外,应用下述快速冷却流程使得柯西机有可能比另两个随机机更快地收敛:

① 在实际应用中,可以限定扫描次数。

#第38页-

Tk = T0 (4.51)

1+ k

其中Tk 为第k次降温或扫描时的温度,T0 是起始温度。

如果应用瞬时激活和硬限函数,则柯西机的动态过程类似于高斯机,只是下式中的η是一个柯西随机变量:

ui= ∑wijsj + Ii+ η且si= sgn(ui) (4.52)

j≠i

其中 的概率密度函数为[48]

η

fn(η) = 1 v (4.53)

πv2+ u2

这里,v> 0是一个常数。众所周知,柯西随机变量的均值和方差是不确定的。所以神经元si被激活的概率为

P(si= 1) = P(ui≥0)= fui(λ)dλ

0

∞ 1 v

= dλ

0 π 2

v + (λ- ∑wijsj - Ii) (4.54)

j≠i

∑wijsj + Ii

1 1 j≠i

= 2 + πarctan

v

其中fui(・)是柯西随机变量ui的概率分布函数。如果设定v等于退火过程的温度参数T,(4.54)式与柯西机在温度T 处有一个神经元被激活的概率相同。换句话说,在每个温度处,(4.54)式可用图4.5中两个等价途径中的任意一个实现。图中rand[0,1]是来自一

图 4.5  柯西机动态过程的实现

#第39页-

个在0和1之间均匀分布的随机数发生器的值,且

ζ(x) = 1 + 1arctan x (4.55)

2 π T