浅析基于量子粒子群优化的dag并行任务调度

《浅析基于量子粒子群优化的dag并行任务调度》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅析基于量子粒子群优化的DAG并行任务调度　　摘要:任务调度是网络并行计算系统的核心问题之一。在有向无环图(DAG)描述问题的基础上,提出了一种进行并行任务调度的量子粒子群优化算法。首先对DAG并行任务调度问题作出定义,并给出了优化问题的目标;然后分别讨论了问题的编码表示、解码方案、位置向量的计算方法、离散问题连续化、算法的总体流程等;最后给出算法的仿真实验情况及分析,实验结果表明,该算法有良好的全局寻优性能和快捷的收敛速度,调度效果优于遗传算法和粒子群优化算法。　　关键词:任务调度;量子粒子群优化;有向无环图　　　　　　Resea

2、rchonDAGparalleltaskschedulingproblembasedonquantum-behavedparticlesoptimization　　　　ZHANGCong,SHENHui-zhang　　(AntaiCollegeofEconomicsManagement,ShanghaiJiaotongUniversity,Shanghai200052,China)　　Abstract:Taskschedulingisoneoftheimportantproblemsinparallelputingsystem.Th

3、ispaperproposedaquantum-behavedparticlesoptimizationalgorithmfortaskschedulingbasedondirectedacyclicgraph.Firstredefinedtheparalleltaskschedulingproblemanditsaim.Thendiscussedtherepresentationoftheencoding,theprocedureofthedecoding,theputationalmethodofpositionvector,t

4、hecontinuativeofthediscreteproblemandthestructureofthealgorithmrespectively.Intheend,presentedthealgorithmsimulation,experimentresultanalysisandtheconclusions.Thesimulationresultsshohasbetterglobaloptimizingabilityandmorerapidconvergence,anditissuperiortogeicalgorithman

5、dparticlesoptimizationalgorithm.　　Key-behavedparticlesoptimization(QPSO);directedacyclicgraph(DAG)　　网络并行计算环境下的任务调度问题是指在一定约束条件下,如何将一组任务分配到多台处理机上执行的组合优化问题,其已被证明是NP完全问题,不可能在多项式时间内找到问题的最优解[1,2]。目前常见的并行任务调度问题按照任务之间有无数据依赖关系可以划分为独立任务调度和依赖关系任务调度。前者在调度任务时不需要考虑任务之间的数据依赖关系;而后者通常用有

6、向无环图(DAG)表示任务之间的数据依赖关系,在调度过程中满足任务之间的数据依赖关系。依赖关系任务调度的求解优化过程比独立任务调度的要复杂许多,且其适用范围也更广。以DAG表示的并行任务模型的研究得到了广泛关注和迅速发展。近年出现的一些启发式算法(如模拟退火算法、遗传算法等)为求解此类NP完全问题提供了新的途径[3~5],但是这些算法有些复杂性太高难以实现,有些实现起来太费时,所以有必要寻求更好的算法来解决此问题。　　粒子群优化(PSO)算法是由Kennedy等人[6]提出的一种源于对鸟群捕食行为模拟的进化计算技术,已成为进化计算的一

7、个最吸引人的分支。与遗传算法类似,PSO是一种基于迭代的优化方法,系统初始化为一组随机解,通过迭代搜寻最优值,但是在许多实际应用领域,更胜于遗传算法,尤其是在非线性优化问题上。量子粒子群优化(QPSO)算法是在传统的PSO基础上提出的一种新型的具有高效率全局搜索能力的进化算法[7,8]。它主要是引入量子物理的思想改进了PSO的进化方法,即更新粒子位置的方法;在更新粒子位置时重点考虑各个粒子的当前局部最优位置信息和全局最优位置信息。QPSO具有调整参数少、容易实现、收敛能力强等优势。为适应任务分配问题的求解,本文设计出合适的粒子编码,利

8、用改进的量子粒子群算法求解任务分配问题,并与其他算法相比较。实验结果表明,本文提出的算法可以获得质量更高的解。　　1问题描述　　本模型的计算系统由一系列异构的处理机组成,需要处理的总任务已分解成一系列子任务。模型的约束条