云環境下方差定向變異遺傳算法的任務調度

孫敏 葉僑楠 陳中雄

摘 要：云環境下遺傳算法（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.