基于改进遗传算法的云计算任务调度算法

胡艳华,唐新来,2

(1.广西科技大学鹿山学院 电气与计算机工程系，广西 柳州 545616；2.广西科技大学 教务处，广西 柳州 545616)

基于改进遗传算法的云计算任务调度算法

胡艳华1,唐新来1,2

(1.广西科技大学鹿山学院 电气与计算机工程系，广西 柳州 545616；2.广西科技大学 教务处，广西 柳州 545616)

任务调度是云计算的核心问题。云计算中的任务调度算法要求在提高系统吞吐量和最大跨度的同时又要兼顾资源的安全与负载均衡问题。传统遗传算法因具有强大的并行空间搜索能力而在云计算中得到广泛应用，但其亦存在明显不足，即随着计算机规模的不断扩大，收敛性逐渐降低，存在易早熟等不足，限制了其调度性能。而Min-Min和Max-Min算法简单易行，且具有较好的时间跨度，可以较好地弥补传统算法的不足。在传统遗传算法的基础上，结合Min-Min和Max-Min算法，提出了一种新的云计算任务调度算法，在产生初始化种群时引入Min-Min和Max-Min算法，并选取任务完成时间和负载均衡作为双适应度函数，提高了初始化种群的质量、算法搜索能力以及收敛速度。仿真结果表明，该算法优于传统遗传算法，是一种有效的云计算任务调度算法。

云计算;遗传算法;任务调度;Min-Min算法;Max-Min算法

0 引 言

作为一种新兴技术,云计算已成为当今计算机领域的一个研究热点。云计算是在分布式处理、并行处理和网格计算等技术的基础上[1-2]，整合了虚拟化、效用计算、IaaS、PaaS及SaaS等诸多概念发展而来[3]。所谓的“云”实际上是一个庞大的网络，该网络将用户请求拆分成若干个子任务，交由至一个庞大服务器群构成的高效处理系统进行搜索并分析计算，然后再返回至用户。它所面向的用户群数量是巨大的，需要高效地处理海量的任务，故如何进行合理而高效的任务调度是云计算的重点与难点。

由于云计算环境中资源的动态异构性，大规模的任务调度要求在尽量提高系统的吞吐量和最优跨度的同时也要考虑资源的安全与负载均衡等问题。目前应用较多的云计算调度算法主要有经典的遗传算法、Min-Min、Max-Min、Suffrage及蚁群算法等。异构环境下的资源调度是个NP问题，在求解NP问题时，遗传算法能够得到很好的解，其在异构环境下任务调度方面的研究较多，与模拟退火、蚁群等算法相比，遗传算法能够得到更优的解。但传统的遗传算法亦存在明显的不足，即随着计算规模的不断扩大，其收敛性逐渐降低[4]。Min-Min和Max-Min这两种算法的优点是比较简单且容易实现，同时具有较好的时间跨度。因此，文中在传统遗传算法的基础上，结合Min-Min和Max-Min两种算法的优点，提出了将Min-Min算法与Max-Min算法和遗传算法(Genetic Algorithm,GA)相结合的改进遗传算法(MMGA算法)。该算法主要对初始种群的生成进行了改进，并设计出了与传统自适应遗传算法不同的选择和交叉算子，从而提高了算法的搜索能力和收敛速度。在CloudSim平台下[5]的仿真实验证明此算法明显优于传统遗传算法。

1 云环境中的任务调度问题描述

目前，云计算的编程模式大多采用Google提出的Map/Reduce模型[6]，其主要原理是将要执行的问题分解成Map和Reduce，通过Map程序将数据分割成若干独立区域，再将其调度给大量的计算机处理，实现并行计算，然后通过Reduce程序汇整计算结果，最后输出用户需要的结果。显然，在此模型中，合理的任务调度至关重要。尽量缩短用户的响应时间，同时也要达到良好的资源动态负载均衡，这是文中要考虑的重点问题。传统GA算法虽然在异构环境下有着较好的调度性能，但有其天生的缺点，即收敛速度缓慢、易早熟等；而Min-Min算法和Max-Min算法都较易实现，同时又具有较好的时间跨度、良好的调度性能。文中以经典的遗传算法为基础，引入Min-Min及Max-Min算法，提出了一种改进遗传算法，并考虑了响应时间和负载均衡问题，旨在建立一个更优的分配调度策略。

