基于粒子群优化与蚁群优化的云计算任务调度算法

《基于粒子群优化与蚁群优化的云计算任务调度算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于粒子群优化与蚁群优化的云计算任务调度算法基于粒子群优化与蚁群优化的云计算任务调度算法刘波涛,湖南文理学院计算机科学与技术学院，湖南常德，415000；基金项目：湖南省教育厅高校科研项目（12C0822） ：在云计算环境中，存在非常多的用户，因而系统处理存在非常大的任务量。为了实现系统能够对服务请求的高效执行，云计算研究的重点问题就是任务调度问题。文章提出了一种基于粒子群优化和蚁群优化的任务调度算法，在CloudSim平台进行了仿真实验之后，发现这一算法的实时性和寻优能力很好，是有效的调度算法。关键词：粒子群优化；蚁群优化；云计

2、算；任务调度云计算发展融合了传统计算机和X络技术，是一种商业实现。基于互联X的计算服务模式，针对一些共享可配置计算资源实现了方便、按需访问；这些资源可借助非常小的管理代价或与服务提供者的交互被快速地准备和实现按需使用[1]。目前用于求解云计算任务调度问题的算法有遗传算法、粒子群优化算法和蚁群算法。在前人研究的基础上提出一种基于粒子群优化与蚁群优化的云计算任务调度算法。1云计算任务调度的设计粒子群优化算法是1995年Kennedy和Eberhart提出的，是受启发于鸟群觅食行为的的一种仿生优化算法。因为该算法简单、易实现且参数少，因

3、而可以实现良好的连续优化和离散优化效果。蚁群算法是上世纪90年代DorigoMacro等人提出的，受启发于模拟蚂蚁群体觅食行为，也是一种仿生优化算法。这一算法将正反馈并行机制引进来，鲁棒性很强；分布式计算机制十分优良；很容易能结合其他算法等，在一些复杂组合优化问题的求解中被广泛应用。当然这两种算法也存在一些不足之处。本文与两种算法的优势相结合，提出基于两种算法的一种云计算任务调度算法。这一算法先是借助粒子群优化算法的快速收敛性迅速生成初始解，接下来依据调度结果生成蚁群算法的初始信息素分布，最后是借助蚁群算法来将任务调度的最优解求出

4、来。2．1粒子群算法云计算任务调度问题是离散问题，而粒子群优化算法对于连续优化问题的解决比较适用。在离散版的粒子群算法中，将粒子位置向量每一位值取0或1，粒子速度不是对连续空间中粒子飞行的速度的表示，而且表示计算粒子位置向量取值为0或1的概率。2．2蚁群算法以云计算任务调度的任务与资源分配关系矩阵X为参照，定义{xij}m×n为节点集，组成一个无向完全图G(V，E)。通过蚁群算法从集合{xij}m×n中选出一组节点{xy11，xy22，…，xyjj，…，xynn}，yj∈{1，2，…，m}，从而实现最小的Cmax值。2．3算法流程

5、在粒子群优化和蚁群优化基础上提出的云计算任务调度算法，其基本步骤是这样的: Step1对云计算任务调度目标函数进行定义。Step2针对该调度算法，进行相关参数和算法结束条件的设定。Step3随即初始化粒子群的位置和速度。Step4对每个粒子的适应值进行计算，将粒子个体最优位置和群体最优位置找出来。Step5按照式(6)、式(7)来更新粒子速度和位置。Step6没有动作。Step7若是已达设定迭代次数，将云计算任务调度的初始调度结果输出，并转到Step8。要不然就跳转至Step4。.17.Step8按照粒子群算法得出的初始调度结果来

6、初始化蚁群算法的信息素进。Step9随机放置若干只蚂蚁到节点上并搜索。Step10每只蚂蚁按照式(8)进行下一节点的选择，并按照式(10)、式(11)对局部信息素进行更新，将调度列表中加入所选节点。Step11完成全部任务调度后，按照任务调度列表对调度结果的适应值进行计算，同时按照式(12)、式(13)对全局信息素进行更新。2实验与分析CloudSim是澳大利亚RajkumarBuyya博士领导团队开发出来的一个云计算仿真平台。其主要是对云环境进行模拟，针对不同的调度策略做性能测试。本文也是采用CloudSim平台来进行云环境的模

7、拟，对任务调度算法进行模拟仿真。为了对本文调度算法的性能进行有效检验，分别于5个虚拟计算资源、50个子任务和5个虚拟计算资源、500个子任务两种调度规模下，分别进行对比实验，包括粒子群优化算法(PSO)、蚁群算法(ACO)和本文算法(PSO-ACO)[2]。在实验中，各虚拟计算资源的处理能力是{400MIPs，600MIPs，800MIPs，1000MIPs，1200MIPs}；子任务长度范围是[400MI，1000MI］[3]。分别对算法的参数进行设置:本文算法的粒子群算法部分，群体规模size=100，c1=c2=2，迭代次数

8、为40，蚁群算法部分，群体规模size=100，α=1，β=1，ρ=0．2，迭代次数为160。粒子群算法、蚁群算法的参数与以上分别对应相同，迭代次数是200。对各算法进行了20次重复运行。最终的实验结果见图1和图2。 图1总任务完成时间曲线(5个资