基于改进混合遗传算法的云资源调度算法

黄海芹，林基明，王俊义

(桂林电子科技大学 广西信息实验中心，广西 桂林 541004)

基于改进混合遗传算法的云资源调度算法

黄海芹，林基明，王俊义

(桂林电子科技大学 广西信息实验中心，广西 桂林 541004)

在云计算中，系统规模和虚拟机迁移数量都是十分庞大的，需要高效的调度策略对其进行优化。将云计算的任务分配抽象为背包求解问题，可通过遗传算法进行求解。传统的遗传算法具有局部搜索能力差以及早熟现象的缺点，采用遗传和贪婪相结合的混合遗传算法。针对混合遗传算法在资源利用率与能源消耗的收敛速度较慢问题，通过改进适应度函数，改变了适应度函数在不同染色体间的差异度，从而提高了染色体在选择算子中的择优性能。仿真结果表明，该方法能够有效提高混合遗传算法在云计算资源优化中的收敛速度。

云计算；资源调度；混合遗传算法

随着云计算[1]技术的日趋成熟，与之相关的服务和应用也在逐年递增，使得云计算环境下的服务器数量高速增长。因此，如何合理地分配这些资源来提高云计算系统的整体性能和效率，是云计算的一个关键性问题。

目前，在云计算环境下基于遗传算法的资源调度问题已经进行了大量研究工作。文献[2]提出一种双适应度的遗传算法，通过两个适应度函数来选择种群，从而保证较短的总任务执行时间和任务平均执行时间。由于云计算的中心思想，是实现廉价高效的运算，对整个系统进行负载均衡研究是十分重要的。文献[3]通过自适应的变异概率，对任务响应时间和资源损耗代价同时进行优化。不但最短化任务执行时间，而且使虚拟机群的资源利用率最高。但未解决传统遗传算法局部搜索能力差以及早熟现象等问题。因此从改变染色体的编码方式出发，文献[4]采用组方式和三空间分割方法分别对染色体进行编码和译码，并根据不同染色体长度的变化设计交叉和变异遗传算子，算法对解空间内的多个区域同时搜索，具有群体和自我进化的优势，优化一次即可获得对不同目标的权值运算多次才能得到的最优解，提高了获得最优解的速度。文献[5]基于负载均衡度和最优跨度准则，改进了染色体编码方式，这种编码方式所形成的基因串的总数小于系统资源池内的总数，所以在计算过程中可以达到最优的资源调度，从而达到提高计算速度和计算准确度的目的。从初始化种群出发，文献[6]通过染色体匹配率将种群个体均匀分布在解空间上，有效地避免了早熟问题；并通过对作业运行时间、费用、系统带宽以及服务质量的子适应度函数加权获得总适应度函数，并通过调节权值系数来满足不同用户需求。从混合遗传算法出发，文献[7]使用了多Agent与遗传算法相结合的混合遗传算法，通过个体之间的交互、协作和自学习，在解决负载均衡问题的同时具有更好的算法收敛性能。文献[8]提出了将贪婪和遗传算法相结合的混合遗传算法，对每个染色体都通过贪婪算法进行处理，达到内存使用量最小，同时能够在较短的时间内找到问题的优化解。但这种使得内存使用量最小的方法依然会出现局部最优解的可能。文献[9]同样采用了贪婪与遗传算法相结合的方式，这里贪婪算法只对无效染色体进行处理，将物理机使用数量引入总适应度函数，可降低局部最优解的出现。并分别从物理机使用数量、负载均衡度和迁移次数3个方面进行加权组合，对资源利用率、能源节约和迁移代价多目标问题进行联合优化。但负载均衡度和迁移次数的适应度函数在不同染色体间的差异度不足，限制了算法的收敛速度；同时只通过物理机数量来衡量内存使用量是不完善的。

