云环境下方差定向变异遗传算法的任务调度

孙敏 叶侨楠 陈中雄

摘 要：云环境下遗传算法（GA）的任务调度存在寻优能力差、结果不稳定等问题。对于上述问题，提出了一种基于方差与定向变异的遗传算法（VDVGA）。在选择部分，在每一次迭代的过程中进行多次选择，利用数学方差来保证种群的多样性并扩大较优解的搜索范围。在交叉部分，建立新的交叉机制，丰富种群的多样性并提高种群整体的适应度。在变异部分，优化变异机制，在传统变异的基础上采用定向变异来提高算法的寻优能力。通过 workflowSim平台进行云环境仿真实验，将此算法与经典的遗传算法和当前的基于遗传算法的工作流调度算法（CWTSGA）进行比较。实验结果表明，在相同的设置条件下，该算法在执行效率、寻优能力和稳定性等方面优于其他两个算法，是一种云计算环境下有效的任务调度算法。

关键词：云环境;任务调度;遗传算法;方差;定向变异

中图分类号：TP393

文献标志码：A

Task scheduling of variancedirectional variation genetic algorithm in cloud environment

SUN Min， YE Qiaonan*， CHEN Zhongxiong

School of Computer and Information Technology， Shanxi University， Taiyuan Shanxi 030006， China

Abstract：

The task scheduling of Genetic Algorithm （GA） in cloud environment has problems such as poor optimization ability and unstable results. For the above problems， a VarianceDirectional Variation GA （VDVGA） was proposed. In the selection part， multiple selections were made in the process of each iteration， and the mathematical variance was used to ensure the diversity of the population and expand the search range of the better solution. In the intersection part， a new intersection mechanism was established to enrich the diversity of the population and improve the overall fitness of the population. In the variation part， the variation method was improved， the directional variation was used on the basis of the traditional variation to increase the optimization ability of the algorithm. The cloud environment simulation experiments were carried out on the workflowSim platform， and the proposed algorithm was compared with the classical GA and the current Workflow Scheduling Algorithm based on Genetic Algorithm （CWTSGA）. The experimental results show that under the same setting conditions， the proposed algorithm is superior to the other two algorithms in terms of execution efficiency， optimization ability and stability， and is an effective task scheduling algorithm in cloud computing environment.

Key words：

cloud environment; task scheduling; Genetic Algorithm （GA）; variance; directional variation

0 引言

云计算是并行计算、分布式计算、虚拟化和网格存储等的融合，是互联网的快速发展与其产生的数据量的产物，其中，如何对数据进行更有效的处理，也就是找到更合理的任务调度方案的当前急需解决的问题。

任务调度属于一个NPhard问题，为此，有很多学者将经典的启发式算法应用到了任务调度上，胡艳华等[1]提出了将MaxMin算法与传统遗传算法相结合的最大最小遗传算法（MaxMin Genetic Algorithm，MMGA），将MaxMin算法运用到了遗传算法的初始化操作上，使得一开始的染色体具有良好的性能，通过这样的改进，达到了缩短最佳任务调度方案的执行时间，提高资源利用率的目的; George等[2]将布谷鸟搜索算法用来寻找任务调度的最佳方案，迭代寻找最优的巢穴，不断地用最近找到的巢穴代替之前的巢穴，直到找到最佳的巢穴或者迭代次数达到最大停止，从而缩短了最佳任务分配方案的执行时间; Rajput等[3]先利用MinMin算法得出一個分配方案，然后在得到的分配方案中找到负载最大的虚拟机与负载最小的虚拟机将占用资源最大的任务迁移到负载小的虚拟机上，这些操作完成之后再用遗传算法找最佳分配方案，这样缩短了最佳分配方案的执行时间并且提高了资源利用率;Yang等[4]提出了染色体多点交叉与交换变异的工作流遗传算法（Workflow Scheduling Algorithm based on Genetic Algorithm， CWTSGA），在最佳分配方案的执行时间方面起到了优化作用。

