网格环境中一种改进的蚁群任务调度算法

摘要

网格计算环境日益成为一种不受地域限制的廉价的超级计算环境,它试图聚合分布在世界各地的计算、存储、知识、通信和信息等各类资源,以服务大众为目的,实现资源共享与协同工作。但由于网格资源具有异构性、动态性、自治性以及分布性等特点,网格环境下进行任务调度是一个很具挑战性的问题。网格任务调度算法直接关系到任务执行的速度,在网格技术研究中起着重要作用。
　　 50年代中期仿生学应运而生,人们不断地从生物进化的机理中得到启发,提出了许多用于解决复杂优化问题的新方法,比如遗传算法、神经网络、模拟退火算法等,并成功应用于解决实际问题。近年来,许多学者将蚁群算法应用于网格任务调度技术,并取得了不错的效果。但是目前研究者较少考虑仿生算法初始参数设置对算法收敛性能的影响。在蚁群算法中存在的信息启发因子α、期望因子β、信息素强度因子Q、信息素挥发因子ρ共四个参数中,α反应了蚂蚁受其它蚂蚁经过网格资源节点时留下的信息素影响程度,其值越大,蚂蚁越倾向于选择其他蚂蚁选择过的资源节点,β反应了蚂蚁受资源的固有属性的影响程度,其值越大,蚂蚁越倾向于选择条件好的资源,这两个参数的值越大,蚁群算法极易陷入局部最优。Q能够加强正反馈,使搜索朝有利于寻找最优解的方向进行,ρ能够避免信息素无限积累,从而扩大搜索范围,以提高求解的效率。本文提出了一种新的改进蚁群算法NACA(new ant colony algorithm),先对蚁群算法中的四个参数进行随机编码,产生染色体,利用蚁群算法得到一组较优解;再利用遗传算法的优点对这组值进行交叉、变异,选择产生更优的解;最后将这组值作为蚁群算法下一轮探索的原始值,进行最大次数的循环迭代直至停止,即求得参数组合的近似最优解。NACA利用遗传算法快速随机的全局搜索能力,以探索出蚁群算法中的四个参数α、β、ρ、Q的优化组合,将它应用于网格系统任务调度中,系统的性能得到了明显的改善。
　　 利用网格模拟器GridSim对所提出的算法进行了仿真模拟,结果表明所提出的算法具有更短的调度长度和更宽的适应性,当任务已知时,执行时间约缩短了21.7％,能有效缩短任务的执行时间,且负载变化时对网格中各处理器资源的影响大大减小。然而当任务未知和系统规模很大时,算法需要进一步完善。

目录

文摘

英文文摘

论文说明:图表目录

第1章 绪论

1.1 本文的研究背景

1.2 研究现状

1.3 本文的主要工作

1.4 论文结构

第2章 网格中的任务调度模型

2.1 网格计算任务调度的特点和主要目标

2.2 网格中任务调度算法的研究

2.2.1 简单的任务调度启发式算法

2.2.2 Min-Min类型的启发式任务调度算法

2.2.3 遗传模拟类的启发式调度算法

2.3 网格任务调度的困难性

2.4 小结

第3章 蚁群算法与遗传算法基本原理

3.1 蚁群算法的基本原理

3.2 蚁群算法的数学模型

3.3 蚁群算法特点

3.4 基本遗传算法

3.4.1 遗传算法

3.4.2 遗传算法基本特点

3.5 蚁群算法与遗传算法的混合的基本方法

3.5.1 混合的基本思想

3.5.2 变异操作

3.5.3 交叉操作

3.5.4 遗传蚁群算法

3.5.5 算法测试

3.6 小结

第4章 一种改进的蚁群网格任务调度算法NACA

4.1 NACA算法描述

4.2 蚁群算法中参数设置的重要性与盲目性

4.3 利用遗传算法对蚁群算法中的参数进行优化

4.4 网格任务调度相关

4.4.1 网格调度

4.4.2 网格资源的负载平衡

4.5 NACA实现

4.5.1 NACA基本思想

4.5.2 初始定义及假设条件

4.5.3 网格计算环境中NACA的设计

4.6 小结

第5章 仿真实验设计与分析

5.1 网络仿真工具

5.2 GridSim模拟器介绍

5.2.1 GridSim与其他仿真工具的比较

5.3 Gridsim仿真实验环境的搭建

5.4 仿真实验

5.5 小结

总结与展望

参考文献

致谢

附录A 攻读学位期间所发表的学术论文目录