针对文献[9]的不足，本文提出了以下两个改进方法：一是对其适应度函数进行改进，从遗传算法染色体选择性出发，通过提高染色体间的优选概率，进而提升遗传算法的收敛速度；二是提出了内存适应度函数，将其与物理机数量适应度函数相结合，增加相同物理机数量染色体间内存使用量的差异度，进一步提高内存使用率的同时，也提高了选择算子中的择优性能。仿真结果表明，该方法能够有效提高遗传算法的收敛速度。

1 总体架构调度系统模型

任务上传到云端的数据中心，数据中心的调度器响应该任务，将其随机分配给物理机PM，并在PM上建立相应的虚拟机VM来执行该任务。由于应用程序信息的不确定性以及PM处理能力的差异性，导致了PM负载不均衡，因此需要实施高效的调度策略，通过迁移VM技术来协调不同PM上的负载，提高资源利用率，同时也降低系统能耗。调度系统模型示意图，如图1所示[10]。

图1 调度系统模型示意图

通过云端的检测模块，检测初始负载信息和VM的配置信息。然后执行调度策略，得到新的配置方案。将其与原配置方案进行比较，是否提高资源利用率。具体通过以下指标进行判断：PM的使用数量和使用的PM负载均衡度。由于通过迁移VM技术来执行调度策略的结果，所以还需要考虑VM迁移成本。若迁移成本太高，则不执行调度算法；反之执行调度算法。

2 混合遗传算法

为了解决云端资源优化问题，可采用基于多维混合遗传算法的资源调度策略[9]。算法考虑了3个评价指标，包括PM使用数量、负载差异度和VM迁移次数。并将其进行加权组合，实现了权值可调的多目标优化。

2.1 混合遗传算法

混合遗传算法执行过程如图2所示。

图2 混合遗传算法流程图

1)选取种群数目P，种群中的个体称为染色体。每个染色体代表着一种VM配置方案，即将所有VM分配在哪些PM上。

2)计算种群中每个个体的适应度函数值。

3)选择：通过适应度函数值得到累积概率，进行染色体的选择。

4)交叉：采用单点交叉法，即随机设置一个交叉点，在该点相互交换部分染色体。

5)修正无效因子：由于每个PM内存是有限的，这样经过交叉后的染色体，可能会产生无效因子，此时通过贪婪算法对无效因子进行修正。

6)变异：依据变异概率将染色体中的某个基因值用其他值替换，从而形成一个新的个体。

7)修正无效因子：同步骤5)。

8)是否达到最大进化代数，如果已是最大代数，则产生最优个体，算法结束。反之，则返回到步骤2)。

注意，为了确保当前种群中最好的个体不被交叉或变异操作破坏，将其直接保留至下一代，覆盖下一代种群中最差的个体。

2.2 适应度函数

适应度函数由3种子适应度函数组合而成，表示染色体被选择的概率。适应度函数值越高，染色体被选中的概率越大，反之，则被选中的概率越小。3种子适应度函数代表着3种评价指标，分别是对物理机使用数量、负载差异度和VM迁移次数的评价。下面进行具体描述。

1)子适应度函数Ei1

物理机数量的评价函数Ei1为

(1)

式中：pm表示云端的物理机数量；counti表示第i条染色体占用的物理机数量；p表示种群中含有的染色体数量。

2)子适应度函数Ei2

则第k个物理机的负载差异度为

(2)

则第i个染色体负载差异度为

Si=∑Vk

(3)

因此，负载差异度的评价函数Ei2可表示为

(4)

3)子适应度函数Ei3

迁移次数的评价函数Ei3可表示为

(5)

4)子适应度函数Ei

Ei为总适应度函数，其将3个子适应度函数进行加权求和

Ei=xEi1+yEi2+zEi3

(6)

式中：x，y和z分别为Ei1，Ei2和Ei3的权重系数，且x+y+z=1。通过改变这3个系数的值来调节评价指标所占的权重。

2.3 评价函数的差异度

3 改进的评价函数

