孫敏 葉僑楠 陳中雄

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

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

中圖分類號(hà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?引言

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

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

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

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

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

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

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

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

FinishTime=max1

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

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

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

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

2.1?染色體的編碼與解碼

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

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

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

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

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

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

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

2.3?遺傳操作

2.3.1?選擇部分

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

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

利用輪盤賭算法進(jìn)行選擇時(shí)需要將種群中每個(gè)個(gè)體被選擇的概率制作成輪盤，通過(guò)式（4），可以得到第j個(gè)體在輪盤上顯示的區(qū)域?yàn)椋?/p>

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

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

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

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

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

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

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

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

本文中選擇部分的思想為：采用多次選擇的方式提高種群的多樣性與種群整體的性能，擴(kuò)大后續(xù)對(duì)較優(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?交叉操作

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

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

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

程序前

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ù)在變異操作中，存在一個(gè)關(guān)鍵參數(shù)：變異概率pm，對(duì)pm的處理與pc類似，對(duì)于指定概率C2，其取值范圍通常在0.01～0.1，另一種方式也是利用自適應(yīng)算法，如式（9）所示得到變異概率。

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

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

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

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

具體步驟如下：

1）取出變異個(gè)體的變異點(diǎn)，獲得j任務(wù)的長(zhǎng)度;

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

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

變異操作對(duì)應(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?實(shí)驗(yàn)仿真與結(jié)果對(duì)比

3.1?實(shí)驗(yàn)環(huán)境配置

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

在本文的仿真實(shí)驗(yàn)中，共設(shè)置了100臺(tái)虛擬機(jī)V，100臺(tái)主機(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?實(shí)驗(yàn)結(jié)果對(duì)比與分析

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

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

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

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

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

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

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

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

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

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

4?結(jié)語(yǔ)

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

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

[1]?胡艷華，唐新來(lái). 基于改進(jìn)遺傳算法的云計(jì)算任務(wù)調(diào)度算法[J]. 計(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ì)算機(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.