文中将云计算中的资源(包括处理器、存储器、网络等)统一视为计算资源，同时假定任务的输入是由若干较大任务分解成的一批子任务，子任务数量远远大于资源数量，各个子任务所需的计算时间已知，且各个子任务的运行时间差异不大。假如用T表示大型任务的数量，N表示子任务的总数量，M表示计算资源的数量，并用M*N的ETC(ExpectTimetoComplete)矩阵来计算各个计算资源上任务队列完成所需时间，其中ETC(i,j)表示第j个子任务在第i个计算资源上运行完成所需的时间。至此，将云计算中的任务调度问题定义为如何合理地将子任务分配到各个计算资源，使得任务运行完成所需的时间最短、负载均衡最小。

2 云环境中遗传调度算法的改进

GA是根据生物遗传和进化规律提出的一种用于复杂系统的自适应概率优化技术。由于GA具有全局解空间搜索及并行性等优势，该算法以及以该算法为基础的诸多算法在云计算任务调度中得到了广泛应用[7]。文献[8]提出了一种双适应度的遗传算法(DFGA)，在考虑最小任务完成时间的同时，亦兼顾了子任务平均完成时间，然而该算法求解效率不高；另外，目前多数改进遗传算法尚未考虑资源的负载均衡情况[9-11]。

文中参照Map/Reduce模型[6]，结合已有云计算环境下的改进遗传算法[9,12]，同时考虑到任务完成时间和负载均衡，将Min-Min与Max-Min算法引入到传统遗传算法中，提出了一种改进遗传算法，以提高云计算环境下的任务调度效率。

2.1 染色体编码与染色体解码

染色体的编码方式包括直接与间接编码。文中考虑到大规模任务处理的特性以及云计算环境的动态异构性等特点，采用间接编码的染色体编码方式，即任务-资源映射模式，对每个子任务所占资源进行编码，每条染色体的总长等于子任务的总数量，染色体中的每一位基因都为正整数，代表子任务编号，此位置上的值代表该子任务所占资源编号，如图1所示。

图1 任务-资源编码

图中，Ti表示任务编号；Rj表示任务Ti执行时所占第j个资源编号。

若有10个子任务，3个可用资源，则染色体长度为10，每个基因取值为1～3之间的随机数，例如随机产生以下的染色体编码：

则此染色体代表第2个资源运行第1个子任务，第3个资源运行第2个子任务，以此类推。得到染色体后，还须解码，以得到各个资源上子任务分布的情况。上述染色体可解码为：

R1:{T5,T6,T9}

R2:{T1,T3,T7,T10}

R3:{T2,T4,T8}

通过解码，求得每个计算资源上的子任务序列，然后通过ETC矩阵，计算出每个子任务序列所需的完成时间，进而得到总任务完成时间函数为：

(1)

其中，time(i,j)为被分配到计算资源Ri上第j个子任务执行所用的时间；n为分配到该计算资源Ri上的子任务数量。

2.2 改进的初始种群生成

初始种群在遗传算法中具有极为重要的作用，其生成方式是首要解决的问题。初始种群的平均适应度越高，较优个体就能越快地引导种群向理想的方向发展而得到最优解，从而使其迭代过程变短、收敛性提高。获取一个具有高平均适应度值的初始种群，是文中的研究重点之一。

图2 改进后的种群初始化

2.3 适应度函数

在进化搜索中，遗传算法一般单纯使用适应度函数为依据，使用个体的适应度值进行搜索。所以适应度函数的选择至关重要，将直接影响到收敛速度以及最终能否找到最优解[13]。最优跨度，即使任务的总执行时间(makespan)最小，是文中调度算法涉及的一个重要内容。故文中选用任务的总执行时间函数作为遗传算法的适应度函数之一：即

(2)

(3)

其中，uLB为文中定义的平衡任务负载因子，代表各个计算资源的利用率情况。uLB的值越大，表示计算资源的利用率越高，那么F1(x)的值就相对越小。

资源负载均衡问题是资源调度中要考虑的另外一个重要方面，它能大大提高资源的利用效率。在设计适应度函数时也应考虑到资源负载均衡问题。文中参考文献[12]，采用染色体上资源节点任务分配数标准差来衡量资源负载均衡。种群初始化后，设种群大小为Scale，子任务总个数为N，计算资源数即worker的个数为M，则每个染色体的资源节点平均分配任务数AT=N/M。对于任一个染色体，基于资源节点任务分配数标准差的适应度函数为：

(4)

