基于可用性任务调度问题的粒子群算法研究与实现

摘要

随着计算机技术的不断发展,分布式异构系统开始越来越多地用在大型复杂问题的解决方案里。该系统把网络中的计算机、工作站等计算资源整合到一起,使之实现全系统内的资源共享,通过高效的资源管理和任务调度技术使系统达到高性能。然而这些资源是有限的,为了让有限的资源能够尽量满足需要,就必须要合理的利用资源,尽可能的降低系统的开销。任务调度技术是使系统达效的关键性技术之一。在一般情况下的任务调度问题属于NP完全问题,很难在合理时间内探求其精确解,因此目前主要是用伺机载入平衡(Opportunistic Load Balancing)、最小完成时间(Minimum Completion Time)、模拟退火(Simulated Annealing)、禁忌搜索(Tabu Search)、遗传算法(Genetic Algorithm)、神经网络(neural networks),极小算法(Min-min),极大极小算法(Max-min)等算法来求该问题的近似最优解。
　　 粒子群算法是从鸟类的群体觅食行为中得到启发,基于人工生命和演化计算理论而提出的一种智能优化算法,它同时保留和利用了位置与速度信息,在大多数情况下都能很快收敛于最优值。由于粒子群算法思想直观、实现简单而且具有很高的执行效率,现在已经被作为一个独立的分支,与遗传算法、进化规划等进化算法相提并论。近十年内粒子群算法被广泛地应用于优化计算、神经网络以及人工智能等多个领域。可用性是分布式异构系统的一个基本性能参数。它是指节点有效计算时间在其整个运行时间中所占的比率。本文在现有粒子群算法的设计框架下,结合遗传算法里的轮盘赌选择来改进基本粒子群算法,同时还对粒子群算法中的编码,适应度函数进行研究,以形成算法的整体思想,来对任务调度问题中的可用性问题进行了深入研究。首先,我们假设任务之间是相互独立的,不同节点的可用性与计算能力各异,且不同任务在不同节点上的可用性的要求也不同。然后提出一个基于粒子群算法的任务调度算法对分布式异构系统可用性做有效改进。最后,采用实验模拟工具SimGrid,对本文所提出的算法与几种传统算法做模拟实验,比较所提出算法与传统方法的实验数据,结果证实了本文算法具有相对更好的调度长度,且较传统算法在可用性上的性能更优。

目录

文摘

英文文摘

论文说明:图表目录

第1章 绪论

1.1 课题来源

1.2 选题背景及意义

1.3 任务调度介绍

1.4 现有研究介绍

1.5 本文的组织结构

第2章 粒子群算法的研究现状

2.1 粒子群算法的基本概念

2.2 粒子群算法的优缺点

2.3 粒子群算法研究现状

2.4 粒子群算法的研究内容和特点

2.5 粒子群算法流程

2.6 粒子群算法在任务调度中的应用

2.7 小结

第3章 基于可用性的任务调度问题粒子群算法

3.1 算法思想

3.2 模型描述

3.2.1 结构模型

3.2.2 任务模型

3.3 问题描述

3.4 基于PSO算法的任务调度算法描述

3.4.1 适应度函数

3.4.2 编码规则

3.4.3 初始种群的形成与选择

3.4.4 粒子飞翔

3.4.5 算法描述

3.5 小结

第4章 实验结果的比较与分析

4.1 SIMGRID仿真包

4.1.1 SIMGRID简介

4.1.2 SIMGRID的使用方法

4.2 实验结果比较及分析

4.3 小结

第5章 总结和展望

参考文献

致谢

附录 攻读工程硕士期间参与的项目