（计算机软件与理论专业论文）基于混合蛙跳算法的网格任务调度研究.pdf

基于混合蛙跳算法的网格任务调度研究 存储分别使用d a g 图和依赖矩阵。本文在元任务调度算法s f l a p s 的基础上，提 出了可用于依赖任务调度的r s s f l a p s 算法，分析了算法的思想和将依赖任务转 化为元任务的方法，给出了编码解码方式和实现流程，然后用g r i d s i m 仿真并在 解质量和资源利用率上和r s - m i n m i n 算法作了比较，以说明它的合理性和有效 性。 关键词：网格；任务调度；混合蛙跳算法；g r i d s i m ；调度跨度 i i s h u f f l e df r o gl e a p i n ga l g o r i t h m ( s f l a ) i sam o d e mh e u r i s t i c sa l g o r i t h mw h i c hi s u s e df o ro p t i m i z a t i o np r o b l e m ，d e v e l o p e di nt h ep a s ts e v e ny e a r s t h i st h e s i sf i r s t l y i n t r o d u c et h ec o n c e p t sa n df e a t u r e so fg r i da n dg r i dt a s ks c h e d u l i n g ，t h e na p p l ys f l a c r e a t i v e l yt os o l v i n gt h ep r o b l e mo fg r i dt a s ks c h e d u l i n g ，w h i c hi sd i v i d e di n t om e t a t a s k ss c h e d u l i n ga n dd e p e n d e n tt a s k ss c h e d u l i n gh e r e ，w ew i l ld i s c u s st w os c e n a r i o s r e s p e c t i v e l y f o rm e t at a s k ss c h e d u l i n g ，c o n s i d e r i n gt h ee s s e n c eo fg r i dt a s ks c h e d u l i n g ，a n a l g o r i t h mc a l l e ds f l a p si sa d d r e s s e d ，i tm a k e ss o m ei m p r o v e m e n t so nt h eb a s i so f s f l a ：i n i t i a lp o p u l a t i o ni sg e n e r a t e dc o m b i n i n gm i n - m i na l g o r i t h mt oe n s u r eq u a l i t y ； l o c a ls e a r c hm e c h a n i s m sb a s e do nd i s c r e t ee x p r e s s i o na n dp r o b a b i l i t ys e l e c t i o na r e i i i 基于混合蛙跳算法的网格任务调度研究 p r e s e n t e dt os u i ts c h e d u l i n gp r o b l e m ；t h ec o n c e p to fs u b m e m e p l e xi s i n t r o d u c e dt o t u n el o c a ls e a r c hm e c h a n i s mi no r d e rt oa v o i dp r e m a t u r ec o n v e r g e n c e w ed e s i g na l l t h ec o m p o n e n t so fs f l a p si nd e t a i l ，a n di m p l e m e n tt h ea l g o r i t h mw i t hg r i d s i m s i m u l a t o r t h r o u g hal a r g en u m b e ro fe x p e r i m e n t s ，w ep r o v i d eag u i d a n c et os e l e c t p r o p e rv a l u e sf o rt h ep a r a m e t e r s ，t h e nm a k e ac o m p a r a t i v ea n a l y s i sw i t hm i n - m i na n d g e n e t i ca l g o r i t h mi np e r f o r m a n c e t h er e s u l t ss h o wt h a ts f l a p sh a sa d v a n t a g e si n t e r m so fs o l u t i o nq u a l i t y , s t a b i l i t ya n dc o n v e r g e n c es p e e d f o rd e p e n d e n tt a s k ss c h e d u l i n g ，t h ei s s u ei sd e s c r i b e df i r s t l y , w ed e c i d e st h a t t a s k sa n dt h e i rr e l a t i o n s h i p sa r ed e n o t e db yd a g g r a p h ，s t o r e db yd e p e n d e n c ym a t r i x b a s e do ns f l a p sf o rm e t at a s k ss c h e d u l i n g a na l g o r i t h mc a l l e dr s s f l a p sw h i c h c a nb ea p p l i e dt od e p e n d e n tt a s k ss c h e d u l i n gi sa d d r e s s e d t h et h e s i ss u m m a r i z e si d e a o ft h ea l g o r i t h m ，d i s c u s s e st h et e c h n i q u et r a n s l a t i n gd e p e n d e n tt a s k si n t om e t at a s k s ， a n dp r e s e n t st h e p r o c e s so fe n c o d i n g a n di m p l e m e n t a t i o n t h e nw ec o m p a r e r s s f l a p sw i t hr s - m i n m i ni nt e r m so fs o l u t i o nq u a l i t ya n dr e s o u r c eu t i l i z a t i o nb y g r i d s i ms i m u l a t i o n ，t h er e s u l t ss h o wr a t i o n a l i t ya n de f f e c t i v e n e s so ft h ea l g o r i t h m p r e s e n t e d k e yw o r d s ：g r i d ；t a s k s c h e d u l i n g ；s h u f f l e df r o gl e a p i n ga l g o r i t h m ；g r i d s i m ； m a k e s p a n i v 华南师范大学硕士学位论文 目录 摘要 a b s t r a c t 目录 第一章绪论 1 1 研究背景和意义。 1 2 网格计算中的任务调度问题 1 2 1 网格任务调度的定义及模型 1 2 2 网格任务调度的特点 1 2 3 网格任务调度评价标准 1 3 国内外研究现状 1 4 论文的主要研究内容和创新之处 1 5 论文的组织结构1 0 第二章混合蛙跳算法l2 2 1 混合蛙跳算法的产生背景1 2 2 1 1 模冈算法( m e m e t i ca l g o r i t h m s ，m a ) 。1 2 2 1 2 微粒群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 1 3 2 2 混合蛙跳算法的基本原理1 5 2 3 混合蛙跳算法的实现过程l6 2 4 混合蛙跳算法的特点及研究现状1 9 2 5 本辛小结2 l 第三章基于改进混合蚌跳算法的元任务调度一2 2 3 1 元任务调度的问题描述2 2 3 2 元任务调度问题的编码解码2 3 3 3 初始种群的生成和适应度函数2 5 3 4 局部更新策略2 6 3 4 1 离散化的局部更新机制2 6 3 4 2 基于概率选择的局部更新机制2 7 3 4 3 局部更新机制的优化：构造子模因群2 9 3 5 全局搜索和停i 卜准则3 l 3 6 基于改进混合蛙跳算法的元任务调度实现框架3l 3 7 仿真实验及结果分析3 5 3 7 1g r i d s i m 网格模拟器介绍3 5 3 7 2 局部更新策略的选择3 7 3 7 3 算法参数调优3 9 3 7 4 元任务调度的实验及比较分析4 3 3 8 本章小结4 5 第四章基于混合蛙跳算法的依赖任务调度4 6 4 1 依赖任务调度的问题描述4 6 4 2 混合蛙跳算法在依赖任务调度中的应用4 7 4 2 1 求任务的深度值4 7 v 基丁：混合蛙跳算法的网格任务调度研究 4 2 2 依赖调度问题的编码解码4 9 4 3 基于混合蛙跳算法的依赖任务调度算法实现框架5 0 4 4 仿真实验及结果分析5 3 4 5 本章小结5 5 第五章总结与展望5 6 参考文献5 7 攻读硕士学位期间发表的学术论文。6 2 至i 谢6 3 v i 华南师范大学硕士学位论文 1 1 研究背景和意义 第一章绪论 随着网络化和智能化的发展，整合互联网上的各类资源、实现资源共享和协 同工作已经成为越来越重要的发展趋势，网格技术被认为是实现这个目标的基础 网络支撑技术。网格是一个集成的计算与资源环境，或者说是一个计算资源池。 网格计算研究的先导i a nf o s t e r 对网格的定义是：网格计算是指在动态的、多 机构的虚拟组织中，灵活安全地协同资源共享和解决问题的过程n 副。当前的 i n t e r n e t 技术实现了计算机硬件的连通，w e b 技术实现了信息的共享，而网格技 术的日的是把i n t e r n e t 上分布的资源集成为一台巨大的超级计算机，提供各种 资源的全面共享哺1 。 在网格计算中，任务管理、任务调度和资源管理是网格必须具备的三个基本 功能。用户通过任务管理系统为任务指定所需资源，向网格提交任务、删除任务 并监测任务的运行状态。用户提交的任务由任务调度系统按照任务的类型、所需 资源、可用资源等情况安排运行日程和策略。而资源管理系统监测网格资源状况， 收集任务运行时的资源占用数据等。三者相互关联、相互影响。 建设网格的一个主要目的是协同解决科学计算i 、u j 题，在如此大规模、异构的 分布式计算环境中进行高效率的科学计算，这使得任务调度成为网格必须解决的 关键技术。用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再 按照某种策略把这些任务分配给合适的资源。高效的调度算法可以充分利用网格 系统的处理能力，从而提高整个网格系统的吞叶量。由于网格计算任务调度面临 的是一个n p 完全问题，它引起了众多学者的关注，成为目前网格计算研究领 域的一个焦点嵋1 。 调度问题一般可分为两人步：第一。步是在空间上对计算和数据进行分配，包 括选取给定任务所需要的资源组，将任务交给这些资源去执行，并分配相关的数 据和计算等；第二步就是在时间上和空间上为计算和通信进行排序，包括在计算 资源上为不同的任务进行排序，同时为不同任务之间的通信进行排序。任务调度 的目的是在异构的计算环境中，同时考虑各网格结点的计算性能、网格结点之间 基于混合蛙跳算法的网格任务调度研究 的通讯性能等参数，最优地分配任务，实现最佳的调度策略，从而充分利用网格 资源，高效地完成计算任务。 任务调度是并行分布式计算中的一个重要组成部分，在传统的并行和分布式 调度问题中，所涉及的计算资源是同构的，因此不必关心资源所具有的属性以及 资源能否满足用户所提交的任务的需要，而且，计算资源通常在地理上是集中的， 因此不用关心系统在运行过程中通信所花费的开销晦1 。而随着网格的出现，其资 源的广域分布、自主管理、本质上异构、负载动态变化等特性，使得网格环境下 的任务调度比传统分布式环境要复杂得多。传统的并行计算调度算法主要是调度 一个应用程序的子任务到并行的计算机，主要目的是减少计算时间；而对于网格 环境，调度算法关心的主要问题是调度来自不同用户的应用流到可用的计算资源 上，从而最大限度地让网格系统得到最大的使用，它追求的是调度的高吞吐率。 然而现有的一些调度算法如b a c k f i l l i n g ，f c f s ( f i r s tc o m ef i r s ts e r v e ) 等并 不能很好的适应网格资源的特性。因此，设计一种网格环境下高效的任务调度算 法对提高网格资源利用率以及网格系统的吞吐量有十分重要的意义。 1 2 网格计算中的任务调度问题 1 2 1 网格任务调度的定义及模型 网格环境下的任务调度是通过查询网格资源信息服务得到资源的性能参数 及状态，生成满足任务需求的可用资源集，然后通过匹配得到完成任务的优化资 源组合，并将任务调度到资源上运行的过程。图1 - 1 给出了在网格环境下的应用 程序调度的一般模型【7 1 。 ( 1 ) 应用程序分析 分析应用程序的类型和类度。网格计算中将应用主要分为二种类型：计算密 集型、通信密集型和计算通信相对均衡型。类度分析用于确定程序中并行化任务 的特点和数目。分析结果将会记录在应用特性描述表中。 ( 2 ) 资源特性分析 该模块首先获取网格中资源的c p u 体系结构，操作系统等静态信息，再调用 资源监测模块来监测各种资源的可用性及动态特性，如可用内存大小，负载状态， 2 ( 6 ) 任务调度 任务调度是根据任务映射的结果，将各个子任务发送到指定机器等待执行或 执行，是一个动态的过程。任务映射和任务调度模块统称为任务调度器。 本论文中所研究的任务调度算法是指调度器已经获得应用程序和资源的特 性，并对应用程序分解和选择了合适的资源子集的基础上，实现任务映射与任务 调度两个过程的算法。 基于混合蛙跳算法的网格任务调度研究 1 2 2 网格任务调度的特点 网格是分布式计算系统的一种，但是网格环境下的任务调度除了具有一般分 布式任务调度的共同性质外，还有以下的一些特点陋1 ： ( 1 ) 任务调度是面向异构平台的。由于网格系统是由地理上分布的各类资源 组成的，包括各类主机、工作站甚至p c 机，也可能是上述机型的机群系统、大 型存储设备、数据库或者其他设备，它们有不同的c p u 体系结构，可运行在u n i x 、 l i n u x 、w i n d o w s 等各种操作系统下，因此网格系统中的任务调度必须面向异构 平台。 ( 2 ) 任务调度是大规模的、非集中式的。由于网格系统的资源跨越多个管理 域且规模庞大，要实现一种全局的统一集中的任务调度管理根本是不可能的。因 此，网格中的任务调度必须以分布、并行方式进行管理与调度。 ( 3 ) 任务调度不干涉网格节点内部的调度策略。在网格系统中，各网格节点 的内部调度策略是自治的，网格任务调度系统干预其内部的调度策略是不可能也 是没有必要的。 ( 4 ) 任务调度能够动态自适应。在网格中资源是异构的而且网格的结构总是 不停地改变：有的新资源要加入到网格中，有的资源出现故障，有的资源重新开 始工作等，这就要求网格任务调度能适应该环境的动态性变化。 ( 5 ) 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着超级 计算机系统等相关节点的不断加入，系统的计算规模也必将随之扩大。因此，网 格系统的任务调度必须具有可扩展性，以适应网格资源规模的不断扩大和应用的 不断增长，而不致降低网格系统的性能。 1 2 3 网格任务调度评价标准 网格计算任务调度的总体目标就是要对用户提交的任务实现最优调度，并设 法提高网格系统的总体吞吐率。具体的目标包括：最优跨度( o p t i m a lm a k e s p a n ) 、 负载均衡( l o a db a l a n c i n g ) 、服务质量o o s ( q u a l i t yo fs e r v i c e ) 、经济原则 ( e c o n o m i cp r i n c i p l e s ) 等引。 ( 1 ) 最优跨度 4 华南师范大学硕士学位论文 跨度是一个最重要、最常见的目标，它指调度的长度，也就是从第一个任务 开始运行到最后一个任务运行完毕所经历的时间。用户总是希望网格系统尽快完 成自己的任务，所以跨度越短，说明调度策略越好，同时可以产生更大的系统吞 吐量。可见实现最优跨度是用户和网格系统的共同目标。 ( 2 ) 负载均衡 在开发分布或并行计算应用时，保证负载均衡是一个关键问题。网格规模庞 大，且涉及到多个虚拟组织，更进一步扩展了这个问题。只有达到系统的负载均 衡才能充分地共享利用各种资源。 ( 3 ) 服务质量q o s 在为网格提交任务时，不同的用户或应用对资源会有不同的q o s 要求。在任 务被映射和调度的过程中，任务调度器必须能够使其满足相应的q o s 约束，这样 的调度才有实际意义。 ( 4 ) 经济原则 ” 各种网格资源是在地理上广泛分布的，它们可能属于不同的虚拟组织拥有， 有自己的资源管理策略。按照市场经济理论，不同资源的使用费用应该是不相同 的。市场经济驱动的任务调度必须使资源使用者和资源拥有者双方互惠互利，才 能使网格系统长久地发展下去。 以上目标有时是相互矛盾的，在某个目标最优的同时可能会造成其它目标的 损失，同时使这些目标最优化几乎是不可能的，所以为了使研究简化，一般只考 虑一个目标或者以一个目标为主，兼顾其它。当前的研究大部分只考虑最优调度， 本文中的调度算法也是一样。 1 3 国内外研究现状 国内外许多学者对网格任务调度做了大量的研究工作，到目前为止，人们提 出了很多网格系统的调度技术和算法。 现有的任务调度算法可分为静态调度和动态调度两人类饽1 ，静态调度算法是 指所有的任务一机器映射策略在执行任务调度前己经全部确定：动态调度算法是 指一些任务一机器映射策略在执行任务调度期间根据实际情况进行确定。动态调 度算法又分为在线模式( o n li n em o d e ) 和批模式( b a t c hm o d e ) 。在线模式是指任 基于混合蛙跳算法的网格任务调度研究 务一到来就映射到机器，该模式对每一个任务的映射只考虑一次，也就是说一旦 任务被映射就不会再改变。批模式下，任务到来并不立即映射到机器，而是把任 务收集起来组成一个任务集合，等映射事件到来后才对该集合中的任务进行集中 映射。映射事件指任务数量达到一预定值，或达到预定的时间间隔，一般采用前 一种策略。批模式可以得到更多任务的资源需求信息和执行时间，从而做出更合 理的任务映射策略，它既有动态的在线模式的实时性，又有静态算法的高效性。 图1 - 2 给出了调度算法的分类及各类的典型算法。 网格任务调度算法 ( 1 ) 动态调度算法 静态调度 动态调度 遗传算法( g a ) 模拟退火算法( s a ) 蚁群算法( a c o ) 粒子群优化算法( p s o ) 在线模 批模式 i 随机负载均衡算法( o l b ) 斗i 最小执行时间算法( m e t ) 扎l 最小完成时间算法( m c t ) l k p b 算法 f 快速贪吃算法( f a s t g r e e d y ) s u f f e r a g e 算法 m i n m i n 算法 m a x - m i n 算法 图卜2 网格任务调度算法的分类 随机负载均衡( 0 p p o r t u n i s t i cl o a db a l a n c i n g ，0 l b ) 算法从任务队列中 随机选择一个任务，将其分配给下一台就绪的机器，而不考虑任务在该机器的执 行时间。该算法追求的目标是尽量不让每一台机器空闲，实现简单。但可能会把 任务分给执行它时间很长的机器，使整个调度的m a k e s p a n 变长。 最小执行时间( m i n i m u me x e c u t i o nt i m e ，m e t ) 算法把任务分配给执行其 最快的机器，而不考虑机器的就绪时间。该算法的目的是使每个任务的执行花费 最少的时间，这可能让许多任务趋向于分配到性能最好的少数几个机器上，使得 各机器的负载严重不均衡。 最小完成时间( m i n i m u mc o m p l e t i o nt i m e ，m c t ) 算法把任务分配给完成它 最快的机器，它结合了o l b 和i d e t 的优点，但导致一些任务不能被分配到执行其 6 华南师范大学硕士学位论文 最快的机器，从而潜在地增大全部任务的完成时间。 极d , - 极小算法( m i n i m u m - m i n i m u mc o m p l e t i o nt i m e ，m i n - m i n ) 是一个经 典高效的任务调度算法。m i n m i n 算法的过程是先根据预测完成时间矩阵c 1 i ，算 出每个任务的最小预测完成时间及对应的机器，再在所有任务的最小预测完成时 间里找出最小值及所对应的任务( 即为最小任务) ，然后将最小任务分配到最早完 成它的机器去运行。映射完成后更新机器就绪时间，并将已分配的任务从任务集 合中删除。如此重复，直到全部任务被分配为止。该算法的目的是尽可能地把大 量任务分配给那些不仅完成时间少，而且执行其速度快的机器，以使全部任务的 完成时间最小。m i n m i n 算法实质上是对m c t 算法的改进，m c t 一次只考虑一个 任务，而m i n m i n 在每次映射时考虑到了全部未映射的任务。m i n - m i n 算法的缺 点是当机器的异构性n 叫较大时，仍然会导致负载不均衡n 。针对m i n m i n 算法的 缺陷，一些基于m i n - m i n 的改进算法已被提出来，如s e g m e n t e dm i n - m i n n2 | ，q o s g u i d e dm i n - m i n 【1 3 】。 极大一极小算法( m a x i m u m - m i n i m u mc o m p l e t i o nt i m e ，m a x - m i n ) 和m i n - m i n 算法非常相似，但是它每次在所有任务的最小预测完成时间罩找出最大值及所对 应的任务( 即为最大任务) ，然后将最大任务分配到最早完成它的机器去运行。 m a x - m i n 算法的目的是让大任务尽早执行，在异构的计算环境中，当短任务比长 任务多很多时，m a x - m i n 算法可能会优于m i n - m i n 算法，也使机器之间的负载较 为均衡盯1 。 ( 2 ) 静态调度算法 a ) 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a 或g a s ) 引是由美国密歇根大学 的j o h nh o l l a n d 教授及其学生于2 0 世纪7 0 年代初提出的。在1 9 7 5 年出版的 ( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s 一书n 朝中，h o l l a n d 系统 地阐述了遗传算法的基本理论和方法。后来d ej o n g 和g o l d b e r g 等人做了大量 的工作n6 1 ，使遗传算法更加完善。 遗传算法是根据自然进化论与遗传变异理论为基础求解全局最优解的仿生 型算法，其本质是一种求解问题的高效并行全局搜索算法。该算法将问题的解表 示成染色体( c h r o m o s o m e ) ，从而构成种群。将它们置于问题的环境中，根据适者 基于混合蛙跳算法的网格任务调度研究 生存的原则，从中选择出适应环境的染色体进行复制，通过交叉( c r o s s o v e r ) 、 变异( m u t a t i o n ) 产生出新一代更适应环境的染色体群，这样一代代地不断进化， 最后收敛到一个最适合环境的个体上，得到问题的最优解。 s h h o u 等人最早将遗传算法应用到多处理机环境中的任务调度问题n7 。，之 后发展迅速，产生了种类繁多的遗传任务调度算法，这些算法大致有如图i - 3 的 分类n 8 1 ： 基于遗传算法的多处理机任务调度 ii l 经典遗传算法扩展遗传算法 ii 动态多处理机任务调度静态多处理机任务调度 li s t g 表示的任务图 d a g 表示的任务图 ii 异构多处理机系统同构多处理机系统 图卜3 基于遗传算法的多处理机调度的研究现状 t r a c yd b r a u n 等人在论文 1 9 中比较了分布式系统的1 1 种静态的启发式任 务调度算法，用实验证明了g a 算法的性能最优。m a r t i n o 将遗传算法引入到网 格计算环境中幢们陋，y a n g g a o 乜引、杨勇提出了自适应的遗传网格任务调度方法。 b ) 蚁群算法 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 心引陀5 1 是意大利学者d o r i g om 等人 在1 9 9 1 年提出的一种模拟蚂蚁群体觅食行为方式的仿生优化算法。当蚂蚁在寻 找食物时，每个走动的蚂蚁都会在其经过的路上分泌一种叫做信息素 ( p h e r o m o n e ) 的化学物质，而且能感知这种物质的存在及其浓度。每条路径上 信息素的数量，会反映出其它蚂蚁选择该路径的概率，蚂蚁趋向于朝着信息素浓 度高的方向移动。在较短路径上的信息素会很快地增加，使得最终所有的蚂蚁将 选择最短的路径。 蚁群算法引入正反馈并行机制，具有较强的鲁棒性、优良的分布式机制、易 于与其他 固有的并 一时间内 简单、快 虽然 要还存在 ( 1 ) 环境的不 ( 2 ) 应用和环 成果很难 ( 3 ) 一些调度技术的结论还只是来自仿真结果，缺乏真实的网格测试环境 来准确验证改进算法的性能收获。不少调度算法还没有完整的理论依据，至今还 没有形成网格计算的任务调度理论。 因此，该领域的研究还亟待进一步发展和完善。具体地说，在网格任务调度 研究方面还要做的工作包括： ( 1 ) 任务调度算法研究的粒度需要进一步细化。目前不少算法研究资源和 任务是粗粒度的，一些调度思想还处于初步的原型阶段，离具体实现还有较大距 离。 ( 2 ) 启发性智能化方法将是网格计算任务调度的一个重要研究领域。目前 启发性任务调度算法的研究还处于模拟仿真阶段，还需要在理论和实践中不断完 善。 ( 3 ) 面向a g e n t 技术将是网格计算及其任务调度的一个重要的软件开发方 法乜引，在该领域同样还有很多工作要做。 网格计算中的任务调度一般形式下是一个n p 问题。由于大量的n p 完全问 题至今还没有找到有效算法，而指数型算法对解决规模较大的问题又十分困难， 以求近似最优解为目的的启发性算法自然就受到了极人的重视旧0 。启发式算法是 基于直观或知识、经验构造的算法，这样构造的算法可以在可接受的计算时间内 寻找较好的解，但不一定能保证解的最优性。也就是说，以降低解的精确性为代 9 基于混合蛙跳算法的网格任务调度研究 价，来换取计算时间的缩短。这就促使人们不断地进行科学研究，设计出比已有 算法计算时间复杂度更低、找到的解更好的算法。近年来，人们提出了很多启发 性智能化算法，诸如遗传算法、蚁群算法、微粒群优化、模拟退火、混合蛙跳算 法等，这类算法具有内在并行性和全局解空间搜索等特点，使它们成为了解决 n p 问题的锐利工具m 1 。 1 4 论文的主要研究内容和创新之处 由于网格技术正成为一个有着巨大实用价值和研究意义的方向，对其任务调 度的研究也成为网格中目前所需研究的热点之一。本文的研究内容是在总结了网 格任务调度的特点和现有算法的基础上，引入了一种较新颖的仿生优化算法 混合蛙跳算法，来解决任务调度的问题。将任务调度分为元任务调度和依赖任务 调度，分别讨论了这两种情况下用混合蛙跳算法调度的改进步骤和流程，并通过 网格仿真工具g r i d s i m 对改进后的算法进行了实验分析和比较，结果表明本文算 法比现有的主要相关算法有更好的性能。本文的创新之处有以下几点： ( 1 ) 首次将混合蛙跳算法应用到网格的任务调度问题中，解决了元任务调 度和依赖任务调度问题，为网格任务调度提出了新的思路。 ( 2 ) 对混合蛙跳算法的局部更新策略作了较大改进，提出了离散化的局部 更新机制和基于概率选择的局部更新机制，并通过构造子模因群对更新策略进行 了优化。 ( 3 ) 通过大量的实验来对提出的改进策略进行选择和证明，找出适合于网 格任务调度问题的算法参数指导范围，并和现有的较优调度算法进行了比较分 析。 1 5 论文的组织结构 第一章为绪论，介绍本文的研究背景及意义、网格任务调度问题描述、研 究现状和研究内容，并给出论文的组织结构。 第二章介绍了经典混合蛙跳算法的基本原理和研究现状，详细阐述了算法 的具体步骤和实现过程，指出其优缺点。 第三章对混合蛙跳算法做了改进，并将改进后的算法应用在网格的元任务 l o 华南师范大学硕士学位论文 调度中，通过实验选择局部更新策略和算法参数，并和g a 和m i n - m i n 算法作了 性能比较。 第四章介绍了依赖任务调度的模型，在前一章提出的元任务调度算法 s f l a p s 的基础上，提出了基于混合蛙跳算法的依赖调度算法r s - s f l a p s ，并用实 验对其和基于m i n - m i n 的r s - m i n m i n 算法做了比较分析。 第五章对全文做了总结，并对未来的研究工作进行展望。 基于混合蛙跳算法的网格任务调度研究 第二章混合蛙跳算法 2 1 混合蛙跳算法的产生背景 大自然的很多生物现象和行为蕴含着有趣而又很有意义的规律，有些生物群 体通过相互协作产生复杂智能行为的现象尤其引起了科学家们的注意。社会学家 w i i s o n 在他的书中是这样描述鱼群活动的2 f ：“至少从理论上说，在搜索食物的 过程中，鱼群中的每个成员个体都能从自己之前的发现和鱼群中其它成员的经验 里获益。这种利益是决定性的，超过了成员间对食物竞争带来的弊端。”这句话 表明在一个群体中实现信息的社会共享有利于群体向好的方向发展进化，此假设 是混合蛙跳算法提出的前提。 混合蛙跳算法结合和扩展了两个应用于连续优化问题的元启发式算法：模因 算法和微粒群算法。作为一个背景，下面我们对这两种算法进行简要的介绍。 2 1 1 模因算法( m e m e t i ca l g o r i t h m s ，m a ) 模因( m e m e ) 一词是新达尔文主义倡导者r i c h a r dd a w k i n s 在他的t h e s e l f i s hg e n e m 1 书中创造的，是指一种会传播的信息模式，它能够在人类或动 物的大脑之间传染，从而改变他们的思想和行为。模因的典型例子有歌曲，妙句， 网络词汇，建筑艺术等。 模因算法借用了m e m e 这一概念，是一种利用启发式搜索来解决优化问题的 群集智能优化方法。它和遗传算法比较相似，但是组成一个问题解的基本元素叫 做m e m e ，而不是g e n e 。问题的一个解决方案被叫做一个模冈型( m e m o t y p e ) ，类 似于遗传算法中的染色体( c h r o m o s o m e ) 。m e m e 和g e n e 的不同之处在于，g e n e 只能在父代和子代之间复制，而m e m e 更灵活，可以在任何两个个体之问传播， 速度比g e n e 复制快得多，并且可被它的吸收者加以改进。 模冈算法可以看作是遗传算法的改进，它在每一代种群进行进化之前，先对 每一个模因型进行局部搜索，以获取一些经验，得到局部较优解，然后才利用繁 殖，交叉，变异等遗传算子对种群运算，所以模因算法有时被称为使用了局部搜 索的遗传算法泓1 。 1 2 华南师范大学硕士学位论文 局部搜索是指在某个模因型的邻域内进行搜索评估。显然，局部搜索策略对 算法性能有很大的影响。对于连续优化问题，可以选取模因型中的一个模因，对 其加减一个随机数( 随机数的取值范围由该位模因的取值范围决定) ，这样产生 的新模因型就是它的一个邻居。而对于离散优化问题，则可随机地选择该模因型 里的两个模因进行交换，得到它的邻居。产生新邻居后，对其实行评估，如果适 应值优于原模因型，则替换之；否则重新执行局部搜索，直到得到更优的模凶型。 模因算法的实现过程如下： s t e p l 初始化。随机地产生m 个解，作为初始种群。 s t e p 2 根据设计的适应度函数，计算种群中每个模因型的适应值。如果算法 收敛或者达到最大迭代代数，则输出最佳个体及最优解，结束计算。否则转s t e p 3 。 s t e p 3 对种群中的每个模因型实行局部搜索，直到计算得到的新模因型的适 应值优于原模因型，则用其替换原模因型。 s t e p 4 按照适应值和选择策略，选择出用于繁殖下一代的模因型，适应值高 的模因型被选中的概率也高。 s t e p 5 按照指定的交叉率和交叉方法，对种群执行交叉运算。 s t e p 6 按照指定的变异率和变异方法，对种群执行变异运算。 s t e p 7 经过选择，交叉，变异后，产生了下一代的种群，转s t e p 2 。 口 o 2 1 2 微粒群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 微粒群算法是由学者j a m e sk e n n e d y 和r u s s e l le b e r h a r t 在1 9 9 5 年提出的【3 5 】， 因为其算法简单，易于实现，对目标函数无特殊要求，不需要梯度信息，参数少 等特点，使它在离散优化和连续优化的实际问题中都体现出了良好的效果，尤其 是它天然的实数编码特点适合于处理实优化问题。 微粒群算法模拟了自然界中的鸟群觅食现象。鸟群在空间中飞行，每只小鸟 被看做是一个粒子，对应于问题的解。粒子含有两个属性，当前位置p 和当前速 度v 。飞行时每个粒子根据自己的历史经验和群体内其他粒子的历史经验，来决 定下一步飞行的方向和距离。 假设种群中有n 个粒子，问题维数为d 。则第i 个粒子的位置可以用 见= ( 只。，只：，) 表示，速度可以用_ = ( v 。，k ：，) 表示。群体在每次改变 基于混合蛙跳算法的网格任务调度研究 位置之前，记录下每个粒子的历史最好位置6 ，= ( 匆。，岛：，b , o ) 和整个群体经历过 的历史最好位置g = ( g 。，9 2 ，g o ) 。 在每一次飞行时，粒子按照以下公式调整它们的位置： 吒= 吩+ q 吒( 毛一p o ) + c 2 5 ( g j 一岛) ( 式2 一1 ) 岛= 岛+ v o ( 式2 2 ) 在上两式中，1 ，刀，1 ，a v m a x 吒v 懈，v 。是允许的最大调整速 度。 从公式2 1 可以看出，粒子的速度更新由三个部分决定：( 1 ) 粒子的当前速 度，即公式的第一项，显示了粒子飞行的惯性作用。( 2 ) 公式第二项中的c 1 是自 身学 - 3 因子，e 是在0 到1 之间的随机数，这一项表明粒子飞行时会吸收自己的 历史经验，向自己飞过的最好位置靠近。( 3 ) 公式第三项中的c 是社会学习因子， 吒是在o 到1 之间的随机数，这一项表明粒子吸收群体内其他粒子的历史经验， 向整个群体飞过的最好位置靠近。学习因子c ，和c 通常取相同值，大部分文献取 c 1 2 c 2 5 2 为了减少当前速度的惯性作用的影响，更好地学习自身积累的经验和群体经 验，s h i 和e b e r h a r t 对初始的微粒群算法进行了改进蛐引，加入了惯性权重的概 念，把速度更新公式修改为： 吒= 国屹+ q _ ( 一p , j ) + c 2 5 ( g ，一p f ，) ( 式2 3 ) 即在原公式第一项的当前速度上乘了一个因子国，称之为惯性权重。改进的目的 是通过调整惯性权重的大小，来控制当前速度在速度更新中的重要性，平衡惯性、 自身经验、群体经验三者之间对粒子飞行的影响。如果惯性权重较大，粒子在原 方向上飞行更远，具有更好的全局探索能力。反之，粒子吸收了更少的原方向的 速度，在附近的区域中飞行，会有更好的局部开发能力。在实际问题的处理中， 一般惯性权重不直接赋予一个固定值，而是定义为一个迭代代数的递减函数的函 数值，这样就使得在算法运行的初始阶段，具有更大的惯性权重，让粒子尽快飞 到全局最优解的附近区域；而在算法的后期阶段，惯性权重越来越小，有利于粒 1 4 华南师范大学硕士学位论文 子在最优解的领域内搜索，防止飞出最优区域。 微粒群算法的实现步骤如下： s t e p l 随机产生n 个粒子的位置只和速度v ，并初始化每个粒子的历史最优 位置匆和整个群体的最优位置g 。 s t e p 2 将每个粒子的当前位置只的适应值和它自身的历史最优位置匆相比 较，如果更优，用其替换该粒子的历史最优值。 s t e p 3 将每个粒子的当前位置只的适应值和整个群体的最优位置g 相比较， 如果更优，用其替换整个群体的历史最优值。 s t e p 4 根据公式2 3 和公式2 2 更新粒子的下一步的飞行速度和位置。 s t e p 5 如果算法收敛或者达到最大迭代次数，停止迭代并输出最优解；否则 转入s t e p 2 2 2 混合蛙跳算法的基本原理 混合蛙跳算法( s h u f f l e df r o g l e a p i n ga l g o r i t h m ，s f l a ) 是一种受自然生 物模仿启示而产生的基于群体的协同搜索方法，由e u s u f fm 和l a n s e yk 在2 0 0 3 年首先提出，并用来成功解决了水资源网络分配问题b 引。这种算法模拟青蛙群体 寻找食物时。按族群分类进行思想传递的过程。 想象有一群青蛙在一个沼泽中跳跃的情景。沼泽里有很多分散在各处的石 头，青蛙可以从一个石头跳到另一个石头上，所有的青蛙有一致的目标，就是找 到含有最多食物的那块石头。青蛙之间可以相互交流，以便它们能够利用其他个 体的经验来改善自已的模因。每次通过调整较差青蛙的跳跃步长，使较差青蛙的 模因得到改进，逐渐改变他们的位置到最优点。 在刚开始的时候，有s 只青蛙分散在沼泽的不同地方。根据按位置聚类的方 法把青蛙分成若干组，相邻的青蛙具有相近的适应值，组成为一个社区( 或叫模 因群) 。每个社区可以从不同的方向上独立地搜寻食物，但是在同一个社区内， 每只青蛙会受其它青蛙想法的感染，即经历模因进化的过程。这个过程改善了青 蛙的模因质量和性能。要注意的是，为了让感染过程往好的方向发展，必须