本文将遗传算法作为研究对象，但是，目前遗传算法在云任务上的调度存在以下缺陷：1）寻优能力差。遗传算法是用来解决NPHard问题的一种较好的方式，但是需要经过多次迭代之后才能得到一个较好的结果，而多次迭代之后，种群的个体出现了单一现象，而这一现象是由于种群多样性差造成的，从而使得找到的最优解只具有局部性，而不具有全局性。2）结果不稳定，具有较大的波动性。遗传算法中的初始化是随机产生个体，然后组成初始种群，这具有极大的随机性，在后续的选择、交叉、变异操作中，种群中的个体会受到交叉概率、变异概率的影响，从而产生的个体会有差别，这种算法在过程中随机性，就会导致最后产生的结果也具有随机性。

针对遗传算法存在的上述问题，本文提出了运用方差提高种群多样性，控制进化方向的方差定向变异的遗传算法（VarianceDirectional Variation Genetic Algorithm， VDVGA）的任务调度算法。在本文中，为了提高种群的多样性，将方差应用在遗传操作的选择部分;在交叉部分，为了在保证个体适应度值高的前提下，保证种群的多样性，建立了新的交叉机制; 为了使得个体总是向好的方向进化，在变异部分对变异操作进行了控制，即定向变异。这样不仅解决了种群多样性不足的问题，还可以对最后得到的分配方案进行优化，减少最佳分配方案的执行时间。

1 云计算的任务调度分析

云环境就是要将用户提交的任务在云环境中进行处理，并将最终的处理结果返回给用户，这个过程为“云计算”。本文的研究重点就在于“云端”如何更快地处理用户提交的任务，也就是当用户将任务提交给云环境时，云环境需要对任务进行整理与划分，然后按照任务资源调度模式完成对任务的分配，使得执行任务的时间最短。

当前，在云计算领域，大多采用Google提出的Map/Reduce模型[5]对数据进行并行处理，主要的工作原理为：将要处理的数据分解成两个部分，即Map与Reduce，利用Map将用户提交的任务进行分割，使一个大任务被分解成多个独立的小任务，然后将这些子任务提交给资源中心进行处理，最后将资源中心处理过的结果通过Reduce进行整理合并，得到用户对提交任务的处理结果。其模型可以简化为如图1所示。用户提交的m个Job，分割成了n个task，最后处理后，得到一个关于资源组V编号的分配方案。在整个过程中，资源是有限的，但是用户的数量是庞大的，故需要处理的任务数量是巨大的，作为资源供应的一方，如何使最后得到的分配方案更加合理至关重要，在这个问题中，有一个好的资源调度方案直接决定了最后的结果。本文的研究重点是让得到的任务分配方案的执行时间最少，面对这样一个NPHard问题，本文采用了遗传算法（Genetic Algorithm，GA）来解决这一问题。

对于云资源调度模型的调度过程，有如下分析：设有m个任务，对m个任务进行预处理，将其分割成{x1，x2，…，xn}大小的子任务，每个子任务的数量分别为{k1，k2，…，kq}， 其中n=∑qi=1ki，size（m）=∑0≤i≤n， 0≤j≤qsize（xi×kj），其中m表示Job的数量。之后将这n个子任务分配到虚拟机组V（V∈[1，M]）上执行，最终得到一个处理n个任務的虚拟机序列编号，也就是任务的执行方案。这个分配方案的完成时间FinishTime、所耗费用Cost分别为：

FinishTime=max1

其中：Time（i， j）为第j个任务在i号虚拟机上执行所用的时间，k为虚拟机i分配的任务个数。

Cost=∑Mi=1∑kj=1Time（i， j）×costi（2）

其中costi表示单位时间内虚拟资源Vi的费用。

2 云环境下的任务调度

2.1 染色体的编码与解码

染色体的编码有很多种方式，可以采用直接编码（对任务的执行状态编码），也可以采用间接编码。在本文中采用的是三位十进制的资源任务间接编码，三位的十进制数的表示编码相较于二进制表示同一个实数时，占用的字节数少，节省空间，相较于八进制与十六进制来说更加直观。完成编码之后，染色体的基因长度为子任务的数量，每个基因片段为该节点任务分配资源的虚拟机编号。如图2所示，其中Ti为任务编号，Vi为虚拟机编号，本文中的染色体就是由虚拟机编号依次排列构成的，也就是得到的任务调度分配方案。假设有6个任务，3台虚拟机，得到一条染色体为：{002，003，002，002，001，003}，该染色体表示在V2虚拟机上有{T1，T3，T4}三个任务被执行。

