（计算机应用技术专业论文）网格环境下任务调度机制的研究与仿真.pdf

摘要 网格技术将所有可用于共享的资源( 例如，计算机、高性能设备、昂贵仪器、 存储设备、科学数据、软件、数据库等) 通过网络连接起来，并将它们转化成一 种随处可得的、可靠的、标准的、经济的计算能力。用户将任务提交给网格后， 需要对任务进行合理的分配和调度，即将任务分配给网格资源去执行。 由于网格中任务调度直接影响到整个系统的计算性能，因此调度成为网格计 算中的一项关键技术。任务调度问题是一类n - p c 问题，经典调度理论一般仅能 获得问题的近似最优解。 本文采用理论分析与仿真实验相结合的方法，研究网格计算中具有依赖关系 的多任务分配与调度的遗传算法。遗传算法是一种有导向性的随机搜索算法，它 以适应度函数为导向，模拟自然界生物进化和遗传过程，搜索全局最优解。 本文针对网格系统中任务调度问题提出一个适用的遗传算法框架。算法中染 色体的编码采用二维0 - 1 矩阵，即文中的“资源任务”匹配矩阵。在此基础上 采用三类遗传算子，即外部交叉算子、内部交叉算子和可变的变异算予。外部交 叉算子和内部交叉算子具有生成最优解的能力；变异算予有效的保存了种群的多 样性。为了保证遗传算法的全局搜索能力，采用任务最大深度值与最小深度值来 共同确定任务的深度值；为了防止早熟，算法自适应的加大变异概率。 遗传算法中主要控制参数的取值通过仿真实验确定，而任务d a g 图、任务 数、任务工作量、资源数、资源计算能力、资源间通信延迟均可在仿真系统初始 化时手动或随机生成。经仿真试验的结果数据比较，本文算法具有较好的解全局 搜索能力，以及较快的收敛速度，能够在较少的进化代数之内收敛于近似最优解。 关键字：网格计算，任务调度，遗传算法，仿真 a b s t r a c t g r i dt e c h n o l o g yl i n k sa l lk i n d so fr e s o u r c e ss h a r e di nt h ei n t e r a c t ，s u c ha sh i 【g h p e r f o r m a n c ee q u i p m e n t ，e x p e n s i v ei n s t r u m e n t ，s t o r a g ee q u i p m e n t ，s o f t w a r e a n d d a t a b a s e ，e t c ，a n dc o n v e r t st h e mt oa l la v a i l a b l e ，r e l i a b l e ，s t a n d a r da n de c o n o m i c a l c o m p u t i n gp o w e r i no r d e rt op r o c e s st a s k so np r o p e rr e s o u r c e ，面ds c h e d u l es y s t e m n e e dm a t c ha n ds c h c d u l et h es u b m i r e dt a s k st or e s o u r c e s t a s km a t c h i n ga n ds c h e d u l i n gp l a y sa ni m p o r t a n tr o l ei nn e t w o r kc o m p u t i n ga n d m a k e san o t a b l ei m p a c to nt h eo v e r a l lp e r f o r m a n c e s c h e d u l i n gp r o b l e m sa r ek n o w n t ob ei ng e n e r a ln p c o m p l e t e o n l ys u b - o p t i m a lc a nb eo b t a i n e db yc l a s s i c a l s c h e d u l i n ga p p r o a c h e si nm o s tc a s e s t h i sp a p e rs t u d i e dt a s ks c h e d u l i n ga l g o r i t h m su s i n gi m p r o v e dg e n e t i ca l g o r i t h m s f o rn e t w o r kc o m p u t i n gb ym e a n so ft h e o r e t i c a la n a l y s i sa n ds i m u l a t i o ne x p e r i m e n t s g e n e t i ca l g o r i t h mi sa “n do f r a n d o ms e a r c h i n gm e t h o dd i r e c t e db yf i t n e s sf u n c t i o n i ts i m u l a t e st h eb i o l o g ye v o l u t i o ni nn a t u r ei no r d e rt of i n dt h eb e s tv a l u e w ef i r s tp r o p o s e dag e n e r a lg e n e t i ca l g o r i t h mf o rt a s km a t c h i n ga n ds c h e d u l i n g i ng r i de n v i r o n m e n t ac h r o m o s o m ei ss p e c i f i e db yar e s o u r c e t a s km a t c h i n gm a t r i x t h r e eg e n e t i co p e r a t o r s ，s u c ha se x t e m a lc r o s s o v e r , i n t e r n a lc r o s s o v e ra n dm i g r a t i o n a sak i n do fm u t a t i o n ，w e r ed e s i g n e db a s e do np e r m u t a t i o nr e p r e s e n t a t i o n t h e a l g o r i t h mc a r la v o i dt h ep r e m a t u r ep h e n o m e n aa n db r e a ko u to ft h et r a po ft h ep a r t b e s tv a l u eu s i n gt h r e eo p e r a t o r sa n dt h eh e i 曲to f t a s k al a r g em o u n to fe x p e r i m e n t sh a db e e np e r f o r m e dt oo b t a i nar a n g eo fm a i n c o n t r o lp a r a m e t e r ss e t t i n g sf o rp r o p o s e da l g o r i t h m t h ed a go ft a s k s ，t h en u m b e ro f t a s k s ，t h em io ft h et a s k s ，r e s o u r c e s ，e x e c u t ee f f i c i e n c y ( m i p s ) ，d e l a yc a na l lb es e t a u t o m a t i c a l l y t h ee m u l a t i o n a le x p e r i m e n tr e s u l t ss h o wt h a tt h eg e n e t i ca l g o r i t h m p r o p o s e di n t h i sp a p e rh a sf a s t e rc o n v e r g e n c es p e e da n dg r e a t e rp r o b a b i l i t yt o f i n d o p t i m a lv a l u e k e yw o r d s ：g r i dc o m p u t i n g ，t a s ks c h e d u l e ，g e n e t i ca l g o r i t h m ，s i m u l a t i o n i i 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名：弓钦靖 指导教师签名： 渤e 年ia | f 日入p 年 o ：设置最大进化代数t ；随机生成m 个个 体作为初始群体p ( o ) 。 ( 3 ) 适应度值评价检测：适应度函数表明个体或解的优劣性。对于不同的 问题，适应度函数的定义方式不同。根据具体问题，计算群体p ( t ) 中各个个体 的适应度。 ( 4 ) 选择：将选择算子作用于群体。 ( 5 ) 交叉：将交叉算子作用于群体。 ( 6 ) 变异：将变异算子作用于群体。 群体p ( t ) 经过选择、交叉、变异运算后得到下一代群体p ( t + 1 ) 。 ( 7 ) 终止条件判断：若t t ，则t 卜t + 1 ，转到步骤( 2 ) ：若f t ，则以 进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。 算法步骤如图4 2 所示【2 6 j ： 交叉 i 适值计算 图4 2 遗传算法的一般步骤 遗传算法流程图4 3 【2 6 】如下图4 3 2 8 图4 3 遗传算法运算流程 简单遗传算法的伪代码描述如下： p r o c e d u r eg a b e g i n t = o ： i n i t i a l i z ep ( t ) ； e v a l u a t ep ( t ) ； w h i l en o tf i n i s h e dd o b e g i n t = t + 1 ： s e l e c tp ( t ) f r o mp ( t 一1 ) ； r e p r o d u c ep a k si np ( t ) ； e v a l u a t ep ( t ) ； 2 9 e n d 4 - 2 3 优点与不足 遗传算法具有如下优点2 6 l ： ( 1 ) 对可行解表示的广泛性。遗传算法的处理对象不是参数本身，而是针 对那些通过参数集进行编码得到的基因个体。此编码操作使得遗传算法可以直接 对结构对象进行操作。所谓结构对象，泛指集合、序列、矩阵、树、图、链和表 等各种一维或二维甚至多维结构形式的对象。这一特点使得遗传算法具有广泛的 应用领域。 ( 2 ) 群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜 索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。相反， 遗传算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间中的多个 解进行评估。这一特点使遗传算法具有较好的全局搜索性能，也使得遗传算法本 身易于并行化。 ( 3 ) 不需要辅助信息。遗传算法仅用适应度函数的数值来评估基因个体， 并在此基础上进行遗传操作。更重要的是，遗传算法的适应度函数不仅不受连续 可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，编码必 须与可行解空间对应。由于限制条件的缩小，使得遗传算法的应用范围大大扩展。 ( 4 ) 内在启发式随机搜索特性。遗传算法不是采用确定性规则，而是采用 概率的变迁规则来指导它的搜索方向。概率仅仅是作为一种工具来引导其搜索过 程朝着搜索空间的更优化的解区域移动的。虽然看起来它是一种盲目搜索方法， 实际上它有明确的搜索方向，具有内在的并行搜索机制。 ( 5 ) 遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度 函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优 解。 ( 6 ) 遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决 求解非常困难的问题。 ( 7 ) 遗传算法具有固定的并行性和并行计算的能力。 ( 8 ) 遗传算法具有可扩展性，易于同别的技术混合。 遗传算法的不足【2 6 1 之处： 遗传算法作为一种优化方法，它存在自身的局限性。 ( 1 ) 编码不规范及编码存在表示的不准确性。 ( 2 ) 单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约 束的一个方法就是对不可行解采用阈值，这样计算的实践必然增加。 ( 3 ) 遗传算法可能出现过早收敛。 ( 4 ) 遗传算法对算法的精度、可信度、计算复杂性等方面，还没有有效的 定量分析方法。 4 3 遗传算法问题分析 4 - 3 1 遗传编码问题 按照遗传算法的工作流程，当用遗传算法求解问题时，必须在问题实际表示 与遗传算法的染色体位串结构之间建立联系，即确定编码和解码运算。一般来说， 参数集及适应函数是与实际问题密切相关的，往往由用户斟酌确定。 由于遗传算法计算过程的鲁棒性，它对编码的要求并不苛刻。实际上，大多 数问题都可以采用基因呈一维排列的定长染色体表现形式，尤其是基于 0 ，1 符号集的二进制编码形式。然而，编码的策略或方法对于遗传算子，尤其是对交 叉和变异算子的功能和设计有很大的影响。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码一交叉问 题。因此，作为遗传算法流程中第一步的编码是遗传算法中需要认真研究的问题， 很多专家提出了各种编码方法【3 9 】【4 0 1 。 对于给定的优化问题，由g a 个体的表现型集合所组成的空间称为问题空间， 由g a 基因型个体所组成的空间称为g a 编码空间。遗传算子在g a 编码空间中 对位串个体进行操作。 定义1 由问题空间向g a 编码空间的映射称作编码( e n c o d i n g ) ，而由编码 空间向问题空间的映射称作译码( d e c o d i n g ) 。 目前尚无一套既严格又完整的指导理论及评价标准来帮助设计编码方案，必 须具体问题具体分析，采用不同的编码方法。问题编码一般应满足以下3 个原则： ( 1 ) 完备性( c o m p l e t e n e s s ) ：问题空间中的所有点( 可行解) 都能成为g a 编码空间中的点( 染色体位串) 的表现型。 ( 2 ) 健全性( s o u n d n e s s ) ：g a 编码空间中的染色体位串必须对应问题空间 中的某一潜在解。 ( 3 ) 非冗余性( n o n r e d u n d a n c y ) 染色体和潜在解必须一一对应。 应该注意到，严格满足上述规范的编码方法和提高遗传算法的效率并无关 系。在某些情况下，为了提高遗传算法的运行效率，允许生成包含致死基因的编 码位串，它们对应于优化问题的非可行解。虽然这会导致冗余或无效的搜索，但 可能有助于生成全局最优解所对应的个体，所需要的总计算量可能反而减少。 上述三个策略虽然具有普遍意义，但是缺乏具体的指导思想，特别是满足这 些规范的编码设计不一定能有效地提高遗传算法的搜索效率。按照遗传算法的模 式定理，d ej o n g 进一步提出了较为明确的编码评估准则，称之为编码原理。包 括两个规则： ( 1 ) 有意义积木块编码规贝j j - 所定编码应易于生成与所求问题相关的短距 和低阶的积木块。 ( 2 ) 最小字符集编码规则：所定编码应采用最小字符集以使问题得到自然 的表示或描述。 编码方式有很多种，本文采用的是二维二进制编码形式。 4 - 3 2 遗传算法欺骗问题 在遗传算法中，将所有妨碍适应度高的个体的生成从而影响遗传算法正常工 作的问题统称为欺骗问题( d e c e p t i v ep r o b l e m ) 。遗传算法运行过程具有将阶数 低、长度短、平均适应度高的模式重组成高阶模式的趋势。如果在低阶模式中包 含了最优解，则遗传算法就可能找出这个最优解来。但是低阶、高适应度的模式 可能没有包含最优串的具体取值，于是遗传算法就会收敛到一个次优的结果。下 面给出有关欺骗性的概念。 定义2 ( 竞争模式) 若模式h 和日中+ 的位置完全一致，但任一确定位的编 码均不同，则称日和日互为竞争模式。 定义3 ( 欺骗性) 假设f ( x ) 的最大值对应的彳集合为x + ，日为一包含x + 的m 阶模式，h 的竞争模式为h ，t ( u j j - f ( h ) f ( h ) ，则，为m 阶欺骗。 定义4 ( 最小欺骗性) 在欺骗问题中，为了造成骗局所需设置的最小的问题 规模( 即阶数) 称为最小欺骗性。其主要思想实在最大程度上违背积木块假设， 是优于由平均的短积木块生成局部最优点的方法。这里的“最小”是指问题规模 采用两位。 4 - 3 3 收敛问题 4 - 3 3 1 收敛定义 应用遗传算法解具体问题，就是要得出其全局最优解。通过遗传算法的进化 计算，最终得到全局最优解就是收敛。在利用遗传算法求解问题时，通常并不知 道适应值函数的最大值究竟是多少，因此当最优个体出现时，算法仍有可能会继 续进行下去，而在实际应用中，总是希望算法收敛时能够得到最优解。 定义5 设e 为t 时刻种群中所包含的个体的适应度的最大值。眦。为适应度 函数厂( ，x ：，t ) 在所有可能的个体所组成的集合x 中所取的最大值。若f 满 足： ! 曲h f = 厶。 _ 1 ( 式4 3 ) 则称算法收敛到最优解。 r u d o l p h 通过m a r k o v 链方法证明了在这个定义下，经典g a 是不会收敛到最 优解的。但是，若在g a 中保留每一代的最佳个体，则算法将收敛到最优解。 4 332 用m a r k o v 链分析g a 收敛性 目前用来分析遗传算法收敛性的工具主要有m a r k o v 链，除了m a r k o v 链外还 有随即过程中的鞅论方法、泛函分析中的压缩映射原理、v o s e 模型等方法。 模式定理分析了简单遗传算法中具有低阶、短定义距、平均适应度高的模式 在子代中增长，但并没有证明遗传算法的收敛性，即说明一定收敛于最优解。 用m a r k o v 链和矩阵变换的有关概念和性质【4 4 1 可以分析遗传算法的收敛特 性。 首先，介绍m a r k o v 链相关概念及理论： 有限马尔科夫链描述了随机变量穿越有限状态空间s 的概率轨迹，s 的状态 数蚓 定义6 设 以 是随机变量列，状态空间s = i ) ，如果对任意正整数k ，任意 的f 0 ，i 。s ，有 p ( 以+ = + ，l k = f 0 ，墨= ，以= i d = p ( 五+ ；= 。i x n = t ) ， ( 式4 4 ) 则称 以) 为m a r k o v 链，4 4 式表达的性质称为m a r k o v 性，也叫无后效性， 简称马氏性。 m a r k o v 性的直观理解为：如果把时刻n 看作“现在”，把时刻0 ，1 ，n 一1 看作“过去”，把时刻n + 1 看作“将来”，那么m a r k o v 性就是在己知“现在”所 处的状态下，n + 1 的状态与所有的“过去”的状态无关。所有，m a r k o v 性也叫 无后效性。 定义7v i ，j s ，称p ( 以。= ，l x 。= f ) = p o ( n ) 为n 时刻的一步转移概率；称 p ( 瓦+ 。= ，i 以= f ) = p o ) 为n 时刻的k 步转移概率。若对v f ，j e s ，p 扩- = p f 与n 无关，则称 瓦，月o ) 为( 时间) 齐次马氏链。 若用p ( 表示m a r k o v 链的k 步转移概率所组成的矩阵，则 p 耻= ( p ) = p 等p 磬 p 扩 称为k 步转移概率矩阵。 若用p 表示一步转移概率组成的矩阵，则 p = ( 腓) = p o i ： p u 称为一步转移概率矩阵，简称为转移矩阵。 转移概率矩阵具有以下性质： i ) p 口0 ， f ，j j ； 2 ) p 笋= 1 ， f ，k = l “2 - - ， 性状2 ) 表明k 步转移概率矩阵中任一行元素之和为1 。通常称满足1 ) 、2 ) 条件的矩阵为随机矩阵。给定一个初始分布p 0 作为行向量，则齐次有限马尔科 夫链在t 时间步后的分布p = p o p l ，因此齐次有限m a r k o v 链完全由( p o ，p ) 决定， 即齐次有限马尔科夫链的远期行为由其初始分布和一步转移概率所决定。 m a r k o v 链的极限性质与转换矩阵的变换有关，因而下面列出矩阵的有关的 概念和性质： 定义8a 是一个方阵， ( 1 ) 如对所有的i ，j ， 0 ，记为a 0 。称a 0 ，称a 为严格正的矩阵， 或称为正定的( p o s i t i v e ) 矩阵； ( 2 ) 如a 0 ，若存在k n ，使得a 。 0 ，则a 为正则的，或称为非负的 ( n o n n e g a t i v e ) 矩阵。 定义9 编码串s 。和s j 之间的海明距离定义为： ( s i ，s j ) = k 一划 ( 式4 5 ) 其中，g 。是串s ，的第k 位基因。 下面，用有限状态空间的m a r k o v 链分析遗传算法的收敛性问题，得出以下 结论： 结论1 基本遗传算法( s g a ) 收敛于最优解的概率小于l ，即通过基本遗传 算法的迭代运算，不收敛于最优解。 础；骱 对结论1 的证明如下： 证明将群体的各种可能状态1 分为包括最优个体的状态厶和不包括最优个 体的状态l ；i = 厶u l ( z o n l = o ) 。要证明# 进入厶状态的稳定概率小于1 。 用反证法。假设基本遗传算法能收敛于最优解的概率等于1 ，则进入l 状态 的稳定概率应等于0 ，即： 嫩p 只l = 0 ( 式4 - 6 ) 在基本遗传算法的进化过程中，群体从某一状态i ，经过选择、交叉和变 异算子的连续作用而转变为状态_ ，。这三种遗传算子的转移概率分别为、 勺、m f ，它们可分别构成相应的随机矩阵s = s o - 、c 2 勺 、m = m 口) ，则遗传 算法的群体状态变化矩阵为：r = s c m = 白 。 由于s 、c 、m 都是随机矩阵，并且口= 掣飞l p 。) 。州棚 0 ，h ( i ，j ) 为状态i 和状态j 2 _ f 日qh a m m i n g 距离，容易证得0 o ，即r 是正定的。 在第t 时刻，群体是状态j 的概率0 ( f ) 为 p ( t ) = 暑( o ) ，( f = 0 , 1 2 ) ( 式4 7 ) 由齐次m a r k o v 链的性质可知，0 ( f ) 的稳定概率分布与其初始概率分布无关， 即有 l i m e j ( t ) = l i m p f ( t ) r r ， 0 ( 式4 8 ) 上式中的状态j 1 ，即j 也可能是l 中的一个状态，从而可知： 磐碧尸 # l o ( 式4 9 ) 上式与式4 6 的假设相矛盾，从而结论l 得证。 模式理论描述了遗传算法在搜索过程中向全局最优解接近的趋势，m a r k o v 链证明简单遗传算法收敛于全局最优解的概率小于1 ，也就是s g a 在搜索过程 可能发现全局最优解，但不能保证每次都收敛于全局最优解。为什么简单遗传算 法不能收敛于全局最优解? 产生这种现象的原因是由于状态转移矩阵r 是正定 的，即咯 0 ，也就是说简单遗传算法满足完全遍历性，即从任一状态出发转移到 任一其它状态的概率 o ，当然也包括最优解所在状态，但由于简单遗传算法没有 设置任何保留策略使得马氏链停留在最优解所在状态不再脱离出来，当算法在搜 索过程中发现了全局最优解时，有可能又通过交叉或变异的操作使得最优解又丢 失了。因此，为了能够让遗传算法收敛于最优解，保证算法的转移矩阵具有非完 全遍历性，最优保存策略的使用是必须的。 最优保存策略的形式化定义为： 定义1 0 设s + = 玩：f ( b k ) = m a x f ( 足) ，钆& ，k = 1 , 2 3 ) ，以，钆+ 。分别为 第k 代和第k + 1 代群体瓯，足+ 。中的最优个体，( 瓯) ，f ( b k + ，) 为其相应的适应 度。若f ( b k ) f ( b k + ，) ，则以+ = 钆，( 吼+ 。) = f ( b k ) 。 具有以上定义的最有保存策略的s g a 称之为最优保存s g a ，简称为o m s g a ( o p t i m u mm a i n t a i n i n gs i m p l eg e n e t i c a l g o r i t h m ) 。 结论2 具有最优个体保存策略的遗传算法收敛于最优解的概率为1 。 该结论在文献中有证明。 具有保优策略的遗传算法随着遗传代数k 的增加，每代最优个体适应度所构 成的数列 f ( b j ) ，厂( 6 2 ) ，) 为不减数列。这是最优保存操作的直接结果和本质表 现。 保优策略仅限于保持进化种群迄今为止所发现的最优解，凡具有这种功能的 g a 均可称作o m g a ( o p t i m u mm a i n t a i n i n gg e n e t i ca l g o r i t h m ) 。具体如何在算法运 行中实现最优保存功能则有不同的方法。实际仅当上一代的最优个体优于下一代 时，需将该个体保留到下一代，否则不必保留。 4 333 防止未成熟收敛 通常利用遗传算法进行优化工作，目的是为了找到全局最优解，算法找到全 局最优解的能力称为全局收敛能力。我们希望运用遗传算法尽快地找到全局最优 解，即提高收敛速度。在过程时间中人们发现基本遗传算法能够较快地搜索到最 优值附近，但到达最优解附近后收敛速度变慢。为此人们提出了若干改进的方法。 基本遗传算法除了具有后期收敛速度慢的问题外，基本遗传算法还存在过早 收敛问题。 我们知道遗传算法具有通过不断遗传操作，种群中的个体不断提高适应度， 即向最优解不断逼近的特点。遗传算法的目的通常也就是是通过遗传操作获得全 局最优解。通过遗传算法的不断迭代，最终获得全局最优解。 然而，有时应用遗传算法解具体问题时，当到达局部最优解时，基本遗传算 法( s g a ) 会出现进化停滞的现象，即继续进行遗传操作，种群中的个体始终在局 部最优解附近徘徊，得到的新个体其适应度不再增加，也就是说进行迭代不能够 得到全局最优解。 ( 1 ) 未成熟收敛( 早熟) 现象 表现在两个方面： ( a ) 群体中所有个体都陷于同一极值而停止进化，而该极值又不是全局最 优解； ( b ) 接近最优解的个体总是被淘汰，进化过程不收敛。 这种现象称为过早收敛，或称为早熟收敛、未成熟收敛，简称早熟。 ( 2 ) 未成熟收敛产生原因 ， ( a ) 理论上考虑的选择、交叉、变异操作都是绝对精确的，它们之间相互 协调，能搜索到整个解空间，但在具体实现时很难达到这个要求。 ( b ) 所求解的问题是遗传算法欺骗问题。当解决的问题对于标准遗传算法 来说比较困难时，遗传算法就会偏离寻优方向，这种问题被称为遗传算法欺骗问 题。 ( c ) 遗传算法处理的群体是有限的，因而存在随机误差，它主要包括取样 误差和选择误差。取样误差是指所选择的有限群体不能代表整个群体所产生的误 差。当表示有效模板串的数量不充分或所选的串不是相似子集的代表时，遗传算 法就会发生上述类似的情况。小群体中的取样误差妨碍模板的正确传播，因而阻 碍模板原理所预测的期望性能产生。选择误差是指不能按期望的概率进行个体选 择。 在遗传算法处理过程的每个环节都有可能导入未成熟收敛的因素。遗传算法 未成熟收敛产生的主要原因是，在迭代过程中，未得到最优解或满意解以前，群 体就失去了多样性。具体表现在以下几个方面： ( a ) 在进化初始阶段，生成了具有很高适应度的个体x 。 ( b ) 在基于适应度比例的选择下，其它个体被淘汰，大部分个体与x 一致。 ( c ) 相同的两个个体进行交叉，从而未能生成新个体。 ( d ) 通过变异所生成的个体适应度高但数量少，所以被淘汰的概率很大。 ( e ) 群体中的大部分个体都处于与x 一致的状态。 ( 3 ) 未成熟收敛的防止 解决方法有如下几种： ( a ) 重新启动法。在遗传算法搜索中碰到未成熟收敛问题而不能继续时， 则随机选择一组初始值重新进行遗传算法操作。假设每次执行遗传算法后陷入不 成熟收敛的概率为q ( o q h ( q ) ； b ) 对紧接交叉点的任务厶，有h ( l ，) h ( q ) ； 则由内部交叉算子生成的调度也是合理的【3 1 】。 证明由于内部交叉只发生在一个调度内部，显然各任务在调度中出现的唯 一性可以得到保证。现在只需要证明在交叉操作后，各任务的依赖关系不会被破 坏。设交叉点在资源置的任务列表中落在皿仲) 和皿伽之间，在资源马的任 务列表中落在兄k 舶) 和兄0 舶圳之间，a 、b 、x 、y 均为0 到n l 之间的熬数，且 a + x 和b + y 都不大于n 一1 ，则有日( 厶) s q 日( t + ，) 及i h ( l 6 ) q h ( l m ) 。交叉 操作后，仍有日( 三。) q h ( l 。) 及日( 厶) q h ( l ) 。即资源的任务列表中 任务的排列还是满足高度值的升序排列，因而是合理的分配与调度策略。( 证毕) 因此，新生成的个体s 1 ( f ) 也仍然是能够满足定义3 的。 相比之下，文献 3 2 1 中交叉算子对交叉点选择的条件要求太强，因而对算子 的搜索能力有一定的局限性。 5 5 2变异算子 变异算子一定程度上克服了遗传算法的早熟收敛，有利于增加种群的多样 性。在解群局部收敛时，通过变异算子的突变作用，来保持解群一定的多样性。 这里变异算子实质上就是将某个子任务迁移到另一个资源上执行。为了防止某个 任务在迁移后，执行的时间增大而造成种群退化，规定迁移后任务占用的资源不 是随机产生，而是在除了该任务目前占用的资源外的资源集合中，选择与该任务 最小深度值一样的任务数最小的资源，将其迁移到该资源上执行。 在任务调度问题中，个体s ( o 中的变异操作实质是任务迁徙的过程，即某个 资源中的一个任务被重新调度到另一个资源中的过程，具体操作过程如下： ( 1 ) 随机生成一个数q ( o q h i g h e s t ) 。 ( 2 ) 计算个体s ( f ) 中各基因行中最小深度值等于q 的任务数 ，o i n ； ( 3 ) 从m 最大的基因行中随机选择一个最小深度值等于q 的基因( 任务) ， 将其迁徙到m 最小的基因行中，从而生成一个新的个体s ( f ) 。 显然任务经迁徙后，这两个基因行中的各基因仍然是按基因( 任务) 深度值升 序排列的。因此，新生成的个体f ( f ) 也是满足定义3 的。 引入迁移算子的好处如下：第一，迁移算子能间接地起到交换两个任务的作 用，包括在同一资源列表中交换两个等高度值的任务；第二，多个串行执行的任 务，通过迁移操作后，有可能获得并行执行的效果，能够充分利用网格资源：第 三，内外部交叉与迁移算子相结合，使得算子的搜索能力是充分的。 假设某个任务有三个等高度值的直接后继任务k 、l i 、l 。，那么，迁移 后，生成的新的调度只中这三个任务有可能并行执行，而s 中的三个任务只能 串行执行。这样，足就可能比s 有更短的完成时间。 _ l i 1 斗l i 斗l i “斗 调度墨任务迁移前 5 - 5 3 选择算子 一l i 1 哼 l 一 斗l i + i 寸 调度s ：任务迁移后 图5 2 任务的串并行执行 选择算子的算法很多，例如适应度比例方法，即轮盘赌选择方法 3 3 】，随机遍 历抽样选择 3 3 等。本文采用适应度比例与精英策略相结合的方法。 适应度比例方法按个体适应度的大小计算选择概率。设群体大小为k ，对于 一个任务调度策略s ( i ) ，即一个个体相应的遗传选择概率 k b = ，( s ( 州厂( s ( f ) ) ， ，i = l 其中，只，反映个体s ( f ) 的适应度在整个群体中的个体适应度总和所占的比 例，个体的适应度越高，其被选择的概率也越大。 精英策略的主要思想是要保持解群体中的最好的解个体不丢失3 4 1 。即根据算 法的适应值( 或目标函数) ，保持解群中最好解的单调递增性。这里由于我们使 用的是适应度比例，故将保存适应度比例最高的两个解个体，从而使进化过程中 优良的个体不被交叉和变异操作所破坏，而直接进入下一代群体。 经过交叉或变异新生成的子个体，我们分别对它们计算适应值。如果生成的 子个体的适应值大于父个体，则替换父个体。反之，则选择原种群中适应值最小 的个体比较，如果新子个体的适应值大于最低适应值，则替换原个体；否则舍弃 生成的子个体，并重新选择父个体进行交叉或变异操作。 s t e p l s t e p 2 s t e p 3 s t e p 4 s t e p 5 s t e p 6 s t 印7 s t e p 8 s t e p 9 5 - 6 遗传算法总体框架 读入一个d a g 图，计算图中每个任务结点的最小深度值、最大深度 值、深度值，构造相应的任务关联矩阵； 生成初始种群p o p ( t ) ，仁o ； 如果不满足算法的终止条件，执行s t e p 4 ；否则，转s t e p 8 ； 计算种群中每个解的适应值； 采用精英策略执行选择，适应值最高的两个个体直接进入下一代： 以交叉概率见执行内部交叉运算，以概率1 一p 。执行外部交叉运算， 在父个体、子个体、以及父代其他较差个体之间进行选择，适应值高 的进入下一代； 以变异概率p 。执行变异运算，进行与s t e p 6 中同样的选择： 若种群过早收敛，则加大变异概率；转步骤3 ； 输出最好解，算法结束。 本文遗传算法终止条件为：最大进化代数耗尽、收敛于最优解。 5 7 1 结果及结论 5 - 7 仿真实验 仿真使用的是g r i d s i m t o o l k i t 3 3 软件开发包，根据前面章节所述的g a 算法 框架和模型，在b r o k e r 中实现任务调度g a ，并将任务属性进行了扩充，便于建 立d a g 中所表示的前驱后继关系，以及便于保存计算任务最小深度、最大深度、 深度值。其中任务数及其工作量、资源数、资源处理时间、资源分配策略、最大 进化代数、种群规模以及交叉概率、变异概率均可在初始化时手动设置。 由于动态建立任务d a g 十分复杂，本文实验中采用预先建立好的d a g ，如 图5 3 ： 图5 3 在备选d a g 中选定后，再进行下一步的设置。 下面给出一个与文献 3 2 中标准算法的仿真比较结果。算法中用到的主要参 数有：分别由2 0 、5 0 、1 0 0 个任务组成的d a g 图，解的种群规模l o ，最大进化 代数6 0 0 代，各资源间数据传输延时随机生成。用于文献【3 2 忡模拟算法的 交叉和变异概率分别为p 。= 1 0 和= 0 0 5 ，本文算法内部交叉概率为p 。= 0 8 ， 迁移概率为p ，= 0 0 5 。 从表5 2 中可以看出，与标准算法相比，本文算法能便于找到最优解。这是 因为，首先本文算法在构造初始种群的时候尽可能对任务深度值进行了均衡分 配，其次使用的交叉算子具有生成最优解的能力，而变异算子可将串行执行的多 个算子任务经过迁移后，可获得并行计算的效率，并且当过早收敛时，变异概率 加大，以保证不会陷入局部最优解。 表5 2 仿真比较结果( 单位时间) 资源个数 任务个数算法 3 2 完 本文算法完算法【3 2 进本文算法进 成时间 成时间化代数化代数 22 03 8 53 5 975 5 07 5 97 2 23 l3 0 1 0 01 4 1 21 3 1 01 3 91 1 5 32 03 6 53 3 8 7 1 5 07 1 76 8 03 23 1 1 0 01 2 2 21 1 6 31 2 71 1 2 42 03 4 93 1 551 5 05 7 95 3 32 92 7 1 0 01 1 0 6 9 4 3 1 1 1 1 0 9 52 03 4 33 1 611 5 05 4 15 0 l3 23 0 1 0 09 1 2 8 3 7 1 2 5l l o 图5 4 和图5 5 所示的是算法的静态性能曲线，分别是1 5 0 个任务在5 个资 源和6 个资源上分配调度的仿真结果。列出了算法在不同进化代数时所找到的最 优解。 算法的静态性能曲线也表明算法有较好的收敛速度。演化策略的选择机制， 保证了最优解性能的不降性。仿真结果表明了本文介绍的算法在分配与调度问题 中的有效性。 图5 4 算法的静态性能曲线( m = 5n = 1 5 0 ) 图5 5 算法的静态性能曲线( m = 6n = 1 5 0 ) 下面的表5 3 给出了收敛到最优解的次数占到实验次数的比例，从表中的比 例也说明了本文算法的编码解码具有较优的对解空间的全局搜索能力。 袭5 3 牧绞鼹；最筏解次数占实验次数翡雷分魄 不同箨法饺务个数2 0经务个数5 0任务个数1 0 0 文献 3 2 1 算法 9 0 7 2 5 8 本文箕法l 9 7 9 2 遮转算法孛各荦孛按京l 参数静遥替辩黧淡瀚佳麓彩确缀大，这些参数包括稀辩 舰模、交叉概率、燮肄概率等。图5 6 为种辩规模性能睦线。 鹜5 。6 穆辞蕊摸镶戆篷绫 s ，弘2 下步方蠢 随格嚣壤孛经务分配与键度懿婿究每实践还存在着许多待解决敬遥莲，遴一 步豹辑究工佟如下： ( 1 )鼷穆溺态茬。在真实豹秘穰群糖下，瓷溪豹状态是动态静，鹣辩 可能发生变化。本文的仿真试验中只考虑了猩资源发现阶段检焱 资源状态著获敬可籍资源，并米考虑农任务执 亍酚段赘源状态酚 可交健，露在餐务撬嚣麓凌，秘穆土瓣资源霄霹笺嚣竣障瑟不可 塌，此时涉及剿任务在资源之间的迁移问题。 ( 2 )遂售鸟延迟。舞实网格鲻蟪下豌任务调度闽粼缀复杂，不纹仪螫 | 一一 i 矮 ( 3 ) ( 4 ) 考虑到网络数据传输延迟，网络拓扑结构、通信节点路由选择也 是影响调度的因素，有待进一步探讨。 多种群共同进化。一个大的作业在被分解为子任务时，可能产生 多个独立d a g 图，这种情况下，应考虑采用多种群共同进化计 算模型来实现调度而不是单种群进化算法。 与其它算法结合。b u y y a 在g r i d s i m 中仿真的是经济模型的调度 算法，而在实际的网格资源的使用上也应该考虑到期限和预算对 任务执行的限制，本文遗传算法中还未涉及到，有待将经济因素 结合到遗传算法中去。目前较多的研究是退火模拟算法【5 0 1 与遗传 算法的结合，若为了提高解的全局搜索能力，可以考虑将蚁群算 法【3 7 1 与遗传算法的结合，已有的结合方式为先使用g a 生成初 始解，克服蚁群算法全局搜索力弱的缺点，之后再用蚁群算法以 较快的速度逼近最优解。 参考文献 【1 1 i f o s t e r a n d c k e s s e l m a n ，t h e g r i d ：b l u e p r i n t f o ra n e w c o m p u t i n g i n f r a s t r u c t u r e ，m o r g a nk a u f m a n n ，s a nf r a n s i s c o ，c 八1 9 9 9 h t t p ：m l q o e o m g r i d s , h t t p ：w w w g r i d f o r n m o r g ，h t t p ：w w w c c g r i d o r g 【2 】f o s t e r 有关网格计算演讲材料， h t t p ：w w w - f p m c s a n l g o v - f o s t e r t a l k s w w w g r i d s m a y 2 0 0 2 p p t ， h t t p ：l l w w w - f p m c s a n l g o v - f o s t e r t a l k s g r i d t u t o r i a l p p t 3 i f o s t e r ，c k e s s e l m a n , s t u e c k e ”t h ea n a t o m yo f t h eg r i d ：e n a b l i n gs c a l a b l e v i r t u a lo r g a n i z a t i o n s ”i n t e r n a t i o n a lj s u p e r c o m p n t e ra p p l i c a t i o n s ，1 5 ( 3 ) ， 2 0 0 1 b c l u s t e rc o m p u t i n ga n dt h eg r i d ，2 0 0 1 p r o c e e d i n