设计与应用

计算机测量与控制.2011.19(5) ComputerMeasurement&Control

文献标识码:A

文章编号:1671 4598(2011)05 1203 02 中图分类号:TP311 5

基于改进蚁群算法的云环境任务调度研究

王永贵1,韩瑞莲2

(1 辽宁工程技术大学软件学院,辽宁葫芦岛 125105;2 辽宁工程技术大学电子与信息工程学院,辽宁葫芦岛 125105)

摘要:针对蚁群优化算法(ACO)在解决大规模的组合优化问题时容易陷入搜索速度慢和局部最优的缺陷,进行算法的改进;结合遗传算法全局收敛的优点,将遗传算法融入到蚁群优化算法的每一次迭代中,加快其收敛速度,并引入逆转变异策略,避免了蚁群优化算法陷入局部最优;深入研究了改进的蚁群优化算法在云计算环境中的任务调度策略,并通过扩展云计算仿真平台CloudSim实现了模拟仿真;实验结果表明,此算法能够缩短云环境下的任务平均运行时间,提高了资源利用率。

关键词:蚁群优化算法;遗传算法;云计算;任务调度

StudyonCloudComputingTaskScheduleStrategyBasedon

MACOAlgorithm

WangYonggui,HanRuilian

1

2

(1 CollegeofSoftwareEngineering,LiaoningTechnicalUniversity,Huludao 125105,China;

2 CollegeofElectronicsandInformationEngineering,LiaoningTechnicalUniversity,Huludao 125105,China)

Abstract:ForcharacteristicsofAntColonyOptimizationAlgorithminsolvingthelarge-scalecombinationoptimizationproblemeasytofallintothesearchspeedslowlyandpartiallythemostsuperior,theglobalfastconvergenceofgeneticalgorithmisutilizedtocombineantcolonyoptimizationalgorithmwithgeneticalgorithmineachgeneration,whichenhancestheconvergencerateandimprovestheefficiency.Andthereversalvariationstrategyisintroducedtoavoidtheantcolonyoptimizationalgorithmfallingintopartialmostsuperior.ThepaperdeeplyresearchestheimprovedAntColonyOptimizationAlgorithm(ACO)inresourcesschedulingstrategyofthecloudcomputing,byex tendingtheCloudComputingplatformCloudSimtotestthesimulation.Theresultsshowthatthismethodcanreducethetaskaveragerun ningtime,andraisestherateavailabilityofresources.

Keywords:antcolonyoptimizationalgorithm;geneticalgorithm;cloudcomputing;taskschedule

0 引言

云计算是一种全新的网络服务方式,是并行计算(Paral lelComputing)、分布式计算(DistributedComputing)和网格计算(GridComputing)等计算机科学概念的商业实现。它强调资源的共享性、异构性、动态协作性,这给用户带来方便的同时,也对任务调度技术提出了更高的要求。云计算任务调度指的是在一个特定的云环境中,根据一定的资源使用规则,在不同的资源使用者之间进行资源调整的过程。目前的任务调度策略大多数是通过虚拟机级别上的调度技术结合一定的调度策略来尝试为虚拟机内部应用做任务调度[1],普遍缺乏精确定性。

蚁群优化算法是一种基于群体的自适应搜索算法,是对蚂蚁群落食物采集过程的模拟。因其并行分布性、扩展性、易实现、鲁棒性强等优点,在动态环境下也表现出高度的灵活性和健壮性,成功解决了许多组合优化问题。任务调度问题本质上从资源分配给任务的多种组合中选出性能比较好的一种动态组合方式,从解决问题角度看,蚁群优化算法非常适合解决云环

收稿日期:2010 09 10; 修回日期:2010 10 20。

基金项目:辽宁省教育厅基金项目(05L169);辽宁省教育厅高等学校科研项目(2009A349)。

作者简介:王永贵,男,内蒙古赤峰人,副教授,主要从事数据挖掘、云计算资源调度方向的研究。

境中的资源调度问题[2]。

调度算法的效率直接影响整个云环境的工作性能。本文深入研究了蚁群优化算法的机理,分析了云计算环境的特殊性质,引入遗传算法并对部分路径进行逆转变异。两种算法优势互补,使寻优能力和求解速度大幅度提高,提高了调度效率。

1 标准蚁群优化算法

蚁群优化算法是20世纪90年代意大利学者M.Dorigo,V.Maniezzo,A.Colorni等从生物进化的机制中受到启发,通过模拟自然界真实蚂蚁群觅食行为,提出来的一种新型模拟进化算法,是群体智能理论研究领域的一种主要算法。所谓群体智能是指具有简单智能的主体,通过合作表现出复杂智能行为的特性,其概念来源于对自然界中一些昆虫,如蚂蚁、蜜蜂等的观察[3]。蚁群是通过信息素的正反馈机制和集体自催化行为来找出最优路径的。M.Dorigo等学者已先后提出了模拟蚁群这一觅食行为的AS(antsystem)算法和ACS(antcolonysystem)算法,并将两种算法定义为ACO(antcolonyoptimi zation)[4]算法。

本文以ACS模型为例,阐述标准蚁群优化算法。为便于理解,我们以求解平面上n个城市的TSP问题为例。首先引入如下符号:

m:代表蚁群中蚂蚁的数量;dij(i,j=1,2,...,n):表示城市之间的距离; ij(t):表示t时刻在城市i,j连线的残留信息量,一般取 ij(0)=C(C常数);