其中，AT'(j,i)为第j个染色体第i个资源节点所分配到的任务数。

由于在选择复制阶段必须选择任务标准差较小的染色体，因此设定基于任务分配数标准差的适应度函数为：

设计咨询企业在履行合同的过程中，相关辅助人员及部分管理人员的投入，应尽可能的增加当地用工比例。一方面，可满足当地移民签证管理部门要求。另一方面，可使得中方员工尽快融入当地文化环境，为设计咨询服务的本土化带来优势。最重要的是，适用当地员工，可最大化的节约合同成本，雇佣当地员工节约工作签证办理费用的同时，增大了境外可列账成本范围，减少了当地社保与中国社保重复缴纳的损失。

(5)

2.4 遗传操作

2.4.1 选择操作

选择操作是指根据“优胜劣汰”的法则，在种群中不断选取适应度较强的个体，逐渐用以产生新种群的过程。个体的适应度越高，被筛选到下一代的概率就越大；反之亦然。如此反复，得到种群中个体的适应度值的最优解。

假设文中算法的种群大小为Scale，首先选择父代中的最优个体和Min-Min算法、Max-Min算法产生的个体，以保留较优个体，其他的Scale-3个体则采用轮盘赌方式作为选择操作算子，通过式(2)、(5)得出个体选择概率为：

(6)

(7)

