基于改进进化算法的网格任务调度研究与实现

作     者：刘芳芳 

作者单位：南京信息工程大学 

学位级别：硕士

导师姓名：薛胜军

授予年度：2012年

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：任务调度 粗粒度并行遗传算法 自适应免疫机制 GridSim 

摘      要：网格系统是目前应用最广泛的分布式应用系统,它利用Internet将世界上不同地域内的资源整合成一个虚拟的有机体,类似于一个逻辑整体或一台超级计算机,用户从中不仅可以享受一体化的信息和应用服务,还可以共享资源和协同工作。网格中不存在资源“孤岛,它实现了信息的充分共享。 网格系统强大的计算能力是通过网格上任务的运行性能体现的,在网格环境中,任务调度问题是网格研究领域的关键问题之一。由于网格环境的动态性、分布性及异构性等特点,网格任务调度面临巨大的挑战。本文在分析网格任务调度的过程、目标和特点的基础上,着重做了如下工作： 1、在介绍遗传算法(Genetic Algorithm, GA)实现过程和算法优缺点的基础上,提出了改进的粗粒度并行遗传算法。该算法在交叉阶段设计了一种基于模式阶的多点交叉算子,在变异阶段采用一种基于任务迁移的定向变异方法,同时采用精英策略保持种群的多样性。此外,还引入统计学中“移动平均的原理来预测种群进化若干代后适应度值的变化趋势。 2、在介绍免疫进化算法(Immune Evolutionary Algorithm, IEA)实现过程和算法优缺点的基础上,提出了自适应的免疫进化算法。将免疫机制引入到适应度函数的设计中,且将调节因子k调整为自适应变化的因子。实验结果表明改进的算法能够改善免疫进化算法的不足,很好地保持种群的多样性。 3、利用GridSim仿真器对改进的算法进行了多次的仿真实验,对比分析了改进前后算法的性能。实验结果表明,与改进前算法的性能相比较,改进后的算法有更快的收敛速度和更佳的寻优能力,并且能够获得更优的调度结果。