一种用于云计算资源调度的改进遗传算法

刘　峰，毕　利，杨　军

（1.宁夏大学数学计算机学院，银川　750021；2.宁夏大学计算机网络管理中心，银川　750021）

一种用于云计算资源调度的改进遗传算法

刘峰1，毕利1，杨军2

（1.宁夏大学数学计算机学院，银川750021；2.宁夏大学计算机网络管理中心，银川750021）

针对轮询调度算法、遗传算法和模拟退火算法在云计算资源调度中存在收敛速度慢、易早熟和资源负载不均衡等问题，提出了一种基于模拟退火思想的改进遗传算法（simulated annealing improved genetic algorithm：SAIGA）；改进算法设计了基于任务平均完成时间和负载均衡的双适应度函数和自适应的交叉变异概率函数，允许算法在退火过程中以一定概率接受劣质解从而避免早熟现象的发生，将虚拟资源上任务分配数的标准差作为选择个体的依据来实现节点的负载均衡；仿真结果表明，改进算法与上述算法相比，在任务平均完成时间、资源利用率以及收敛速度上表现得更优越，能够较快地找到资源最优调度方案，具有较好的可行性和实用性。

云计算；轮询调度；模拟退火思想；改进遗传算法；负载均衡

0　引言

云计算作为继网格计算、并行计算和分布式计算之后的新兴计算模式，被高校、科研机构以及商业组织进行了大量的研究。中国网格计算、云计算专家刘鹏给出如下定义：“云计算将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根据需要获取计算力、存储空间和各种软件服务［1］”。然而，云计算服务的核心问题是资源的调度，其服务质量的好坏取决于调度效率的高低，因此资源调度一直是云计算研究领域重点和难点［2］。

传统资源调度算法大都是一些静态算法，如贪心算法、轮询调度算法等，这类方法对于少量任务的调度可以获得较好的调度方案。随着任务数的不断增加，云计算系统的复杂性增大，传统方法存在任务完成时间过长、节点间负载不均衡和资源利用率低等缺点［3-4］。目前，人工智能技术的日趋成熟，智能算法越来越多地被用于资源调度中，成为当前研究的热点。

刘瑜等［5］提出了基于最优跨度和负载均衡改进遗传算法的资源调度策略，考虑到云计算任务的数量大和复杂性，设计了基于资源数的编码方式，在算法接近收敛阶段自适应调节最优跨度适应度函数来提高算法的收敛速度。袁浩等［6］提出了一种基于社会力群的智能优化算法，通过模拟人群的拥挤退让行为寻找使任务总时间最小的调度方案。徐文忠［7］等提出了一种新的基于遗传算法的关于虚拟机负载均衡的调度策略，但没有考虑到任务平均完成时间指标，不能满足用户对任务响应时间的需求。李建锋等［8］设计了双适应度函数去优化资源调度过程，寻求使总任务完成时间和任务平均完成时间都较小的调度方案，并取得了不错的效果。薛玉［9］提出一种基于混沌粒子群算法的云资源调度模型，把资源的负载均衡度作为要优化的目标函数，在寻优过程中人工引入混沌机制对粒子进行扰动，通过粒子间的信息交流与共享，寻求调度最优解。邬海艳［10］提出了基于元胞自动机模型改进遗传算法用于云资源调度，其主要作用于遗传算法的选择和交叉操作中，根据演化规则自适应调节元胞与邻居元胞的状态，获取最大适应度值个体。Gao等［11］提出一种以任务完成时间、系统吞吐量为优化目标的蚁群算法构建云计算资源调度模型，在任务总完成时间上取得不错的效果，但资源的利用率不高。Zhan Zhi-Hui等［12］提出了基于Min-min和上Max-min方法的负载均衡感知遗传算法（LAGA），通过在适应度函数中引入时间负载均衡模型（TLB）选择优势个体，生成资源节点负载更均衡的调度方案，仅考虑了资源的负载情况，却对牺牲了算法的收敛速度。

针对以上问题，本文结合模拟退火的思想来改进遗传算法在云计算资源中的调度，提出了基于任务平均完成时间和负载均衡的双适应度函数，设计自适应的交叉和变异概率函数，使算法在寻优时以一定概率接受劣质解，减小改进算法收敛到局部最优解的可能性，同时采用基于资源节点数作为染色体的总长度，每个资源所映射的任务总数和任务编号作为基因值的编码方式，加快了算法的收敛速度，提高了算法的寻优能力。

1　云计算资源调度问题描述

