基于多精英协同进化遗传算法的云资源调度

魏士伟 邓 维

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

0 引 言

云计算是一种新兴的信息技术，它将传统的以单机节点形式的任务处理方式转换成以网络为中心的任务处理模式，从而提高了系统扩展的灵活性，降低了硬件建设的成本[1]。用户只需将他们所要完成的任务提交到云计算系统，云计算服务提供商就可根据用户的需求快速提供计算和存储等服务，从而完成任务的执行，真正实现按需计算[2]。云计算服务提供商提供的服务通常以虚拟机(Virtual Machine,VM)的形式表示[3]。通常，云计算系统中用户的数量和用户提交的任务数量规模很大，云计算中心每时每刻都要处理海量的任务。因此，如何高效而合理地进行任务调度是云计算要解决的一个关键问题。然而，云计算任务调度问题已被证明是一个NP完全问题[4-5]。云计算系统中的节点具有异构、动态、复杂等特点，使用传统的、具有固定规则式的调度策略和算法来解这类问题会面临很大挑战。因此，在具体的工程实践中，研究人员常常用进化算法、启发式算法等来求解云资源的调度问题[6-11]，并且取得了不错的效果。虽然这些算法不能保证一定可以求解出云资源任务调度问题的全局最优解(精确解)，但其求解出来的较优解(或局部最优解)往往与精确解的差别很小，完全能够满足工程实践的需要。因此，用进化算法来解决云资源调度问题已经成为一个研究热点。

遗传算法是最经典的一种进化算法，在1975年由Holland[12]首次提出。由于其高效、隐含并行性和全局的搜索能力，以及在处理复杂的非线性问题时能自动获取和积累知识，并且自动地优化结果，因而在云计算的任务调度机制中被广泛使用。例如，文献[7]在传统遗传算法的基础上，提出了一种具有双适应度的遗传算法，减少任务执行时间。文献[8]以遗传算法为基础提出了一种任务调度模型，并通过引入服务质量标准以改进适应度函数，同时考虑到用户对调度结果的满意程度，通过采用规则约束的交叉和变异操作来提高群体中个体的质量。文献[11]在传统遗传算法的基础上，引入元胞自动机模型，提出了一种基于元胞自动机遗传算法的云资源调度算法，将元胞遗传算法应用于云环境下的资源调度问题中，用于避免遗传算法陷入局部最优问题。

上述这些GA在解决云资源调度问题时，尽管在一定程度上都能求解出相对较好的结果。但是随着求解问题的规模变大，遗传算法的搜索空间就会增大，在种群规模一定的情况下，算法搜索最优解的难度就会加大，算法在进化过程中就很容易出现搜索效率低下(种群向最优解方向移动的速度很慢)、早熟收敛(在进化前期种群虽然能快速向最优解方向移动，但在进化后期却失去了寻优能力，出现过早过快收敛现象)、易陷入局部最优(容易陷入到局部最优解且没有跳出局部最优解的能力)等问题，不易求出问题的最优解或者较好的次优解。为此，本文提出一种多精英协同进化的遗传算法(MECGA)用于解决上述存在的问题。MECGA通过适应度评价函数选出种群中适应度值大的个体，通过个体评价策略选出种群中差异度高的个体，并将它们组合成精英子种群，种群中剩下的个体则组成普通子种群。精英子种群与普通子种群进行协同交叉操作，精英子种群中适应度值大的个体可引导整个种群向最优解的方向移动；精英子种群中差异度高的个体又能够保证种群的多样性，使整个种群具备跳出局部最优解的能力。通过这种多精英协同进化的策略，MECGA具备了解决大规模云资源调度问题的能力。仿真实验表明，MECGA即使在问题规模变大的情况下，依然能够很好地解决算法的搜索效率低下、早熟收敛和易陷入局部最优等问题，相对于其他GA在解决大规模云资源调度问题时具有更优的性能。

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

在云计算环境下，系统中的用户把要执行的任务提交到云计算中心，云计算中心根据相应的调度算法为每个任务分配合适的资源完成任务的执行。为准确描述该问题，方便此类问题的统一求解，建立云资源调度模型。