之后对染色体进行解码，即002解码为2，003解码为3。当完成所有染色体的解码之后，将会得到一个任务资源的矩阵，根据这个矩阵可以得到将所有任务执行完毕的时间，也就是通过式（1）得到最后的完成时间。

2.2 适应度函数

适应度函数是衡量个体性能是否优良的标准，本文内容的研究重点为任务调度后的执行时间和费用与结果的稳定性，稳定性是对最后的结果进行处理得到的，故不可以放在适应度函数当中。将式（1）、（2）结合起来，作为判断染色体是否为优良个体的适应度函数f（x）设置为：

f（x）=α×FinishTime + （1-α）×Cost（3）

其中： α为执行时间在适应度函数当中占比重的影响因子，α∈[0，1]。当α取值为0.5时，在适应度函数中任务的执行时间与费用需要被同等考虑;若α>0.5，则表明在适应度函数中，任务的执行时间的权重较大。

关于算法的稳定性，本文在实验部分经过多次实验，将最后的结果进行整理后进行判断。

2.3 遗传操作

2.3.1 选择部分

选择操作是遗传算法中根据个体适应度选择出优良个体的操作，将适应度高的染色体大概率地保留下来，并将其优良的基因传递给下一代，保持种群性能的优良，符合生物学中“物竞天择”的进化论。根据式（3）得到每一个个体的适应度函数的值后，可得每条染色体被选中的概率为：

Pj=f（xj）∑nj=1f（xj） （4）

利用轮盘赌算法进行选择时需要将种群中每个个体被选择的概率制作成轮盘，通过式（4），可以得到第j个体在轮盘上显示的区域为：

Pj′=∑jj=1f（xj）-∑j-1j=1f（xj）（5）

根据式（4）、（5），可以得出轮盘指针指向每一条染色体的概率为：

Pj″=1-f（xj）∑nj=1f（xj）（6）

当f（xj）越大，Pj″就越小，该染色体被选择的概率就越低。

为了使得最终的结果不要过早地收敛，提高稳定性，在本文中，通过n轮盘赌算法选择之后，计算每次选择后的个体组成的种群的方差D（n）。在数学上，方差是用来衡量一组数据波动大小的数字，方差的值越大，这一组数据波動越大，反之，则越小。它反映样本与平均值的偏离程度，但这个偏离可以是正向偏离，也可以是负向偏离。方差D（n）是统计与概率学的一个概念：

D（n）=[∑ni=1（A-xi）]/n（7）

在遗传算法中的初始化部分，染色体是随机产生的，每次初始化产生的种群中的个体，从原来的种群选出新的种群时具有较大的波动性，这种波动给遗传算法产生的结果带来了双面的影响：一方面，扩大了遗传算法搜索最优解的范围，经过多次实验可以找到一个最佳的解;另一方面，初始化的波动导致最后的结果不具有稳定性，多次实验结果不是同一个确定的值，故在应用时不能保证当前实验结果就是最优解。

在本文中，将方差与遗传算法结合，利用波动性好的一面，尽量减少负面影响，可以让结果得到进一步的优化。

而在本文中，需要的是正向偏离，也就是种群中包含的个体种类的个数多于平均值，偏离的值越大，种群的多样性越好。为了保证是正向偏离，所以对式（7）进行处理，令：

D′（i）=D（i）×（xi-A）（8）

D′（i）为与偏离方向保持一致的方差，如果该种群个体的多样性小于平均值，D′（i）<0;否则，D′（i）>0。

在n次选择之后，通过式（8）计算找到D′（i）max，并将与之对应所产生的种群作为新的种群。通过方差，将包含个体种类最多的种群留下进行之后的操作，个体的种类越多，则种群的多样性越丰富，能扩大寻找较优解的搜索范围，在一定程度上减少了算法的过早收敛问题的出现。

