再上一篇:9. 3  进化程序设计
上一篇: 第 10 章  多处理器调度
主页
下一篇:10.3  遗传算法
再下一篇:10.4  习题
文章列表

10.2  均场退火

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

本节讨论利用霍普费尔德网络的均场退火求解MSP 的基本方法。运用霍普费尔德神经元网络求解最优化问题的基本方法包括两个主要步骤:

(1) 为待解问题建立一个适当的霍普费尔德能量函数。

(2) 选取并设计一个最小化能量函数的递归机制。霍普费尔德能量函数的最小化可分别运用第3章讨论过的确定性更新规则、第4章介绍过的模拟退火方法以及第5章描述过的均场退火方法。

10.2.1  MSP 霍普费尔德能量函数

任务调度问题的霍普费尔德能量可用类似于第5章中介绍的方法推导出来以反映问题的代价和约束。这里让我们首先考虑所有任务的运行时间都相同的情况,然后再推广到不同任务具有不同运行时间的情况。

如图10.3所示的MSP 可依下列约束被映射到处理器-时间段空间:

(1) 每个任务只占有一个时间段。

(2) 因为共有P 个处理器,在同一时间段中最多可有P 个任务被处理。

(3) 如果在当前时间段上运行的任务Ti前面有k个任务与其相连,这k个任务必须在前面的时间段上已被处理。

#第98页-

图10.3  将任务Ti映射到处理器-时间段(p,t)坐标上去

sia = 1  如果任务Ti在时间段a运行 (10.1)

0  否则

注意,对于MSP,神经元变量取值1或0而不是1或- 1。定义任务Ti与任务Tj 之间的连接性cij如下:

cij = 1  如果Ti在Tj 之前且与之相连,i≠j (10.2)

0  否则

前述三项约束可由下面能量函数相应表达:

E1 = ij(1- ab)siasjb= siasib (10.3)

∑i∑j∑a∑b ∑i∑a∑b≠a

E2 = 2 (10.4)

∑ ∑sia - P ∑sja

a i j

i- 1 a- 1 2

E3 = ∑∑sia∑cij 1- ∑sjb (10.5)

i a j= 1 b= 1

(10.3)式对应于约束(1)。当E1 被最小化(理论上E1= 0)时,sia= sib= 1(a≠b)的情况不存在。也就是说,每个任务的执行不超过一次。(10.4)式中的E2 用来施行约束(2)。一旦达到E2 的最小值,相应调度应为最有效率的,因为这一约束尽可能地使很多处理器被利用或使所有处理器在该单位时间闲置(未被任何处理器占用的单位时间不被计入总运行时间)。显然,(10.5)式中的E3 总为正值。如果约束(3)被满足,可得E3 的最小值。一个违反先后关系的调度的E3 值会较大。

另外,引入下列辅助函数可以加速收敛:

E4 = ∑ 1- ∑sia (10.6)

i a

E5 = ∑∑sia(1- sia) (10.7)

i a

E4 保证每个任务只在一个时间段里运行,而E5将sia强行置为0或1。

任务图的总能量ET 为

ET = αE1 + βE2 + γE3 + ξE4 + λE5 (10.8)

#第99页-

其中α,β,γ,ξ和λ是用于为E1,E2,E3,E4和E5加权的相应拉格朗日参数[105]。

在每个任务都可有不同的运行时间的情况下,任务图可分解为一个不同的任务图,其中每个新的任务可为原有任务图中任务的子任务。假定原有任务图中的每个任务都可以被分解为一些运行时间相等的子任务。在这种情况下,我们得到一个所有任务都具有同样运行时间的新的任务图,并可用上述公式求解。

10.2.2  均场近似

在si= 1或0的情况下,可以证明(见第5章)均场退火公式为

- u - 1

vi= 1+ e i

E1 - 1

= vT

1+ e i

(10.9)

= 1 1+ tanh - 1 E

2 2T vi

10.2.3  MSP 的均场公式

从(10.3)~(10.7)式及(10.9)式可得

E1 = 2vib (10.10)

via ∑

b≠a

E2 2

= 2 ∑vja- P ∑vja + ∑vja- P (10.11)

via j j j

i- 1 a- 1 2

E3 = cij 1- vjb (10.12)

via ∑ ∑

j b=1

E4

= 2 vib- 1 (10.13)

via ∑

b

E5 = 1- 2via (10.14)

via

将(10.10)~(10.14)式代入(10.9)式,迭代更新公式变为: 对所有i和a,有

1 1 E1 E2 E3 E4 E5

via = 2 1+ tanh - 2T αvia + βvia + γvia + ξvia + λvia (10.15)10.2.4  数值解法和仿真

在得到MSP 的霍普费尔德能量函数和均场退火公式后,第5章给出的均场退火算法可用于求解MSP。

一个由图10.4给出的17-任务图被用于仿真求解以给出这一算法的示例。图10.5(a),(b)和(c)分别给出了这一任务图在2,3,4个处理器情况下的结果。在仿真计算中,(10.15)式的参数α,β,γ,ξ和λ分别为7.5,3.5,1.0,1.0及1.0。上述仿真均获得最优解。

一个更复杂的40-任务图示例由图10.6给出。这一拥有40个任务的MSP 在3,5,7个处理器情况下的模拟退火调度分别为图10.7(a),(b)和(c)。这些解答的完成时间分别为15,9,8,而最优解的完成时间相应为14,9,7。

#第100页-

图10.4  一个17-任务图示例

T0 T1

T2 T3

T4 T6

T5 T9 T0 T1 T2 sET7 T8 T3 T4 T10 T0 T1 T2 ET10 T11 T5 T6 T7 T3 T4 T5 T10 sT12 T16 T8 T9 T16 T6 T15 T16 %T13 T14 T15 T7 T8 T9 jST14 T15 T11 T12 T13 T11 T12 T13 T14 j%(a) 总执行时间 (b) 总执行时间 (c) 总执行时间

图 10.5  图10.4中任务图示例的均场退火调度

图10.6  一个40-任务图示例

#第101页-

T0 T1 T2 T3

T4 T5 T6 T7

T10 T11 T13 T14

T0 T1 T8 T9 T12 T17

T3 T4 T6 T15 T16 T18 T21

T T T T19 T20 T22 T23 T24

2 5 9 T25 T26 T27 T28 T29

T10 T11 T30 T31 T32 T34 T35

T8 T12 T18 T33 T36 T37 T38 T39 %

T7 T15 T16 %

T13 T17 T23 (b) 总执行时间 %

T14 T19 T24 %

T25 T26 T27 %

T20 T21 T34 %

T22 T35

T30 T31 T32 T0 T1 T2 T3 T4 %

T T T5 T6 T7 T8 T9 T10 T11 #

29 38

T28 T33 T13 T14 T15 T16

T12 T17 T18 T19 T21 T23

T36 T37 T39 T20 T22 T24 T25 T26 T27 %

(a) 总执行时间 T28 T29 T30 T31

T32 T33 T34 T35

T36 T37 T38 T39

(c) 总执行时间

图 10.7  图10.6中任务图示例的均场退火调度

在这一节中,我们示范了用模拟退火求解MSP 的基本方法。实验结果表明均场退火

是求解MSP 的一个有效方法。运用这一方法的难度仅在于将待解问题转化为均场退火

可解的形式。