云環(huán)境下方差定向變異遺傳算法的任務(wù)調(diào)度

孫敏 葉僑楠 陳中雄

摘 要：云環(huán)境下遺傳算法（GA）的任務(wù)調(diào)度存在尋優(yōu)能力差、結(jié)果不穩(wěn)定等問題。對于上述問題，提出了一種基于方差與定向變異的遺傳算法（VDVGA）。在選擇部分，在每一次迭代的過程中進(jìn)行多次選擇，利用數(shù)學(xué)方差來保證種群的多樣性并擴(kuò)大較優(yōu)解的搜索范圍。在交叉部分，建立新的交叉機(jī)制，豐富種群的多樣性并提高種群整體的適應(yīng)度。在變異部分，優(yōu)化變異機(jī)制，在傳統(tǒng)變異的基礎(chǔ)上采用定向變異來提高算法的尋優(yōu)能力。通過 workflowSim平臺進(jìn)行云環(huán)境仿真實驗，將此算法與經(jīng)典的遺傳算法和當(dāng)前的基于遺傳算法的工作流調(diào)度算法（CWTSGA）進(jìn)行比較。實驗結(jié)果表明，在相同的設(shè)置條件下，該算法在執(zhí)行效率、尋優(yōu)能力和穩(wěn)定性等方面優(yōu)于其他兩個算法，是一種云計算環(huán)境下有效的任務(wù)調(diào)度算法。

關(guān)鍵詞：云環(huán)境;任務(wù)調(diào)度;遺傳算法;方差;定向變異

中圖分類號：TP393

文獻(xiàn)標(biāo)志碼：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?引言

云計算是并行計算、分布式計算、虛擬化和網(wǎng)格存儲等的融合，是互聯(lián)網(wǎng)的快速發(fā)展與其產(chǎn)生的數(shù)據(jù)量的產(chǎn)物，其中，如何對數(shù)據(jù)進(jìn)行更有效的處理，也就是找到更合理的任務(wù)調(diào)度方案的當(dāng)前急需解決的問題。

任務(wù)調(diào)度屬于一個NPhard問題，為此，有很多學(xué)者將經(jīng)典的啟發(fā)式算法應(yīng)用到了任務(wù)調(diào)度上，胡艷華等[1]提出了將MaxMin算法與傳統(tǒng)遺傳算法相結(jié)合的最大最小遺傳算法（MaxMin Genetic Algorithm，MMGA），將MaxMin算法運用到了遺傳算法的初始化操作上，使得一開始的染色體具有良好的性能，通過這樣的改進(jìn)，達(dá)到了縮短最佳任務(wù)調(diào)度方案的執(zhí)行時間，提高資源利用率的目的; George等[2]將布谷鳥搜索算法用來尋找任務(wù)調(diào)度的最佳方案，迭代尋找最優(yōu)的巢穴，不斷地用最近找到的巢穴代替之前的巢穴，直到找到最佳的巢穴或者迭代次數(shù)達(dá)到最大停止，從而縮短了最佳任務(wù)分配方案的執(zhí)行時間; Rajput等[3]先利用MinMin算法得出一個分配方案，然后在得到的分配方案中找到負(fù)載最大的虛擬機(jī)與負(fù)載最小的虛擬機(jī)將占用資源最大的任務(wù)遷移到負(fù)載小的虛擬機(jī)上，這些操作完成之后再用遺傳算法找最佳分配方案，這樣縮短了最佳分配方案的執(zhí)行時間并且提高了資源利用率;Yang等[4]提出了染色體多點交叉與交換變異的工作流遺傳算法（Workflow Scheduling Algorithm based on Genetic Algorithm， CWTSGA），在最佳分配方案的執(zhí)行時間方面起到了優(yōu)化作用。