本文中选择部分的思想为：采用多次选择的方式提高种群的多样性与种群整体的性能，扩大后续对较优解的搜索范围。伪码如下：

程序前

Start

make roulette（Pj）

Start for

{

Choose group;

D′（i）=D（i）×（xi-A）;

if D′（i） is max;

best group if found;

break;

}

End for

End

程序后

2.3.2 交叉操作

在交叉操作中，对于交叉概率有两种处理：一种是指定概率，即pc=C1，C1为指定的常量，通常取值在0.1～0.3;另外一种方式是利用自适应算法得出交叉概率[6]，如

pc=k2（f（x）max-f（x）′）f（x）′-f（x）avg，f（x）′≥f（x）avg

k2，f（x）′

其中：f（x）avg为种群染色体的平均适应度函数值，f（x）′为两条染色体中较好个体的适应度函数值，f（x）avg为种群中最好个体的适应度函数值。根据式（9）计算得出随着染色体性能变化而变化的交叉概率。交叉操作的目的是丰富种群个体的多样性，避免陷入局部最优解。自适应交叉概率的计算过程中，为了保证个体的优良性，当交叉的两条染色体中有一条染色体的适应度函数值大于f（x）avg，两条染色体的交叉概率相对较小，这样可以尽可能地留下性能好的个体;否则，交叉概率较大，起到丰富种群多样性的作用。

但是，两条性能较差的染色体进行交叉产生的新个体的性能相对较差。为了能够解决这一问题，本文对交叉操作作出了如下改进：当两条染色体的适应度函数值都低于f（x）avg时，从种群中随机选出两条适应度函数值大于f（x）avg的染色体，进行两两交叉，产生新的个体。这样产生的新个体可以在丰富种群多样性的同时保证了新个体性能有较大的可能高于原先适应度函数值低于f（x）avg的两个个体，保证新的种群在整体的适应度上优于交叉前的种群。

交叉部分的思想为尽可能地将旧种群的个体保留到新的种群中，将性能差的个体用来提高种群的多样性，并且提高种群整体的性能。伪码如下：

程序前

Start

Choose xi，xj;

If

f（xi）>f（x）avg‖f（xj）>f（x）avg;

pc=k1（f（x）max-f（x）′）f（x）′-f（x）avg;

Random（） k∈[0，cloudletsize];

Intersect （xi，yj）→xi′，yj′;

Else

Start for

Choose xi1，yj1;

If f（xi1）>f（x）avg&&f（xj1）>f（x）avg;

End for

pc=k2;

Random（） k∈[0，cloudletsize];

Intersect （xi，xi1，xj，xj1）→xi′，xi1′，xj′，xj1′;

End if

End

程序后

2.3.3 变异操作

在执行变异操作之前，需要确定被选中的染色体变异的位置，用rand（）函数在变异操作中，存在一个关键参数：变异概率pm，对pm的处理与pc类似，对于指定概率C2，其取值范围通常在0.01～0.1，另一种方式也是利用自适应算法，如式（9）所示得到变异概率。

为了保证个体始终能向好的方向进化，采用了定向变异。定向变异是本文对于遗传算法应用到云任务调用的改进。当被选中要变异的个体经过变异操作得到新的个体后，计算得出其适应度f（xj′）与被选中个体适应度f（xj）进行比较。若f（xj′）

FinishTimej=waitTime（i）j+executeTime（i）j （10）

由于虚拟机的性能各不相同，提交上来的任务也是有长有短，这就造成了每台虚拟机对同一个任务的执行时间是不同的，而该任务在任务队列中的位置将影响其等待时间，其分配到的虚拟机将影响其执行时间。

通常，缩小关于独立任务的完成时间，是通过减少执行时间或是减少等待时间来实现的，但是会出现第j个任务在队列的k位置，再分配到i虚拟机上，会存在其等待时间是在所有虚拟机上最短的，由于任务过长，或者虚拟机性能不佳，导致任务j的执行时间不是最短的。综合这两个方面的因素，将两个时间结合到一起，可以最大限度减少该任务的完成时间，从而缩短所有任务的最终完成时间。

具体步骤如下：

1）取出变异个体的变异点，获得j任务的长度;