3.1 改进的适应度函数

(7)

其中，Smax表示种群中最大的负载差异度。

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

图3 选择概率的示意图

(16)

式中：Mi表示第i条染色体需要迁移虚拟机的次数；vm表示总虚拟机的个数。

而对于物理机数量的评价函数Ei1，其使用物理机数量的最大值即为物理机的总数量pm，因此不需要进行改动。

3.2 内存适应度函数

PM内存利用率对衡量资源利用率是一个很重要的指标。虽然贪婪算法是以内存最小化为目标修正无效因子，但是在选择最优染色体的时候，评价函数并不会因此选择内存空闲率低的染色体。图4所示为更新迭代150次后，物理机数量达到最小染色体的内存使用量。从图中可以看出，具有物理机数量最小的染色体方案不止一种，但每种方案物理机的内存空闲量是不同的，这表明评价函数不仅要考虑物理机数量，同时也应该考虑到内存使用量。所以需要选取恰当的物理机以便满足虚拟机的需求，同时还不浪费物理机的内存资源。

图4 物理机内存空闲量

1)内存利用率评价指标

(17)

式(17)为物理机内存利用率评价函数。其中，sum_pm表示云端所有物理机的内存和；Ri表示第i个染色体的闲置内存量，闲置内存量为染色体中所使用PM的总容量与所有虚拟机的内存容量之差。

总的适应度函数需要综合所有子适应度函数，原有的方法是将子适应度函数进行加权求和得到总的适应度函数Ei。但在一些情况下，这样直接进行加权求和存在一定的问题，如物理机数量越小内存空闲率就会越小，这样内存空闲率与物理机数量具有一定的相关度，如果直接进行加权，会使得总的适应度函数值偏向物理机数量和内存空闲率这两个评价指标，会造成对其他评价指标的不公平性。

(18)

(19)

4 仿真结果及分析

4.1 遗传算法收敛性

仿真参数如表1所示。

表1 仿真参数表

参数类型数值物理机数量100物理机配置类型[2048，3072，4096]虚拟机数量200虚拟机配置类型[512，1024，1536，2048]负载范围(归一化)[0 2，0 8]种群个数200更新代数150交叉概率0 8变异概率0 01

为了更好地分析物理机负载均衡度和虚拟机迁移度的收敛性能，分别取负载均衡加权系数为0.9和迁移度加权系数为0.9，对原始算法与改进算法的收敛曲线进行对比，如图5、图6所示。物理机数量变化率为最优方案与原始方案的物理机数量之比；负载均衡变化率为最优方案与原始方案的协方差之比；迁移次数变化率为最优方案的迁移次数与总的VM数量之比。

图5 负载均衡度收敛性能对比图

图6 迁移度的收敛曲线对比图

从图5、图6可以看出，随着遗传迭代次数的增加，负载均衡变化率和迁移次数变化率逐渐降低。但改进后的负载均衡度和迁移次数变化率曲线整体要低于原始的收敛性曲线，说明在相同的遗传迭代次数下，改进后的遗传算法的收敛速度比原始方法的收敛速度快，这与理论分析一致。

图7、图8所示迭代150次后，负载均衡度和迁移度随权值变化曲线。

图7 不同加权系数下的负载均衡度曲线对比图

图8 不同加权系数下的迁移次数变化率曲线对比图

从图7中可以看出，随着负载加权系数y的逐步增大，负载均衡度在Ei中的比重就会增大，所以负载均衡变化率会逐步降低。同时，从图8可以看出，随着迁移度权重z的增大，迁移次数变化率也逐步降低。但是经过改进后得到的负载均衡度曲线和迁移次数变化率曲线整体均低于改进前的负载均衡度和迁移次数变化率曲线。这表明改进后的方法在不同的加权系数下均具有更好的收敛速度。

4.2 内存使用率的收敛性

图9 内存空闲率收敛性对比图

图10 物理机使用率收敛性对比图