在云计算平台上，管理者利用虚拟化技术把计算机的物理资源抽象为统一的虚拟资源，统一的虚拟资源又被分配到相互独立的虚拟机上，而云计算中的资源调度问题就是利用一种调度策略把大量的计算任务分配到虚拟机上，实现虚拟资源的最大化利用。具体的讲，就是如何把云计算中大量的计算任务根据一定的调度策略分配到最佳虚拟资源上，保证最少的任务完成时间和最大的资源利用率，云计算资源调度管理模型如图1。

图1　云计算资源调度管理模型

云计算资源调度包括数据中心D=｛d1，d2，…，dm｝

虚拟资源V=｛vm1，vm2，…，vmm｝、计算任务T=｛t1，t2，…，tn｝以及它们之间的映射关系。云计算资源调度模型可描述为：S=｛T，V，D，Mtv，Mvd｝（1）式中，Mtv为任务与虚拟资源之间的映射关系，Mvd为虚拟机与数据中心的之间的映射关系。根据上述用户任务-虚拟资源之间的映射关系，本文用二维数组统计每个任务在每个虚拟资源上的预计完成执行时间ETC（Excepted Time To Completion）。

其中：ETCij=cloudlet［i］.length/vm［j］.mips，表示第i个任务在第j个资源上的预计执行时间。设Start（i，j）为任务ti在vmj上的开始执行时间。则ti在vmj上的完成时间见式（3）。Finish（i，j）=Start（i，j）+ETCij（3）那么vmj上全部任务的完成时间见式 （4）（5）。

式（5）中，cij=1表示任务ti在vmj上执行，cij=0表示ti不在vmj上执行。

对于用户全部计算任务T= ｛t1，t2，…，tn｝的任务平均完成时间见式（6）。

对于云计算资源的调度问题，即求使式（6）值最小的解，因此本文的目标函数见式（7）。

2　遗传算法与模拟退火思想的融合设计

2.1模拟退火思想

2.2基于模拟退火思想的改进遗传算法设计

2.2.1染色体编码与种群初始化

在任务调度的问题中，传统遗传算法通常将任务总数作为染色体基因串的长度，每个任务对应的资源ID作为染色体的基因值。但是云计算环境中任务的总数远远大于资源节点的个数，如果把任务总数作为染色体基因串的长度，会导致算法收敛速度慢，找到最优解的时间过长。因此本文对染色体的编码方式进行了改进，将资源节点的数量作为染色体基因串的长度，每个资源所映射的任务总数和任务编号作为染色体基因值，这种编码方式可以加快算法的收敛速度。本文采用资源——任务的间接编码方式，先对染色体进行预编码，设有n个任务，M个资源节点，如下产生一条染色体。

｛3，1，1，2，3，…，m-1，m，m-1｝

表示第1、5个任务分配到第3个资源上，第2、3个任务分配到第1个资源上，第n-2，n-1个任务分配到第m-1资源上，第n个任务分配到第m个资源上。接着对该染色体进行二次编码，则染色体基因串的长度为资源总数m，染色体基因值为每个资源节点分配任务的总数和任务ID，二次处理后的染色体见表1。

表1　二次处理后染色体的编码方式

在对染色体进行编码后，接着对种群进行初始化，本文采用随机方式产生N个染色体。

2.2.2基于任务平均完成时间和负载均衡的双适应度函数设计

基于任务平均完成时间的适应度函数见式（9）。

式（9）表示第k个染色体上所有任务在节点j上平均执行时间。在任务调度的过程中，我们还需要考虑资源负载均衡问题，节点负载较均衡使得资源利用率较高，避免计算能力高的节点出现负荷同时能力低的节点被闲置。采用资源节点上任务分配数的标准差来衡量节点的负载均衡问题，设任务数为n，资源节点数为M，则每个资源节点上平均分配的任务数为资源节点任务分配数标准差的适应度函数见式（10）。

其中：Assign_tasksk，i表示第k个染色体上的第i个资源节点所分配到的任务数。

所以，本文设计基于任务平均完成时间和负载均衡的双适应度函数见式（11）。

ω1和ω2分别是基于最小完成时间和任务分配数标准差适应度函数的权重。用户根据自己的偏好决定每个适应度函数的权重，且满足ω1+ω2=1。

2.2.3选择算子设计

在选择算子的设计采用改进的轮盘赌方法。首先根据式（9）计算每个染色体的适应度值，然后计算该适应度值相对于整个种群适应度值总和中所占的比例，即该个体被复制到下一代中的概率。则个体k被选中的概率见式（12）。

2.2.4交叉和变异算子设计

本文采用模拟退火的思想对个体进行交叉操作，种群中较优个体以较低概率进行交叉，增加种群中“弱势”个体的交叉可能性，提高种群的多样性，使算法陷入局部最优解的可能性减小。交叉概率函数见式（13）。