2）遍历所有的虚拟机，找到minFinishTime（i）j，獲取虚拟机编号i;

3）将虚拟机Vi替换到变异的点，完成定向变异。

变异操作对应的伪码如下：

程序前

Start

Choose xj

if f（xj）>f（x）avg

pm=k1（f（x）max-f（xj））f（xj）-f（x）avg

Else

pm=k2

End if

Random k∈[0，cloudletsize];

Variation xj→xj′

If f（xj）>f（xj′）

Get Vi id at k

for

FinishTimej=waitTime（i）j+executeTime（i）j

Find min FinishTimej1

Get Vi1 id

Vi→Vi1

xj→xj″

End if

End

程序后

3 实验仿真与结果对比

3.1 实验环境配置

在本文中，实验是在虚拟平台workflowSim对任务调度进行实验模拟。为了证明实验的有效性，与GA和现在侧重于缩短执行时间的遗传算法（CWTSGA）处理云任务调度进行了对比，并对实验需要用到的虚拟机与主机环境在仿真平台上进行了设置，其设置信息如表1与表2，确保在同等环境下对这三种实验进行仿真。

在本文的仿真实验中，共设置了100台虚拟机V，100台主机host，其种类信息如上述的表1与表2所示。相关的参数如表3所示，在表3中，CWTSGA的参数设置是根据文献[4]中的参数进行设置的，自适应算法中涉及到的k1，k2是参考文献[6]当中的参数进行设置。

3.2 实验结果对比与分析

在本文中，将三种算法从任务调度的策略性与最终结果的稳定性两个方面进行了对比与分析。

3.2.1 任务调度策略性的结果对比与分析

在本文中，通过4组不同数量与类型的任务进行实验验证新型GA在云任务调度的运用的结果优于传统GA在云任务调度的运用。为了证明其研究必要，在每一组实验当中，都将任务分成了4个类别，每个类别的任务长度各不相同。

通过对总任务数量分别为：500、1-000、1-500和3-000用传统的GA、CWTSGA和VDVGA进行75次实验，求得平均值用时，将结果整理绘制成图3（a）。

将图3结合对比，可以得出：三种调度算法在费用上的差别是十分微小的，几乎可以忽略，但是在时间上却有着显著的差别。对于小型任务来说，即图3（a）中任务数量为500时，三者基本没有差别;随着任务数量的增加，VDVGA与GA、CWTSGA的差距逐渐扩大，当任务规模达到1-500时，可以看到VDVGA任务调度的完成时间上是用时最少的，与GA有明显差距，与CWTSGA对比也可以看出在费用几乎没有差别的情况下，在时间上VDVGA也是具有优势的;当任务数量达到3-000时，DDGA与GA、CWTSGA在时间上的差距相较于任务规模为1-000与1-500时更大，VDVGA所需的完成时间最少。

分析可以得出：通过对GA的改进提高了GA的寻优能力，这是通过：在交叉部分建立的新的交叉机制，保证了种群整体的适应度在每次迭代的过程中都得以提高;在变异部分，定向变异与传统变异的结合保证了经过变异的个体是向性能更加优良的方向发展的。而在实际的应用中，云平台处理的任务数量远远超过3-000，大多情况下处理的为大型任务，这些大型任务会被分割成大量甚至海量的子任务，当任务数量越多，在费用相同的情况下VDVGA云任务调度节省的时间就会更多，也就说明对任务的分配方案就更加合理，其策略性也就越好。

3.2.2 結果稳定性的对比与分析

对于遗传算法来说，除了寻优能力差，还有一个明显的缺点就是经过多次实验后得到的结果具有极大的波动性，本文通过对遗传算法的改进在稳定性方面与GA、CWTSGA针对执行时间进行了对比。

在本文中，对500个任务和1-000个任务的两种调度方式选取了10组值绘制成图4，通过观察可以得到：VDVGA云任务调度的值波动较小，这是因为在进行选择操作时，利用方差扩大了种群个体的多样性，提高了性能优良个体被选中的概率，在交叉部分建立的新的交叉机制在保证种群多样性的前提下，在整体上提高了种群中个体的性能，而传统GA云任务调度的值波动比较大。也就可以得出VDVGA云任务调度得到的任务调度方案在时间上是相对稳定的。与当前的CWTSGA云任务调度相比，VDVGA的波动也是要小于CWTSGA的。