通常，在云计算系统中，云计算服务提供商主要提供计算和存储服务，它们都是以虚拟机的形式来进行管理和向用户提供服务的，而用户提交的任务则由这些虚拟机来执行。现假设云计算系统中共有m个虚拟处理机，即V={V1,V2,…,Vm}，其中Vi(1

(1)

云计算中心完成所有的任务，所需的完成时间T为最后一个任务完成所需要的时间，即：

(2)

此外， 一个任务Lj(1

(3)

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

(4)

云资源调度的目标就是最小化完成时间T， 因此，云资源调度的求解模型可表示为：

(5)

该云资源调度模型为带有约束条件的单目标优化问题求解模型，它将云资源环境下的资源调度问题用数学的形式表示出来，对此类问题的描述和刻画更为准确和严谨，方便此类问题的统一求解。并且，以此为基础，可以根据该数学模型的特点，有针对性地开发更为有效和高效的算法对此模型进行求解。这对于云资源调度问题的解决具有重要意义。

2 多精英协同进化的遗传算法

由于传统的遗传算法存在早熟收敛、易陷入局部最优和求解效率低等问题，根据所建立的云资源调度模型的具体特征，提出一种多精英协同进化的遗传算法(MECGA)，以使其求解效率更高，寻找最优解的能力更强。

2.1 编码与解码

遗传算法的编码方式有很多，常见的有二进制编码、整数编码和实数编码。以编码/解码简单性和表示上的直观性为原则，本文采用整数编码的方式，即虚拟机和任务的编号用整数来表示。具体来说，每一个染色体(个体)就是问题的一个解决方案，染色体的长度与系统中任务的数量相同，即系统中有多少个任务需要分配，染色体的长度就为多长。我们给定的任务数量为n，则染色体的长度也为n，即S=[s1,s2,…,sn]。染色体的每个基因位si(1≤i≤n)的取值为虚拟机的编号，因此有1≤si≤m，其中m为虚拟机的数量。si的值表示任务Li被分配到虚拟机Vsi上去执行。例如，系统中有10(n=10)个任务L1,L2,…,L10；有3(m=3)台虚拟机V1、V2、V3。假设一个染色体(个体)S=[s1,s2,…,s10]=[1,1,2,2,3,2,2,1,1,3]，则表示的具体含义为;任务L1被分配到虚拟机V1上执行，任务L2被分配到虚拟机V1上执行，任务L3被分配到虚拟机V2上执行，…，任务L10被分配到虚拟机V3上执行。

从上面的例子可以看出，不同的个体(染色体)就是一种不同的资源调度方案，根据个体S的取值，可以得知θij的具体取值：θ11=θ12=θ23=θ24=…=1，其他θij的取值全部为0。此外，还可以通过θij的取值情况判定出虚拟机Vi上所分配到的任务。例如，在上述的例子中，V1上分配的任务为{L1,L2,L8,L9}；V2上分配的任务为{L3,L4,L5,L6}；V3上分配的任务为{L5,L10}。

2.2 个体评价策略

协同进化的思想最早是由Ehrlich等[13]提出的，它主要指多个种群间通过信息共享和相互间的交互，共同进化，以便提高算法的寻优能力。因此，协同进化算法的重点在于，如何恰当地划分子种群，如何让各个子种群之间的信息充分共享，并相互交互和共同进化。为了让算法具有更好的寻优能力，本文将种群划分为精英子种群E_SUBPOP和普通子种群C_SUBPOP。精英子种群中的每个个体相对普通子种群的个体具有更优秀的特征，在进化过程中通过与普通种群的交叉和变异操作可以引导整个种群向最优解的方向移动。因此，精英子种群中个体的确定非常关键。一般情况下，可以选择适应度值高的个体作为精英个体。但是，这会导致精英子种群出现同质化现象，种群的多样性降低，导致算法出现早熟现象。为此，本文定义了个体的差异度来评价个体与个体之间的同质化程度。进而，通过差异度这一评价指标，再制定两种不同的策略对个体的适应度进行评价，从而选择出一定数量的精英个体组成精英子种群。这样的精英子种群就不容易出现同质化现象。

个体之间的差异度的定义如下：设由popsize个个体组成的种群POP={S1,S2,…,Spopsize},个体Si与Sj之间的差异度定义为：

(6)

式中：n为染色体的长度;sik与sjk分别表示第i个个体Si与第j个个体Sj上第k个基因位上的取值。可以看出，若个体Si与个体Sj取值完全一样则差异度D(i,j)为0，若他们的取值完全相异则差异度D(i,j)=1。从差异度的定义可以看出，个体间的差异度越大，他们的相似性越小，种群的同质化现象就越小。

本文第一种评价策略采用常规的评价方式，直接将适应度值大的个体选择出来。适应度值越大表明该个体所提供的解决方案越好，即任务完成时间越小。 这样可以把种群中适应度值大的个体挑选出来组成精英子种群，从而使精英子种群能够引导整个种群向最优解的方向移动。在本文中，适应度函数F1定义为：

(7)

式中：T(Si)表示个体Si的任务完成时间，可由式(2)计算得出。以适应度函数F1作为个体评价函数的第一种评价策略虽然可以保证将适应度值大的个体选择出来，并组成精英子种群。但是，若算法仅采用这一种评价策略就只考虑了个体的适应度值，而没有考虑到个体与个体之间的差异性问题，即精英子种群的多样性问题。在算法运行过程中，随着种群的进化，可能会导致种群中个体的多样性不足，个体的同质化现象越来越严重，常常导致算法会出现早熟收敛等现象。

因此，本文提供了第二种评价策略来保证种群在进化过程中保持应有的种群多样性。它是在适应度函数F1的基础上引入个体差异度因素，定义一个新的个体评价函数F2：

F2(Si)=D(i,j)×F2(Si)

(8)

式中：j表示种群中的不同于i的其他个体。以F2为个体评价函数的第二种策略能够增加种群的多样性，有效避免算法在种群进化过程中出现种群多样性消失的情况。

在种群进化过程中本文算法交替使用这两种评价策略(具体参看2.5节)来选择精英个体，从而确保精英子种群中的个体既具有较高的适应度值，又能保持种群的多样性，从而既能引导种群向最优解的方向移动，又能避免算法出现早熟收敛等问题。

2.3 多精英保留技术

本文采用多精英保留技术(Multi-Elite Reservation)，以精英个体作为种群中的核心元素，引导和推动种群向最优解的进化方向移动，从而提高算法的求解效率。精英个体对于种群进化有着重要作用，它们可以引导整个种群向最优解的方向移动，使算法能够有效快速地找到全局最优解。这里的精英个体指的是种群中适应度值最高的个体(又称为最佳个体)。传统的遗传算法为了能找到最优解，只保留一个精英个体， 但该精英个体引导种群进化的方向可能只是一个局部最优解而非全局最优解，此时算法就可能会陷入到局部最优解中而无法跳出。为了解决这一问题，本文设计了一种多精英保留技术。在种群进化过程中保留多个精英个体，指导种群向多个最优解的方向进化，让种群有更高概率跳出局部最优解从而找到全局最优解。多精英保留技术的具体操作方式如下。

假设第g(g=1,2,…)代种群为POP(g)，从中选择出M个个体作为精英个体组成精英子种群E_SUBPOP，剩下的个体组成普通子种群C_SUBPOP。其中参数M的取值一般为种群数量的25%。

精英子种群E_SUBPOP由三部分构成，分别用a、b和c标识，它们分别占总数的1/3。a类个体的来源方式如下：将POP(g)中的个体按照适应度函数(公式7)值的大小按照从大到小的顺序排序，排在前面的M/3个个体即为a类个体；b类个体和c类个体的确定方法为：首先找出POP(g)中适应度值最高的个体(最佳个体)，然后根据式(6)计算种群中的其他个体与它的差异度值，并将差异度值最小的M/3个个体挑选出来作为b类个体，将差异度值最大的M/3个个体挑选出来作为c类个体。a、b和c类个体共同构成精英子种群E_SUBPOP。其中的a类个体是适应度值最高的精英个体，他们通过与种群中的其他个体的交叉变异操作，可以引领种群快速向最优解的方向演进，有利于加快种群的进化速度。b类个体是与最佳个体差异度最小的个体，可以看作是最佳个体的邻居，通过这些个体间的交叉变异操作，相当于在最佳个体的周围进行局部搜索操作，有利于算法快速收敛到问题的最优解。c类个体是与最佳个体差异度最大的个体，可以用来保证在群体进化过程中保持种群的多样性，有效避免算法陷入局部最优解。

除去精英子种群E_SUBPOP中的个体，剩下的个体组成普通子种群C_SUBPOP。通过精英群体E_SUBPOP与群体C_SUBPOP相互合作与竞争，推动算法不断进化。

2.4 协同进化机制

本文的算法是将种群划分为E_SUBPOP精英子种群和C_SUBPOP普通子种群。精英子种群中个体的数目较少，大约为个体总数的25%，普通子种群中个体的数目较多，大约为个体总数的75%。如果每类子种群都只在子种群内部进行个体间的交叉变异操作，则并不能推动整个种群向最优解的方向移动和进化。 原因是，精英子种群中个体的数目少，但搜索空间大，会导致算法的进化速度慢，执行效率低；而普通子种群中的个体数目虽然较多，但缺乏精英个体指引种群的进化方向，也会导致算法不易找到最优解。因此，为了克服上述问题，本文设计了一种协同进化机制，不仅让精英子种群和普通子种群可以通过种群内部个体间的交叉变异操作生成新的个体。同时，也可以通过子种群与子种群之间的交叉变异操作(协同进化)生成新的个体。具体的进化机制设计如下。

1) 精英子种群E_SUBPOP的进化。随机选择M/2个精英个体，将其与剩下的M/2个个体进行随机交叉操作，生成的个体以Pm概率进行变异操作，然后将其插入到辅助种群POP′中。

2) 精英子种群E_SUBPOP与普通子种群C_SUBPOP的协作进化。从E_SUBPOP中随机选择出(popsize-M)个精英个体， 从C_SUBPOP中随机选择出(popsize-M)个普通个体，精英个体与普通个体两两相互配对完成交叉操作，生成的个体再以Pm概率进行变异，最后插入到辅助种群POP′中。

