再上一篇: 第 10 章  多处理器调度
上一篇:10.2  均场退火
主页
下一篇:10.4  习题
再下一篇: 第 11 章  作 业 调 度
文章列表

10.3  遗传算法

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

正如第6章所述,运用遗传算法的三个关键元素为

(1) 符号串表示。

(2) 适度函数。

(3) 遗传操作。

用GA 求解MSP,为任务调度所设计的表达形式须使遗传操作可以有效地检验新的

调度并寻找最优调度。

#第102页-

10.3.1  符号串表示

符号串表示必须能够唯一地表示搜索空间中的所有搜索节点。对于多处理器调度问题,一个有效的搜索节点(一个调度)必须满足下列条件:

(1) 计算任务之间的先后关系。

(2) 完整性和唯一性条件(每个任务都在调度中且只出现一次)。

一种满足这两个条件的可行方法是将调度表示为一些计算任务的表。每个表对应于在一个处理器上运行的计算任务。图10.8给出了图10.1中调度的表表示。表中任务的顺序保持了在一个处理器上运行的任务的先后顺序

(处理器内先后顺序)而忽略了在不同处理器上运行

的任务的先后顺序(处理器间先后顺序)。这是因为

处理器间先后顺序关系在实际计算调度的完成时间 图10.8  一个调度的表表示之前并不起作用。

10.3.2  起始群体

在遗传算法的每一次迭代中,必须维持一个符号串的群体。起始的符号串群体(MSP的调度)通常是随机生成的。群体的大小一般取决于问题本身,并需要在实验中确定。为了方便调度的生成和遗传操作的构造,引入了如下高度排序条件:在调度中每个处理器上的任务都按高度升序排列于表中。例如,在图10.8的处理器P1 中,height(T2)≤height(T5)≤height(T4)≤height(T7)。可以证明一个满足高度排序条件的调度是一个有效调度,亦即先后关系不会被破坏[87]。

以图10.1中的任务图为例。任务T3(高度为1)是T8(高度为3)的一个前辈。如果它们两个都被分配给同一个处理器,则T3 依照高度排序在T8 的前面,从而保证了T3 在T8之前在该处理器上得到执行。不过,如果在两个任务之间不存在先后关系,则不必采用高度排序。例如,任务T6(高度为2)与T5(高度为1)无关,所以它们可在同一处理器中以任意顺序执行。

高度排序条件只是一个必要条件,最优调度有可能并不满足这一条件。高度的定义可被修正以减小这种情况出现的可能性。任务Tj 的新高度被定义为一个在1+ maxheight(Ti)与- 1+ maxheight(Tk)之间的随机整数,其中Ti∈PRED(Tj),Tk∈SUCC(Tj)。在这一章的余下部分,height 遵从新的定义。

对于一个具有p 个处理器的多处理器系统,下面是一个可以生成满足高度排序条件的随机调度的算法。

调度生成算法  为一个具有p 个处理器的多处理器系统生成满足高度排序条件的随机调度的算法。

(1) 计算TG中每个任务的高度height。

(2) 通过将TG中的任务划分为不同的子集G(h),即高度为h的任务集,把任务按高度分开。

(3) 对前p- 1个处理器中的每一个处理器,进行以下操作:

#第103页-

① 对每一个子集G(h),置NG(h)为G(h)中的任务个数。

② 随机生成一个在0和NG(h)之间的数字r。

③ 从G(h)中选取并移出r 个任务,分配给当前处理器。

(4) 将所有子集中剩下的任务分配给最后一个处理器。

搜索节点的起始群体可由重复执行以上调度生成算法而得到。

10.3.3  适度函数

适度函数被用来评价搜索节点并控制遗传操作。对于MSP,适度函数需要考虑吞吐量、完成时间以及处理器的使用等因素。在这里所介绍的遗传算法中,适度函数仅基于调度的完成时间。一个调度S 的完成时间定义为任务图中所有任务执行完成所用的时间,并以FT(S)表示。

因为我们所要求的是将完成时间最小化,而遗传操作之一(繁殖)总是试图将适度函数最大化,调度的适度值可被定义为Cmax- FT(S),其中Cmax是在上一次迭代中获得的最大完成时间。因此,最优调度会有最小的完成时间和比其它调度大的适度值。

10.3.4  遗传操作

