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

并行遗传算法及其在网格任务调度中的应用研究

作　者: 刘文娟
导　师: 张京军
学　校: 河北工程大学
专　业: 计算机应用技术
关键词: 并行遗传算法 网格计算 任务调度 消息传递接口
分类号: TP18
类　型: 硕士论文
年　份: 2013年
下　载: 43次
引　用: 0次
阅　读: 论文下载
 

内容摘要


网格是当前并行计算技术的一个重要发展方向，其目标是实现对地理上广泛分布的大量异构资源的资源共享。其中，任务调度是实现高性能网格计算的核心服务技术，也是保证应用程序有效执行的重要组成部分。网格任务调度是将并行程序任务分配到网格系统的处理节点上，涉及到程序模型和并行计算系统模型，算法的设计要综合考虑程序和目标系统的特点，是一种典型的NP完全问题。遗传算法由于具有良好的全局搜索能力，在处理任务调度算法时比传统调度算法更具优越性。但是，应用基本的遗传算法容易陷入“过早收敛”的误区，同时求解精度不高。本文针对网格任务调度问题，提出了一种基于MPI的并行遗传算法处理方式。文章首先简述了一下遗传算法的基本原理，针对传统遗传算法自身的并行性，从全局并行的角度出发提出了一种粗粒度的并行遗传算法。该算法采用分布式并行模式，通过子种群的个体迁移策略，缓解“早敛”和求解精度不高的问题，同时精英保留机制的引入，让调度策略有更好的收敛性。然后，研究了任务调度的机理、调度过程和调度模型，通过与现有调度算法的比较，确定了采用并行遗传算法的任务调度方案，并规划了任务调度的目标，在满足任务优先约束关系的前提下实现最优跨度。最后，针对网格动态的、异构的、分布的计算环境，采用C语言和消息传递接口MPI实现了本文算法，在建立的模拟网格环境PC机群中分别对本文算法、传统遗传算法进行了不同分组的任务调度仿真实验，通过不同规模的调度时间性能进行对比分析，结果表明，本文提出的改进遗传算法具有更好的寻优能力，适合处理一定规模的调度问题。

全文目录


摘要  5-6
Abstract  6-10
第1章 绪论  10-16
  1.1 研究背景及意义  10-11
  1.2 国内外研究现状  11-14
    1.2.1 并行遗传算法研究现状  11-13
    1.2.2 网格任务调度的研究现状  13-14
  1.3 本文主要工作  14-15
  1.4 本文的章节安排  15-16
第2章 并行遗传算法简介  16-25
  2.1 遗传算法简介  16-18
    2.1.1 遗传算法原理  16-18
    2.1.2 遗传算法自身的并行性  18
  2.2 并行遗传算法  18-24
    2.2.1 并行遗传算法的产生  18-19
    2.2.2 并行遗传算法的分类  19-22
    2.2.3 并行遗传算法的性能与参数选取  22-24
    2.2.4 并行遗传算法与一般最优化方法  24
  2.3 本章小结  24-25
第3章 网格计算中的任务调度  25-33
  3.1 网格计算  25-28
    3.1.1 网格计算的概念与特点  25-26
    3.1.2 网格计算的应用  26-27
    3.1.3 网格计算的核心服务技术  27-28
  3.2 网格任务调度概述  28-32
    3.2.1 网格调度问题定义  28-29
    3.2.2 网格任务调度的目标和特点  29-30
    3.2.3 网格任务调度过程  30-31
    3.2.4 传统调度算法简介  31-32
  3.3 本章小结  32-33
第4章 基于并行遗传算法的网格任务调度  33-48
  4.1 网格任务调度  33-36
    4.1.1 网格任务调度的定义  33-34
    4.1.2 网格任务调度模型  34-36
    4.1.3 算法的可行性分析  36
  4.2 粗粒度并行遗传算法的参数设计  36-42
    4.2.1 染色体编码的设计  36-37
    4.2.2 初始种群的生成  37-38
    4.2.3 染色体的适合度计算函数  38-39
    4.2.4 遗传算子的确定  39-40
    4.2.5 迁移策略  40-42
    4.2.6 停止条件  42
  4.3 系统平台介绍  42-47
    4.3.1 MPI 的消息传递接口  42-44
    4.3.2 MPI 并行环境的搭建  44-47
  4.4 本章小结  47-48
第5章 仿真实验与结果分析  48-55
  5.1 网格任务在 MPI 编程结构中的调度框架  48-50
  5.2 模拟实验及结果分析  50-54
  5.3 本章小结  54-55
结论与展望  55-56
致谢  56-57
参考文献  57-60
作者简介  60-61
攻读硕士学位期间发表的论文和科研成果  61-62

相似论文

  1. 基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
  2. 农业供应链系统网络平台的构建,S126
  3. 遥感数据处理网格平台的设计与初步实现,TP79
  4. 网格任务调度算法研究及其有色Petri网的建模与仿真,TP301.1
  5. 基于OGSA的IVS研究及设计,TP391.41
  6. 嵌入式实时操作系统MQX的内核分析及应用研究,TP316.2
  7. 基于遗传算法的无线传感器网络优化,TN929.5
  8. 基于网格与并行技术的电力系统动态安全评估,TM712
  9. 线性分组码的基本网格理论以及极小化构造方法,TP301.1
  10. 网格资源定价机制和交易策略研究,TP393.09
  11. 法方程层面地球参考框架数据融合及其网格计算应用研究,P228.4
  12. 无线传感网络在环境监测中的应用,TN929.5;TP212.9
  13. 带有协商机制的任务流网格调度模型的设计与实现,TP393.02
  14. 网格环境中数据传输服务的研究与应用,TP393.02
  15. 基于Min-Min和Max-Min算法改进的网格调度算法的研究,TP393.01
  16. 企业计算网格作业管理系统的研究与实现,TP338.8
  17. 基于LBM的两相流数值模拟及其并行算法的实现,O359
  18. 基于网格技术的电力稳态安全分析研究与应用,TM712
  19. 基于并行遗传算法的叶轮机叶片优化设计,V232.4
  20. 遗传算法求解TSP问题的研究与改进,TP18
  21. 企业网格计算系统中注册中心的研究与实现,TP393.18

中图分类: > 工业技术 > 自动化技术、计算机技术 > 自动化基础理论 > 人工智能理论
© 2012 www.xueweilunwen.com