基于自适应遗传算法的网格任务调度研究与实现

论文摘要

网格是构建在互联网上的一组新兴技术,通过它可以把分散在不同地理位置的资源整合起来实现各种资源的全面共享,所以网格的根本目标是协调资源的共享。网格中任务调度追求的是系统的高吞吐率。但由于网格环境中资源的广域性、异构性、自治性和动态性等特点使得网格中的任务调度要比传统环境下的调度要复杂得多,再加上任务调度本来就是一个NP难解问题,因此研究并提出一种网格环境下的高效合理的任务调度算法具有重要意义。本课题在研究网格计算及任务调度现状的基础上,选择了自适应遗传算法来进行网格中任务调度。针对遗传算法容易产生早熟收敛的现象,结合网格任务调度的特点和目标,本文运用了一些运算量较小的操作对算法进行改进:在算法初始种群产生时引入min-min算法与遗传变异相结合的新方法来提高初始种群质量;算法迭代过程中采用了一种局部收敛判断的新标准以及改进的变异操作来防止局部收敛;算法迭代结束后结合邻域搜索扩大寻优范围。最后利用现有仿真工具GridSim实现了用课题中改进的算法进行网格任务调度的仿真。初步的实验结果表明改进后算法具有较好的全局搜索能力和较快的收敛速度,提高了网格任务调度的性能,尤其是对于任务量比较大的网格任务调度。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 网格简介
• 1.1.2 网格中任务调度的重要性
• 1.2 本文的主要研究工作及其意义
• 1.3 论文结构
• 第二章 网格计算及其任务调度的基本问题
• 2.1 网格计算基本问题
• 2.1.1 网格计算概念
• 2.1.2 网格计算研究现状
• 2.1.3 网格计算特点
• 2.2 任务调度及其研究现状
• 2.2.1 任务调度的基本问题
• 2.2.2 网格中任务调度常见算法
• 2.3 网格环境下任务调度的特点及流程
• 2.3.1 网格环境下任务调度的特点
• 2.3.2 网格环境下任务调度流程
• 2.3.3 网格环境下任务调度的主要目标
• 第三章 遗传算法（GENETIC ALGORITHMS）
• 3.1 GA 的产生与发展
• 3.2 GA 概要
• 3.2.1 基本思想
• 3.2.2 遗传算法的特点
• 3.3 遗传算法的基本组成
• 3.3.1 编码机制（Encoding Mechanism）
• 3.3.2 适应度函数（Fitness Function）
• 3.3.3 遗传算子（Genetic Operator）
• 3.3.4 控制参数（control parameters）
• 3.4 遗传算法实现流程
• 3.4.1 遗传算法原型
• 3.4.2 遗传算法流程图
• 第四章 基于自适应遗传算法的网格任务调度
• 4.1 引言
• 4.2 自适应遗传算法
• 4.2.1 遗传算法缺点分析
• 4.2.2 基于遗传算子的自适应遗传算法策略研究
• 4.3 自适应遗传算法的改进
• 4.3.1 引入min-min 算法与变异算子结合的初始种群产生
• 4.3.2 一种新的早熟局部收敛判断标准
• 4.3.3 改进的变异算子
• 4.3.4 邻域搜索
• 4.4 改进后的算法实现
• 4.4.1 编码和解码
• 4.4.2 初始种群及适应度函数的设定
• 4.4.3 进化操作
• 4.4.4 参数选择
• 4.5 改进后算法流程
• 第五章 基于自适应遗传算法网格任务调度的设计与仿真实现
• 5.1 仿真模拟器GRIDSIM介绍
• 5.1.1 仿真器简介
• 5.1.2 Gridsim 体系结构
• 5.1.3 Gridsim 的实体和通信
• 5.2 基于自适应遗传算法的网格任务调度的设计与实现
• 5.2.1 基于GridSim 的网格调度算法的开发
• 5.2.2 使用GridSim 的仿真过程
• 5.3 实验结果及其分析
• 5.3.1 仿真实验结果
• 5.3.2 实验小结
• 第六章 总结与展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表的学术论文