基于分布式并行遗传算法的网格任务调度研究

作     者：陈然 

作者单位：湖南科技大学 

学位级别：硕士

导师姓名：张会福;陈安华

授予年度：2009年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：网格任务调度 分布式并行遗传算法 迁移策略 消息传递接口 

摘      要：任务调度系统是网格计算系统的重要组成部分,也是实现高性能网格计算的关键技术,遗传算法由于具有良好的全局搜索能力,在处理任务调度问题时比传统调度算法更具优越性。但是基本遗传算法(SGA)存在如“过早收敛、求解精度不高和寻优时间较长等不足。本文针对网格任务调度问题,研究遗传算法的并行化处理方法,提出了一种分布式并行遗传算法。主要研究以下内容: 1.研究网格任务调度机理、过程和现有的任务调度算法。针对子任务间存在依赖关系的网格任务调度情况,以实现任务调度的最优跨度为目标,确定采用基于遗传算法的任务调度方案。 2.分析遗传算法的基本原理,针对SGA“过早收敛和求解精度不高的问题,引入精英保留机制的串行遗传算法(EGA),确保进化过程中产生的最优解不被后续的遗传操作破坏。分析了遗传算法的四种可能并行性,从全局并行的角度,基于群体分组的并行性提出一种分布式并行遗传算法(DPGA),该算法采用分布式并行模式,通过引入子种群最优个体迁移策略,提升了子种群个体平均适应度,提高了算法求解精度。 3.针对网格任务调度问题特点,采用C语言和消息传递接口(MPI)实现DPGA,并在PC机群中对DPGA、EGA和SGA进行网格任务调度模拟仿真,将它们对不同任务规模的调度时间性能进行对比分析。实验结果表明,本文提出的DPGA相对于EGA和SGA具有更好的搜索能力和更快的收敛速度,能够实现网格任务调度的最优跨度。