本文將遺傳算法作為研究對象，但是，目前遺傳算法在云任務(wù)上的調(diào)度存在以下缺陷：1）尋優(yōu)能力差。遺傳算法是用來解決NPHard問題的一種較好的方式，但是需要經(jīng)過多次迭代之后才能得到一個較好的結(jié)果，而多次迭代之后，種群的個體出現(xiàn)了單一現(xiàn)象，而這一現(xiàn)象是由于種群多樣性差造成的，從而使得找到的最優(yōu)解只具有局部性，而不具有全局性。2）結(jié)果不穩(wěn)定，具有較大的波動性。遺傳算法中的初始化是隨機(jī)產(chǎn)生個體，然后組成初始種群，這具有極大的隨機(jī)性，在后續(xù)的選擇、交叉、變異操作中，種群中的個體會受到交叉概率、變異概率的影響，從而產(chǎn)生的個體會有差別，這種算法在過程中隨機(jī)性，就會導(dǎo)致最后產(chǎn)生的結(jié)果也具有隨機(jī)性。

針對遺傳算法存在的上述問題，本文提出了運用方差提高種群多樣性，控制進(jìn)化方向的方差定向變異的遺傳算法（VarianceDirectional Variation Genetic Algorithm， VDVGA）的任務(wù)調(diào)度算法。在本文中，為了提高種群的多樣性，將方差應(yīng)用在遺傳操作的選擇部分;在交叉部分，為了在保證個體適應(yīng)度值高的前提下，保證種群的多樣性，建立了新的交叉機(jī)制; 為了使得個體總是向好的方向進(jìn)化，在變異部分對變異操作進(jìn)行了控制，即定向變異。這樣不僅解決了種群多樣性不足的問題，還可以對最后得到的分配方案進(jìn)行優(yōu)化，減少最佳分配方案的執(zhí)行時間。

1?云計算的任務(wù)調(diào)度分析

云環(huán)境就是要將用戶提交的任務(wù)在云環(huán)境中進(jìn)行處理，并將最終的處理結(jié)果返回給用戶，這個過程為“云計算”。本文的研究重點就在于“云端”如何更快地處理用戶提交的任務(wù)，也就是當(dāng)用戶將任務(wù)提交給云環(huán)境時，云環(huán)境需要對任務(wù)進(jìn)行整理與劃分，然后按照任務(wù)資源調(diào)度模式完成對任務(wù)的分配，使得執(zhí)行任務(wù)的時間最短。

當(dāng)前，在云計算領(lǐng)域，大多采用Google提出的Map/Reduce模型[5]對數(shù)據(jù)進(jìn)行并行處理，主要的工作原理為：將要處理的數(shù)據(jù)分解成兩個部分，即Map與Reduce，利用Map將用戶提交的任務(wù)進(jìn)行分割，使一個大任務(wù)被分解成多個獨立的小任務(wù)，然后將這些子任務(wù)提交給資源中心進(jìn)行處理，最后將資源中心處理過的結(jié)果通過Reduce進(jìn)行整理合并，得到用戶對提交任務(wù)的處理結(jié)果。其模型可以簡化為如圖1所示。用戶提交的m個Job，分割成了n個task，最后處理后，得到一個關(guān)于資源組V編號的分配方案。在整個過程中，資源是有限的，但是用戶的數(shù)量是龐大的，故需要處理的任務(wù)數(shù)量是巨大的，作為資源供應(yīng)的一方，如何使最后得到的分配方案更加合理至關(guān)重要，在這個問題中，有一個好的資源調(diào)度方案直接決定了最后的結(jié)果。本文的研究重點是讓得到的任務(wù)分配方案的執(zhí)行時間最少，面對這樣一個NPHard問題，本文采用了遺傳算法（Genetic Algorithm，GA）來解決這一問題。

對于云資源調(diào)度模型的調(diào)度過程，有如下分析：設(shè)有m個任務(wù)，對m個任務(wù)進(jìn)行預(yù)處理，將其分割成{x1，x2，…，xn}大小的子任務(wù)，每個子任務(wù)的數(shù)量分別為{k1，k2，…，kq}， 其中n=∑qi=1ki，size（m）=∑0≤i≤n， 0≤j≤qsize（xi×kj），其中m表示Job的數(shù)量。之后將這n個子任務(wù)分配到虛擬機(jī)組V（V∈[1，M]）上執(zhí)行，最終得到一個處理n個任務(wù)的虛擬機(jī)序列編號，也就是任務(wù)的執(zhí)行方案。這個分配方案的完成時間FinishTime、所耗費用Cost分別為：

FinishTime=max1

其中：Time（i， j）為第j個任務(wù)在i號虛擬機(jī)上執(zhí)行所用的時間，k為虛擬機(jī)i分配的任務(wù)個數(shù)。

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

