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

群集智能及其在分布式系统中的应用研究

作　者: 蒲汛
导　师: 卢显良
学　校: 电子科技大学
专　业: 计算机系统结构
关键词: 群集智能组播路由优化任务调度云计算连续范围查询
分类号: TP393.09
类　型: 博士论文
年　份: 2012年
下　载: 450次
引　用: 0次
阅　读: 论文下载

内容摘要

群集智能作为一种新兴的求解问题的方案，在工程优化领域具有不可替代的作用，它对提高大规模优化问题的求解速度及优化精度具有非常重要的实际意义。但在处理复杂的优化问题时，往往存在收敛速度较慢，求解精度不够等缺点。因此当面对复杂多变的实际问题时，除了研究如何有效改进群集智能算法本身的算子之外，还要结合算法与实际问题的特点，合理的选择其它的融合算法，以提高算法解决问题的整体能力。论文主要针对网格计算环境和云计算环境中带用户QoS约束的多目标任务调度问题，以及组播路由优化等问题展开讨论。在深入分析和研究了蚁群算法和粒子群算法这两种典型的群集智能算法的基础之上，通过对两种算法相关算子的优化，并融合其它算法设计思想，如配方均匀设计，分治算法等，实现了对带约束条件的多目标任务调度和组播路由的快速优化，从而提高了应用环境的整体性能。论文的主要贡献归纳如下：1）论文提出了一种基于改进Pareto蚁群算法的组播路由策略，对如何快速构建多约束条件下的QoS组播路由问题进行求解。通过分析组播路由问题的数学模型，在QoS参数以及网络信息不确定的情况下，利用区间表达来模糊定义网络参数，并采用分类蚁群算法快速查找出在给定QoS条件下满足需求概率最大的组播树Pareto非劣解。在算法执行过程中引入局部信息节点惩罚更新机制，以降低无关节点的重复搜索率；同时在全局信息素更新阶段，引入了对Pareto精英解的激励更新机制，以提高算法的收敛速度。仿真实验表明，该机制是可行和有效的，并能较快地搜索到全局（近似）最优解。2）论文提出了一种优化的最大最小蚂蚁系统（IMMAS），用以解决网格环境中工作流的调度优化问题。通过分析MMAS算法的不足，优化其执行效率，并利用分而治之的思想，将用户对任务截止时间（DeadLine）的QoS限制，合理地分配到相应子任务中，同时，在IMMAS算法优化的过程中动态地调整服务节点的启发式信息，以期在满足QoS限制的情况下，快速高效地找到系统和用户都比较满意的近似最优解。3）针对网格环境中多QoS约束条件下独立任务调度问题，论文提出一种融合配方均匀设计与离散PSO算法的任务调度策略，以实现对独立任务优化调度的快速生成。该算法采用类似于离散DPSO算法的速度和位置更新方法，结合配方均匀设计，快速衡量各QoS约束条件的适应度，以产生分布均匀且较优的Pareto解集，最终为系统提供一组较优的任务调度方案。理论证明该算法能快速收敛，且算法复杂度不高。仿真实验表明该算法更符合网格调度的复杂环境，能得到较短的任务执行时间和较均衡的QoS保障。4）针对云计算环境中用户任务调度的不同需求，提出基于改进离散PSO算法的任务调度策略，力图实现在短时间内对云计算任务的相对较优调度。该算法将用户费用与该任务的截止时间相结合，构建出相对合理的用户优先级，以引导算法的适应度函数的偏好；并引入重优化判断准则在保证算法有能力跳出局部最优的同时保持解的多样性，最终求出满足用户优先级偏好的任务调度映射。仿真实验表明该算法更符合云计算调度的复杂环境，能得到全局较优的任务调度方案。5）论文分析了移动环境中时空对象以线性模式和分段线性模式运动时，进行连续范围查询（Continuous Range Neighbors Queries CRNQ）的效率问题，证明了时空对象在两种运动模式中CRNQ的在线查询算法（On-line CRNQ）和离线查询算法（Off-line CRNQ）的时间复杂度分别是O (Nlog(N))和O (m2Nlog(mN))，为移动环境中对象查询算法优化提供了较完备的理论依据。

全文目录