遗传操作的功能之一是在当前搜索节点群体基础上生成新的搜索节点。新的节点通过合并或重组旧的节点而构造出来的。就像在遗传学中一样,适当选择一个搜索节点的符号串表示,其特定结构可以表示该搜索节点的“优度”。因此,合并两个搜索节点的好的结构可能得到一个更好的搜索节点。将这一概念应用于MSP,一个调度的特定部分可能属于最优调度。组合这些“最优”部分,我们也许会有效地发现最优调度。

对于MSP,遗传操作必须确保调度中处理器内先后关系和任务的完整性和唯一性,正如10.3.1节讨论过的那样。这将保证新生成的符号串是表示有效搜索节点。下面我们介绍一个基于交叉概念的MSP 遗传操作[64]。

1. 交叉

考虑图10.1所示任务图TG。图10.9所示的两个符号串都是这一任务图对于两处理器的有效调度。新的符号串可由如下交换两个符号串的部分结构而得。

(1) 选择将表切断为两段的截点(交叉截点),见图10.9。

(2) 交换P1的符号串A和符号串B的尾部。

(3) 交换P2的符号串A和符号串B的尾部。

新生成的符号串如图10.10所示。注意,新的符号串之一D的完成时间短于原有的两个符号串。事实上,这是任务图TG在两处理器情况下的最优完成时间。上述操作可以很容易地扩展到p 处理器的情况下并且十分有效。不过,我们还需要确定选取交叉截点的方法,并证明其生成的新符号串是有效的。

毫无疑问,被生成截点的有效性极大地取决于交叉截点的选择。注意在上面例子中交叉截点总是介于两个不同高度的任务之间(height(T5)≠height(T8),height(T4)≠height(T6),等等)。这实际上是基于下面定理[87]。

#第104页-

图10.9  交叉操作的两个符号串

图10.10  交叉操作生成的两个新符号串

定理1  如果交叉截点的选取使得

(1) 每个交叉截点两侧的任务的高度都是不同的。

(2) 所有交叉截点前面最近任务的高度都是一样的。

则新生成的符号串一定有效。

交叉操作利用以上特性选择交叉截点以使新的符号串总为有效调度。这一过程被归纳为如下算法。

交叉算法  这一算法在两个符号串A和B上施用交叉操作并生成两个新符号串。

(1) 在0与任务图的最大高度之间随机生成数值c。

(2) 选取交叉截点。

① 对符号串A和符号串B中的每个处理器Pi,找出其中高度为c的最后一个任务Tj,且令Tk为紧跟其后的任务,亦即c= height(Tj)< height(Tk),且对所有i,height(Tji)均相同。

② 对符号串A和符号串B中的每个处理器Pi,从交叉截点处交换处理器Pi中符号串A和符号串B的底半部。

虽然交叉操作十分有效,它在本质上是随机的并可能抹去最优解答。在一般情况下,它的使用要由交叉概率来控制,而交叉概率的值又通常是由实验中得到的。再进一步,我们总可以在下一代中保留已经发现的最优解答。

2. 繁殖

繁殖操作通过从旧的群体中选取适度值最大的符号串来构成新的群体。选取准则为:

#第105页-

具有较高适度值的符号串应有较高的机会在下一代中存活。这是因为“好的”符号串具有较高的适度值并应被保留到下一代。一般来说,一个偏置轮盘可用来实现繁殖。在这个轮盘上,群体中的每个符号串都占有面积与其适度值大小成正比的一席之地。随机生成的数值被用作轮盘上的指针以决定哪一个符号串会存活到下一代。因为适度值大的符号串占有面积较大,它们会有更大可能被选中并延续到下一代(见6.2.1节)。

对基本的繁殖操作稍加改动,即可将当前群体中最好的符号串繁衍到下一代中去。这一改动可以提高遗传算法的性能。下面算法归纳了繁殖操作。

繁殖算法  这一算法在符号串群体POP 上施用繁殖操作并生成一个新的符号串群体NEWPOP。令NPOP 为POP 中的符号串个数。

( 1) 构造一个轮盘。令 NSUM 为 POP 中符号串适度值的总和; 将轮盘划分为NSUM 个格,然后根据适度值的大小将相应数目的格分配给符号串。

(2) 重复下面步骤NPOP-1次:生成一个在1和NSUM 之间的随机数,并将它指到的格所对应的染色体加入NEWPOP。

(3) 将POP 中具有最大适度值的符号串加入NEWPOP。

3. 突变

突变可视为以小概率发生的符号串值的随机转移。它也可被看作逃脱不成熟收敛的方式。对于MSP,突变由随机交换两个高度相同的任务来实现。突变操作可归纳为如下算法。