上述的进化机制可以充分发挥精英个体在引导种群进化中的核心作用，也可保证种群有很好的多样性。待辅助种群POP′完成创建后，将其与种群POP(g)合并，然后按照前文给出的两种个体评价策略(式(7)和式(8))从中选择出popsize个个体形成下一代种群POP(g+1)。

2.5 MECGA描述

多精英协同进化遗传算法MECGA的基本思想如算法1所示。

算法1多精英协同进化遗传算法MECGA

Step1令g=0,生成初始化种群POP(g)。

Step2对POP(g)中的个体根据式(7)计算适应度值, 选择适应度值最高的前M/3个个体放入E_SUBPOP中，适应度值最高的个体为Best_Individual。

Step3根据式(6)计算POP(g)中每个个体与最佳个体Best_Individual的差异度值，分别将差异度值最小的M/3个体和差异度最大的M/3个个体放入E_SUBPOP中。

Step4将POP(g)中剩下的个体放入C_SUBPOP中。

Step5将E_SUBPOP中的个体随机两两组队进行交叉操作，生成的新个体以Pm概率进行变异操作，然后将其插入到辅助种群POP′中。

Step6分别随机从E_SUBPOP中挑选出(popsize-M)个精英个体，从C_SUBPOP中挑选出(popsize-M)个普通个体，两两组合进行交叉操作，生成的个体以Pm概率变异后插入到辅助种群POP′中。

