基于蚁群遗传算法的网格任务调度策略研究

摘要

网格技术试图聚合分布在世界各地的计算、存储、知识、通信和信息等各类资源，以服务大众为目的，实现资源共享与协同工作。 网格任务调度技术问题尤其突出。网格所具有的动态性、异构性等特征使得网格任务调度变得更加复杂，必须研究出适合于网格计算环境的任务调度策略，提高用户完成总任务的效率，提供给用户满意的服务质量。 仿生优化算法应用于网格任务调度中，日益成为解决网格任务调度问题的锐利工具。作为仿生优化算法之一的蚁群算法其动态性、自相似性与网格任务调度原理极其相似，许多学者将蚁群算法应用于网格任务调度技术，并取得了不错的效果。 但是其研究没有考虑到蚁群算法的收敛性能对初始化参数的设置比较敏感，对于蚁群算法中的4个参数信息启发因子α、期望因子β、信息素挥发因子p、信息素强度Q在经验值的范围内随意或者是拼凑取值，这对蚁群算法的计算效率和收敛性产生了不利的影响。 参数信息启发式因子α反应了蚂蚁受其它蚂蚁经过网格资源节点时留下的信息素影响程度，其值越大，蚂蚁越倾向于选择其他蚂蚁选择过的资源节点，期望因子β反应了蚂蚁受资源的固有属性的影响程度，其值越大，蚂蚁越倾向于选择条件好的资源，这两个参数的值越大，蚁群算法越容易陷入局部最优。 信息素挥发因子p能够避免信息素无限积累，有利于扩大搜索范围；信息素强度Q能够加强正反馈，使搜索朝有利于寻找最优解的方向进行，提高求解的效率。针对这些参数的特征，本文提出蚁群遗传算法ACAGA（ant colony algorithm genetic algorithm）并用于网格任务调度。 ACAGA利用遗传算法快速随机的全局搜索能力，探索蚁群算法中的四个参数α，β，p，q的优化组合，实现网格中任务更加合理地调度。 文中使用网格模拟器GridSim对蚁群遗传算法进行了仿真模拟。模拟结果表明该算法缩短了任务的执行时间，同时有利于网格负载均衡。

目录

文摘

英文文摘

声明

1绪论

1.1问题的提出

1.2现状及意义

1.3解决方案及措施

1.4本文的组织结构

2 蚊群算法与遗传算法基本原理

2.1基本蚁群算法基本原理

2.1.1自然界中蚁群行为

2.1.2基本蚁群算法的逻辑结构

2.1.3基本遗传算法的数学模型

2.1.4基本蚁群算法特点

2.2基本遗传算法基本原理

2.2.1自然界中生物自然进化行为

2.2.2基本遗传算法的逻辑结构

2.2.3基本遗传算法特点

2.3本章小结

3基于ACAGA的网格任务调度策略

3.1ACAGA描述

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

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

3.2条件定义

3.3ACAGA实现

3.3.1ACAGA的基本思想

3.3.2初始定义及假设条件

3.3.3网格计算环境中ACAGA的设计

3.4本章小结

4 GridSim的仿真实验

5结束语

5.1研究总结

5.2进一步工作

参考文献

在校期间发表的论文、科研成果等

致谢