摘要  5-7
Abstract  7-16
第一章绪论  16-35
  1.1 研究背景、目的和意义  16-17
  1.2 群集智能的研究现状  17-26
    1.2.1 群集智能的概念和特点  17-19
    1.2.2 群集智能计算的研究现状  19-26
  1.3 相关问题的研究现状  26-32
    1.3.1 网格任务调度研究现状  27-29
    1.3.2 云计算任务调度研究现状  29-31
    1.3.3 网络组播路由技术  31-32
  1.4 论文主要研究内容和贡献  32-34
  1.5 本文结构  34-35
第二章基于改进 Pareto 蚁群算法的多 QoS 组播路由策略  35-48
  2.1 引言  35-36
  2.2 多 QoS 组播路由问题描述  36-38
  2.3 基于 Pareto 蚁群算法的网络路由算法设计  38-44
    2.3.1 算法原理  38
    2.3.2 路由信息素与启发式规则定义  38-41
    2.3.3 蚁群状态转移规则  41
    2.3.4 局部信息素更新规则  41-42
    2.3.5 基于 Pareto 最优解集的全局更新规则  42-43
    2.3.6 MPACO 算法描述  43-44
  2.4 仿真实验与性能评估  44-46
  2.5 本章小节  46-48
第三章基于 IMMAS 的多 QoS 网格工作流调度策略  48-69
  3.1 引言  48-50
  3.2 基于用户 QoS 的网格任务调度模型  50-54
    3.2.1 网格模型中的相关定义  50-52
    3.2.2 问题描述  52-54
  3.3 基于 IMMAS 的网格任务调度算法设计  54-63
    3.3.1 用户 QoS 需求的启发式规则  54-56
    3.3.2 信息素初始化  56-59
    3.3.3 任务执行顺序的构建  59-60
    3.3.4 信息素更新规则  60-62
    3.3.5 IMMAS 算法的实现流程  62-63
  3.4 算法分析与仿真实验  63-68
    3.4.1 算法相关性质分析  63-64
    3.4.2 仿真实验  64-68
  3.5 本章小结  68-69
第四章基于均匀离散 PSO 算法的多 QoS 网格任务调度策略  69-84
  4.1 引言  69-71
  4.2 多 QoS 约束的网格任务调度问题  71-73
    4.2.1 网格任务调度模型  71-72
    4.2.2 网格任务调度问题定义  72-73
  4.3 基于 UDPSO 网格任务调度算法的设计  73-79
    4.3.1 算法原理  73-74
    4.3.2 UDPSO 针对网格任务调度的编码  74
    4.3.3 粒子速度和位置的更新公式  74-76
    4.3.4 基于均匀设计的适应值函数  76-78
    4.3.5 UDPSO 算法描述  78-79
  4.4 算法讨论及性能评估  79-83
    4.4.1 算法收敛性讨论  79-80
    4.4.2 算法复杂度分析  80
    4.4.3 算法性能比较  80-83
  4.5 本章小结  83-84
第五章云计算中基于用户等级的动态任务调度策略  84-95
  5.1 引言  84-85
  5.2 Hadoop 框架结构  85-86
  5.3 Hadoop 任务分配问题定义  86-88
  5.4 基于 IDPSO 的 Hadoop 任务调度算法的设计  88-91
    5.4.1 相关工作  88
    5.4.2 IDPSO 针对网格任务调度的编码  88-89
    5.4.3 基于优先级的适应值函数  89-90
    5.4.4 粒子速度和位置的更新方法  90-91
  5.5 IDPSO 算法描述  91-92
  5.6 性能评估  92-93
  5.7 本章小结  93-95
第六章基于动态环境的连续范围查询算法效率分析  95-113
  6.1 引言  95-98
  6.2 连续范围查询的应用场景  98-99
  6.3 移动系统模型的相关定义  99-105
    6.3.1 线性模型  100-103
    6.3.2 分段线性模型  103-105
  6.4 基于在线 CRN 查询算法分析  105-109
    6.4.1 线性模型中在线 CRN 查询算法及其复杂度分析  106-108
    6.4.2 分段线性模型中在线 CRN 查询算法及其复杂度分析  108-109
  6.5 离线 CRN 查询算法分析  109-111
    6.5.1 线性模型中离线 CRN 查询算法  109-111
    6.5.2 分段线性模型中离线 CRN 查询算法及其复杂度分析  111
  6.6 两种查询算法的通讯效率分析  111-112
  6.7 本章小节  112-113
第七章全文总结  113-116
致谢  116-117
参考文献  117-127
在学期间参与的项目研究  127-128
在学期间发表和录用的学术论文  128-129

群集智能及其在分布式系统中的应用研究

内容摘要

全文目录

相似论文