其中：favg表示每代群体的平均适应度值，f2，f1分别表示随机选择的两个个体中适应度值的较大者与较小者。α为退火系数，T为算法当前迭代的温度。当适应度函数值较大时 （f2＞f 1＞favg），这时让交叉概率Pc变小，防止较优的个体被破坏，同时较小的交叉概率能加快种群向最优解收敛。当适应度函数值较小时（f1＜f2＜favg），使交叉概率变大，期望重组出新的个体。交叉算子有利于在全局范围内找到较好的个体，容易出现在最优解附近徘徊的现象，对局部解空间的寻优能力较差，使用变异算子可以微调个体的基因值，提高全局的收敛精度，个体的变异概率函数见式（14）。

其中，f′表示随机选择的个体适应度函数值，favg表示种群适应度的平均值。当随机选择个体的适应度值大于平均适应度值时（即f′＞favg），根据上面的公式，f′越大，种群中个体的变异概率则越小。这样可以在很大程度上避免较优个体的结构被破坏。

2.2.5算法终止条件

当连续60代适应度函数值无变化或者进化代数达到200次时，终止算法的执行。

本文使用均匀交叉、多点交叉相结合的实现方式，变异方式使用基因值变异。最后基于模拟退火的改进遗传算法（SAIGA）流程图如图2所示。

图2　改进算法的流程图

3　仿真实验

3.1仿真环境

在Intel.Core2四核2.83 GHz CPU，4 G RAM，操作系统为Windows7 32 bit，采用CloudSim3.0软件对算法进行仿真，其核心是中心代理人和虚拟机调度策略，改进算法通过扩展Datacenter Broker和VMAllocationPolicy类实现云资源调度的模拟。

3.2对比算法

本文选择轮询调度算法（RR）、遗传算法（GA）和模拟退火算法（SA）做对比实验，分析比较4种算法在任务总完成时间、任务平均完成时间、负载均衡以及收敛速度方面的优劣性。GA、SA和SAIGA算法的参数设置见表2。

表2　GA、SA及SAIGA算法参数设置表

3.3结果与分析

实验中模拟任务的长度MI取1 000～20 000之间，资源的运算能力MIPS取500～5 000之间，分析任务数和虚拟资源数的变化对任务总完成时间、平均完成时间以及资源负载均衡的影响。

1）将任务分配到10个资源节点，改变任务的数量从10到200，记录任务的总完成时间（ms），结果见表3，图3。

表3　资源数一定，不同任务数下的完成时间

图3　资源数一定，不同任务数下的总完成时间

从图3可以看出，在任务数不多时，4种算法下任务的完成时间差别不大，这是由于初期资源节点的数量和任务的数量差别不大，节点有足够的能力去处理这些任务。随着任务数的增多，特别地当任务数大于150时，SAIGA算法调度下的任务总完成时间明显优于其他3种算法。

2）当任务数量固定为1 000时，改变虚拟资源的数量，从10到50，记录任务的平均完成时间如图4。

从图4可以看出，在虚拟资源数较少时，SAIGA的任务完成时间远远小于RR、GA和SA。随着虚拟资源数量的增加，4种算法下任务的完成时间都在不断减少，最后SAIGA、GA和SA算法的任务平均完成时间大致接近，这是由于随着资源节点数量的增加，其处理能力能够逐渐满足任务的执行需求，任务抢占资源的情况减少。

3）任务数为1 000时，将任务分配到5个资源节点（R1，R2，R3，R4，R5）上，设置其处理能力分别为：（1 200， 900，600，1800，800）MIPS，记录5个资源节点上的负载情况如图5。

图4　不同资源数下任务的平均完成时间

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

从图5可以看出，在资源计算能力有较大差异的情况下，SAIGA算法的分配的任务数更加均衡，而RR没有考虑到节点能力的差异性，采取了均分任务的方式，GA、SA中则出现计算能力高的节点分配到任务数较多，计算能力低的节点分配到的任务数较少的现象。总之，SAIGA算法在资源节点的负载均衡方面表现出较好的优越性。

4）任务数为1 000时，资源节点为40时，GA和SAIGA算法的迭代收敛情况如图6。

图6　SAIGA和GA算法收敛结果比较

从图6可以看出，在算法迭代初期GA和SAIGA性能差不多，但由于SAIGA采用任务总数加编号的方式作为染色体的基因值，使它后期的收敛速度加快。SAIGA算法在迭代120次后开始收敛，而GA算法在接近160代时才出现收敛的趋势，在收敛精度上改进算法提高了近130秒。另外，GA算法迭代大约至60代时出现一些适应度值超常的个体误导了种群进化的方向，但这些个体并不是算法最优解。由于SAIGA采用自学习的交叉概率函数，在算法接近收敛的阶段对超常适应度值的个体进行了一定概率的调整，避免误导了种群的进化方向，使得改进算法更快地收敛到最优解。

