论文部分内容阅读
网格是一个将空间分布的资源,通信服务和计算资源集成而形成的大型的计算机系统,以实现资源共享和协调工作。由于网格环境中的资源具有动态性、异构性、自治性等特点,而任务调度是一个NP难解问题,如何对网格的任务高效调度,实现网格系统最佳性能,成为网格研究的重点之一。因此提出一种网格环境下的高效合理的任务调度算法具有十分重要意义。本文在研究网格及任务调度现状的基础上,基于传统遗传算法的任务调度分析,针对遗传算法容易产生早熟收敛的现象,进化后期搜索效率低和收敛性差等问题,结合网格任务调度的特点和目标,提出一种基于双适应度的改进的混合遗传算法(Double-Fitness Hybrid Genetic Algorithm,即DFHGA),本文对原算法进行以下改进：(1)在种群初始化阶段,采用两种方式产生初始种群：min-min算法与遗传变异相结合的方式和随机方式,提高了初始种群质量,减少算法运行迭代次数并提高全局最优解的质量；(2)基于自适应遗传算法AGA,增加了一个适应度,即用两个适应度来选择种群个体；然后通过设置适应度函数,利用选择、交叉和变异概率对每代种群中个体进行进化,获得总任务执行时间和任务平均执行时间都较短的任务调度结果,通过比较调度结果,验证改进的算法的有效性。(3)改进的算法采用了一种新的局部收敛判断原则,提前预测早熟和收敛现象的发生,及时更新种群中的个体保证不断加入新个体,有效的防止局部收敛和早熟现象,保证了种群个体多样性。在算法迭代结束后结合邻域搜索扩大寻优范围。利用仿真工具GridSim,对用本文中改进的算法进行仿真和比较。实验结果表明：改进后算法能优于自适应遗传算法,不但能找到总任务完成时间较短的调度结果,而且此调度结果的任务平均完成时间也较短,实现了较好的全局搜索能力和较快的收敛速度,尤其是对于任务量比较大的网格任务调度,提高了网格任务调度的性能。