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

设计与应用

计算机测量与控制.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常数);

1204 计算机测量与控制 第19卷

ij:表示t时刻蚂蚁由城市i转移到城市j的启发信息,一般取 ij=;

dij

k

pij(t):表示t时刻蚂蚁由城市i转移到城市j的概率,计算公式为:

[ ij(t) [ ij]

,j tabuk

[ t ikik

pk(1)ij(t)=k tabu

间的距离来表示,而在云环境中需要用资源的计算和通讯能力

等相关系数来表示信息素。

(3)启发信息也起着非常重要的作用,在云环境中,需要以资源固有的属性(如计算和通讯能力等),来表示在蚁群算法中的启发信息。

基于以上3点,蚂蚁根据当前的资源信息量,决定分配给云计算环境现有资源的下一个任务的概率的计算方法也作相应改变如下:p(t)=

ijk

k

0,j tauk

, 分别代表留信息的重要程度和启发信息的重要程度。

(1)初始化。将每条边上的信息素初始化为一个很小的常数值,将m只蚂蚁随机地放置到n个城市,并将出发点城市设置到禁忌表tabuk中。

(2)蚂蚁根据式(1)选择下一个城市,并修改禁忌表。(3),(2)更新该边信息素。

& ijk(2) ijt+1=(1- ) ijt+

Q/lp,当蚂蚁k走过城市ij时

ijk=

0,其它

其中,ljb是蚂蚁k从开始城市到当前城市已走过的路径长度。 表示信息的持久性。

(4)计算最佳路径。当全部蚂蚁走完所有城市后,按式(3)计算最优路径长度并保留。

lmin=minlk,k=1,2,...,m(3)

lk第k只蚂蚁所走路径长度。

(5)当所有蚂蚁走完全部城市以后,仅对最优路径上的信息素按式(4)进行更新。

new ij=(1- ) old k(4)ij+ ij

式中, 为全局信息素挥发系数,lk为最优路径长度。

(6)如果设置的迭代次数未完,则清空禁忌表,重复上述过程。

k

( kt

,j,k 云计算现有资源

其它

(5)

0,

式中, j(t)是t时刻资源的信息素浓度; j表示资源的固有属性, j= j(0); 表示信息素的重要程度; 表示资源固有属性的重要程度。

蚂蚁路径变异的个数可由随机数产生,产生随机数可以通过Integer.parsedouble(Math.random()*10)Java代码实现。

本文中云环境资源调度的目标是:在云环境下将M个任务分配到N个资源上,通过改进的蚁群优化算法计算任务在各个资源上执行的平均最短时间,实现系统的资源最优化。即求下面函数的最小值[7]。

minF(mi)=

式中,

mifi(mi)

,i=1,2,...,N

M

(6)

i

mi=M,M是在给定时间段内提交给云计算环境的

总的任务数量,mi表示在资源i上分配mi个任务,0 mi Mmax,Mmax表示在资源i上所能执行的最大任务并行数,可以ii

用实验确定。

云环境下,基于蚁群优化算法的任务调度算法执行流程图如下。

2 改进的蚁群优化算法与云环境下的任务调度

蚁群优化算法有很多优点。目前,提出的蚁群改进的优化算法多种多样,取得了非常好的效果。但是由于算法随机性很大,在解决大规模优化问题时容易限于局部最优解、收敛速度慢的缺陷。本文引入遗传算法,结合它快速随机的全局搜索能力,将遗传算法融入到蚁群优化算法的每一次迭代中,提高了收敛的速度,还保证了原算法的求解精确性。同时引入了逆转变异策略[5],避免了陷入局部最优的风险,维持和增加了种群的多样性。基于这种改进的蚁群优化算法,云计算服务集群可以快速实现资源发现、资源匹配、调度产生、任务执行以及蚂蚁路径的逆转变异。

对于每个资源请求者,云环境服务集群必须推荐出一个较优的任务与资源的组合。采用改进的蚁群优化算法来搜索当前分配策略中的最佳策略,在同一时间内,影响资源状态的因素都可以由信息素来描述,那么调度就能简单、快速获得预测的结果。由于云环境的独特性质,我们需要对TSP问题与云环境资源调度问题的特征差异进行关联,以供改进的蚁群优化算法使用[6]。这些差异主要表现在以下3个方面:

(1)在TSP问题中,城市之间有边相连且这些边是可达的并有不同的距离,而在云环境中,资源没有固定的网络拓扑结构。故在云环境中要利用资源活动的相互作用来模拟拓扑关系。

(2)在TSP问题中,城市与城市之间的信息素用城市之

图1 改进算法的任务调度流程图

3 仿真实验结果

本文扩展了云计算仿真平台CloudSim2 1[8],重写了Dat

(下转第1211页)

第5期刘羽峰,等:六轴旋翼碟形飞行器控制系统软件设计及仿真研究

[3]耿德根,宋建国,马 潮,等.AVR高速嵌入式单片机

原理及应用(修订版)[M].北京:北京航空航天大学出版社.2002.

[4]张 军.AVR单片机应用系统开发典型实例[M].北

京:中国电力出版社,2005.

[5]盛 显.飞行器集成设计框架软件研究[D].西安:西

北工业大学,2006.

[6]McKerrowP.Modellingthedragan-flyerFour-Rotor

Helicopter[A].ProceedingsofIEEEInternationalCon ferenceonRoboticsandAutomation[C],3596 3601.

图6 六路PWM信号输出仿真模拟图

[7]BOUABDALLAHS,NOTHA,SIEGWARTR.PID

vsLQcontroltechniquesappliedtoanindoormicro-quadrotor[A].ProceedingsoftheIEEEInternationalConferenceonIntelligentRobotsandSystems(IROS)[C],2004:2451 2456.

[8]聂博文,马宏绪,王 剑,等.微小型四旋翼飞行器的研究现状

与关键技术[J].电光与控制,2007,14(6):113 118.

[9]彭军桥.四浆碟形飞行器飞行控制系统研究[D].上海:上海大

学,2004.

参考文献:

[1]杨明志,王 敏.四旋翼微型飞行器控制系统设计[J].计算机

测量与控制,2008,16(4):485 488.

[2]马 潮,詹卫前,耿德根.Atmega8原理及应用手册[M].北京清

华大学出版社,2003.

[10]王岩松.微型飞行器系统电路设计[D].成都:电子科技大学,

2005(5).

[11]周润景,张丽娜,刘印群.PROTEUS入门实用教程[Z].PRO

TEUS入门实用教程.2007.

[12]刘丽丽,彭 辉,刘敏安.四旋翼飞行仿真器的建模研究[J].

仿真技术,2009,85(4):88 91.

2004:

4 结束语

由于本文采用了通过调节6个电机的转速来改变其螺旋桨

的速度,实现升力的变化,从而能够很灵活的对飞行姿态和位置进行控制,使六轴飞行器的设计成为可能。同时经过基于ProtuesISIS软件所搭建的模型进行的系统仿真,进一步验证了该控制系统软件设计的合理性,通过仿真结果显示该控制系统能够满足飞行器控制姿态的要求。

(上接第1204页)

aCenterBroker、Cloudlet等类,对改进的任务调度算法进行了模拟仿真。为验证本算法的优越性,在本次实验中,我们分别采用了CloudSim现有的轮循(RoundRobin,RR)调度算法、ACO算法及MACO算法进行任务调度。各任务平均执行时间如图2所示。从总体上看,RR算法随着任务数量的增加,所花费的时间也就越多。而ACO算法,开始时信息素较少,任务执行的较慢,后期随着信息素的不断增加,正反馈性增强,时间增加幅度小于RR算法。改进的ACO算

法,显然比前两种算法执行时间要短,效率要高。

的缺陷,综合考虑了云环境的一系列特点,将遗传算法融合到蚁群优化算法中,并引入了逆转变异策略,不仅加快了蚁群优化算法的收敛速度而且避免了陷入局部最优。实验结果表明,改进的蚁群优化调度算法大大缩短了任务的平均运行时间,实现了在该环境中高效的为用户任务提供合适的资源,提高了资源的利用率。

参考文献:

[1] 虚拟化与云计算 小组.虚拟化与云计算[M].北京:电子工业

出版社,2009.[2]王天擎,谢 军,曾 洲.基于蚁群算法的网格资源调度策略研究

[J].计算机工程与设计,2007,28(15):3611 3613.

[3]李庆玉,徐敏强,往日新,等.基于蚁群算法的航天器观测动态调

度研究[J].计算机测量与控制,2009,17(5):822 825.[4]DorigoM,CaroGD.Antcolonyoptimization:Anewmeta-heu

ristic[A].Proc.ofthe1999CongressonEvolutionaryComputa tion[C].Washington:IEEEPress,1999.1470 1477.[5]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合[J].计

算机研究与发展,2003,9(40):1352 1356.

[6]张 青.网格环境下任务调度算法的应用研究[D].大连:大连

海事大学,2009.

[7]张晓杰,孟庆春,曲卫芬.基于蚁群优化算法的服务网格的作业调度[J].计算机工程,2006,8(32):216 218.

图2 任务平均执行时间对比

[8]CloudSim:AFrameworkforModelingandSim-ulationofCloud

ComputingInfrastructuresandServicesIntroduction[EB/OL]./gridbus/.

4 结论

本文针对蚁群优化算法在解决大规模优化问题时容易出现

本文来源：https://www.bwwdw.com/article/sxy1.html