Step7将E_SUBPOP中的个体放入下一代种群POP(g)中。

Step8交替以两种个体评价策略(式(7)和式(8))为基础，以轮盘赌的方式从辅助种群POP′中选择(popsize-M)个个体放入下一代种群POP(g+1)中。

Step9令g=g+1。

Step10判断是否满足终止条件，若是,则结束;否则,转到Step2。

3 实验与结果分析

为了验证MECGA在进行云资源调度时具备的良好性能，本文使用MATLAB R2014b对MECGA、传统的遗传算法GA、带有精英保留策略的遗传算法GAE和文献[11]的元胞遗传算法CGA进行了模拟仿真测试。并在相同的软硬件环境下，通过实验结果对比分析本文各对比算法的性能。表1给出了实验过程中各对比算法所用到的参数取值情况。

表1 实验中参数的取值

在对比实验中，假设云计算系统中虚拟机的数量为5个，即V={V1,V2,V3,V4,V5}，其对应的运算速度Pi(1≤i≤5)分别为{50,100,150,200,300}。系统中的任务数量分别取值为200、250、300、350、400、450和500时，用GA、GAE、CGA和MECGA这四个算法求解任务的最小完成时间，然后比较哪个算法可以得到更优的解。其中每个任务Lj的计算量Wj的大小(需执行的机器指令的条数)在1～100之间随机取值。对每个算法都随机运行30次，求解出任务的最小完成时间，最终的实验结果如图1所示。