选择下一代个体时，先以c1和c2的概率分别选择P1和P2(其中0

2.4.2 交叉与变异操作

普通自适应算法中，当个体适应度值趋向最大适应度值时，交叉概率与变异概率减小。这对于种群进化后期较为有利，但不利于初期进化，因其能增加进化走向局部最优的几率。因此，需要做进一步修改，修改后的公式为：

(8)

(9)

当f'=fmax时,Pc=Pc2>0;当f=fmax时,Pm=Pm2>0。

这样，种群中的较优个体之间拥有更高的交叉与变异概率。同时采用最优保存策略，将每一代的最优个体直接复制到下一代中而保证其不被破坏。上述公式中，一般取Pc1=0.9;Pc2=0.6;Pm1=0.1;Pm2=0.001。

3 算法仿真结果与分析

文中采用云仿真器CloudSim[5]对上述提出的MMGA进行验证和分析。

同时，在相同的环境条件下，对GA和MMGA进行了比较实验，主要参数如表1所示。

算法初始条件：Scale取值为100，M取值为5～50，N取值为1 000～5 000。

算法终止条件：文中设最大进化代数为200，当算法连续50代没有找到更好的解，认定算法为基本收敛，将终止算法。

(1)若取M=20，N取1 000～5 000，实验过程中多次跟踪记录任务的完成时间，结果如图3所示。

表1 实验参数设置

图3 任务的完成时间曲线(时间单位：104 ms)

由图3可以看出，与GA相比，MMGA的任务完成时间明显较短。

(2)若N=4 000，M=20，考察算法的收敛迭代情况，如图4所示。

图4 算法的收敛结果比较(时间单位：104 ms)

由图4可知，在算法进化初期，GA和MMGA得出的任务完成时间相差不大，但MMGA算法在初始化种群产生时引入Min-Min算法和Max-Min算法，较好地提高了初始化种群的质量，使收敛速度加快，缩短了寻找最优解时间，MMGA在140次就开始收敛；随着进一步的进化，在GA初始阶段出现的超常个体误导了种群的进化方向，因而陷入了局部收敛，而MMGA随着进一步进化，同任务完成时间明显低于GA，得到的最优解更好。

(3)若N=5 000，将任务分配到M=5个资源节点(R1,R2,R3,R4,R5)上，若其处理能力为(120,200,150,340,500)MFLOPS，实验过程中分别记录5个资源节点上的资源负载情况，其结果如图5所示。

图5 多任务情况下节点的资源负载情况

由图5可知，在任务量大、资源节点运算能力差异较大的情况下，MMGA的资源负载均衡程度明显好于GA。

综上所述，文中提出的MMGA比GA收敛速度更快，且可以使得任务执行时间较短，资源负载较均衡，能较好地应用在云计算资源环境中。

4 结束语

文中在充分考虑大规模任务处理特性和云计算环境动态异构性的基础上，提出了一种基于传统遗传算法的改进任务调度算法-MMGA。该算法既可以保证种群具有较高的平均适应度，又可以维护种群个体的多样性；同时，算法中采用任务执行时间和负载均衡作为双适应度函数，使得在提高收敛速度的同时，兼顾资源均衡。仿真结果表明，该改进算法收敛性能较好、资源负载较均衡，具有良好的效率，能更有效地解决云计算环境下的任务调度问题。

[1]ChienA,CalderB,ElbertS,etal.Entropia:architectureandperformanceofanenterprisedesktopgridsystem[J].JournalofParallelandDistributedComputing, 2003, 63(5): 597-610.

[2]KimJS,NamB,MarshM,etal.Creatingarobustdesktopgridusingpeer-to-peerservices[EB/OL].[2009-10-16].ftp://ftp.cs.umd.edu/pub/hpsl/papers/papers-pdf/ngs07.pdf.

[3]ArmbrustM,FoxA,GriffithR,etal.Aviewofcloudcomputing[J].CommunicationsoftheACM,2009,53(4):50-58.

[4]CarreteroJ,XhafaF.Usegeneticalgorithmsforschedulingjobsinlargescalegridapplications[J].TechnologiesandEconomicDevelopmentofEconomy,2006,12(1):11-17.

[5]BuyyaR,RanjanR,CalheirosRN.ModelingandsimulationofscalablecloudcomputingenvironmentsandtheCloudSimToolkit:challengesandopportunities[C]//Proceedingsoftheseventhhighperformancecomputingandsimulationconference.NewYork,USA:IEEEPress,2009:21-24.

[6]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[C]//Proceedingsofthe6thsymposiumonoperatingsystemdesignandimplementation.NewYork:ACM,2004:137-150.

[7] 王小平,曹立明.遗传算法[M].西安:西安交通大学出版社,2002.

[8] 李建锋,彭 舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011,31(1):184-186.

[9] 朱宗斌,杜中军.基于改进GA的云计算任务调度算法[J].计算机工程与应用,2013,49(5):77-80.

[10] 叶春晓,陆 杰.基于改进遗传算法的网格任务调度研究[J].计算机科学,2010,37(7):233-235.

[11] 王春莲.基于改进遗传算法的网格任务调度算法[D].济南:山东大学,2009.

[12] 刘 愉,赵志文,李小兰,等.云计算环境中优化遗传算法的资源调度策略[J].北京师范大学学报:自然科学版,2012,48(4):378-384.

[13] 段卫军,付学良,王 芳,等.云计算环境下融合遗传算法和蚁群算法QoS约束任务调度[J].计算机应用,2014,34(S2):66-69.

[14] 邹伟明,于 炯.云计算环境下基于用户满意度的遗传算法[J].计算机应用研究,2014,31(1):85-88.

A Task Scheduling Algorithm Based on Improved Genetic Algorithm in Cloud Computing Environment

HU Yan-hua1，TANG Xin-lai1,2

(1.Department of Electrical and Computer Engineering,Lushan College of Guangxi University of Science and Technology,Liuzhou 545616,China; 2.Office of Academic Affairs,Guangxi University of Science and Technology,Liuzhou 545616,China)

Task scheduling mechanism is one of the core issues in cloud computing.The task scheduling algorithm in cloud computing requires improvement of the system throughput and the largest span while considering resources security and load balancing problems.As a classical task scheduling algorithm with powerful and implicit parallel space search capability,genetic algorithm is widely used in cloud computing.However,it has many deficiencies,such as slow convergence and premature with the increasing calculation scale.Min-Min algorithm and Max-Min algorithm are simple and practicable with better makespan,which can well make up the deficiencies of traditional genetic algorithm.On this basis,an improved algorithm is put forward,which introduces Min-Min algorithm and Max-Min algorithm in the process of population initialization,and uses the minimizing makespan and the load balancing of resource as double-fitness function meanwhile.The simulation shows that this algorithm can elevate the quality of initial population,the search capability and the convergence rate,which is more efficient.

cloud computing;genetic algorithm;task scheduling;Min-Min algorithm;Max-Min algorithm

2015-12-22

2016-04-12

时间：2016-09-19

广西壮族自治区自然科学基金项目(2013GXNSFAA019347);广西科技大学鹿山学院科学基金项目(2015LSKY05)

胡艳华(1980-)，女，硕士研究生，讲师，研究方向为云计算和计算机网络；唐新来，博士，教授，研究方向为云计算。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0839.010.html

TP393

A

1673-629X(2016)10-0137-05

10.3969/j.issn.1673-629X.2016.10.030