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