其中costi表示單位時間內(nèi)虛擬資源Vi的費用。

2?云環(huán)境下的任務(wù)調(diào)度

2.1?染色體的編碼與解碼

染色體的編碼有很多種方式，可以采用直接編碼（對任務(wù)的執(zhí)行狀態(tài)編碼），也可以采用間接編碼。在本文中采用的是三位十進(jìn)制的資源任務(wù)間接編碼，三位的十進(jìn)制數(shù)的表示編碼相較于二進(jìn)制表示同一個實數(shù)時，占用的字節(jié)數(shù)少，節(jié)省空間，相較于八進(jìn)制與十六進(jìn)制來說更加直觀。完成編碼之后，染色體的基因長度為子任務(wù)的數(shù)量，每個基因片段為該節(jié)點任務(wù)分配資源的虛擬機(jī)編號。如圖2所示，其中Ti為任務(wù)編號，Vi為虛擬機(jī)編號，本文中的染色體就是由虛擬機(jī)編號依次排列構(gòu)成的，也就是得到的任務(wù)調(diào)度分配方案。假設(shè)有6個任務(wù)，3臺虛擬機(jī)，得到一條染色體為：{002，003，002，002，001，003}，該染色體表示在V2虛擬機(jī)上有{T1，T3，T4}三個任務(wù)被執(zhí)行。

之后對染色體進(jìn)行解碼，即002解碼為2，003解碼為3。當(dāng)完成所有染色體的解碼之后，將會得到一個任務(wù)資源的矩陣，根據(jù)這個矩陣可以得到將所有任務(wù)執(zhí)行完畢的時間，也就是通過式（1）得到最后的完成時間。

2.2?適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是衡量個體性能是否優(yōu)良的標(biāo)準(zhǔn)，本文內(nèi)容的研究重點為任務(wù)調(diào)度后的執(zhí)行時間和費用與結(jié)果的穩(wěn)定性，穩(wěn)定性是對最后的結(jié)果進(jìn)行處理得到的，故不可以放在適應(yīng)度函數(shù)當(dāng)中。將式（1）、（2）結(jié)合起來，作為判斷染色體是否為優(yōu)良個體的適應(yīng)度函數(shù)f（x）設(shè)置為：

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

其中： α為執(zhí)行時間在適應(yīng)度函數(shù)當(dāng)中占比重的影響因子，α∈[0，1]。當(dāng)α取值為0.5時，在適應(yīng)度函數(shù)中任務(wù)的執(zhí)行時間與費用需要被同等考慮;若α>0.5，則表明在適應(yīng)度函數(shù)中，任務(wù)的執(zhí)行時間的權(quán)重較大。

關(guān)于算法的穩(wěn)定性，本文在實驗部分經(jīng)過多次實驗，將最后的結(jié)果進(jìn)行整理后進(jìn)行判斷。

2.3?遺傳操作

2.3.1?選擇部分

選擇操作是遺傳算法中根據(jù)個體適應(yīng)度選擇出優(yōu)良個體的操作，將適應(yīng)度高的染色體大概率地保留下來，并將其優(yōu)良的基因傳遞給下一代，保持種群性能的優(yōu)良，符合生物學(xué)中“物競天擇”的進(jìn)化論。根據(jù)式（3）得到每一個個體的適應(yīng)度函數(shù)的值后，可得每條染色體被選中的概率為：

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

利用輪盤賭算法進(jìn)行選擇時需要將種群中每個個體被選擇的概率制作成輪盤，通過式（4），可以得到第j個體在輪盤上顯示的區(qū)域為：

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

根據(jù)式（4）、（5），可以得出輪盤指針指向每一條染色體的概率為：

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

當(dāng)f（xj）越大，Pj″就越小，該染色體被選擇的概率就越低。

為了使得最終的結(jié)果不要過早地收斂，提高穩(wěn)定性，在本文中，通過n輪盤賭算法選擇之后，計算每次選擇后的個體組成的種群的方差D（n）。在數(shù)學(xué)上，方差是用來衡量一組數(shù)據(jù)波動大小的數(shù)字，方差的值越大，這一組數(shù)據(jù)波動越大，反之，則越小。它反映樣本與平均值的偏離程度，但這個偏離可以是正向偏離，也可以是負(fù)向偏離。方差D（n）是統(tǒng)計與概率學(xué)的一個概念：

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

