（计算机软件与理论专业论文）基于遗传算法的分布式系统任务调度问题研究.pdf

a b s t r a c t a b s t r a c t 1 、h ed i s t r i b u t e ds y s t e mr e c e n t l yg o tm u c ha t t e n t i o n sa so n eo ft h eh o tt o p i c si nt h e r e s e a r c ho fc o m p u t e rs c i e n c e t h et a s ks c h e d u l i n ga l g o r i t h mp l a y sa v e r yi m p o r t a n tr o l e i ne n h a n c i n gt h i ss y s t e m sp a r a l l e lp e r f o r m a n c ea n dm a i n t a i n i n gi t sl o a de q u a t i o n t h e s c h e d u l i n gp r o b l e mh a st u r n e do u tt ob ean p cp r o b l e ma n do p t i m a ls o l u t i o n se a r l _ n o tb e f o u n di np o l y n o m i a lt i m e s o ，m a n yp e o p l em a k eg r e a te f f o r t so nf i n d i n gab e t t e ra l g o r i t h m w h i c hc a np r o d u c eab e t t e rs o l u t i o nw i t h i nl i m i t e dc o s t s o m ea l g o r i t h m sw h i c hh a v eb e e n t h o u g h to u tc a nf i n ds a t i s f a c t o r ys o l u t i o n s ，b u ti n c u rh i g ht i m ec o m p l e x i t y w h i c ht e n dt o e x a c e r b a t ei nm o r ec o m p l e xe n v i r o n m e n t s t h eg e n e t i ca l g o r i t h m ( g a ) i san e wp a r a l l e lo p t i m i z ea l g o r i t h m ，w h i c hc a nb eu s e d t os o l v em a n yk i n d so fn p h a r dp r o b l e m s s o m er e s e a r c h e r sh a v eu s e dg ao ns c h e d u l i n g p r o b l e m ，a n dt h i sa l g o r i t h mi st u r n e do u tt ob eb e t t e rt h a nh e u r i s t i ca l g o r i t h m s b u ta l lo ft h e s ea l g o r i t h m sh a v es o m ef a u l t s i no r d e rt oo v e r c o m et h e s ef a u l t s ，w e d e s i g n e dan e wg a t h i sg ai sd i f f e r e n tf r o ms t a t i s t i cg ai nc o d i n g 、s e l e c t 、c r o s s o v e r 、 m u t a t i o n ad e c i m a ls e p a r a t e dc o d i n gi su s e ds oc r o s s o v e ra n dm u t a t i o ni ss e p a r a t e da l s o o u rs e l e c tm e t h o di ss e l e c t i n gt w of r o mf o u ri n s t e a do fe l i t es e l e c t i nt h i sp a p e r , f i r s t ，w eu s em a r k o vm o d e l i n gt oa n a l y s i so u rg a ，t h a na p p l yt h i s a l g o r i t l m ai n t a s ks c h e d u l i n gp r o b l e m t h es i m u l a t e dr e s u l t ss h o wt h a to u ra l g o r i t h m o u t p e r f o r m st h ea l g o r i t h mu s i n gt w od i m e n s i o n sc o d i n ga n dc anp r o d u c em u c hb e t t e r r e s u l t s b e s i d e st h i s ，o u r a l g o r i t h m h a sf a s t e r c o n v e r g e n c es p e e dt h a n e l i t es e l e c t m e t h o d t h ec o n c l u s i o ni st h a to u ra l g o r i t h mi sm u c hb e t t e rt h a no t h e ra l g o r i t h m sa n dc a l l b eu s e dt os o l v el a r g es c h e d u l i n gp r o b l e m s k e yw o r d s ：g e n e t i ca l g o r i t h m ，d i s t r i b u t e ds y s t e m ，t a s ks c h e d u l i n g ，m a r k o vc h a i n s ， g e n e r a lg e n e t i ca l g o r i t h m i i 第一章绪论 第一章绪论 1 1 弓i 言 现代计算机时代从1 9 4 5 年开始到现在，经历了半个多世纪。从1 9 4 5 年到1 9 8 5 年，计算机一直是庞大昂贵的设备。然而。从8 0 年代开始，两项技术进步改变了这 种局面：一是功能日益强大的微型计算机的发展；二是高速局域网的出现。这两项 进步的直接结果是：通过高速网络。将许多c p u 连接起来构成一个计算系统的做法 变得可行，并且非常容易，这种系统通常称为分布式系统。分布式系统已成为计算 机界中的研究热赢，j m g i l d e r 早在1 9 7 6 年就预言，f 一代计算机体系结构的关键 与核心必然悬_ l ； 分布式结构为主的【i l 。 一 分布残系统的求解过程大体分为四个步骤： 镊务分解：指把一个大任务划分为可并行执行的相关的予任务的过程。 任务调度：指将这些予任务分配到各个并行处理机上，并安排处理机一_ i 二予任 务的执行次序的过程。 并行运算：指这些子任务在被分配的处理机上进行并行运算。 解的合成：指将子镬务钓运行结果合成为整个大任务的运行结果。 其中任务调度这一步骤对发挥系统的并行计算能力、提高系统吞吐量具有非常 重要的影响。良好的调度算法可以充分运用系统中每个处理机的计算能力，避免有 的处理机没有可执行的任务，而有的处理机待执行的任务排起了长队，致使总任务 的执行时问较长。 1 一求解组合最优化问题的方法 分布式系统的经务调度超鼹属于组合最优化问题。 归纳而言，最优化问题可分为函数优化问题和组合优化问题两大类，其中函数 优化的对象是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态。 最优化问题由目标函数和约束条件两部分构成。 将满足所有约束条件的解空问s 称为可行域，可行域中的解称为可行解；将i j j 。 行域中使目标函数最小的解称为最优解。对于最火化问题，可将目标函数乘以( 1 ) ， 转化为最小化问题求解。 当s 为离散集合构成的解空问时，最优化问题称为组合最优化。它的研究列象 可以看作是在有限集合上定义的函数在各利条件下的极值问题。从理沦上米醴，这 类问题若有解，总是r i 】以用枚举的方法找到，这意味着以枚举为拱础发展起来的分 枝定界法具有普遍适 日性。但实际卜，刘j + 大舰摸的问题，分枝定界法通常足q ：能 第一章绪论 第一章绪论 1 1 弓i 言 现代计算机时代从1 9 4 5 年开始到现在，经历了半个多世纪。从1 9 4 5 年到1 9 8 5 年，计算机一直是庞大昂贵的设备。然而。从8 0 年代开始，两项技术进步改变了这 种局面：一是功能日益强大的微型计算机的发展；二是高速局域网的出现。这两项 进步的直接结果是：通过高速网络。将许多c p u 连接起来构成一个计算系统的做法 变得可行，并且非常容易，这种系统通常称为分布式系统。分布式系统已成为计算 机界中的研究热赢，j m g i l d e r 早在1 9 7 6 年就预言，f 一代计算机体系结构的关键 与核心必然悬_ l ； 分布式结构为主的【i l 。 一 分布残系统的求解过程大体分为四个步骤： 镊务分解：指把一个大任务划分为可并行执行的相关的予任务的过程。 任务调度：指将这些予任务分配到各个并行处理机上，并安排处理机一_ i 二予任 务的执行次序的过程。 并行运算：指这些子任务在被分配的处理机上进行并行运算。 解的合成：指将子镬务钓运行结果合成为整个大任务的运行结果。 其中任务调度这一步骤对发挥系统的并行计算能力、提高系统吞吐量具有非常 重要的影响。良好的调度算法可以充分运用系统中每个处理机的计算能力，避免有 的处理机没有可执行的任务，而有的处理机待执行的任务排起了长队，致使总任务 的执行时问较长。 1 一求解组合最优化问题的方法 分布式系统的经务调度超鼹属于组合最优化问题。 归纳而言，最优化问题可分为函数优化问题和组合优化问题两大类，其中函数 优化的对象是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态。 最优化问题由目标函数和约束条件两部分构成。 将满足所有约束条件的解空问s 称为可行域，可行域中的解称为可行解；将i j j 。 行域中使目标函数最小的解称为最优解。对于最火化问题，可将目标函数乘以( 1 ) ， 转化为最小化问题求解。 当s 为离散集合构成的解空问时，最优化问题称为组合最优化。它的研究列象 可以看作是在有限集合上定义的函数在各利条件下的极值问题。从理沦上米醴，这 类问题若有解，总是r i 】以用枚举的方法找到，这意味着以枚举为拱础发展起来的分 枝定界法具有普遍适 日性。但实际卜，刘j + 大舰摸的问题，分枝定界法通常足q ：能 第一章绪论 实际使用的，该方法的计算时间一般为输入数据量的指数函数，计算时间会迅速增 加到现代计算工具难以承受的地步。 根据计算复杂性的理论，一个好的算法，其计算时间作为输入数据量的函数应 该有一个多项式作为上界，这样的算法被称为多项式时间算法。在组合优化中，至 今还没有似乎也不可能发现普遍适用的多项式时间算法。一个多项式时问算法问题 被称为多项式时间可解问题，或者p 问题。组合优化中多数问题属于一类不知道是 否为p 问题的问题，其中包括所谓的n p c 问题。在这类问题里，只要有一个被证明 是p 问题，那么它们全部是p 问题。至今已经被证明是属于n p c 问题的数目有几千 个之多，其中分布式系统的任务调度问题已被证明是n p c 问题1 2 j 。一般认为，n p c 问题不会是p 问题，因此，对n p c 问题，既然没有准确的多项式时问算法，比较现 实的妥协方法是采用多项式时间近似算法。 近似方法分为启发式方法( h e u r i s t i cm e t h o d ) 和随机搜索方法两种。启发式方法就 是运用启发信息，应用某些经验或规则来使搜索沿着某个被认为最有希望的前沿区 段扩展。启发式方法较多地依赖于对问题构造的性质的认识和经验，适用于解决不 太复杂的问题。 随机方法不依赖于问题的性质，从解空间中随机地选择多个解，检查这些解的 可行性，在可行解集中选择最好的解。这种方法简单明了，但因为需要检查相当多 的可行解集，计算非常耗时，尤其对于大范围的搜索，很有可能遗漏最优解。 遗传算法的经典应用领域就是最优化问题。对于组合最优化问题，与常规方法 比较，可以认为遗传算法处于随机方法与启发式方法之间。它在引入随机搜索的同 时，在解的构成法和进化过程中考虑了问题的原有构造。 遗传算法是一种概率搜索算法，非常适于解决大规模的优化问题，目前已成功 应用在机器学习、过程控制、经济预测、图像处理等领域p j 。 与传统的启发式算法相比，遗传算法最大的好处是具有并行搜索、群体寻优的 能力。传统的启发式搜索算法都是单点搜索算法，即通过一些变动规则，问题的解 从搜索空间中的当前解( 点) 移到另一解( 点) 。这种点对点的搜索方法，对于多峰分布 的搜索空间常常会陷于局部的某个单峰的优解。相反，遗传算法采用同时处理群体 中多个个体的方法，即同时对搜索空问中的多个解进行评估。更形象地说，遗传算 法是并行地爬多个峰。这一特点使遗传算法具有较好的全局搜索性能，减少了陷入 局部优解的风险。同时，这使遗传算法本身也十分易于并行化。 此外，遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体； 它仅用适应值来评估个体，基本上不用搜索空间的知识或其它辅助信息。这一特点 使得遗传算法具有广泛的应用领域，具有启发式算法无法比拟的通用性。 与传统的随机搜索算法相比，遗传算法的主要特点在于：具有自组织、自适 第一章绪论 应和自学习性( 智能性) ；应用遗传算法求解问题时，在编码方案、 传算子确定后，算法将利用进化过程中获得的信息自行组织搜索； 规则，而不是确定的转换规则。 上述这些特点使遗传算法使用简单、鲁棒性强，易于并行化， 分广泛。 适应值函数及遗 强调概率转换 从而应用范围十 1 3 求解任务调度问题的常用算法 在对任务调度问题进行分析研究时，通常用有向无回路图( d a g d i r e c t e d a c y c l i cg r a p h ) 描述任务之间的约束关系。图中结点代表子任务，边代表予任务n u 的 依赖关系。由于分布式系统的任务调度问题是n p c 问题1 2 1 ，已知可在多项式列+ 问内 求得最优解的情况只有以下三种【4 l ：d a g 是一个树，并行处理机同构且全连接， 忽略通信代价：d a g 是任意形状的图，并行处理机只有两个同构处理机，忽略 通信代价； d a g 图上的结点具有相同的计算代价，间隔排序( i n t e r v a l o r d e r e d ) ，处 理机数目不限，忽略通信代价1 5 j 。 由于调度问题是n p c 问题，用枚举法耗时过长，难以求得最优解，以往人们常 使用一些启发式算法在多项式时间内找到近似最优解。近似最优解指不能确保是最 优解的解。 最常用的启发式算法是l i s t 调度算法【2 】。在l i s t 调度中，首先给每个任务动态或 静态地分配一个优先级，按照优先级将任务排成一列，然后从第一个任务开始，将 每个任务逐个分配到一个能使其丌始执行时间最早的处理机。人们研究的焦点即是 如何确定任务的优先级，找到一个最优排列，使所有任务能够尽快完成【6 0 引。肩发 式算法在求得的解的质量和求解时f ( i j 两者之间存在着相互制约。也就是 兑，以降低 解的最优性为代价，来换取求解时间的缩短。在解决规模较小的凋度问题时，求解 的时问尚且可以接受，效果较好，但当问题规模较大时，石是由于时1 1 _ u 复杂度较商、 运算的时间过长而导致无法求解，就是在可接受的时间内求到的解与最优解差距太 大【1 3 i 。 遗传算法在任务调度问题上的应用最早可以追溯到1 9 9 4 年。e d w i n 首先将遗传 算法用于同构多处理机的任务调度【l ，以后又有一些学者紧随其后，进行了进一步 的深入研究 1 5 - 2 2 1 。 许多中外学者在算法中普遍采用二维编码方式，染色体形式并非基本遗传算法 使用的一维二进制编码，而是由二维类似矩阵的形式表示。这种编码形式虽然直观 明了，但有很大的局限性。 首先，采用这种编码方式进行杂交运算时，要求杂交后生成的新个体仍然满足 同一处理机上子任务深度俩洋n 0 排列顺序，以确保生成的新个体是i 稍了解。闲此， 第一章绪论 应和自学习性( 智能性) ；应用遗传算法求解问题时，在编码方案、 传算子确定后，算法将利用进化过程中获得的信息自行组织搜索； 规则，而不是确定的转换规则。 上述这些特点使遗传算法使用简单、鲁棒性强，易于并行化， 分广泛。 适应值函数及遗 强调概率转换 从而应用范围十 1 3 求解任务调度问题的常用算法 在对任务调度问题进行分析研究时，通常用有向无回路图( d a g d i r e c t e d a c y c l i cg r a p h ) 描述任务之间的约束关系。图中结点代表子任务，边代表予任务n u 的 依赖关系。由于分布式系统的任务调度问题是n p c 问题1 2 1 ，已知可在多项式列+ 问内 求得最优解的情况只有以下三种【4 l ：d a g 是一个树，并行处理机同构且全连接， 忽略通信代价：d a g 是任意形状的图，并行处理机只有两个同构处理机，忽略 通信代价； d a g 图上的结点具有相同的计算代价，间隔排序( i n t e r v a l o r d e r e d ) ，处 理机数目不限，忽略通信代价1 5 j 。 由于调度问题是n p c 问题，用枚举法耗时过长，难以求得最优解，以往人们常 使用一些启发式算法在多项式时间内找到近似最优解。近似最优解指不能确保是最 优解的解。 最常用的启发式算法是l i s t 调度算法【2 】。在l i s t 调度中，首先给每个任务动态或 静态地分配一个优先级，按照优先级将任务排成一列，然后从第一个任务开始，将 每个任务逐个分配到一个能使其丌始执行时间最早的处理机。人们研究的焦点即是 如何确定任务的优先级，找到一个最优排列，使所有任务能够尽快完成【6 0 引。肩发 式算法在求得的解的质量和求解时f ( i j 两者之间存在着相互制约。也就是 兑，以降低 解的最优性为代价，来换取求解时间的缩短。在解决规模较小的凋度问题时，求解 的时问尚且可以接受，效果较好，但当问题规模较大时，石是由于时1 1 _ u 复杂度较商、 运算的时间过长而导致无法求解，就是在可接受的时间内求到的解与最优解差距太 大【1 3 i 。 遗传算法在任务调度问题上的应用最早可以追溯到1 9 9 4 年。e d w i n 首先将遗传 算法用于同构多处理机的任务调度【l ，以后又有一些学者紧随其后，进行了进一步 的深入研究 1 5 - 2 2 1 。 许多中外学者在算法中普遍采用二维编码方式，染色体形式并非基本遗传算法 使用的一维二进制编码，而是由二维类似矩阵的形式表示。这种编码形式虽然直观 明了，但有很大的局限性。 首先，采用这种编码方式进行杂交运算时，要求杂交后生成的新个体仍然满足 同一处理机上子任务深度俩洋n 0 排列顺序，以确保生成的新个体是i 稍了解。闲此， 第一章绪论 选择d a g 中同一深度值的点作为杂交点执行单点杂交。这样做，无法使搜索子空 间波及整个解空问。因为在同一处理机上，可能存在这样的情况：如果两个子任务 之间没有相互依赖关系，深度值高的子任务排在深度值低的子任务之前也能也是可 行解。当最优解恰好属于这种情况时，这种算法无疑是无论进化多少代都不可能找 到最优解的。虽然此后有很多针对如何定义深度值，来尽可能扩大搜索空间的研究 【l6 1 8 , 2 0 - 2 舢，但这样做并不能保证搜索空间扩大到整个解空问。 其次，任务调度包括两个环节，一个环节是确定把子任务分配到哪一台处理机， 我们称为任务分配；一个环节是确定每一处理机上予任务的执行顺序，我们称为任 务排列。如果用二维矩阵形式编码，在进行杂交和变异时，一个结点位置的改变意 味着任务分配情况和排列情况同时作出了改变。分配与排列实质上是两个分离的过 程，如果同时作出改变，搜索解空间的跳跃跨度较大，很多可行解无法在一步搜索 到。 还有一些用于任务调度的遗传算法采用了一维编码方式，个体的形式就是所仃 子任务的一个队列【1 5 , 1 7 , 1 9 1 。解码的方法是：从队列的第一个任务开始，任务逐个被 分配到能使其最早丌始执行的处理机。遗传算法的目标是找寻一个最优的队列。山 于这种算法得到的结果只是一个调度序列，不指定任务分配到哪个处理机上，调度 序列对应的解需要象l i s t 算法那样，计算任务分配到哪个处理机上可以最早地获准 执行，所以复杂性较大。在遗传算法中，也就是用来描述个体与解之问映射的适应 值函数复杂性较大。由于在遗传算法的进化过程中，需要多次适应值函数的计算。 适应值函数的复杂度对遗传算法的复杂度有着最直接的影响，所以列适应值函数复 杂度的降低将大大提高算法的性能。 针对这种情况，有学者将l i s t 调度算法与遗传算法结合起来，来加快遗f 专鳍法 的收敛速度 1 9 1 ，减少计算时问。还有一些研究，对初始种群的选择作了改进，1 1 的 也是加快算法的收敛速度1 1 8 , 1 9 1 。 除了对编码形式进行的研究外，还有一些学者将对遗传算法本身进行改进后应 用于任务调度问题。如共同进化遗传算法【列l 、混合遗传算法 1 8 , 2 1 1 9 及自适应遗传算 法1 1 5 1 在任务调度问题上的应用等等。这些改进的遗传算法有些是对进化过程进j i f i ：j 改进，有些是对操作算子进行的改进，有些是列控制参数进行的改进。但编码方式 基本上是我们介绍过的二维编码或一维编码。 1 4 本文所做的工作 本课题的主要任务是深入研究遗传算法的机理，进而探索一乖 更适合分x l i j t ；系 统任务调度的遗传算法。该算法应该具有较快的收敛速度和找到全局最优解的能力。 自从1 9 7 5 年l l o l l a n d 系统地提出遗传算法的完接结构和理论以来，众多学者一 第一章绪论 选择d a g 中同一深度值的点作为杂交点执行单点杂交。这样做，无法使搜索子空 间波及整个解空问。因为在同一处理机上，可能存在这样的情况：如果两个子任务 之间没有相互依赖关系，深度值高的子任务排在深度值低的子任务之前也能也是可 行解。当最优解恰好属于这种情况时，这种算法无疑是无论进化多少代都不可能找 到最优解的。虽然此后有很多针对如何定义深度值，来尽可能扩大搜索空间的研究 【l6 1 8 , 2 0 - 2 舢，但这样做并不能保证搜索空间扩大到整个解空问。 其次，任务调度包括两个环节，一个环节是确定把子任务分配到哪一台处理机， 我们称为任务分配；一个环节是确定每一处理机上予任务的执行顺序，我们称为任 务排列。如果用二维矩阵形式编码，在进行杂交和变异时，一个结点位置的改变意 味着任务分配情况和排列情况同时作出了改变。分配与排列实质上是两个分离的过 程，如果同时作出改变，搜索解空间的跳跃跨度较大，很多可行解无法在一步搜索 到。 还有一些用于任务调度的遗传算法采用了一维编码方式，个体的形式就是所仃 子任务的一个队列【1 5 , 1 7 , 1 9 1 。解码的方法是：从队列的第一个任务开始，任务逐个被 分配到能使其最早丌始执行的处理机。遗传算法的目标是找寻一个最优的队列。山 于这种算法得到的结果只是一个调度序列，不指定任务分配到哪个处理机上，调度 序列对应的解需要象l i s t 算法那样，计算任务分配到哪个处理机上可以最早地获准 执行，所以复杂性较大。在遗传算法中，也就是用来描述个体与解之问映射的适应 值函数复杂性较大。由于在遗传算法的进化过程中，需要多次适应值函数的计算。 适应值函数的复杂度对遗传算法的复杂度有着最直接的影响，所以列适应值函数复 杂度的降低将大大提高算法的性能。 针对这种情况，有学者将l i s t 调度算法与遗传算法结合起来，来加快遗f 专鳍法 的收敛速度 1 9 1 ，减少计算时问。还有一些研究，对初始种群的选择作了改进，1 1 的 也是加快算法的收敛速度1 1 8 , 1 9 1 。 除了对编码形式进行的研究外，还有一些学者将对遗传算法本身进行改进后应 用于任务调度问题。如共同进化遗传算法【列l 、混合遗传算法 1 8 , 2 1 1 9 及自适应遗传算 法1 1 5 1 在任务调度问题上的应用等等。这些改进的遗传算法有些是对进化过程进j i f i ：j 改进，有些是对操作算子进行的改进，有些是列控制参数进行的改进。但编码方式 基本上是我们介绍过的二维编码或一维编码。 1 4 本文所做的工作 本课题的主要任务是深入研究遗传算法的机理，进而探索一乖 更适合分x l i j t ；系 统任务调度的遗传算法。该算法应该具有较快的收敛速度和找到全局最优解的能力。 自从1 9 7 5 年l l o l l a n d 系统地提出遗传算法的完接结构和理论以来，众多学者一 第一章绪论 直致力于推动遗传算法的发展。对编码方式、控制参数的确定、选择方式和交叉机 理等进行了深入的探冗，引入了动态策略和自适应策略以改善遗传算法的性能，提 出了各种改进的遗传算法。归纳起来有以下几类： 改变遗传算法的组成成份或使用技术。如选用优化控制参数、适合问题特性 的编码技术等； 采用非标准的遗传操作算子： 采用改进的进化程序； 采用动态自适应技术，在进化过程中调整算法控制参数和编码粒度； 采用并行遗传算法、与其它算法相结合的混合遗传算法； 本文提出的遗传算法，涉及上述三个方面的改进。 1 9 9 8 年，董聪在大自然探索一刊上发表了文章“广义遗传算法” 2 3 1 0 该文 以m o r g a n 的基因理论及e l d r i d g e 与g o u l d 的间断平稳理论为依据，在融合了m a y r 的边缘物种形成理论和b e r t a l a n f f y 一般系统理论的基础上，引入了一些新的概念和 算子，建立了系统的遗传算法理论和相应的算法结构，并将其定义为“广义遗传算 法”。在发现广义遗传算法确实能够加快收敛速度、确保收敛至全局最优解后，我们 首次用马尔可夫链的有关知识，对广义遗传算法的机理和性能进行了数学解析。更 进一步，将其用于任务调度问题的仿真模拟中，用实例证明了广义遗传算法比传统 遗传算法具有更快的收敛速度。 在任务调度问题的遗传算法设计中，为了克服已有两种主流编码方式各自的缺 陷，本文提出了一种新的编码方式，即“一维分离编码”方式。每个个体由左予串 和右子串两部分构成。左子串描述任务分配的情况，右子串描述任务排列的情况。 左、右子串因为任务分配和任务排列的要求不同而执行不同的杂交和变异操作。这 样做可以使搜索空间扩大的所有解空间，且对任务所在的处理机也做了指定，并且 进化程序吸收了广义遗传算法的思想。通过仿真实验证明，与采用二维编码的遗传 算法相比，本算法能得到更好的解。与不采用，“义遗传而代之以采用精英策略的传 统遗传算法相比，本算法具有更快的收敛速度。 本文内容安排如下：第一章是绪论；第二章简要介绍分布式系统及其任务调度 问题；第三章讲述遗传算法的有关知识：第四章建立了广义遗传算法的数学模型， 证明其全局收敛性；第五章讲述了我们设计的用于任务调度问题的广义遗传算法： 第六章是总结与展望。 第二章分布式系统及其任务调度问题 第二章分布式系统及其任务调度问题 2 1 分布式系统概述 分布式系统是二十世纪九十年代以来计算机领域的研究热点之一。作为网络一 体化和并行处理分布化的产物，分布式系统解决了系统透明性及处理机动态分配等 问题，表现出了强大的生命力。 一个被大家公认的分布式系统的定义是：“分布式系统是一些独立的计算机的集 合，但在用户看来却是一台计算机”1 2 4 j 在硬件结构上，尽管所有的分布式系统都是由多个c p u 构成的，但可以用不同 的方法将硬件组织起来，形成不同的系统。按照体系结构划分，当前典型的分布式 系统可分为两种：共享存储多处理机、分布存储多计算机。如果结点问通过公用存 储器中的共享变量实现相互通信，就称为多处理机( m u l t i p r o c e s s o r s ) ；如果结点 问使用消息传递方式来实现相互通信，就称为多计算机( m u l t i c o m p u t e r s ) 1 2 9 1 共享存储多处理机属于紧密耦合的分成式系统，采用共享主存通信。一个典型 的共享存储多处理机系统由m 个存储模块、p 个处理器和d 个i o 通道组成，( m ，p ，d ) 的数目按情况而定。由于处理机与主存之间互连网络带宽有限，所以当处理机数增 多时，访问主存的冲突概率会加大，互连网络会成为系统性能的瓶颈。但出于是单 一地址空间，所以较易于编程。 分布存储多计算机属于松散耦合的分布式系统，它的每个处理单元都是一个独 立性较强的节点，系由c p u 、本地存储器、i o 设备和消息传递通信接口所组成。由 于每个计算节点的本地存储器容量较大，所以运算时所需的绝大部分指令和数据均 可取自本地存储器。当不同计算节点上的进程需要通信时，就可通过接口进行消息 交换。在有的松散耦合的多计算机系统中，其计算节点本身就是一台完整的计算机， 这样就演变成了现代的机群系统。这种松散性耦合结构易于扩展，但多地址空问却 使编程较困难。 分布式系统与集中式系统相比，有其自身的优点。分布式系统有较高的性能价 格比，它还可能具有任何价位上的大型机都无法达到的性能。随着计算机的发展， 其应用领域越来越广，其中许多应用本身就是分布式的。与集中式系统相比，分伽 式系统能更好地处理分布式应用。分布式系统的另一个优点是它有更高的可靠性， 通过将任务交由多个机器共同承担，单个芯片的故障只会止一台机器停下来，丽其 他的机器将继续工作。对于一些关键性应用来说，例如控制核反应堆或飞机，使用 分布式系统来达到高可靠性是最主要的考虑因素，并且在负载增加时分布式系统较 集中系统更容易扩展。 第二章分布式系统及其任务调度问题 2 2 分布式系统中的任务调度问题 在分布式操作系统中，任务调度是其中一个非常重要的环节，它对于发挥各处 理单元的作用，从整体上提高系统资源的利用率等具有非常重要的意义。 在论及任务调度的必要性时，r i c h a r df f r e u n d 等人列举过一个假设具有多层 并发度计算需求的计算实例 2 5 1 。经计算分析表明，“该程序对于普通串行机需要运行 1 0 0 个时问单位，对于向量机需要5 0 个时间单位，而采用由5 种机器构成的分布式 系统，计算过程仅需5 个时问单位。显然，后者所付出的代价是：必须进行适当的 任务分解、分配和调度。”任务分配和调度统称为任务调度。 简单来说，任务调度就是把组成并行程序的一组相关的任务或构成工作负载的 一组相关的作业，按照一定的执行时序分配到分布式系统的多个处理单元上，并且 安排好每一计算节点上任务的执行次序，以期获得较好的系统执行性能。 对于一个任务调度实例，一组可并行执行任务可以用一个有向无网路图( d a g ) 表示。如图2 1 所示。 图2 1 六个子任务的d a g 在d a g 中，设g = ( t ，e ) 。其中丁为结点集，每个结点z 对应系统中的一个 任务；e 为边集，( z ，e ) e 表示只有在霸执行结束后，将执行结果传递给i ，l 才能开工。z 称为乃的前趋，i 称为巧的后继。用c ( 1 ，1 ) 表示7 ：与i 问的通信 代价。 调度的目标是通过合理地分配各任务到不同的处理单元上，并且安排好每处 理单元上任务的执行顺序，而使总任务的执行时间最短。在图2 1 中，如果用彬表 示z 的执行时间，调度的目标是使最后一个任务死完成的时问最短。此时，芑的所 有前趋任务已全部执行完毕。 近年来，人们对任务调度算法进行了大量研究，设计了很多算法。在设计算法 时，设计者主要考虑了以下，l 方酹的问题1 2 7 2 r 1 ： 任务调度的时机 根据任务调度的时机不i 司，般可分为静态调度、动态调度和混合调度。静态 7 第二章分布式系统及其任务调度问题 调度是指在并行程序编译时，就决定每个任务分配的处理机及其执行顺序。这经常 用予任务图比较确定的情况下。动态调度是在并行程序运行过程中，“根据当前任务 调度及系统执行情况，一临时决定每个任务的处理机及其起始执行时刻。动态调度主 要用于任务图不确定的情况，不可避免地带来一些额外开销。混合调度是介于静态 调度和动态调度之间的一种调度方法。在编译时先静态调度一部分任务，剩余部分 则采用动态调度方法在系统运行过程中给它们分配处理机。 调度目标的实现要求 从任务调度目标的实现上看，分布式系统的任务调度划分为最优调度和次优调 度两类。前者以系统的最优调度为目标，获取系统的最高并行度；后者则追求一种 次优调度，以用户要求的时限为标准，达到较高的并行度。因为任务调度问题是一 个n p c 问题，没有在多项式时闻内找到最优解的算法，所以通常采用启发式算法， 以得到问题的近似最优解。 紧迫性任务的响应问题 按照调度程序所执行的调度操作是否允许任务抢先执行，可分为抢占式凋度和 非抢占式调度。如果一个任务一旦占有一个处理机，那么它就不能被中断执行，而 是必须一直运行完毕后才释放该处理机，这种情形即为非抢占式执行方式。i 扫丁抢 占执行方式所引起的环境切换会增加系统开销，所以一般情况下不采用。 任务迁移问题 根据任务是否允许迁移执行，任务调度可分为两大类：第一类是非迁移算法。 即当一个进程创建时就已决定好它应在的位置，一旦把它放在某台处理机上，它将 一直在那台处理机上运行直至完成。无论它所在的机器负载有多重，也无论有多少 其它的处理机空闲，它都不能移动。另一类是迁移分配算法，即使一个任务已经开 始运行，它也可以移动。这种迁移策略能更好地平衡负载，但实现起来非常复杂。 目前已经证明，任务调度问题是n p c 问题，只有在三种特例下，任务调度算法 才可在多项式时间内找到最优解。所以对于一般情况，人们不得不采用启发式算法 来求得近似最优解。启发式算法是基于直观或知识、经验构造的算法，这样构造的 算法可以在可接受的计算时问内寻找较好的解，但不一定能保证解的最优性。也就 是说，以降低解的精确性为代价，来换取计算时间的缩短。这就促使人们不断地进 行科学研究，设计出比已有算法计算时间复杂度更低、找到的解更好的算法。 以往的大多数调度算法是基于1 is t 调度的算法。l i s t 涧度的基本思想是按照 结点的属性为每个结点指定优先级，按优先级高低生成一个调度序列，然后重复执 行下丽两个步骤直到序列中所有结点都被调度完毕为止：从调度列表中取出第一 个结点：将结点分配到使它的启动时间最早的处理机上。 此后在此基础上又出现了动态l i s t 调度算法阻3 2 l 。动态调度算法在每次结点被 第二章分布式系统及其任务调度问题 分配后，都要重新计算所有未被调度结点的优先级，来重新安排剩余结点的顺序。 因此，执行算法需要三个步骤：确定所有未被调度结点的优先级；选择具有最 高优先级的结点进行调度；将结点分配到使它的启动时间最早的处理机上。 决定优先级的方法有很多【4 ，2 q ，如t l l f ( i l l g h e s tl e v e lf i r s t ) 、l p ( l o n g e s t p a t h ) 、l p t ( l o n g e s tp r o c e s s i n gt i m e ) 、c p ( c r i t i c a lp a t h ) 等。 任务调度中有代表性的传统启发式算法有：洲算法【6 1 、d l s 算法1 7 i 、b s a 算法【8 】、 ， p b s a 算法 吼。其复杂度分别为：o ( v ( p 3 v + p ) ) 、o ( v 3 p ) 、o ( p 2 p v ) 、o ( p t 2 + ”乃) ， 其中，p 为处理机数目，e 为d a g 中的边数，v 为d a g 中的结点数，p 为执行 并行算法本身的处理单元数目。 因为并行任务数一般大于处理机数目，可以看出删算法复杂度较低。原因是 m h 是一般的静态调度。d l s 算法是动态调度，b s a 算法允许任务迁移，p b s a 算法是 对b s a 算法的并行优化算法。有关这些算法的详细内容请参见有关文献。 在静态调度中，并行任务的运行时间、通信关系以及处理单元的拓扑结构已知。 每个任务在执行前已静态地分配给特定的处理单元。而动态调度允许根据在任务执 行过程中进行任务迁移或重新分配。动念调度技术虽然可以取得较好的负载平衡效 果，但开销也很大。所以，如果静态调度技术有较好的负载平衡效果时，应尽量采 用静态调度技术。本文只研究静态调度，因此下面所说的调度均指静态调度。 随着遗传算法、神经网络、模拟退火等现代优化算法研究的逐渐兴起，用遗传 算法解决任务分配问题的研究也在进行，并且显示了强大的优越性。 1 9 9 4 年，e d w i n 最早将遗传算法用于同构多处理机的任务凋度问题。根据任务 调度问题的特点，采用一种二维显式排列的方法来表示d a g 图中的分配和凋度情 况，即每个处理机上所有的任务排成一个列表，排列的顺序代表了各子任务的先后 执行顺序。通过模拟实验证明，与传统的l i s t 调度算法相比，遗传算法能在可接受 的运算时间内得到更好的解。 此后，又有很多学者将遗传算法用于任务凋度问题的研究。文献 2 0 - - t 测传统 遗传算法中初始种群构造和遗传算子的局限性，结合遗传算法和演化策略的优点， 提出了一个异构系统中任务调度的进化算法。文献 3 3 1 专门研究了任务调度l | 遗传 算法的知识表示和遗传算子。文献【2 1 】提出了任务调度的共同进化计算模型，解决 了多个不相关的可分解任务在单种群进化方法下，过早收敛或停滞不前的问题。文 献 1 6 】设计了一种基于问题空问的遗传算法。文献 1 8 1 将遗传算法与l i s t 调度算法桐 结合起来设计了一套新算法。文献【1 5 】在遗传算法中动态地改变控制参数，使种群 快速向更好的解进化。 9 第三章遗传尊法 第三章遗传算法 3 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 研究的历史比较短。2 0 世纪6 0 年代末期到 7 0 年代初期，主要由美国m i c h i g a n 大学的j o h nl l o l l a n d 与其同事、学生们研究形成 了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模 拟生物进化的机制来构造人工系统的模型 3 4 , 3 5 1 。随后经过3 0 余年的发展，取得了丰 硕的应用成果和理论研究的进展，特别是近年来世界范围形成豹进化计算热潮，计 算智能已成为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗 传算法受到广泛的关注。从1 9 8 5 年在美国卡耐基梅隆大学召月：的第一届国际遗传 算法会议，到1 9 9 7 年5 月i e e e 的 t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) ) 创刊， 遗传算法的研究渐趋成熟。目前，遗传算法已被成功应用在机器学习、过程控制、 经济预测、工程优化等领域。 遮转算法的基本思想模拟了自然界的生物进化过程。通常认为达尔文的自然选 择学说揭示了生物进化的内在舰律，“适者生存，不适者被淘汰”是自然选择的中心 思想。遗传算法用适应值来刻划个体适应环境的程度，适应值越商的个体越能适应 环境，生存下来的机率越大。生存下来的个体再经过配偶选择，繁殖出下一代。同 时，在繁殖鼹过程中某些细胞的基因会发生突变。那些导致生存能力提高的突变所 产生的新的蓦因片惭，会经过很多代的进化逐步传给群体中的多数个体。这样，自 然界从群体中选出了优良的个体，并把他们的优点遗传给下一代。从总体上看，新 的一代适应自然界的能力得到了提高，群体得到了进化。现代细胞学和遗传学的研 究表明，遗传物质的主要载体是染色体，杂交和变异发生在作为生物体结构编码的 染色体上。表3 1 所示为生物遗传中的基本概念与遗传算法中的作用的对应表。 表3 1 生物遗传概念遗传算法中的作用 个体 染色体 基因 适应性 种群 杂交 变异 解 解的编码 编码中的某一分量 适应值函数的值 一组解，种群规模决定解的个数 通过杂交算子产生一组新解的过程 编码的某一分量发生变化的过程 第三章遗传尊法 第三章遗传算法 3 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 研究的历史比较短。2 0 世纪6 0 年代末期到 7 0 年代初期，主要由美国m i c h i g a n 大学的j o h nl l o l l a n d 与其同事、学生们研究形成 了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模 拟生物进化的机制来构造人工系统的模型 3 4 , 3 5 1 。随后经过3 0 余年的发展，取得了丰 硕的应用成果和理论研究的进展，特别是近年来世界范围形成豹进化计算热潮，计 算智能已成为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗 传算法受到广泛的关注。从1 9 8 5 年在美国卡耐基梅隆大学召月：的第一届国际遗传 算法会议，到1 9 9 7 年5 月i e e e 的 t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) ) 创刊， 遗传算法的研究渐趋成熟。目前，遗传算法已被成功应用在机器学习、过程控制、 经济预测、工