图1 总任务完成时间的比较(1)

可以看出，当任务数量从200到500变化过程中，传统的GA和带有精英保留策略的GAE求解出来的总任务完成时间较大，说明它们的总体寻优能力较差。而CGA的寻优能力相对较好，但表现最好的算法是MECGA。相对而言，MECGA总是能求出最好的解，它求解出的任务完成时间总是最小的，说明其寻优能力是最强的。

将云计算系统中虚拟机的数量设置为6个,即V={V1,V2,V3,V4,V5,V6},将其对应的运算速度Pi(1≤i≤6)分别设置为{30, 50, 100, 150,200, 300}。其他条件不变，然后求解任务的最小完成时间，其结果如图2所示。

图2 总任务完成时间的比较(2)

可以看出，MECGA表现最好，相对其他三个算法，它总是能够求得最优的解。

MECGA优秀的寻优能力得益于其多精英保留技术和系统进化机制。种群在进化过程中，每一代种群都会被分割成包含多个(M)精英的E_SUBPOP子种群和普通子种群C_SUBPOP。通过E_SUBPOP和C_SUBPOP的协同交叉进化，精英子种群能够引导群体快速向最优解的方向移动，以便快速找到最优解。另外，根据我们设计的个体评价策略，E_SUBPOP中的个体既有目前找到的最优的解，又能保证群体的多样性，这样就能在种群进化过程中有效避免算法的早熟收敛和陷入局部最优等问题。下面通过实验来验证MECGA这些性能。

设定虚拟机的数量为5个，系统中任务的数量为500，查看这四种算法从第1代进化到第100代过程中它们的统计情况。
图3显示的是群体在进化过程中，每一代群体中求得的最小用户完成时间。

图3 用户任务最小完成时间的比较

随着种群代数的不断递增，MECGA可以快速地向最优解演进。从第1代到第20代的进化过程中，可以看到MECGA下降的曲线非常陡峭，说明MECGA能够引导群体迅速向最优解靠近。在进化的后期(30～100代)MECGA由于能够保持种群的多样性，又能不断跳出局部最优，从而找到更优的解。而其他三种算法相比MECGA都不具备优势。为了进一步说明MECGA能够保持种群多样性，图4给出了在种群进化过程中，用户任务平均完成时间的统计信息。

图4 用户任务平均完成时间的比较

在种群进化后期(30～100代)，可以看出GA、GAE和CGA的平均用户任务完成时间变化波动不大，这说明算法在进化的后期，种群中的个体相似度很大，而多样性不足，算法很难跳出局部最优。而MECGA波动性很明显，说明算法在进化的后期，种群中的个体的差异度还很大,算法较好地保持了群体的多样性，能够避免算法过早收敛、陷入局部最优等问题，具备更好寻优性能。

4 结 语

传统的GA在进行云资源调度时容易出现算法早熟收敛、种群多样性差、易陷入局部最优等问题。本文提出一种基于多精英协同进化的遗传算法MECGA，用于解决云资源调度问题。在种群进化过程中，首先将种群划分为精英子种群和普通子种群。精英子种群由多个精英个体共同构成，并且这些精英个体分别具有适应度值高、相似性大和个体差异明显等特点。这样的设计方式可以保证精英子种群体现出很好的代表性(即子种群总体的适应度值较高)，又可以保证子种群的多样性(即个体之间的差异度较大)。精英子种群在与普通子种群进行协同交叉进化时，可以引领种群快速向最优解的方向移动，同时又能保证种群的多样性，让算法在演化过程中，更容易跳出局部最优解，从而找到最优解。为了验证算法的性能，我们设计了多组实验，并与GA、GAE和CGA进行了对比分析。实验结果说明MECGA具备很好的性能。在进行云资源调度时，MECGA求解出的最终解总是优于另外三个算法的最终解，其寻找最优解和跳出局部最优的能力表现得十分明显，鲁棒性更好。