在遺傳算法中的初始化部分，染色體是隨機(jī)產(chǎn)生的，每次初始化產(chǎn)生的種群中的個體，從原來的種群選出新的種群時具有較大的波動性，這種波動給遺傳算法產(chǎn)生的結(jié)果帶來了雙面的影響：一方面，擴(kuò)大了遺傳算法搜索最優(yōu)解的范圍，經(jīng)過多次實驗可以找到一個最佳的解;另一方面，初始化的波動導(dǎo)致最后的結(jié)果不具有穩(wěn)定性，多次實驗結(jié)果不是同一個確定的值，故在應(yīng)用時不能保證當(dāng)前實驗結(jié)果就是最優(yōu)解。

在本文中，將方差與遺傳算法結(jié)合，利用波動性好的一面，盡量減少負(fù)面影響，可以讓結(jié)果得到進(jìn)一步的優(yōu)化。

而在本文中，需要的是正向偏離，也就是種群中包含的個體種類的個數(shù)多于平均值，偏離的值越大，種群的多樣性越好。為了保證是正向偏離，所以對式（7）進(jìn)行處理，令：

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

D′（i）為與偏離方向保持一致的方差，如果該種群個體的多樣性小于平均值，D′（i）<0;否則，D′（i）>0。

在n次選擇之后，通過式（8）計算找到D′（i）max，并將與之對應(yīng)所產(chǎn)生的種群作為新的種群。通過方差，將包含個體種類最多的種群留下進(jìn)行之后的操作，個體的種類越多，則種群的多樣性越豐富，能擴(kuò)大尋找較優(yōu)解的搜索范圍，在一定程度上減少了算法的過早收斂問題的出現(xiàn)。

本文中選擇部分的思想為：采用多次選擇的方式提高種群的多樣性與種群整體的性能，擴(kuò)大后續(xù)對較優(yōu)解的搜索范圍。偽碼如下：

程序前

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;另外一種方式是利用自適應(yīng)算法得出交叉概率[6]，如

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

k2，f（x）′

其中：f（x）avg為種群染色體的平均適應(yīng)度函數(shù)值，f（x）′為兩條染色體中較好個體的適應(yīng)度函數(shù)值，f（x）avg為種群中最好個體的適應(yīng)度函數(shù)值。根據(jù)式（9）計算得出隨著染色體性能變化而變化的交叉概率。交叉操作的目的是豐富種群個體的多樣性，避免陷入局部最優(yōu)解。自適應(yīng)交叉概率的計算過程中，為了保證個體的優(yōu)良性，當(dāng)交叉的兩條染色體中有一條染色體的適應(yīng)度函數(shù)值大于f（x）avg，兩條染色體的交叉概率相對較小，這樣可以盡可能地留下性能好的個體;否則，交叉概率較大，起到豐富種群多樣性的作用。

但是，兩條性能較差的染色體進(jìn)行交叉產(chǎn)生的新個體的性能相對較差。為了能夠解決這一問題，本文對交叉操作作出了如下改進(jìn)：當(dāng)兩條染色體的適應(yīng)度函數(shù)值都低于f（x）avg時，從種群中隨機(jī)選出兩條適應(yīng)度函數(shù)值大于f（x）avg的染色體，進(jìn)行兩兩交叉，產(chǎn)生新的個體。這樣產(chǎn)生的新個體可以在豐富種群多樣性的同時保證了新個體性能有較大的可能高于原先適應(yīng)度函數(shù)值低于f（x）avg的兩個個體，保證新的種群在整體的適應(yīng)度上優(yōu)于交叉前的種群。

交叉部分的思想為盡可能地將舊種群的個體保留到新的種群中，將性能差的個體用來提高種群的多樣性，并且提高種群整體的性能。偽碼如下：

程序前

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?變異操作

在執(zhí)行變異操作之前，需要確定被選中的染色體變異的位置，用rand（）函數(shù)在變異操作中，存在一個關(guān)鍵參數(shù)：變異概率pm，對pm的處理與pc類似，對于指定概率C2，其取值范圍通常在0.01～0.1，另一種方式也是利用自適應(yīng)算法，如式（9）所示得到變異概率。

