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

4. 2  模拟退火

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

表4.1给出了麦绰泼里斯算法与模拟退火的类比。麦绰泼里斯算法描述了液体结晶的过程: 在高温下,粒子能量较高,可以自由运动和重新排序; 在低温度下,粒子能量减弱,迁移率减小,并最终进入平衡态,固化为具有最小能量的晶体。模拟退火算法搜索组合优化问题的最优解或最佳组合。假定有待解决的问题是寻找一个多变量代价函数的最小值,可采用一种简单的迭代算法——局域搜索来求解最小代价。局域搜索从一个给定的初始解答出发,随机地生成新的解答。如果这一新解的代价小于当前解答的代价,则用它取代当前解答,否则舍弃这一新解。局域搜索算法不断地随机生成新解并重复上述步骤,直至求得最小代价解。不幸的是,局域搜索可能陷于局部最小值而不能自拔。为避免搜索过程在局部最小处受阻,模拟退火允许产生“爬山运动”,即转移到代价较高的解答。

表4.1  麦绰泼里斯算法与模拟退火的类比

麦绰泼里斯算法 模拟退火

・ 热退火过程的数学模型 ・组合优化中局域搜索的推广

・ 物理系统中的一个状态 ・最优化问题的一个解答

・ 状态的能量 ・解答的代价

・ 粒子的迁移率 ・解答的接受率

・ 温度 ・控制参数

考虑一个定义在某个有限集S 上代价函数为f:s→R+ 的组合优化问题,并定义有限集S,其中s∈S 是待求问题的解或构形。对每一个构形s∈S 都存在一个由对s的微小扰动而生成的邻域集合N(s) S。

在模拟退火中,接受从一个状态s(k)到另一个状态s′(k)的概率由麦绰泼里斯准则[108]决定:

[f(s′(k))- f(s(k))]+

- T

P[s(k),s′(k)] = Pr{s(k) →s′(k)}= e (4.13)其中 ′( )是通过一个扰动机制由 ( )生成的新解, 表示第 次迭代,而[ ]+ = {0,

s k N s k k x maxx}。相应地

1  若f(s′(k)) < f(s(k))

Pr{s(k+ 1) = s′(k)}= - f(s′(k))- f(s(k)) (4.14)

e T 否则

从(4.14)式给出的麦绰泼里斯准则可以看出,在一个给定温度T 下,模拟退火的操作类似于局域搜索但却允许搜索过程按一定概率从一个较低代价构形“爬山”到一个较高代价构形,从而避免搜索过程陷于局部最小值。随机点过程{s(k):k≥0}可用离散时间齐次马尔科夫( )链[2]来分析。一步转移矩阵为

Markov

#第30页-

P(i,j)= Pr[s(k+ 1) = j©¦(k) = i]

0 若j | N(i) 且j ≠i

- f(j)- f(i)

T (4.15)

= G(i,j)min{1,e } 若j ∈N(i) 且j ≠i

- f(j)- f(i)

1- G(i,i′)min{1,e T }  若j ≠i

∑i′≠i

其中G(ij, )是从构形i生成构形j 的概率。

如果生成任一组合i的概率在其邻域集合N(i)中均匀分布,且构形的转移基于(4.15)式,则相应的马尔科夫链可被证明是不可约的、非周期性的、循环的[2]。在这些条件下,经过有限次的转移,组合i的静平衡分布πi(T)由波尔兹曼分布给出,即

πi(T)= klim∞Pr{s(k) = i©¦ }

