基于智能优化算法的网格任务调度策略研究

论文摘要

任务分配问题,一般是NP完全问题。存在许多任务调度问题的具体实例的启发式算法,但多数情况下效率都不高。本文主要探索了几种智能优化算法及其改进策略在任务调度中的应用,主要包括均场退火算法、微正则均场退火算法、模糊动态遗传算法等。首先将均场退火算法(MFA)应用到网格任务调度中,构造了满足各种约束条件的能量函数和状态更新函数等,并进行了仿真实验,验证了均场退火算法的有效性。接着本文对微正则退火算法作了改进,并将其应用到任务调度中。首先提出了分段的能量奖励策略和混合能量补偿策略。其次,在基本微正则退火算法的基础上,提出了微正则均场退火算法(MMFA),采用均场退火算法的能量函数形式和新状态产生方法,保证新状态都是向能量降低的方向转移,从而加快搜索速度,提高算法性能。最后针对网格任务调度的动态特性,提出并实现了一种改进的遗传算法—模糊动态遗传算法FDGA,重新对遗传算法编码机制、适应度函数确定、选择算子、交叉算子、变异算子等进行了设计,在编码阶段考虑了网格的动态性,适应度函数采用基于模糊数学的模糊评价机制,综合考虑到总的完成时间、主机的空闲时间和任务的deadline要求等性能指标,根据网格系统各服务节点的计算能力、负载等状态进行动态调度,从而向用户提供较优性能。同时,在OPNET环境中构建了一个可扩展的局部网格仿真平台,对所提出的算法进行了仿真实验,结果表明模糊动态遗传算法具有很好的优化能力,提供了较好的服务质量。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 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 网格中常见的资源管理和任务调度系统
• 2.3.4 带QoS 的网格调度
• 2.4 本章小结
• 第三章 基于均场退火的网格任务调度算法
• 3.1 模拟退火算法介绍
• 3.1.1 模拟退火算法的主要思想
• 3.1.2 模拟退火算法的参数控制问题
• 3.1.3 模拟退火算法的特点和研究现状
• 3.2 均场退火算法的研究
• 3.2.1 均场近似
• 3.2.2 鞍点展开
• 3.2.3 稳定性分析
• 3.2.4 均场网络参数的确定
• 3.3 均场退火算法在网格任务调度中的应用
• 3.3.1 均场退火方程
• 3.3.2 问题映射
• 3.3.3 能量函数
• 3.3.4 Hopfield 神经网络能量函数构造
• 3.3.5 均场退火算法
• 3.3.6 参数取值
• 3.3.7 实验结果
• 3.4 本章小结
• 第四章 改进的微正则退火算法及应用
• 4.1 微正则退火算法的物理背景
• 4.2 微正则退火算法的原理
• 4.2.1 算法依据
• 4.2.2 算法介绍
• 4.3 微正则退火算法的研究现状
• 4.4 改进的微正则均场退火算法的思想
• 4.4.1 分段的能量奖励策略
• 4.4.2 混合能量补偿策略
• 4.4.3 基于均场退火的微正则退火算法
• 4.5 基于微正则均场退火算法的有序任务多处理器调度
• 4.5.1 模型与定义
• 4.5.2 仿真实例
• 4.5.3 能量函数及均场更新函数
• 4.5.4 实验仿真及结果分析
• 4.6 本章小结
• 第五章 基于模糊动态遗传算法的网格任务调度实现
• 5.1 遗传算法介绍
• 5.1.1 基本遗传算法原理
• 5.1.2 遗传算法的特点及运行过程
• 5.1.3 遗传算法求解分布式任务调度问题的研究现状
• 5.2 模糊数学原理
• 5.2.1 模糊数学基础知识
• 5.2.2 模糊数学综合评价
• 5.3 模糊动态遗传算法原理
• 5.3.1 编码机制
• 5.3.2 适应度函数
• 5.3.3 选择算子
• 5.3.4 杂交和变异算子
• 5.3.5 主要参数的选择
• 5.4 局部网格仿真模型
• 5.4.1 网络仿真简介
• 5.4.2 OPNET 仿真软件简介
• 5.4.3 局部网格仿真模型设计
• 5.5 模糊动态遗传算法实现
• 5.5.1 仿真参数选择
• 5.5.2 仿真结果及分析
• 5.6 本章小结
• 第六章 总结与展望
• 6.1 全文总结
• 6.2 研究展望
• 参考文献
• 发表论文和科研情况说明
• 致谢
• 附录