為了保證個體始終能向好的方向進(jìn)化，采用了定向變異。定向變異是本文對于遺傳算法應(yīng)用到云任務(wù)調(diào)用的改進(jìn)。當(dāng)被選中要變異的個體經(jīng)過變異操作得到新的個體后，計算得出其適應(yīng)度f（xj′）與被選中個體適應(yīng)度f（xj）進(jìn)行比較。若f（xj′）

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

由于虛擬機(jī)的性能各不相同，提交上來的任務(wù)也是有長有短，這就造成了每臺虛擬機(jī)對同一個任務(wù)的執(zhí)行時間是不同的，而該任務(wù)在任務(wù)隊列中的位置將影響其等待時間，其分配到的虛擬機(jī)將影響其執(zhí)行時間。

通常，縮小關(guān)于獨立任務(wù)的完成時間，是通過減少執(zhí)行時間或是減少等待時間來實現(xiàn)的，但是會出現(xiàn)第j個任務(wù)在隊列的k位置，再分配到i虛擬機(jī)上，會存在其等待時間是在所有虛擬機(jī)上最短的，由于任務(wù)過長，或者虛擬機(jī)性能不佳，導(dǎo)致任務(wù)j的執(zhí)行時間不是最短的。綜合這兩個方面的因素，將兩個時間結(jié)合到一起，可以最大限度減少該任務(wù)的完成時間，從而縮短所有任務(wù)的最終完成時間。

具體步驟如下：

1）取出變異個體的變異點，獲得j任務(wù)的長度;

2）遍歷所有的虛擬機(jī)，找到minFinishTime（i）j，獲取虛擬機(jī)編號i;

3）將虛擬機(jī)Vi替換到變異的點，完成定向變異。

變異操作對應(yīng)的偽碼如下：

程序前

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?實驗仿真與結(jié)果對比

3.1?實驗環(huán)境配置

在本文中，實驗是在虛擬平臺workflowSim對任務(wù)調(diào)度進(jìn)行實驗?zāi)M。為了證明實驗的有效性，與GA和現(xiàn)在側(cè)重于縮短執(zhí)行時間的遺傳算法（CWTSGA）處理云任務(wù)調(diào)度進(jìn)行了對比，并對實驗需要用到的虛擬機(jī)與主機(jī)環(huán)境在仿真平臺上進(jìn)行了設(shè)置，其設(shè)置信息如表1與表2，確保在同等環(huán)境下對這三種實驗進(jìn)行仿真。

在本文的仿真實驗中，共設(shè)置了100臺虛擬機(jī)V，100臺主機(jī)host，其種類信息如上述的表1與表2所示。相關(guān)的參數(shù)如表3所示，在表3中，CWTSGA的參數(shù)設(shè)置是根據(jù)文獻(xiàn)[4]中的參數(shù)進(jìn)行設(shè)置的，自適應(yīng)算法中涉及到的k1，k2是參考文獻(xiàn)[6]當(dāng)中的參數(shù)進(jìn)行設(shè)置。

3.2?實驗結(jié)果對比與分析

在本文中，將三種算法從任務(wù)調(diào)度的策略性與最終結(jié)果的穩(wěn)定性兩個方面進(jìn)行了對比與分析。

3.2.1?任務(wù)調(diào)度策略性的結(jié)果對比與分析

在本文中，通過4組不同數(shù)量與類型的任務(wù)進(jìn)行實驗驗證新型GA在云任務(wù)調(diào)度的運用的結(jié)果優(yōu)于傳統(tǒng)GA在云任務(wù)調(diào)度的運用。為了證明其研究必要，在每一組實驗當(dāng)中，都將任務(wù)分成了4個類別，每個類別的任務(wù)長度各不相同。

通過對總?cè)蝿?wù)數(shù)量分別為：500、1-000、1-500和3-000用傳統(tǒng)的GA、CWTSGA和VDVGA進(jìn)行75次實驗，求得平均值用時，將結(jié)果整理繪制成圖3（a）。