= klim∞Pr{s(k) = i©¦(0) = j," j,T}

f(i) (4.16)

- T

= e

- f(i)

e T

j∈S

与统计力学((4.4)式)的分析类似,构形i在过程冻结时的静平衡分布变为

1 如果i∈Smin

* ©¦min©¦

πi = lim∞πi(T) = (4.17)

0  否则

而且

lim[limP(s(k) ∈Smin)] = lim πi(T) = * = 1 (4.18)

T→0 k→∞ T→0∑ ∑

i∈S i∈Smin

该式表明模拟退火算法渐进收敛于具有最小代价的构形。也就是说,如果温度是缓慢下降的,且在每个温度下都有足够数目的转移,则最小代价的全局最优构形(解答)以概率1被找到。关于收敛性的各种证明可见文献[59,60,61,70],其中文献[70]给出了最严格的充要条件。

4.2.1  有限时间实现

模拟退火算法有两个主要操作: 一个是称为冷却流程的热静力学操作,用于设定温度下降幅度(算法的一个参数); 另一个用于在每个温度下搜索最优解的随机松弛过程。本章前述分析只是说明模拟退火具有逐渐达到最优解的能力,但却是以搜索过程经历无限次转换为前提的。在实际应用中,模拟退火必须在有限时间内实现,否则它就显示不出相对于简单随机搜索的优势。

在有限时间条件下实现模拟退火算法需要有: 一个起始温度、一个控制温度下降的函数、一个决定在每个温度下状态转移参数的准则、一个终止温度以及一个终止模拟退火的准则。

科克派特里克等人[98]在解决计算机芯片的布线问题时采用了下列指数冷却流程:

(1) 给定一个高起始温度T0= 10。相应于材料溶化为液态的物理状况,一个高的温度确保接受率接近1。一个温度下的接受率定义为被接受的状态转移数与在给定温度下所有提出的状态转移数之比。在高温下,事实上所有提出的转移都被接受。随着温度的下

#第31页-

降,状态转移的接受率越来越小。状态转移最终随着系统冻结于一个很低温度时停止。起始温度的获取可从一个较低温度出发,逐渐升温直至接受率接近1。

(2) 降温函数为Tk+1= αTk,其中α通常接近1,且Tk代表第k次递减时的温度。科克派特里克等用的是α= 0.9。

(3) 在每个温度下的马尔科夫链的长度就是达到ε-准平衡态时被生成的状态转移个数,其中ε是一个特定的正常数。换句话说,当给定温度下马尔科夫链的长度足以使已得解答的概率分布以ε(在范数意义上)接近于相应的静态分布。直观上,这一条件可被定量化为要求在每个温度下被接受的转移数超过特定阈值。科克派特里克等以50000次被接受的转移作为每个温度下的阈值。同时,ε越大,要求的马尔科夫链越小。注意,在高温下几乎所有生成的转移都被接受,因而ε-准平衡态迅速达到。也就是说,高温下解答的概率分布接近均匀,与(4.3)式给出的静态分布相同。这就是为什么退火应从起始温度T0 出发。当温度降到T0 以下时,接受率从1急剧下降。在降温函数的降温梯度与马尔科夫链的长度之间,存在这一个取舍的问题。降温梯度越大,达到准平衡态所需的马尔科夫链越长。在温度趋于零时,基本上没有可被接受的状态转移,因而马尔科夫链可能会非常的长。在实际应用中,为马尔科夫链的长度设有一个常数上限。

(4) 当温度足够接近于零,或连续一组马尔科夫链上最后一个解答的代价不再发生变化时,退火过程终止。科克派特里克等所用的终止条件则是在最后连续三个温度下都达不到所希望的接受数。

阿特斯( )和拉合文( )提出了另一个冷却流程[2][4]。该流程使得模拟

Aarts Laarhoven

退火算法的运行可在多项式时间内完成。

(1) 起始温度T0 由下述过程得到:

令  n1 为代价减小的转移的数目,

n2 为代价增大的转移的数目,

(+ )为 2 个代价增大转移的平均代价差。

Δ n

将接受率近似为

(+)

- T

A≈n1+ n2e (4.19)

n1 + n2

可得

(+ )

T ≈ n2 (4.20)

loge

n2A- n1(1- A)

① 设置T0= 0。

② 生成n组解答,并以(4.20)式更新T。这里n= n1+ n2。

③ 基于②,以(4.19)式更新A。

④ 重复②和③直到A超过一个接近于1的阈值。

(2) 按下式降温

Tk+ 1= Tk (4.21)

1+ Tkloge(1+ δ)

3σk

#第32页-

其中δ被称为距离参数,σk 是在温度Tk 处生成的所有解答(状态)的标准差。在实际应用中,标准差可由样本差来近似。δ越大,降温幅度也就越大; 反之亦然。

(3) 在每个温度下马尔科夫链的长度可被视为在这一温度下起始解答邻域的大小,而这一邻域的大小又取决于生成解答的机制。以N 城市TSP 为例,如果使用稍后将要介绍的对换机制,邻域的大小为(N- 1)(N- 2)。

(4) 退火过程在温度T 到达终止温度Ts 时停下。Ts 满足下列条件:

Ts < f > T < εs (4.22)

< f > ∞ T T=T

s

其中εs是称为停止参数的较小正常数,而< f> T 则为温度T 下生成的解答的代价均值(代价期望值)。在实际应用中,代价的期望值通常由样本均值来近似。

可以证明, 在应用上述冷却流程的条件下,到达停止准则时的马尔科夫的链数以O(loge©¦©¦为上限,算法计算复杂度为O(τLloge©¦ ©)¦,其中τ是计算一次转移所需的时间,L 则是每个马尔科夫链的长度(假定在任一温度下的马尔科夫链长度不变)。

大量用快速动态流程(文献[22,68,92, 155])或并行计算方法(文献[5, 23,33,93,169])加速退火过程的研究工作已经发表,一些新近涌现出来技术也被用于与模拟退火相比较和结合,例如进化算法和tabu搜索等(文献[29,101,106,172,174])。

4.2.2  一个例子: TSP

用模拟退火解决组合优化问题需要有:

・ 简明的问题表示: 在解答空间上所有可能解有良好定义的代价函数。

・ 从一个解答到另一个解答的扰动和转移机制。

・ 冷却流程。

下面以旅行商问题为例给出模拟退火求解过程的框架。这一TSP 已在第3章定义过,在此只简述如下: 旅行商要访问N 个城市并回到起始城市,令D= [dXY]为距离矩阵,且dXY为城市X 和城市Y之间的距离,其中X,Y= 1,2,…,N。将此TSP 映射到用模拟退火解决的框架中去要经过以下步骤:

(1) TSP 的解答空间定义为

S = {N 城市的所有循环排列,Ξ= (ξ(1),…,ξ(N))} (4.23)其中ξ(k)表示从城市k出发访问的下一个城市。旅程的总代价定义为

N

f(Ξ) = ∑dX,ξ(X) (4.24)

X=1

(2) 有很多类型生成机制可用于TSP。这里采用二交换机制[102]作为示例。任选两个城市X 和Y,二交换机制通过反转X 和Y之间访问城市的顺序而获取新的旅程(见图4.2)。给定一个旅程

(ξ(1),…,ξ- 1(X),X,ξ(X),…,ξ- 1(Y),Y,ξ(Y),…,ξ(N)) (4.25)施加交换机制于城市X 和Y,可得新的旅程

(ξ(1),…,ξ- 1(X),X,ξ- 1(Y),…,ξ(X),Y,ξ(Y),…,ξ(N)) (4.26)注意(4.25)式中从城市 ( )到城市 - 1( )的一段路径被反转为(4.26)式中从城市

ξX ξ Y

#第33页-

图4.2  交换机制示例

- 1(Y)到城市ξ(X)的路径,但这段路径的距离并没有变化。所以,旅程代价的变化为

Δf = dX,ξ-1(Y) + dξ(X),Y- dX,ξ(X) - d- 1(Y),Y (4.27)这一转换机制符合麦绰泼里斯准则,因此

1  如果Δf ≤0

接受新旅程的概率= - Δf (4.28)

e T 否则

图4.3  应用模拟退火求解TSP的总结

#第34页-

(3) 可以采用诸如4.2.1节介绍的各种冷却流程。图4.3所示流程图总结了用模拟退火求解TSP 的步骤。图中

・ i和j 标记旅程,k标记温度(算法参数), 而l 则为在每个温度下已生成旅程的个数。

・Tk 和Lk 分别为第k个马尔科夫链的温度和允许长度。

・ i是当前旅程,而Ξj 是新生成的旅程。

・f (Ξi)是旅程Ξi的代价。

・ Δf= f(Ξ)- f (Ξi)

・rand[0,1]是来自一个在0和1之间均匀分布的随机数发生器的值。