4　结束语

针对云资源调度的动态性、实时性等特点，提出了一种基于模拟退火思想的改进遗传算法SAIGA。该算法比GA、SA和RR在任务平均完成时间上分别缩短了11%，25%和56%，在算法的收敛精度和速度上都有显著的提高，收敛速度上提高了40代左右，能够有效避免超常个体误导种群的进化方向和算法陷入局部最优，同时改进算法能够较均衡地分配任务到各个节点上，提高了资源的利用率。因此，改进算法更加适合云环境下的资源调度，具有较好的实用性。

［1］刘鹏.云计算［M］.北京：电子工业出版社，2011.

［2］Armbrust M，Fox A，Griffith R，et al.A View of Cloud Computing［J］.Communications of the ACM，2010，53（4）：50-58.

［3］Caballer M，Blanquer I，MoltóG，et al.Dynamic Management of Virtual Infrastructures［J］.Journal of Grid Computing，2015，13（1）：53-70.

［4］林伟伟，齐德昱.云计算资源调度研究综述［J］.计算机科学，2012，39（10）：1-6.

［5］刘愉，赵志文，李小兰，等.云计算环境中优化遗传算法的资源调度策略［J］.北京师范大学学报（自然科学版），2012，48（4）：378-384.

［6］袁浩，李昌兵.基于社会力群智能优化算法的云计算资源调度［J］.计算机科学，2015，42（04）：206-208.

［7］徐文忠，彭志平，左敬龙.基于遗传算法的云计算资源调度策略研究［J］.计算机测量与控制，2015，23（5）：1653-1656.

［8］李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法［J］.计算机应用，2011，31（1）：184-186.

［9］薛玉.云计算环境下的资源调度优化模型研究［J］.计算机仿真，2013，30（5）：362-365.

［10］邬海艳.基于云计算环境下资源调度算法研究 ［D］：赣州：江西理工大学，2012.

［11］Gao Y，Guan H，Qi Z，et al.A multi-objective ant colony system algorithm for virtual machine placement in cloud computing［J］.Journal of Computer and System Sciences，2013，79（8）：1230-1242.

［12］Zhan Z H，Zhang G Y，Ying L，et al.Load Balance Aware Genetic Algorithm for Task Scheduling in Cloud Computing［A］.In：Dick G，Browne W，Whigham P，Zhang M，Bui L，Ishibuchi H，Jin Y，Li X，Shi Y，Singh P，Tan K，Tang K，editors.Simulated Evolution and Learning［C］.Springer International Publishing，2014：644-655.

［13］Gall J，Rosenhahn B，Seidel H P.An Introduction to Interacting Simulated Annealing［A］.In：Rosenhahn B，Klette R，Metaxas D，editors.Human Motion［C］.Springer Netherlands，2008：319-345.

［14］S K，P VM.Optimization by simmulated annealing［J］.science，1983，220（4598）.

An Improved Genetic Algorithm for Cloud Computing Resource Scheduling

Liu Feng1，Bi Li1，Yang Jun2
（1.School of Mathematics and Computer Science，Ningxia University，Yinchuan750021，China；2.Network Administration Center，Ningxia University，Yinchuan750021，China）

For Round-Robin scheduling algorithm and genetic algorithm and simulated annealing algorithm in cloud resource scheduling having shortcomings，such as slow convergence speed，easy to premature and the imbalance of the resource load，the paper proposed the improved genetic algorithm combined with simulated annealing thought（Simulated Annealing Improved Genetic Algorithm：SAIGA）.The improved algorithm gave a dual fitness function based on task average completion time and load balance and adaptive crossover mutation probability function.It allowed the algorithm in the annealing process to accept inferior solution with a certain probability to avoid prematurity phenomenon occurs.We regarded the virtual machine task allotment standard deviation as the basis of individual choice to realize the resource node load balancing.Simulation experiments showed that the improved algorithm is more superior on average task completion time，resource load balancing，and the convergence rate.It can rapidly find the optimal scheduling scheme and has good feasibility and practicability.

cloud computing；round robin scheduling；simulated annealing thought；improved genetic algorithm；load balancing

1671-4598（2016）05-0202-05

10.16526/j.cnki.11-4762/tp.2016.05.057

TP393

A

2015-11-09；

2015-12-11。

国家自然科学基金项目（61261001）；教育部科学技术研究重点项目（212189）。

刘峰（1989-），男，山东菏泽人，硕士研究生，主要从事智能调度算法方向的研究。

毕利（1968-），女，宁夏银川人，教授，硕士生导师，主要从事数据挖掘及组合优化控制方向的研究。

杨军（1972-），男，宁夏吴忠人，教授，硕士生导师，主要从事云计算资源调度及无线传感器网络方向的研究。