將圖3結(jié)合對比，可以得出：三種調(diào)度算法在費用上的差別是十分微小的，幾乎可以忽略，但是在時間上卻有著顯著的差別。對于小型任務(wù)來說，即圖3（a）中任務(wù)數(shù)量為500時，三者基本沒有差別;隨著任務(wù)數(shù)量的增加，VDVGA與GA、CWTSGA的差距逐漸擴(kuò)大，當(dāng)任務(wù)規(guī)模達(dá)到1-500時，可以看到VDVGA任務(wù)調(diào)度的完成時間上是用時最少的，與GA有明顯差距，與CWTSGA對比也可以看出在費用幾乎沒有差別的情況下，在時間上VDVGA也是具有優(yōu)勢的;當(dāng)任務(wù)數(shù)量達(dá)到3-000時，DDGA與GA、CWTSGA在時間上的差距相較于任務(wù)規(guī)模為1-000與1-500時更大，VDVGA所需的完成時間最少。

分析可以得出：通過對GA的改進(jìn)提高了GA的尋優(yōu)能力，這是通過：在交叉部分建立的新的交叉機(jī)制，保證了種群整體的適應(yīng)度在每次迭代的過程中都得以提高;在變異部分，定向變異與傳統(tǒng)變異的結(jié)合保證了經(jīng)過變異的個體是向性能更加優(yōu)良的方向發(fā)展的。而在實際的應(yīng)用中，云平臺處理的任務(wù)數(shù)量遠(yuǎn)遠(yuǎn)超過3-000，大多情況下處理的為大型任務(wù)，這些大型任務(wù)會被分割成大量甚至海量的子任務(wù)，當(dāng)任務(wù)數(shù)量越多，在費用相同的情況下VDVGA云任務(wù)調(diào)度節(jié)省的時間就會更多，也就說明對任務(wù)的分配方案就更加合理，其策略性也就越好。

3.2.2?結(jié)果穩(wěn)定性的對比與分析

對于遺傳算法來說，除了尋優(yōu)能力差，還有一個明顯的缺點就是經(jīng)過多次實驗后得到的結(jié)果具有極大的波動性，本文通過對遺傳算法的改進(jìn)在穩(wěn)定性方面與GA、CWTSGA針對執(zhí)行時間進(jìn)行了對比。

在本文中，對500個任務(wù)和1-000個任務(wù)的兩種調(diào)度方式選取了10組值繪制成圖4，通過觀察可以得到：VDVGA云任務(wù)調(diào)度的值波動較小，這是因為在進(jìn)行選擇操作時，利用方差擴(kuò)大了種群個體的多樣性，提高了性能優(yōu)良個體被選中的概率，在交叉部分建立的新的交叉機(jī)制在保證種群多樣性的前提下，在整體上提高了種群中個體的性能，而傳統(tǒng)GA云任務(wù)調(diào)度的值波動比較大。也就可以得出VDVGA云任務(wù)調(diào)度得到的任務(wù)調(diào)度方案在時間上是相對穩(wěn)定的。與當(dāng)前的CWTSGA云任務(wù)調(diào)度相比，VDVGA的波動也是要小于CWTSGA的。

綜上所述，從時間與穩(wěn)定性兩個方面看，對于大規(guī)模云任務(wù)調(diào)度來說，VDVGA都優(yōu)于傳統(tǒng)GA與CWTSGA。

4?結(jié)語

在本文的工作中，確實通過對遺傳算法的改進(jìn)縮短了任務(wù)調(diào)度之后得到的最佳方案的執(zhí)行時間，在實際應(yīng)用中，能夠更快更好地處理用戶提交的任務(wù)，但是還是存在一些不足，如費用并沒有明顯的變化，這是在今后的工作中需要進(jìn)行研究的內(nèi)容;其次，本文主要的研究對象為遺傳算法，對其他的其方式算法還沒有進(jìn)行深入研究，下一步將會對其他啟發(fā)式算法進(jìn)行任務(wù)調(diào)度的研究。

參考文獻(xiàn) （References）

[1]?胡艷華，唐新來. 基于改進(jìn)遺傳算法的云計算任務(wù)調(diào)度算法[J]. 計算機(jī)技術(shù)與發(fā)展，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]?孫敏，陳中雄，盧偉榮. 云環(huán)境下基于DOGAPSO的任務(wù)調(diào)度算法[J]. 計算機(jī)科學(xué)， 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.