改进的遗传算法在云资源调度上的应用*

李勋章 王如月* 莫静容

(桂林航天工业学院 计算机科学与工程学院，广西 桂林 541004)

近年来，云计算已发展成为一种高效的分布式平台。云计算在基础设施和基础设施成本降低中起着重要作用。当今的云计算服务提供商会根据他们的需求为不同的用户提供不同的服务模型。这些服务模型具有成本效益，并对其用户的资源使用产生重大影响。在大多数情况下，资源的分配和调度对于减少资源浪费很重要。文献[1]针对云资源分配调度浪费问题，运用NSGA-II的优化算法，提出了一种资源分配和调度框架，与传统的遗传算法相比，该框架改善了资源分配，调度，分配速度，减少了不可用请求。众所周知，与云平台相关的主要问题是任务调度。在云计算中为任务分配合适的VM是一项艰巨的任务。提出了许多算法来优化云环境中的调度过程。 现有算法具有其自身的缺点。文献[2]提出了一种混合模型，该模型使用分层过程对任务进行优先级排序，然后再提交给调度程序。通过添加Bar系统模型来修改带宽感知可分任务(BAT)调度模型，以开发混合优化机制。使用不同的参数评估了提出的混合模型的性能。最后通过仿真结果证明了混合模型的有效性[3]。

1 云资源调度问题描述及求解模型

在云数据中心中，系统中的租户将要执行的任务提交到数据中心，然后数据中心运用相应的资源调度算法将租户的任务准确快速的执行完，从数据中心的角度来看，他们是希望在确保租户任务计算结果准确的前提下，数据中心花费的资源越少越好。为描述和解决这一问题，我们建立的模型表述如下所示。

一般情况下，云数据中心通过创建虚拟机的方式给系统中的租户提供服务，租户也是将要执行的任务提交到虚拟机中，假设云数据中心中有m台虚拟机，即V={V1,V2,V3,…,Vm},基于成本考虑，云数据中心租给租户的虚拟机的配置是不一样的，有的虚拟机配置高运算速度快，有的虚拟机配置低运算速度慢，假设每台虚拟机的运算速度为Pi(每秒执行指令的次数)，当然与此同时每台虚拟机每秒消耗的资源也不一样，假设每台虚拟机V1每秒消耗的资源为PVi,假设云数据中心中的租户一共有L个任务待执行，即L={L1,L2,L3,…,Ln},假设这些任务相互独立，不存在先后关系，并且每个任务Lj需要的运算量Wj也不一样，因此，现在要解决的问题是，在确保任务计算准确的前提下，如何让数据中心消耗更少的资源，使租户的L个任务，在这m台虚拟机上快速地执行完。

(1)

云数据中心完成租户所有的任务，需要消耗的资源PPw可表示为式(2)

(2)

此外， 一个任务Lj( 1

(3)

最后，还必须保证任何一个任务Lj( 1

(4)

云资源调度的目标就是最小化消耗资源PPw， 因此，云资源调度的求解模型可用下式(5)表示：

(5)

该云资源调模型为带有约束条件的单目标优化问题求解模型，下面针对这一问题进行算法求解[4]。

2 联合进化的遗传算法

2.1 编码与解码

传统的遗传算法的编码方式主要有二进制编码和实数编码[5]，本文采用的是实数编码，假设染色体的长度和云数据中心的任务数量是相同的，假定云数据中心的任务数量和染色体的长度都为n，即S=[s1,s2,s3,…,sn]。染色体中基因位Si(1≤i≤n)的取值为虚拟机的编号。Si的值表示任务Lj被分配到虚拟机Vsi上去执行。假设，云数据中心中有200个任务L1,L2,…,L200；有5(m=5)台虚拟机V1,V2,V3,V4,V5。假设一个染色体(个体)S=[s1,s2,s3,…,s200)]= [2,3,1,1,3,2,2,1,1,3,…,3,4]，则表示的具体含义为，任务L1被分配到虚拟机V2上执行，任务L2被分配到虚拟机V3上执行，任务L3被分配到虚拟机V1上执行，…，任务L200被分配到虚拟机V4上执行。

2.2 适应度函数选取

对于遗传算法而言，适应度函数的选取是至关重要的，它直接影响到最后的结果[6]。正常情况下，大多数都是选取目标函数作为适应度函数[7]，本文同样也是选取目标函数作为适应度函数，故我们的适应度函数fitness为式(6)

(6)

2.3 联合进化机制

本文的算法通过将种群分为O_pop优选子种群和G_pop普通子种群。优选子种群中的个体数量占个体总数的30%，普通子种群中的个体占个体总数的70%。具体步骤如下：

1)优选子种群O_pop的进化。随机选择M/2(M为优选子种群的大小)优选个体，将其与剩下的m/2个个体进行随机交叉操作，生成的个体以pm概率进行变异操作，然后将其插入到辅助种群p'中。

2)优选子种群O_pop与普通子种群G_pop的联合进化。从G_pop中随机选择出(Pop - m)个优选个体， 从G_pop中随机选择出(Pop - m)个普通个体，优选个体与普通个体两两相互配对完成交叉操作，生成的个体再以pm概率进行变异，最后插入到辅助种群p'中。

