基于多精英協同進化遺傳算法的云資源調度

魏士偉 鄧 維

(桂林航天工業學院計算機科學與工程學院 廣西 桂林 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求解出的最終解總是優于另外三個算法的最終解，其尋找最優解和跳出局部最優的能力表現得十分明顯，魯棒性更好。