图11 不同加权系数下的收敛性对比曲线

5 小结

本文基于混合遗传算法在云计算资源调度中的应用，对其收敛性能进行了分析，并通过改进其评价函数，增加了适应度函数值在不同染色体间的差异度，提高了染色体的择优性。同时提出了内存使用率的评价函数，通过将物理机数量与内存使用量适应度值相结合，提升了内存的优化效率。最后通过仿真对比，表明算法的收敛速度得到了有效的提高。

[1] FOSTER I, ZHAO Y, RAICU I, et al. Cloud computing and grid computing 360-degree compared[C]//Proc. IEEE Grid Computing Environments Workshop (GCE'08). [S.l.]:IEEE Press，2008: 1-10.

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

[3] 刘漳辉,王晓莉. 云计算虚拟机群中带遗传算法的负载均衡算法[J].福州大学学报：自然科学版, 2012(4): 453-458.

[4] 李强, 郝沁汾, 肖利民, 等. 云计算中虚拟机放置的自适应管理与多目标优化[J].计算机学报, 2011(12): 2253-2264.

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

[6] 熊聪聪, 冯龙, 陈丽仙, 等. 云计算中基于遗传算法的任务调度算法研究[J].华中科技大学学报：自然科学版, 2012(40):1-4.

[7] 程国建, 刘丽景, 石彩云, 等. 一种混合遗传算法在云计算负载均衡中的应用研究[J].西安石油大学学报：自然科学版, 2012(2): 93-123.

[8] 吴世山, 翟健宏. 基于混合遗传算法的云计算任务节能调度算法[J].智能计算机与应用, 2013(6): 36-43.

[9] CHEN S, WU J, LU Z. A cloud computing resource scheduling policy based on genetic algorithm with multiple fitness[C]//Proc. 12th IEEE International Conference on Computer and Information Technology (CIT). [S.l.]:IEEE Press，2012: 177-184.

[10]GKATZIKIS L, KOUTSOPOULOS I. Migrate or not? exploiting dynamic task migration in mobile cloud computing systems[J].IEEE Wireless Communications, 2013, 20(3): 24-32.

黄海芹(1989— )，女，硕士研究生，主研通信网络的性能分析与优化；

林基明(1970— )，教授，博士生导师，主要研究方向为无线通信技术；

王俊义(1977— )，副教授，硕士生导师，主要研究方向为无线通信网络的性能分析与优化。

责任编辑：许 盈

Cloud Resource Scheduling Based on Improved Hybrid Genetic Algorithm

HUANG Haiqin, LIN Jiming, WANG Junyi

(GuangxiExperimentCenterofInformationScience,GuangxiGuilinUniversityofElectronicTechnology,GuangxiGuilin541004,China)

The size of system and the number of virtual machine migration in cloud computing are very large, for which the efficient scheduling strategy is essential. The task allocation for cloud computing can be abstracted to knapsack problem, and then is solved by genetic algorithm. The traditional genetic algorithm has the shortcoming of poor local searching ability and precocious phenomenon, which can adopt the combination of genetic and greed hybrid genetic algorithm to solve. For hybrid genetic algorithm convergence speed problem in resource utilization and energy consumption, in this paper, the fitness function is changed to increase the difference of chromosomes and improve the performance of chromosome preferred in selection operator. The simulation results show that this method can effectively improve the hybrid genetic algorithm convergence speed in cloud computing resources optimization.

cloud computing; resource scheduling; hybrid genetic algorithm

国家自然科学基金项目(61172054；61362006)；广西自然科学基金项目(2014GXNSFAA118387； 2013GXNSFAA019334)；桂林电子科技大学研究生创新项目(GDYCS201409)

TP393.01

A

10.16280/j.videoe.2015.18.009

2015-03-16

【本文献信息】黄海芹，林基明，王俊义.基于改进混合遗传算法的云资源调度算法[J].电视技术,2015，39(18).