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

摘要

群集智能作为一种新兴的求解问题的方案，在工程优化领域具有不可替代的作用，它对提高大规模优化问题的求解速度及优化精度具有非常重要的实际意义。但在处理复杂的优化问题时，往往存在收敛速度较慢，求解精度不够等缺点。因此当面对复杂多变的实际问题时，除了研究如何有效改进群集智能算法本身的算子之外，还要结合算法与实际问题的特点，合理的选择其它的融合算法，以提高算法解决问题的整体能力。
　　论文主要针对网格计算环境和云计算环境中带用户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(N㏒(N))和O(m2N㏒(mN))，为移动环境中对象查询算法优化提供了较完备的理论依据。

目录

封面

声明

中文摘要

英文摘要

目录

主要符号表

第一章 绪论

1.1研究背景、目的和意义

1.2群集智能的研究现状

1.3相关问题的研究现状

1.4论文主要研究内容和贡献

1.5本文结构

第二章 基于改进Pareto蚁群算法的多QoS组播路由策略

2.1引言

2.2多QoS组播路由问题描述

2.3基于Pareto 蚁群算法的网络路由算法设计

2.4仿真实验与性能评估

2.5本章小节

第三章 基于IMMAS的多QoS网格工作流调度策略

3.1引言

3.2基于用户QoS的网格任务调度模型

3.3基于IMMAS的网格任务调度算法设计

3.4算法分析与仿真实验

3.5本章小结

第四章 基于均匀离散PSO算法的多QoS网格任务调度策略

4.1引言

4.2多QoS约束的网格任务调度问题

4.3基于UDPSO网格任务调度算法的设计

4.4算法讨论及性能评估

4.5本章小结

第五章 云计算中基于用户等级的动态任务调度策略

5.1引言

5.2 Hadoop框架结构

5.3 Hadoop任务分配问题定义

5.4基于IDPSO的Hadoop任务调度算法的设计

5.5 IDPSO算法描述

5.6性能评估

5.7本章小结

第六章 基于动态环境的连续范围查询算法效率分析

6.1引言

6.2连续范围查询的应用场景

6.3移动系统模型的相关定义

6.4 基于在线CRN查询算法分析

6.5 离线CRN查询算法分析

6.6两种查询算法的通讯效率分析

6.7本章小节

第七章 全文总结

致谢

参考文献

在学期间参与的项目研究

在学期间发表和录用的学术论文