再上一篇:3. 4  组合最优化
上一篇:3. 5  习题
主页
下一篇:4. 2  模拟退火
再下一篇:4. 3  随机机
文章列表

第 4 章  模拟退火和随机机

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

自从科克派特里克、小哥拉特和瓦克奇(Kirkpatrick,Gelatt Jr.and Vecchi)在前人对于统计力学的研究[108]基础上发表了他们开创性的论文[98]以来,模拟退火算法被赞誉为解决许多高难度组合最优化问题的“救星”,并已被应用于诸如超大规模集成电路(VISI)的计算机辅助设计[100][146][164]、图象处理和计算机视觉[18][159][170]、电信(文献[15,37,51,55,139,165,166,167,168])、经济[63][171]以及其它众多工程和科学领域(文献[104,115,133,152,157])。在将退火的概念运用于神经网络的过程中,一系列被称为随机机的新型计算方法又涌现了出来。这一章对模拟退火和各种随机机的派生进行综述,并重点介绍模拟退火的基本特点。读者可从文献[2,58,59,123,163]等找到更多详细的分析。

4. 1  统计力学和麦绰泼里斯算法

模拟退火是根据液态或固态材料中粒子的统计力学与复杂组合最优化问题的求解过程的相似之处而提出来的。统计力学论述材料中相互作用粒子的特性。材料中粒子结构的不同对应于不同的能量水平。如果用粒子结构或其相应能量来定义材料的状态,麦绰泼里斯( )算法[108]可以给出一个简单的数学模型,用于描述材料在温度 下从具

Metropolis T

有能量E(i)的状态i进入具有能量E(j)的状态j 的机制:

・ 若E(j)≤E(i),状态转换被接收。

・ 若E(j)> E(i),则状态转换以如下概率被接收:

E(i)- E(j)

e KT (4.1)其中K 是物理学中的波尔兹曼常数,T 是材料的温度。

在一个特定温度下,如果进行足够多次数的转换,将能达到热平衡。此时材料处于状态i的概率可由波尔兹曼分布表述

- E(i)

e KT

πi(T) = PT(s= i) = ZT (4.2)

- E(j)

其中 是一个用于表示材料当前状态的随机变量, ZT = e KT 被称为划分函数,它对

s ∑

j∈S

在状态空间S 上的所有可能状态求和。显而易见,

- E(i)

e KT 1

limπi(T) = lim E(j) = (4.3)

T→∞ T→∞ -

KT ©¦©¦

∑e

j∈S

这表明所有状态在高温下具有相同的概率。而随着温度的下降,

#第27页-

E(i)- Emin

- KT

limπi(T)= lim e

E(j)- Emin

T→0 T→0 -

e KT

∑j∈S

E(i)- Emin

- KT

= lim e

E(j)- Emin E(j)- Emin

T→0 - -

e KT + e KT

j∈∑S j|∑S

min min (4.4)

E(i)- Emin

- KT

= lim e

E(j)- Emin

T→0 -

e KT

j∈∑S

min

1 如果i∈Smin

= ©¦min©¦

0  其它

其中Emin= minj∈SE(j)且Smin= {i:E(i)= Emin}。从上式可见,当温度降至很低时,材料倾向于进入具有最小能量的状态。

在统计力学中,固体的晶格结构通常处于低能状态。退火作为一个获取热槽中固体低能状态的热处理过程,经常用于晶体生长。这一过程首先将热槽中的固体加热,使其溶化为液体,然后逐步降温。在每个温度下,所有粒子随机排列直至达到热平衡。如果冷却过程足够缓慢,从而确保在每个温度下都达到热平衡,则当系统冻结时(T→0)低能晶体固态形成。相反,热槽温度迅速下降的淬火过程会使固化的结果为具有非晶结构或亚稳非晶结构(有缺陷的晶体)的玻璃状物质。

熵的概念有些深奥,但毕竟是理解热过程的一个非常重要的热力学工具。材料在热平衡状态下熵的定义为

H(T) = - ∑πi(T) ¡¤lnπi(T) (4.5)

i∈S

因此,材料在极限温度下的熵为

limH(T) = - 1 ln 1 = ln©¦©¦ (4.6)

T→∞ ∑

i∈S ©¦©¦ ©¦©¦

limH(T) = - 1 ln 1 = ln©¦min©¦ (4.7)

T→0 ∑

i∈S ©¦min©¦ ©¦min©¦

min

且有

H(T)= - [lnπi(T) + 1] ¡¤ πi(T)

T ∑ T

i∈S (4.8)

= - - E(i) - lnZT + 1 ¡¤ πi(T)

∑ KT T

i∈S

如果我们定义平均能量为

ET = ∑πi(T) ¡¤E(i) (4.9)

i∈S

方差为

#第28页-

2 = (E(i) - ET)2 = E2 - E2 (4.10)

∑i∈S

- E(i)

π(T)i KT

= e

T T T

Z

- E(i)

KT - E(i)

E(i) e 1 KT

= 2 - 2e ZT

KT ZT ZT T

πi(T) - E(i)

E(i) 1 KT

= 2πi(T) - 2 e E(i) (4.11)

ZT∑

KT KT i∈S

= πi(T)[E(i) - ET]

KT2

H(T) E(i) πi(T)

= + lnZ - 1 ¡¤ 2 [E(i) - ET]

T ∑ KT KT

i∈S

= 1 E(i)πi(T)[E(i) - ET]

2 3∑

K T i∈S

+ (lnZ- 1) πi(T)[E(i) - ET] (4.12)

2 ∑

KT i∈S

1 2

= 2 3 E (i) ¡¤πi(T) - ET E(i) ¡¤πi(T)

K T ∑ ∑

i∈S i∈S

2

= δ

K2T3

2 H(T)

由T> 0和σT≥0,可知 T ≥0。可从(4.3)式、(4.4)式和(4.12)式看出熵随温度下降而单调递减(见图4.1)。在统计力学中,熵被用来衡量物理系统的有序性: 熵越大,系统越无序。如果温度缓慢下降并使材料在每个 温度下都松弛到热平衡,材料的熵在退火过程中会单调递减,使得材料进入有序的(晶态)结构。

图4.1  材料的熵H(T)与温度T 的关系

#第29页-