学位论文 > 优秀研究生学位论文题录展示

基于改进混合蛙跳算法的网格任务调度算法研究

作　者: 孙元姝
导　师: 杨武
学　校: 重庆理工大学
专　业: 计算机应用技术
关键词: 网格网格任务调度混合蛙跳算法局部搜索混洗过程
分类号: TP338.8
类　型: 硕士论文
年　份: 2011年
下　载: 52次
引　用: 1次
阅　读: 论文下载

内容摘要

网格是分布式计算领域中的一个新兴研究方向,在未来社会中发挥着越来越重要的作用,吸引了大批专家致力于网格的研究。网格是一个集成的计算与信息服务环境,它借助网络连接地理上分布的计算资源,并将它们转变成便利、经济、可靠的计算能力,以实现资源的共享。网格资源具有动态性、异构性、自治性等特点,如何合理匹配网格任务与资源,使网格系统达到最佳性能,成为网格研究的重点之一,这也是本文研究的主要内容。网格任务调度是一类组合优化问题,围绕网格任务调度算法,网格学者作了大量的研究工作,已将遗传算法、粒子群算法、Min-Min算法等经典组合优化算法,成功应用于求解网格任务调度问题。混合蛙跳算法SFLA(Shuffled Frog Leaping Algorithm)是一种新兴的启发式算法,它兼具了粒子群算法和模因算法的优点,在求解网格任务调度问题上取得不错的效果。基于对SFLA算法和网格任务调度问题的深入分析,论文针对SFLA算法自身存在的易陷入局部最优以及信息共享不足等缺陷,进行了如下几个方面的研究:首先,考虑到“虎父无犬子”的自然进化规律,鉴于Min-Min算法思路简单、能在较短时间内获得较高质量解等优点,提出Min-Min与随机算法相结合的种群初始化策略,既改善初始种群的质量,又不失其多样性,使种群快速收敛到全局最优;其次,基于种群进化对局部极值的依赖性,对局部极值添加了遗传算子,扩大了局部搜索范围,降低陷入局部最优的几率。同时,借鉴PSO算法中粒子更新思想,优化SFLA算法中最差青蛙个体步长移动公式;最后,在混合过程中,对各族群局部极值添加遗传算子,加强个体间的信息共享,提高种群的多样性,加快算法的收敛速度。为了评估改进SFLA的性能,论文利用Gridsim模拟器,结合JCreator IDE环境,对基于改进SFLA算法的网格任务调度进行仿真实验。实验结果表明,论文改进的SFLA算法是可行的,提高了网格调度系统的吞吐量。论文从种群初始化、个体矢量更新以及混合操作等方面,对SFLA算法进行了改进,并通过Gridsim模拟器对改进的算法进行了仿真。仿真结果表明,论文提出的改进方法是有效的,对网格任务调度算法领域的研究提供一定的帮助。

全文目录

摘要  4-5
Abstract  5-10
1 绪论  10-15
  1.1 研究背景及意义  10-11
  1.2 研究现状  11-13
    1.2.1 网格研究现状及动态  11-12
    1.2.2 网格任务调度研究现状  12-13
  1.3 主要研究内容  13-14
  1.4 论文框架结构  14-15
2 网格环境下的任务调度  15-26
  2.1 网格  15-20
    2.1.1 网格概述  15-16
    2.1.2 网格的特性  16
    2.1.3 网格的体系结构  16-20
  2.2 网格任务调度  20-25
    2.2.1 网格任务调度概述  20
    2.2.2 网格任务调度的目标  20-21
    2.2.3 网格任务调度系统及特点  21-22
    2.2.4 网格任务调度过程  22-23
    2.2.5 经典网格任务调度算法  23-25
  2.3 本章小结  25-26
3 一种改进的混合蛙跳算法  26-38
  3.1 算法理论基础  26-29
    3.1.1 模因算法  26-27
    3.1.2 混合算法  27
    3.1.3 粒子群算法  27-29
  3.2 混合蛙跳算法  29-33
    3.2.1 混合蛙跳算法原理  29
    3.2.2 混合蛙跳算法数学模型  29
    3.2.3 混合蛙跳算法流程  29-32
    3.2.4 混合蛙跳算法参数分析  32-33
  3.3 混合蛙跳算法的改进策略  33-37
    3.3.1 种群初始化优化策略  33-34
    3.3.2 局部搜索优化策略  34-36
    3.3.3 混合操作优化策略  36-37
  3.4 本章小结  37-38
4 基于改进混合蛙跳算法的网格任务调度  38-50
  4.1 问题描述  38-39
  4.2 改进混合蛙跳算法实现过程  39-47
    4.2.1 参数设置  39-40
    4.2.2 模因编码  40-41
    4.2.3 种群初始化  41-45
    4.2.4 适应度函数  45
    4.2.5 青蛙种群分族  45-46
    4.2.6 局部搜索  46-47
    4.2.7 混合操作  47
  4.3 改进混合蛙跳算法执行流程  47-49
  4.4 本章小结  49-50
5 仿真实验及结果分析  50-64
  5.1 GridSim 网格模拟器概述  50-54
    5.1.1 GirdSim 的主要特征  50-51
    5.1.2 GirdSim 体系结构  51
    5.1.3 GirdSim 的通信实体  51-52
    5.1.4 GridSim 仿真流程  52-54
  5.2 算法的设计与实现  54-59
    5.2.1 种群初始化模块的实现  54-55
    5.2.2 局部搜索模块的实现  55-57
    5.2.3 混合操作模块的实现  57
    5.2.4 算法主体的实现  57-59
  5.3 实验及结果分析  59-63
    5.3.1 配置仿真环境  59-60
    5.3.2 实验参数  60
    5.3.3 实验结果分析  60-63
  5.4 本章小结  63-64
6 总结与展望  64-65
  6.1 论文工作小结  64
  6.2 后续研究工作  64-65
致谢  65-66
参考文献  66-68
个人简历、在学期间发表的学术论文及取得的研究成果  68

基于改进混合蛙跳算法的网格任务调度算法研究

内容摘要

全文目录

相似论文