联合进化机制可以充分发挥优选个体在引导种群进化中的核心作用，也可保证种群有很好的多样性。待辅助种群p'完成创建后，将其与种群p(e)合并形成下一代种群p(e+1)。

2.4 JCGA算法描述

联合进化遗传算法JCGA的基本思想如算法1所示。

算法1联合进化遗传算法JCGA

Step 1. 令e=0, 生成初始化种群p(e)，对p(e)中的个体根据式(6)计算适应度值, 选择适应度值最高的前m/3个个体放入O_pop中，适应度值最高的个体为 H_f。

Step 2. 根据式(6)计算p(e)中每个个体与最佳个体H_f的适应度值，分别将适应度值最小的m/3个体和适应度最大的m/3个个体放入O_pop中。

Step 3. 将p(e)中剩下的个体放入G_pop中。将O_pop中的个体随机两两组队进行交叉操作，生成的新个体以pm概率进行变异操作，然后将其插入到辅助种群p’中。

Step 4. 分别随机从O_pop中挑选出(Pop - m)个优选个体，从G_pop中挑选出(Pop - m)个普通个体，两两组合进行交叉操作，生成的个体以Pm概率变异后插入到辅助种群Pop’中。

Step 5. 将O_pop中的个体放入下一代种群p(e+1)中.以适应度值为基础，以轮盘赌的方式从辅助种群p’中选择(Pop - M)个个体放入下一代种群p(e+1)中。

Step 6. 令e=e+1.判断是否满足终止条件，若是, 则结束; 否则, 转到Step 2。

3 实验与结果分析

本文使用C语言对联合进化的遗传算法、精英保留策略GAE、传统的遗传算法GA进行了模拟仿真测试。并在相同的软硬件环境下，通过实验结果对比分析本文各对比算法的性能。表1给出了实验过程中各对比算法所用到的参数取值情况。

表1 实验中参数的取值

在对比实验中，我们假设云数据中心中虚拟机的数量为5个即V={V1,V2,V3,V4,V5}，其对应的运算速度Pi(1≤i≤5)分别为{10,35,60,85,110}，其每秒消耗的资源PVi(1≤i≤5)分别为{10,25,40,55,70}。系统中的租户任务数量分别取值为100、200、300、400、500、600和700时，用GA、GAE和JCGA求解任务的最小资源消耗，然后比较哪个算法可以得到更优的解。其中，每个任务Lj的计算量Wj的大小(需执行的机器指令的条数)在5～3 500之间以5的倍数即{5,10,15,…,3 500}进行取值。对每个算法都随机运行30次，求解出任务的最小资源消耗，最终的实验结果如表2所示。

表2 虚拟机格式为5租户资源消耗

从表2中可以看出，当虚拟机的个数为5时，随着租户任务数量的增加，三个算法计算出的资源消耗都在逐步递增，但总的来看，本文提出的JCGA算法增长的幅度是最慢的，而且在相同的任务数的情况下，本文的JCGA算法计算出资源消耗都是最小的。

将云计算系统中虚拟机的数量设置为50个即V={V1,V2,V3,…,V49,V50}将其对应的运算速度Pi(1≤i≤50)分别设置为{10, 35, 60,…, 1 210, 1 235}，其每秒的消耗的资源PVi(1≤i≤50)分别为{10, 25, 40,…, 730， 745}。系统中的租户任务数量分别取值为100、200、300、400、500、600和700时，其中，每个任务Lj的计算量Wj的大小(需执行的机器指令的条数)在5～3 500之间以5的倍数进行取值,即{5,10,15,…,3 500}。然后求解任务的最小资源消耗，其结果如表3所示。

表3 虚拟机格式为50租户资源消耗

从表中可以看出，随着虚拟机的个数增多，三个算法计算出的资源都在递减，但总的看来，本文提出的JCGA算法计算的资源消耗依旧是最小的。

将云计算系统中虚拟机的数量设置为500个即V={V1,V2,V3,…,V49,V500}将其对应的运算速度Pi(1≤i≤500)分别设置为{10, 35, 60,…, 12 460, 12 485}，其每秒的消耗的资源PVi(1≤i≤500)分别为{10, 25, 40,…, 7 470， 7 485}。系统中的租户任务数量分别取值为100、200、300、400、500、600和700时，其中，每个任务Lj的计算量Wj的大小(需执行的机器指令的条数)在5～3 500之间以5的倍数进行取值,即{5,10,15,…,3 500}。然后求解任务的最小资源消耗，其结果如表4所示。

表4 虚拟机格式为500租户资源消耗

从表中可以看出，随着虚拟机的个数增多到500时，三个算法计算出的资源依旧都在递减，这说明三种算法都很稳定。但总的看来，本文提出的JCGA算法计算的资源消耗依旧是最小的。

4 结束语

传统的遗传算法GA在进行云资源调度时容易出现算法早熟收敛，种群多样性差，易陷入局部最优等问题。本文提出了一种联合进化的遗传算法JCGA，用于解决云资源调度问题。实验结果说明我们提出的联合进化的遗传算法具备很好的性能。在进行云资源调度时，联合进化的遗传算法求解出的最终解总是优于另外两个算法的最终解，其寻找最优解和跳出局部最优的能力表现得十分明显，鲁棒性更好。