突变算法  这一算法在一个符号串上施用突变操作以生成一个新的符号串。

(1) 随机选取一个任务Ti。

(2) 比较高度。找出符号串中与之高度相同的任务Tj。

(3) 交换任务。通过在调度中交换任务Ti与Tj 来生成一个新的符号串。

一般来讲,施用突变操作的频率由突变概率控制,而突变概率的值通常又是由实验得到。

10.3.5  完整的算法

现在让我们来把上述单个算法集中到一起,构成MSP 的完整遗传算法。

调度搜索算法  这一算法用于求解MSP。

(1) 调用调度生成算法N 次并将生成的符号串存入POP。

(2) 重复下面步骤直至算法收敛:

① 计算POP 中每个符号串的适度值。

② 调用繁殖算法。令BESTSTRING为POP 中适度值最大的符号串。

③ 从i= 1到NPOP/2,进行

・ 从POP 中取出两个符号串并以概率pc调用交叉操作。

・ 如果执行交叉操作,则将新生成的符号串加入 TMP; 否则,将原符号串加入TMP。

#第106页-

④ 对TMP 中的每个符号串,以概率pm 调用突变算法。如果执行突变操作,则将新

生成的符号串加入POP;否则,将原符号串加入POP。

⑤ 用BESTSTRING取代POP 中适度值最小的符号串。

算法在满足收敛准则时终止,亦即经过连续数代群体中的最好解答不再变化。

10.3.6  仿真结果

我们对上节中讨论的遗传算法用随机选择的任务图实现并测试。这些任务图的最优

调度都是已知的。随机生成的调度具有20~90个任务。每个任务的子节点个数是在1和

4之间的随机整数,且每个任务的运行时间为1和50之间的随机整数。这些任务图同时

也用列表调度算法进行了测试[91]。随机生成的任务图不是显式构造的,但在它们的构造

过程中,可获取最优调度。仿真采用了下列参数:

・ 群体大小= 10

・ 交叉概率= 1.0

・ 突变概率= 0.05

・ 最大迭代次数= 1500

表10.1~10.4比较了在不同处理器个数情况下遗传算法和列表算法得到的完成时

间以及随机任务图的最优调度。仿真是在一台SUN4/490工作站上完成的,且程序运行

时间通常只有一两秒钟。在所有情况下,遗传算法在小于1000代之内收敛于一个解答。从

表10.1~10.4可见,利用遗传算法得到的解答总是优于列表算法,且与最优解的误差不

超过10%。

表10.1  两处理器情况下最优调度、遗传算法和列表算法用于各种任务图的比较

任务个数 最优调度(OPT) 遗传算法(GA) 列表算法(LA) GA- OPT% LA- OPT%

OPT OPT

30 392 395 416 0.77 6.12 `

35 410 436 457 6.34 11.46 `

41 490 508 522 3.67 6.53 `

51 653 662 674 1.38 3.22 `

61 768 783 822 1.95 7.03 `

表10.2  三处理器情况下最优调度、遗传算法和列表算法用于各种任务图的比较

任务个数 最优调度( ) 遗传算法( ) 列表算法( ) GA- OPT% LA- OPT%

OPT GA LA OPT OPT

31 260 266 280 2.31 7.69 `

36 295 305 366 3.39 24.07 `

42 352 378 393 7.39 11.65 `

53 434 451 454 3.92 4.61 `

68 561 584 608 4.1 8.38 `

#第107页-

表10.3  四处理器情况下最优调度、遗传算法和列表算法用于各种任务图的比较

任务个数 最优调度( ) 遗传算法( ) 列表算法( ) GA- OPT% LA- OPT%

OPT GA LA OPT OPT

28 190 198 237 4.21 24.74 `

41 267 285 291 6.74 8.99 `

57 372 385 400 3.49 34.14 `

64 394 434 484 10.15 22.84 `

75 458 467 511 1.97 11.57 `

表10.4  五处理器情况下最优调度、遗传算法和列表算法用于各种任务图的比较

任务个数 最优调度( ) 遗传算法( ) 列表算法( ) GA- OPT% LA- OPT%

OPT GA LA OPT OPT

29 147 153 186 4.08 26.53 `

42 220 232 268 5.45 21.82 `

56 280 305 329 8.93 17.50 `

67 346 357 363 3.18 4.91 `

77 383 407 421 6.27 9.92 `