（计算机软件与理论专业论文）基于蚁群遗传算法的网格任务调度策略研究.pdf

项士学位论文 m a s t e r st h e s i s 摘要 网格技术试图聚合分布在世界各地的计算、存储、知识、通信和信息等各类资 源，以服务大众为目的，实现资源共享与协同工作。网格任务调度技术问题尤其突 出。网格所具有的动态性、异构性等特征使得网格任务调度变得更加复杂，必须研 究出适合于网格计算环境的任务调度策略，提高用户完成总任务的效率，提供给用 户满意的服务质量。 仿生优化算法应用于网格任务调度中，日益成为解决网格任务调度问题的锐利 工具。作为仿生优化算法之一的蚁群算法其动态性、自相似性与网格任务调度原理 极其相似，许多学者将蚁群算法应用于网格任务调度技术，并取得了不错的效果。 但是其研究没有考虑到蚁群算法的收敛性能对初始化参数的设置比较敏感，对于蚁 群算法中的4 个参数信息启发因子口、期望因子夕、信息素挥发因子p 、信息素强 度q 在经验值的范围内随意或者是拼凑取值，这对蚁群算法的计算效率和收敛性产 生了不利的影响。 参数信息启发式因子口反应了蚂蚁受其它蚂蚁经过网格资源节点时留下的信 息素影响程度，其值越大，蚂蚁越倾向于选择其他蚂蚁选择过的资源节点，期望因 子夕反应了蚂蚁受资源的固有属性的影响程度，其值越大，蚂蚁越倾向于选择条件 好的资源，这两个参数的值越大，蚁群算法越容易陷入局部最优。信息素挥发因子 p 能够避免信息素无限积累，有利于扩大搜索范围；信息素强度q 能够加强正反馈， 使搜索朝有利于寻找最优解的方向进行，提高求解的效率。针对这些参数的特征， 本文提出蚁群遗传算法a c a g a ( a n tc o l o n ya l g o r i t h mg e n e t i ca l g o r i t h m ) 并用于网格 任务调度。a c a g a 利用遗传算法快速随机的全局搜索能力，探索蚁群算法中的四 个参数口，夕，p ，q 的优化组合，实现网格中任务更加合理地调度。文中使用网 格模拟器g r i d s i m 对蚁群遗传算法进行了仿真模拟。模拟结果表明该算法缩短了任 务的执行时间，同时有利于网格负载均衡。 关键词：参数组合；蚁群算法；遗传算法：蚁群遗传算法；g r i d s i m a b s t r a c t g r i dw h i c hg a t h e r sc o m p u t a t i o nr e s o u r c e s , s t o r a g er e s o 嘲，k n o w l e d g er e s o u r c e ， c o m m u n i c a t i o nr e s o u r c e ，a n di n f o r m a t i o nr c s o u r c g se t c t o g e t h e rf r o ma l lo v e rt h ew o r l d , a i m sa ts e r v i n gp u b f i ea n dr e a l i z i n gr e s o u r c e ss h a r i n ga n dc o o p e r a t i v ew o r k i n g g r i d t e c h n o l o g i e s , w i t hi t se x t e n s i v ed e v e l o p i n gp e r s p e c t i v ea n dc o m m e r c i a lv a l u e ，h a v eb e e n ah o tt o p i cb o t ha th o m ea n da b r o a dr e s e a r c h h o w e v e r , t h e r er e m a i nq u i t eal o to fk e y t e c h n i c a li s s u e sw a i t i n gt ob er e s o l v e di ng r i d , a m o n gw h i c h , g r i dt a s ks c h e d u l i n gi s e s p e c i a l l yo u t s t a n d i n g t h ed y n a m i cc h a n g e ，g e o g r a p h i c a ld i s p e r s i o na n dh e t e r o g e n e o u s s y s t e m so fg r i dc o m p l e xt h eg r i dt a s ks c h e d u l i n g t h e r e f o r e ，i ti sn e c e s s a r yt ow o r ko u t ad i s p a t c h i n gs c h e m ea d a p t a b l ei ng r i dc o m p u t a t i o ne n v i r o n m e n t t h es c h e m ec o u l d i m p r o v et h ee f f i c i e n c yo fu s e r st a s kc o m p l e t i o ns ot h a tt h es e r v i c eq u a l i t yc o u l db e s a t i s f a c t o r yt ot h eu s e r s b i o n i co p t i m i z a t i o na l g o r i t h ma p p l i e di ng r i dt a s ks c h e d u l i n gb e c o m e sas h a r pt o o l t os o l v et h ep r o b l e mo fg r i dt a s ks c h e d u l i n g a so n eo ft h eb i o n i co p t i m i z a t i o na l g o r i t h m , a n tc o l o n ya l g o r i t h mh a sb e e na p p l i e di ng r i dt a s ks c h e d u l i n gb ym o r ea n dm o r e s c h o l a r s 、i lag o o de f f e c tf o ri t sd y n a m i ca n ds e l f - s i m i l a r i t yw i t ht h et h e o r yo fg r i d t a s ks c h e d u l i n g b u tt h e yd on o tt a k ep a r a m e t e ro p t i m i z a t i o ni n t oa c c o u n ta n dv a l u e i n s p i r i n gi n f o r m a t i o np a r a m e t e r sg ，t h ee x p e c t a t i o n sf a c t o r8 ，i n f o r m a t i o nv o l a t i l ef a c t o r p ，p h e r o m o n es t r e n g t hqa c c o r d i n gt op r e v i o u se x p e r i m e n t i nf a c t , t h ec o n v e r g e n c e p e r f o r m a n c ea n dc o m p u t a t i o n a le f f i c i e n c yo fa n tc o l o n ya 陀 s e n s i t i v et oi ta na n t s y s t e mb a s e de x p l o r a t i o n - e x p l o i t a t i o nf o rr e i n f o r c e m e n tl e a r n i n g ， i nt h i sp a p e r ，w ei n t e g r a t eg e n e t i ca l g o r i t h mi n t oa n tc o l o n ya l g o r i t h ma n df o r ma n t c o l o n yg e n e t i ca l g o r i t h m t h i sa l g o r i t h mu s e sf a s tg l o b a ls e a r c hr a n d o m l yo fg e n e t i c a l g o r i t h ma n de x p l o r e so p t i m i z a t i o no ff o u rp a r a m e t e r s 伍，8 ，p ，qt oa c h i e v ea m o r e r e a s o n a b l es c h e d u l i n g k e yw o r d s ：p a r a m e t e r sg r o u p i n g ；a n tc o l o n y ；g e n e t i ca l g o r i t h m ；a n tc o l o n ya n d g e n e t i ca l g o r i t h m ；g r i d s i m 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 参7 移 日期：珈7 年r 月獭 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用 作者签名： 日期：侧 i 本人已经认 学位论文提交“c a l l s 高校学位论文全文数据库 中全文发布，并可按“章程 中的 规定享受相关权益。 作者签名：加 日期加1 年r 1 1 绪论 1 1 问曩的提出 网格是将分布在世界各地的计算，存储知识和通信等资源融合起来形成一个 功能强大的虚拟计算机”。网格的这个想法出自于电力网。它希望人们在使用网格 的计算能力等功能时就像使用电力网一样方便，无需考虑资源在什么地方以及这个 资源的配置方法例，图1 1 表示了电力网和网络的组成结构图。 匠霎韶翌要j k 电力网构成示意图 匮震豇噩卜因 网格组成示意图 图l1电力阿与阿格组成示意图 从图l _ 1 我们可以看出电力网中的组成部分风力。火力，水力等设施负责提供 资源，用户作为使用者直接使用资源，网格与电力网非常相似，将两格中的用户， 资源抽象出来，同时加上一个协调机构即资源中介便构成了一个简单的网格模型， 如图12 所示。 嗲一，套 图l2简单网格横型 项士学位论文 m a s t e r st h e s i s 在简单的网格模型中，当用户向网格资源提交任务并提出任务请求时，资源 中介便充当了协调任务调度的角色，它从当前可用资源中选取合适的资源并执行该 任务。任务调度的过程是以总任务的执行时间最小化为目标，将n 个任务分配给m 个合适的网格资源并在网格资源上执行的过程。我们可以用图l - 3 网格资源管理图 来描述。 任务调度策略 二_ 二= 资源请求i 任务调度器 客户机卜一 任务及任务请求 a 3 用资源 资源分配并执行任务 图1 3 网格资源管理图 资源管理器 用户任务 从图1 3 中，可以看出网格任务调度是协调网格系统有效运转的重要机构，其 调度策略好坏直接关系到网格的整体性能。图中资源管理器由资源监控器和本地任 务调度组成，资源监控器监视资源的使用情况及运行状态并将当前可用资源信息提 交给任务调度器，用户向客户机提出任务及任务请求后，客户机根据执行任务所需 要的资源向任务调度器提出资源请求，此时，任务调度器根据事先预定好的任务调 度策略分配资源并执行任务，需要指出的是任务的执行是由本地任务调度完成的， 任务执行完毕后，将执行结果返回给用户。 网格的动态性和异构性等特征使得网格任务调度具有一些这样的特点。首先， 它必须面向异构平台，屏蔽一些底层差异。其次，它具有分布式的特点，虽然网格 任务调度不会影响资源节点内部的调度策略，但是网格资源分布在世界各地，不可 能存在一个任务调度器负责完成网格中所有任务的调度。更为重要的是，网格任务 调度必须具备动态适应性和可扩展性，随时应对资源增加，退出和发生故障等突发 情况。网格任务调度存在的这些特点使得网格任务调度这个组合问题变得异常复 杂。一方面，它要求用户提交的任务实现最优跨度，负载均衡和提高系统的吞吐率： 另一方面，它还希望这个调度符合经济原则并能提高好的服务质量，提高用户的满 意度，推进网格的应用与发展。网格任务调度问题已经被证明n p 难闯题【3 】。传统 的任务调度策略很少需要考虑资源的异构性，动态性和可扩展性等特点。因此，我 2 们必须研究出适合于网格环境下的任务调度的策略，应对诸如n p 难等问题。对此， 国内外展开了广泛的研究。 1 2 现状及意义 目前，按照调度策略来分，网格任务调度策略可以分为静态调度策略和动态调 度策略。静态调度策略指用户提交任务后，并不立即执行，而是将一个时间段中的 任务集中起来，当任务映射事件到来时集中映射，该算法缺乏灵活性，一旦资源状 态发生变化，原先消耗不少时间计算出来的任务调度列表需要重新计算，增加了用 户的响应时间。动态调度策略却不同，用户提交任务后便马上映射，它能够随着网 格环境的变化而变化，具有较好的适应性和灵活性。常见比较传统的静态调度策 略有：m a x m i n 4 1 ，m i n _ m i n 5 1 ，s u f f r a g e s l 等；常见的动态调度算法比如蚁群算法忉， 免疫遗传算法嗍，模拟退火算法1 9 1 等。蚁群算法和模拟退火算法等启发式智能算法 应用于网格任务调度且达到了预期效果，这些算法毫无争议地成为解决网格任务调 度问题的锐利工具。 作为网格核心服务之一的网格任务调度技术负责完成网格资源的调度工作，既 要体现“能者多劳”又要保证“耕者有其田”，充分利用网格资源。一个好的调度策略 能高效地协调和分配网格资源，有效降低网格任务调度的总执行时间和平衡负载， 提高网格性能。 本文在仔细分析启发式智能化算法蚁群算法和遗传算法基本原理和特性的基 础上，提出蚁群遗传算法a c a g a ，将该算法用于解决网格计算环境下的任务调度 问题，减少用户交付时间，提高用户满意度，最终促进网格的推广与应用。 1 3 解决方案及措施 本文在阅读国内外关于网格任务调度相关文献后，提出了适应网格计算环境， 提高网格任务调度效率的网格任务调度策略a c a g a 。论文主要内容如下： 1 解析网格环境下，任务调度特征及当前面临的问题，是本文进行理论研究的 前提条件： 2 分析比较仿生优化算法中的蚁群算法和遗传算法的特点，是本文进行理论研 究的现实基础。 3 将蚁群算法和遗传算法融合后的蚁群遗传算法应用于网格任务调度并进行了 必要的仿真，验证该算法合理性和可行性。 1 4 本文的组织结构 3 硕士学位论文 m a s t e r st h e s i s 本文在对网格。网格环境中的任务调度进行剖析后，围绕设计a c a g a 及其在 网格任务调度中的应用进行研究本文分为五个部分，其内容具体安排如下： 1 提出问题并给出了解决方案，介绍了网格任务调度的研究现状及研究意义： 2 剖析蚁群算法和遗传算法的基本原理及特点，为本文的研究奠定理论基础； 3 提出适用于网格环境下的任务调度策略蚁群遗传算法a c a g a ： 4 仿真实验及分析； 5 总结与展望。本章节对本文的研究工作进行回顾和总结，并提出了值得进一 步探索的问题。 4 2 蚁群算法与遗传算法基本原理 人们不断地从自然界的许多自适应优化现象中获得启发：被人们认为的极其复 杂的优化问题经过生物体和自然生态系统的自身演化就可以得到完美的解决。于是 人们希望模拟自然生态机制从而获取求解组合优化问题的仿生优化算法，为传统最 优化技术难以解决的组合优化问题提供切实可行的解决方案。随着模拟自然与生物 机制为特征的仿生优化算法的研究不断深入，些仿生优化算法如蚁群算法，遗传 算法已在经典n p 难问题的求解和实际应用中展现出强大的能力和进一步发展的潜 力。这一部分主要剖析蚁群算法和遗传算法的基本原理及特点，为后面网格环境下 任务调度策略问题的研究奠定理论基础。 2 1 基本蚁群算法基本原理 基本蚁群算法( a n tc o l o n ya l g o r i t h m , a c a ) 是一种模拟昆虫王国中蚁群群体智能 行为的仿生优化算法。生物学家通过对蚂蚁行为的长期观察研究发现，每只蚂蚁的 智能并不高，看起来没有集中的指挥，但它们却能协同工作，集中食物，建起坚固 漂亮的蚁穴并抚养后代，依靠群体能力发挥出超出个体的智能，其中最引人注目的 智能是蚂蚁在觅食过程中总能找到一条从蚁巢到食物源的最短路径。 2 1 1 自然界中蚁群行为 昆虫世界中，蚂蚁群体是一种群居的世袭大家庭，我们称之为蚁群。蚂蚁根据 分工不同分为蚁后、工蚁、兵蚁和雄蚁等等，蚁后专司产卵，为数众多的工蚁主要 从事觅食打猎、兴建屋穴和抚育后代，兵蚁负责守卫门户和对敌作战，而雄蚁专备 为蚁后招婿纳赘。它们具有高度结构化的社会组织，不仅可以借助触觉和视觉的联 系，而且可以借助特有的被人们成为信息素的分泌物等信息介质相互沟通并协调行 动，找到一条从蚁巢到食物源的最优路径。 经研究发现，蚂蚁在运动时会在所经过的路径上留下信息素，蚂蚁遇到食物时， 并不急于进食，而是将食物搬回蚁巢或者回到蚁巢搬来救兵。蚂蚁在回巢的过程中 也会留下信息素，当蚂蚁搬来救兵前往食物源时，信息素浓度越大的路径，蚂蚁选 择的概率越大，这样便形成了正反馈现象。正是这种正反馈，促使蚂蚁群体最终能 找到最优路径。另外，蚂蚁的环境适应能力很强，即使蚂蚁在运动途中遇到障碍物， 它也能通过感知信息素浓度重新找到蚁巢到食物源的最优路径【i o j 。 5 2 1 2 基本蚊群算法的逻辑结构 蚂蚁能够通过信息素感知环境的变化并通过信息素实现与其它蚂蚁个体的相 互沟通与协作。蚂蚁个体自身的行为是随机的，独立的，但是蚂蚁群体可以在没有 外界的作用下完成从无序到有序的过程。其逻辑结构图如图2 1 所示。 图2 1 基本蚁群算法的逻辑结构 图2 1 中，首先把组合优化问题表示成规范的形式，制定决策机制并设置相应 的决策点，蚂蚁个体“利用( e x p l o i t a t i o n ) ”信息素的浓度感知环境的改变和过去的行为 结果同时“探索( e x p l o r a t i o n ) ”未来的情况，并按照相应的信息素更新规则对每只蚂蚁 个体的信息素进行更新，随后从整体角度规划出蚁群活动的行为方向，周而复始， 即可求出组合优化问题的最优解【i 。 2 1 3 基本遗传算法的数学模型 基本蚁群算法思想来自于自然界中真实蚂蚁觅食的群体行为，但基本蚁群算法 中的人工蚂蚁具备了真实蚂蚁所不具备的一些特性，比如人工蚂蚁有内在状态，该 状态能够记忆自身过去的行为，在算法上表现为一个称为t a b u 的禁忌表，该禁忌表 储存了该蚂蚁已走过的路径，避免蚂蚁走以前走过的路径。 旅行商问题t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 展示了组合优化问题的所有方面， 已成为测试新算法好坏的一个标准。t s p 问题可描述为已知n 个城市之间的距离， 有一个推销员必须访问这n 个城市，并且每个城市只能访问一遍，推销员访问完所 有的城市后必须回到原来出发的城市，他该如何访问这些城市才能使其旅行线路最 短? 为了说明基本蚁群算法的实现原理，以典型的旅行商问题t s p 为例，建立其模 6 型如下： 设多个城市集合c ； c 。，c 2 , - - , c 。) ，城市之间连线的集合l = 1 。i c i ，c jc c ， 在这里我们把连线抽象为边，城市之间的距离为d i i ( i ，j - 1 ，2 ，n ) ，即 b i ( t ) 表示t 时刻位于元素i 的蚂蚁数目，吒( t ) 为t 时 s j i 备径( ij ) 上的信息量，t s p 规模为n ，蚁群中蚂蚁的总数目为m ，贝l jm = b ；( t ) ： i - , - 1 r = 吒( t ) i c i ，c jc c 是t 时刻集合c 中城市两两连接b 上残留信息量的集合。在初 始时刻各条路径上信息量相等。 给出数学模型后，根据基本蚁群算法的实现步骤作出流程图如下： 1 参数初始化。 初始时刻将m 只蚂蚁随机置于n 个城市上，此时，t - 4 ) 和循环次数c = 0 ，循环 最大次数为c m 觚，初始化城市中每条边o 刀的信息素浓度( t ) 为常数c o r l s t ，这 里设初始时刻( o ) 为o 。 2 循环次数坼卜c + l 。 3 蚂蚁的禁忌表索引号k = - i 。 4 蚂蚁个体根据状态转移概率公式计算的概率选择城市，并前进， j c t a b u t ，状态转移概率公式如下： p ：( f ) = ( 2 1 ) 其中，p ：( t ) 表示t 时刻蚂蚁k 由城市f 转移到城市，的状态转移概率，口为信 息启发式因子，为期望启发式因子，a l l o w e d k = c - t a b u k ，a l l o w e d k 表示蚂蚁k 1 下一步允许选择的城市，启发函数，7 ；i i ( t ) ，( t ) = 。 u i j 5 修改禁忌表指针，即选择好下一个城市之后将蚂蚁移动到新的城市，并把该 城市移动到该蚂蚁个体对应的禁忌表中。 6 蚂蚁数目k 卜足+ 1 。 7 若蚂蚁还没做过所有的城市，即k m ，则跳转到第4 步，否则执行第8 步。 7 硕士学位论文 m a s t e r st h e s i s 8 更新每条路径上的信息素浓度。 每只蚂蚁每经过一个城市或者经过所有城市( 也即一个循环结束) 后，更新路 径上的信息素浓度。 t + n 时刻在路径( i j j ) 上的信息量可按如下规则进行调整 r i j ( t + n ) = ( 1 一p ) - r i ( t ) + a r i j ( t ) ( 2 2 ) a r i j ( t ) = 盯k 一( t ) k 矗1 ( 2 3 ) 式中，p 表示信息素挥发因子，那么1 - p 就是信息素残留因子，a f i j ( t ) 表示本 次循环中路径( i j ) 上的信息素增加值，初始时刻吒( o ) = o ，( t ) 表示第k 只蚂蚁 在本次循环中留在路径( i j ) 上的信息素浓度。 根据信息素更新策略的不同，d o r i g om 提出t - - 种不同的基本蚁群算法模型， 分别称之为a n t c y c l e 模型、a n t - q u a n t i t y 模型、a n t - d e n s i t y 模型，其差别在于a 碚( t ) 的求法不同。 在a n t - c y c l e 模型中 州t ) - 净若第k 只蚂蚁在本次循种经过( i ，j ) ( 2 - 4 ) 【0 ， 否则 式中，q 表示信息素强度，它在一定程度上影响算法的收敛速度：l 。表示第k 只蚂蚁在本次循环中所走路径的总长度。 在a n t q u a n t i t y 模型中 州t ) ：傺若第k 只蚂蚁在t 和t + 1 中经过( i ，j ) ( 2 - 5 ) 【0 ， 否则 在a n t - d e n s i t y 模型中 喇= 善一瓤煦蚁在咖+ 1 畅烈 ( 2 - 6 ) 在公式( 2 5 ) ，公式( 2 6 ) 中蚂蚁没每走完一步后更新路径上的信息素，我们把这 种方式称为局部信息素更新；而公式( 2 - 4 ) q b 蚂蚁是在循环一周后更新所走过路径上 的所有边的信息素浓度，这种方式称为全局更新，通常采用公式( 2 - 4 ) 作为蚁群算法 的基本模型。 9 若满足结束条件，即如果循环次数c c 一，则循环结束并输出程序计算 硕士学位论文 m a s t e r st h e s i $ 结果，否则清空禁忌表并跳转到第2 步。 根据基本遗传算法的实现步骤，可以其对应的流程图如下： 图2 2 基本蚁群算法的程序流程图 2 1 4 基本蚁群算法特点 从自然界中蚁群行为的描述中，归纳出基本蚁群算法的特点如下： 1 基本蚁群算法具有较强的发现近似最优解的能力。 基本蚁群算法不仅具有正反馈特性还隐含着负反馈机制，正反馈特性使得蚂蚁 选择信息素浓度强的路径的概率越来越大，搜索的范围越来越小，最终促进问题朝 最优解的方向发展。算法隐含的负反馈机制使得算法具有一定随机性能将搜索的范 围保持在一个合适的范围，这样有利于全局寻优。换句话说，基本蚁群算法就是在 这种探索和利用之间找到一个平衡点，从而求出问题的近似最优解。 2 基本蚁群算法具有很强的并行性，健壮性和鲁棒性。 基本蚁群算法是从蚂蚁觅食行为中抽象出来的，每只蚂蚁在问题空间的多个点 同时相互独立的构造问题解。因此，基本蚁群算法隐含着并行性。即使某只蚂蚁构 造问题解失败，整个问题的求解也不会受到丝毫影响，基本蚁群算法具有健壮性和 鲁棒性的特点。 9 硕士学位论文 m a s t e r st h e s i s 3 基本蚁群算法具有自组织性。 自组织性是相对他组织性而言的，基本蚁群算法在没有外界的作用也可以实现 从无序到有序的过程，我们即使没有对问题的所有问题有个很清楚的认识也可将该 算法应用于问题的求解中。 2 2 基本遗传算法基本原理 基本遗传算法( g e n e t i c a l g o r i t h m ) 的思想来自于英国博物学家，进化论的奠 基人达尔文的自然选择学说和遗传学的交叉和突变等机理的生物进化过程。自 然选择的过程实质是“适者生存，不适者淘汰一的过程。 2 2 1 自然界中生物自然进化行为 生物必须通过与无机环境斗争，种间斗争和种内斗争等三个方面的斗争才能生 存下来。适应能力强的个体不仅保存实力，同时通过变异作相应调整能够存活下来， 并把优秀基因遗传给下一代个体；适应能力差的个体变异能力不强，存活概率可能 性较小，后代相应也会比较少，这就是人们所说的自然选择，它其实就是一个“物 竞天择，适者生存”的过程。在这个过程中，体现了遗传学的遗传和变异等操作。 通过遗传保持了物种的相对稳定性，通过变异使物种具有了一些新的特征，甚至能 够形成一种新物种1 1 2 j 。 2 2 2 基本遗传算法的逻辑结构 遗传算法的基本思想来源于生物学进化论，作为一种随机算法，遗传算法在问 题可能存在的解空间产生一个初始种群，种群中的每个个体都是问题的一个解，人 们通常称它为染色体，染色体以适应值为依据通过交叉，变异和选择等操作产生一 代新的染色体，迭代一定代数后，算法收敛于最优染色体，从而可以求出问题的最 优解。因此，在确定研究方案后，将问题表达成一种规范的形式，抽象出问题的目 标函数及对应的适应度量，控制好算法的参数和变量，最后明确停止运行的准则。 用逻辑结构流程图2 3 表示如下： 1 0 硕士学位论文 m a s t e r st h e s i s 图2 3 基本遗传算法逻辑结构流程图 2 2 3 基本遗传算法特点 遗传算法是一种基于自然界生物进化的方法和特征发展起来的方法，具有随机 性，鲁棒性，全局优化以及易于与其它算法融合等特征【l3 1 。 1 遗传算法具有自组织，自适应性和自学习等智能型。 遗传算法根据目标函数度量个体对环境的适应程度，遗传算法的精髓在于对群 体进行简单的选择，交叉和变异作用。其中自然选择策略体现了适者生存，优胜劣 汰的进化思想。该策略使得遗传算法能够根据环境的变化感知当前环境的特征和规 律。 2 遗传算法具有多点概率搜索能力，使算法具有良好的全局寻优能力。 遗传算法从问题解空间的不同区域中的多个点以某种概率随机搜索，处理，评 硕士学位论文 m a s t e r st h e s i s 估，最后并行地爬到问题解的最高峰。该特征使得该算法不会陷于局部最优，具有 很好的全局寻优的能力。 3 遗传算法具有潜在的并行性。 遗传算法的潜在并行性是遗传算法优于其它算法的最主要的因素。这里的并行 性可以理解为内在并行性或者内含并行性。内在并行性是指遗传算法在分布式环境 下可以做并行处理：内含并行性是指遗传算法可以从问题解空间中不同区域中多个 点开始搜索，获取问题近似最优解。 2 3 本章小结 这部分详细介绍了蚁群算法和遗传算法实现的基本原理及各自的特点，为下 一部分的进行奠定理论基础。仿生优化算法之一蚁群算法在组合优化问题中展现出 强大的生命力并成为解决组合优化问题的强有力工具。 目前，已经有相当多的学者将模拟蚂蚁群体觅食行为的蚁群算法应用于涉及到 组合优化问题的相关领域【1 3 , 1 4 , 1 5 ，如有许多学者将蚁群算法应用于网格的任务调度， 但这些算法很少注意到蚁群算法的参数组合对蚁群算法性能的重要影响 1 6 , 17 ，墙】。鉴 于这种情况，本文提出蚁群遗传算法a c a g a ( a n tc o l o n ya l g o r i t h mg e n e t i ca l g o r i t h m ) 并应用于网格任务调度，旨在提高蚁群算法性能，从而提高网格环境下任务调度的 效率，提高网格吞吐量和用户的满意度，为网格的广泛推广和应用发挥一定作用。 硕士学位论文 m a s t e r st h e s i s 3 基于a c a g a 的网格任务调度策略 3 1 a c a g a 于苗：述 蚁群算法在解决组合优化问题中展现出强大的生命力和美好的应用前景。蚁群 算法一方面希望探索的范围尽量大，从而能够探索到可能存在问题最优解的解空 间：另一方面，它又希望充分利用自己所拥有的资源即信息素缩短寻优时间。蚂蚁 个体之间通过信息素进行交互和协作，通过信息素不断强化蚂蚁个体的行为方向， 使蚂蚁群体完成一个从无序到有序的过程。蚂蚁群体的这种行为就是人们常说的正 反馈自催化行为，从而发现问题的最优解。因此，蚁群算法研究的关键问题之一， 便是在“探索( e x p l o r a t i o n ) 一和“利用( e x p l o i t a t i o n ) 之间建立一个平衡点【1 9 1 。 在“探索一和“利用一中，蚁群算法用到了概率搜索技术以及信息素浓度更新 技术。从前文的介绍中我们可以看到问题解的构建及求解所涉及的技术离不开参数 的设置。大量的研究表明，信息启发式因子a ，期望启发式因，信息素强度q ， 信息素挥发系数p 等参数的设置对蚊群算法的性能有着相当重要的影响 2 0 2 1 捌。 3 1 1 蚊群算法中参数设置的重要性与盲目性 在蚁群算法中，信息启发式因子g 表示蚂蚁曾经走过的路线对算法的重要程度， 反映了蚂蚁在行走的过程中所累积的信息素浓度对算法的影响程度，其值越大，说 明该蚂蚁越倾向于选择其它蚂蚁走过的路线，蚂蚁之间的协作性越强，但如果其值 过大，就会使算法搜索过早收敛于局部最优解；期望启发式因口表示能见度的相对 重要程度，反映了蚂蚁在行走过程中启发式信息在指导蚂蚁群体搜索过程中的受重 视程度，其值越大，- 贝i j 该状态转移概率越接近于贪心规则，易于限于局部最优；信 息素挥发因子p 是指信息量隔一段时间便会按照一定的比例消失一部分，主要是为 了防止信息素浓度无限扩大，信息素浓度挥发有利于给算法自我创造机会扩大搜索 范围，有利于算法全局寻优，p 的取值范围为：pcr 0 。l i ：信息素浓度q ，为蚂蚁 行走完所有路线时释放在所经途径上的信息素总量，信息素强度q 越大，在蚂蚁所 经过路线上的信息素的积累加快，这方式可以提升蚁群算法搜索最优解时的正反馈 性能，有利于算法收敛。 信息启发式因子a ，期望启发式因，信息素强度q ，信息素挥发系数p 等参 数是紧密耦合的，由于信息素强度q 对算法性能的影响依赖于信息启发式因子口、 期望启发式因卢、信息素强度q 这三个参数的配置以及对算法模型a n t q u a n t i t y 、 硕士学位论文 m a s t e r st h e s i s a n t - q u a n t i t y 、a n t - d e n s i t y 的选取。因此。信息启发式因子口，期望启发式因， 信息素挥发系数p ，信息素强度q 这组参数配置不当，会导致求解效率低且求解 质量特别差。因此，信息启发式因子a ，期望启发式因口，信息素挥发系数p 这三 个关键参数的最佳组合配置策略对蚁群算法的性能有着非常重要的意义。 虽然目前有相当多的学者将仿生优化算法之一的蚁群算法应用于网格的任务 调度中，但是他们均没有考虑到蚁群算法的收敛性能对初始化参数的设置比较敏 感，主要通过循环设置参数，然后将每组参数配置给蚁群算法，通过分析算法运行 的时间和结果，对该组参数是否优异进行判断，或者对蚁群算法中的3 个参数信息 启发式因子口，期望启发式因，信息素挥发系数p ，信息素强度q 在经验值的范 围内随意拼凑取值，无论哪种方式对蚁群算法的计算效率和收敛性都产生了非常不 利的影响。 3 1 2 利用逮传算法对蚁群算法中的参数进行进化 上一部分介绍了遗传算法基本思想以及特点，从中我们可以了解到遗传算法作 为仿生化算法之一，具有鲁棒性强，并行性，智能化等特点，更为重要的是其可扩 展性强，易于与其他技术结合。许多研究结果表明，采用混合模型可有效提高遗传 算法的局部搜索能力，从而进一步改善收敛速度和解的质量。 本文将遗传算法应用于蚁群算法中，形成蚁群遗传算法a c a g a ，利用遗传算 法快速随机的全局搜索能力，探索蚁群算法中四个参数口，罗，p ，q 的优化组合， 实现网格环境中更加合理的任务调度，具体的实现方法将陆续详细介绍。 3 2 条件定义 网格作为下一代i n t e m e t 应用技术，实现了科学计算中的高性能计算和分布式 计算等技术后，以满足大众需求为目的，试图实现互联网上计算资源，存储资源， 通信资源，软件资源，信息资源和知识资源等所有资源的全面连通。当用户向资源 管理系统提交任务后，由资源管理系统统一分配资源并在资源节点执行用户提交的 任务。一般而言，任务之间要么是相互独立的，没有任何关系，更不存在通信了： 要么是有相互依赖关系的，任务之间存在一定的交互和通信，有一定制约关系。 本文认为后面的情况是前面的情况中的特殊情况，后面的那种情况更能反映网 格环境下任务调度的特征。针对这个特点，本文在假设各任务之间相互约束且约束 关系已知的情况下，研究网格环境下的任务调度问题。 3 3 a c a g a 实现 1 4 硕士学位论文 m a s t e r st i - i e s i s 蚁群算法，遗传算法和微粒子算法等仿生优化算法是解决诸如t s p 问题，j s s p 问题，g c p 问题等组合优化问题的强有力工具，而网格计算中的任务调度问题本质 上组合优化问题，也是一个n p 难问题，它把任务调度给网格资源的多种组合中选 择性价比最高的一种组合。从问题解决的角度讲蚁群算法非常适合于解决任务调度 问题。鉴于蚁群算法中参数的设置对算法的性能的重要影响以及遗传算法具有搜索 寻优，易于与其他技术相结合的特点，本文将两者结合起来，形成a c a g a 。 3 3 1 a c a g a 的基本思想 a c a g a 的基本思想是使两种算法相互配合，取长补短，从而求得网格任务调 度问题的最优解。 本文利用遗传算法对蚁群算法所需要的初始参数进行交叉变异，探索蚁群算法 参数组合较优解，解决蚁群算法对初始化参数设置的敏感问题首先对蚁群算法的参 数组合进行随机编码，产生的群体即为染色体，利用蚁群算法的鲁棒性，潜在并行 性，正反馈机制等优点，得到一组较优解，再利用遗传算法的快速性，随机性，随 机并行性对该组值进行交叉，变异，选择产生更好解，把该组值作为蚁群算法下一 次探索的初始值，循环直至达到遗传算法的最大迭代次数或满足停止规则，求得参 数组合近似最优解。 3 3 2 初始定义及假设条件 在网格计算环境中，网格资源的处理能力和通讯能力随时调整变动。在每个任 务调度周期开始时，资源管理系统必须监视资源节点的增加、退出以及已有资源节 点处理能力和通信能力的变化等相关信息。 当新的资源节点加入网格中时，需要提供该资源的处理能力，存储能力和通信 能力等相关资料，这些初始信息构成形成蚁群算法中的信息素。 当网格资源节点由于发生故障而不能正常工作或者退出网格环境时，我们将资 源的状态修改为停用标志。 当网格资源节点恢复使用，重新加入网格环境中时，我们将网格资源的状态更 改为启用标志。 与此同时，根据上一任务调度周期任务返回的完成情况，我们对完成任务的 资源予以奖励，而对在有限的时间内尚为完成或者失败返回的任务所对应资源予 以惩罚，动态更新资源信息素浓度，从而改变任务分配资源的方式，使得执行时 间更小。 由此，我们可以做如下假设： 一个大型应用任务被分解成若干个具有某种约束关系的多个子任务。其一般性 定义如下： 定义l n 个子任务的集合t = 石，互，互 ，霉为第i 个子任务。 定义2 r r l 个资源节点的集合r = 玛，足，疋 ，足为第i 个资源。资源节点 的处理能力与通信能力构成蚁群算法的信息素t i ( t ) 。初始信息素i ( o ) 由公式 气( o ) = m p i + c s i 计算出来。其中m 表示主机资源处理机个数，p i 表示计算机的 处理能力，c 表示参数包的大小，s ；表示传输参数包所用的时间，c ，s ；表示通信带宽， 吒( o ) 表示了资源的固有处理能力。 定义3 一个n m 的执行时间矩阵e 【n ，1 3 1 1 】。元素科i ，j 】表示第i 个子任务 在第j 个资源上运行的执行时间。 定义4 初始状态时蚂蚁随机分布在网格计算节点上。根据状态转移公式( 1 ) 计 算在t 时刻第k 只蚂蚁在资源i 的状态转移概率p ：( t ) 。 ，、l ；而量唾拿蝇j ，u 在线资源u p = ( f i u ( t ) 。 ( t ) ，) 4 。( 3 - 1 ) l c o l - 0 ，其他 其中：口为信息启发式因子，夕为期望启发式因，r i j ( t ) 表示t 时刻第k 只蚂蚁 选择在资源i 选择的资源j 上的信息素浓度，表示第k 只蚂蚁在资源i 选择的资 源j 上的计算能力，存储能力和通信能力等固有属性，砺( t ) = ( o ) ； 定义5 在a c a g a 中，我们采用局部信息素更新与全局信息素更新相结合的 方法。在蚂蚁算法中完成一次循环后，对完成任务的资源节点，我们予以奖励，信 息素浓度增加l ，设奖励因子为g ，k 为系数，则 厶毛=cexk(3-2) 对于未完成任务的资源节点，我们予以惩罚，信息素浓度减少q ，设惩罚因 子为c p ，则 = c p x k ( 3 3 ) 对于完成任务总执行时间最短的蚂蚁在其经过的资源节点上均予以信息素更 新r ；( t ) ，即全局信息素更新，更新方式为： 1 6 硕士学位论文 m a s t e r st h e s i s 州：慝若第识蚂蚁经过资源节桶 ( 3 4 ) 。 【0 ， 否则 其中q 表示信息素强度，其值越大，越倾向于选择相应的资源节点：五表示第 k 只蚂蚁在本次循环中所用总的完成时间。 综上，信息素更新方式为：矿- 0 - p ) 吒瑚+ a r j ( 3 5 ) 3 3 j 周格i - i - j m l 环境中a c a g a 的设计 根据a c a g a 的基本思想及假设，a c a g a 描述如下： 1 编码，创建初始群体。 j 由于需要通过遗传算法获取蚁群算法中的参数组合，因此在建立网格平台之前 先进行编码并产生蚂蚁群体。 遗传算法的个体编码方案在很大程度上依赖于问题的性质和遗传算子的设计。 一般而言，编码方案分为四种：位串编码- - 进制编码，实数编码，有序串编码和结构式 编码。二进制编码类似于生物染色体的组成，比较容易使用生物遗传理论来解释并 进行交叉，变异等遗传操作，它将问题的解空间映射到位串空间，然后在位串空间 上进行遗传操作，得到的结果再通过解码过程还原为表现型以进行适应值评估。 本文采用二进制编码方案，在a c a g a 中，对参加进化的四个参数a ，声，p ， q 进行随机编码，产生由四个个体组成的群体；每个参数编码成7 位，则染色体长 度为2 8 位。一个个体便对应着蚁群算法中四个参数。在这里四个参数a ，p ，p ，q 的取值范围定为：o 口5 ；0 p 5 ；0 1 p 0 9 9 ；1 0 _ q 1 0 0 0 0 。 2 搭建网格平台，注册资源节点。 初始化网格资源节点上的所有信息素，赋初值为r i ( 0 ) = m p ；+ 以；，当有新的 资源加入时，新的资源节点应该注册，成为网格资源的一部分，注册时需要提供构 成这个资源的计算能力，存储能力等基本信息作为初始信息素。将m 只蚂蚁随机分 布在网格资源节点上，每只蚂蚁负责完成一组任务。 3 为每只蚂蚁建立禁忌表索引号。 将第k 只蚂蚁所处资源节点号放入禁忌表t a b u k ( s ) ，记录执行任务的资源节点， 每只蚂蚁根据状态转移概率公式选择执行下一个任务的资源节点，