综上所述，从时间与稳定性两个方面看，对于大规模云任务调度来说，VDVGA都优于传统GA与CWTSGA。

4 结语

在本文的工作中，确实通过对遗传算法的改进缩短了任务调度之后得到的最佳方案的执行时间，在实际应用中，能够更快更好地处理用户提交的任务，但是还是存在一些不足，如费用并没有明显的变化，这是在今后的工作中需要进行研究的内容;其次，本文主要的研究对象为遗传算法，对其他的其方式算法还没有进行深入研究，下一步将会对其他启发式算法进行任务调度的研究。

参考文献 （References）

[1] 胡艳华，唐新来. 基于改进遗传算法的云计算任务调度算法[J]. 计算机技术与发展，2016，10（26）：137-141.（HU Y H， TANG X L. A task scheduling algorithm based on improved genetic algorithm in cloud computing environment [J]. Computer Technology and Development，2016，10（26）：137-141.）

[2] GEORGE N， CHANDRASEKARAN K， BINU A. Optimizationaware scheduling in cloud computing[C]// Proceedings of the 2016 International Conference on Informatics and Analytics. New York： ACM， 2016， 8（16）： Article No.15.

[3] RAJPUT S S， KUSHWAH V S. A genetic based improved load balanced minmin task scheduling algorithm for load balancing in cloud computing[C]// Proceedings of the 8th International Conference on Computational Intelligence and Communication Networks. Piscataway： IEEE， 2018：677-681.

[4] YANG C， ZHANG X. Workflow tasks scheduling optimization based on genetic algorithm in clouds[C]// Proceedings of the IEEE 3rd International Conference on Cloud Computing and Big Data Analysis. Piscataway： IEEE， 2018：6-10.

[5] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters[C]// Proceedings of the 6th Symposium on Operating Systems Design and Implementation. Berkeley， CA： USENIX Association， 2004：137-150.

[6] WU M. Research on improvement of task scheduling algorithm in cloud computing[J]. Applied Mathematics and Information Sciences， 2015， 9（1）：507-516.

[7] BOKHARI M U， MAKKI Q， TAMANDANI Y K. A survey on cloud computing[M]// AGGARWAL V B， BHATNAGAR V， MISHRA D K. Big Data Analytics， AISC 654. Singapore： Springer， 2018： 149-164.

[8] WANG T， LIU Z， CHEN Y， et al. Load balancing task scheduling based on genetic algorithm in cloud computing[C]// Proceedings of the IEEE 12th International Conference on Dependable， Autonomic and Secure Computing. Piscataway： IEEE， 2014：146-152.

[9] 孫敏，陈中雄，卢伟荣. 云环境下基于DOGAPSO的任务调度算法[J]. 计算机科学， 2018， 45（6A）：300-303. （SUN M， CHEN Z X， LU W R. Task scheduling algorithm based on DOGAPSO under cloud environment[J]. Computer Science， 2018， 45（6A）： 300-303.）

[10] KAUR S， VERMA A. An efficient approach to genetic algorithm for task scheduling in cloud computing environment[J].International Journal of Information Technology & Computer Science，2012，4（10）：159-190.

[11] AKILANDESWARI P， SRIMATHI H. Survey and analysis on task scheduling in cloud environment[J].Indian Journal of Science & Technology，2016，9（37）： 102058.

[12] ALMAKADMEH K， ALMAAITAH W. Comparison of crossover types to build improved queries using adaptive genetic algorithm[C]// Proceedings of the 2017 International Conference on New Trends in Computing Sciences. Piscataway： IEEE， 2017： 1-5.

SUN Min， born in 1965， M. S.， associate professor. Her research interests include cloud computing， Web intelligence， collaborative editing.

YE Qiaonan， born in 1995， M. S. candidate. Her research interests include cloud computing， artificial intelligence.

CHEN Zhongxiong， born in 1992， M. S. candidate. His research interests include cloud computing， artificial intelligence.