基于改進混合遺傳算法的云資源調(diào)度算法

黃海芹，林基明，王俊義

(桂林電子科技大學(xué) 廣西信息實驗中心，廣西 桂林 541004)

基于改進混合遺傳算法的云資源調(diào)度算法

黃海芹，林基明，王俊義

(桂林電子科技大學(xué) 廣西信息實驗中心，廣西 桂林 541004)

在云計算中，系統(tǒng)規(guī)模和虛擬機遷移數(shù)量都是十分龐大的，需要高效的調(diào)度策略對其進行優(yōu)化。將云計算的任務(wù)分配抽象為背包求解問題，可通過遺傳算法進行求解。傳統(tǒng)的遺傳算法具有局部搜索能力差以及早熟現(xiàn)象的缺點，采用遺傳和貪婪相結(jié)合的混合遺傳算法。針對混合遺傳算法在資源利用率與能源消耗的收斂速度較慢問題，通過改進適應(yīng)度函數(shù)，改變了適應(yīng)度函數(shù)在不同染色體間的差異度，從而提高了染色體在選擇算子中的擇優(yōu)性能。仿真結(jié)果表明，該方法能夠有效提高混合遺傳算法在云計算資源優(yōu)化中的收斂速度。

云計算；資源調(diào)度；混合遺傳算法

隨著云計算[1]技術(shù)的日趨成熟，與之相關(guān)的服務(wù)和應(yīng)用也在逐年遞增，使得云計算環(huán)境下的服務(wù)器數(shù)量高速增長。因此，如何合理地分配這些資源來提高云計算系統(tǒng)的整體性能和效率，是云計算的一個關(guān)鍵性問題。

目前，在云計算環(huán)境下基于遺傳算法的資源調(diào)度問題已經(jīng)進行了大量研究工作。文獻[2]提出一種雙適應(yīng)度的遺傳算法，通過兩個適應(yīng)度函數(shù)來選擇種群，從而保證較短的總?cè)蝿?wù)執(zhí)行時間和任務(wù)平均執(zhí)行時間。由于云計算的中心思想，是實現(xiàn)廉價高效的運算，對整個系統(tǒng)進行負載均衡研究是十分重要的。文獻[3]通過自適應(yīng)的變異概率，對任務(wù)響應(yīng)時間和資源損耗代價同時進行優(yōu)化。不但最短化任務(wù)執(zhí)行時間，而且使虛擬機群的資源利用率最高。但未解決傳統(tǒng)遺傳算法局部搜索能力差以及早熟現(xiàn)象等問題。因此從改變?nèi)旧w的編碼方式出發(fā)，文獻[4]采用組方式和三空間分割方法分別對染色體進行編碼和譯碼，并根據(jù)不同染色體長度的變化設(shè)計交叉和變異遺傳算子，算法對解空間內(nèi)的多個區(qū)域同時搜索，具有群體和自我進化的優(yōu)勢，優(yōu)化一次即可獲得對不同目標的權(quán)值運算多次才能得到的最優(yōu)解，提高了獲得最優(yōu)解的速度。文獻[5]基于負載均衡度和最優(yōu)跨度準則，改進了染色體編碼方式，這種編碼方式所形成的基因串的總數(shù)小于系統(tǒng)資源池內(nèi)的總數(shù)，所以在計算過程中可以達到最優(yōu)的資源調(diào)度，從而達到提高計算速度和計算準確度的目的。從初始化種群出發(fā)，文獻[6]通過染色體匹配率將種群個體均勻分布在解空間上，有效地避免了早熟問題；并通過對作業(yè)運行時間、費用、系統(tǒng)帶寬以及服務(wù)質(zhì)量的子適應(yīng)度函數(shù)加權(quán)獲得總適應(yīng)度函數(shù)，并通過調(diào)節(jié)權(quán)值系數(shù)來滿足不同用戶需求。從混合遺傳算法出發(fā)，文獻[7]使用了多Agent與遺傳算法相結(jié)合的混合遺傳算法，通過個體之間的交互、協(xié)作和自學(xué)習(xí)，在解決負載均衡問題的同時具有更好的算法收斂性能。文獻[8]提出了將貪婪和遺傳算法相結(jié)合的混合遺傳算法，對每個染色體都通過貪婪算法進行處理，達到內(nèi)存使用量最小，同時能夠在較短的時間內(nèi)找到問題的優(yōu)化解。但這種使得內(nèi)存使用量最小的方法依然會出現(xiàn)局部最優(yōu)解的可能。文獻[9]同樣采用了貪婪與遺傳算法相結(jié)合的方式，這里貪婪算法只對無效染色體進行處理，將物理機使用數(shù)量引入總適應(yīng)度函數(shù)，可降低局部最優(yōu)解的出現(xiàn)。并分別從物理機使用數(shù)量、負載均衡度和遷移次數(shù)3個方面進行加權(quán)組合，對資源利用率、能源節(jié)約和遷移代價多目標問題進行聯(lián)合優(yōu)化。但負載均衡度和遷移次數(shù)的適應(yīng)度函數(shù)在不同染色體間的差異度不足，限制了算法的收斂速度；同時只通過物理機數(shù)量來衡量內(nèi)存使用量是不完善的。

針對文獻[9]的不足，本文提出了以下兩個改進方法：一是對其適應(yīng)度函數(shù)進行改進，從遺傳算法染色體選擇性出發(fā)，通過提高染色體間的優(yōu)選概率，進而提升遺傳算法的收斂速度；二是提出了內(nèi)存適應(yīng)度函數(shù)，將其與物理機數(shù)量適應(yīng)度函數(shù)相結(jié)合，增加相同物理機數(shù)量染色體間內(nèi)存使用量的差異度，進一步提高內(nèi)存使用率的同時，也提高了選擇算子中的擇優(yōu)性能。仿真結(jié)果表明，該方法能夠有效提高遺傳算法的收斂速度。

1 總體架構(gòu)調(diào)度系統(tǒng)模型

任務(wù)上傳到云端的數(shù)據(jù)中心，數(shù)據(jù)中心的調(diào)度器響應(yīng)該任務(wù)，將其隨機分配給物理機PM，并在PM上建立相應(yīng)的虛擬機VM來執(zhí)行該任務(wù)。由于應(yīng)用程序信息的不確定性以及PM處理能力的差異性，導(dǎo)致了PM負載不均衡，因此需要實施高效的調(diào)度策略，通過遷移VM技術(shù)來協(xié)調(diào)不同PM上的負載，提高資源利用率，同時也降低系統(tǒng)能耗。調(diào)度系統(tǒng)模型示意圖，如圖1所示[10]。

圖1 調(diào)度系統(tǒng)模型示意圖

通過云端的檢測模塊，檢測初始負載信息和VM的配置信息。然后執(zhí)行調(diào)度策略，得到新的配置方案。將其與原配置方案進行比較，是否提高資源利用率。具體通過以下指標進行判斷：PM的使用數(shù)量和使用的PM負載均衡度。由于通過遷移VM技術(shù)來執(zhí)行調(diào)度策略的結(jié)果，所以還需要考慮VM遷移成本。若遷移成本太高，則不執(zhí)行調(diào)度算法；反之執(zhí)行調(diào)度算法。

2 混合遺傳算法

為了解決云端資源優(yōu)化問題，可采用基于多維混合遺傳算法的資源調(diào)度策略[9]。算法考慮了3個評價指標，包括PM使用數(shù)量、負載差異度和VM遷移次數(shù)。并將其進行加權(quán)組合，實現(xiàn)了權(quán)值可調(diào)的多目標優(yōu)化。

2.1 混合遺傳算法

混合遺傳算法執(zhí)行過程如圖2所示。

圖2 混合遺傳算法流程圖

1)選取種群數(shù)目P，種群中的個體稱為染色體。每個染色體代表著一種VM配置方案，即將所有VM分配在哪些PM上。

2)計算種群中每個個體的適應(yīng)度函數(shù)值。

3)選擇：通過適應(yīng)度函數(shù)值得到累積概率，進行染色體的選擇。

4)交叉：采用單點交叉法，即隨機設(shè)置一個交叉點，在該點相互交換部分染色體。

5)修正無效因子：由于每個PM內(nèi)存是有限的，這樣經(jīng)過交叉后的染色體，可能會產(chǎn)生無效因子，此時通過貪婪算法對無效因子進行修正。

6)變異：依據(jù)變異概率將染色體中的某個基因值用其他值替換，從而形成一個新的個體。

7)修正無效因子：同步驟5)。

8)是否達到最大進化代數(shù)，如果已是最大代數(shù)，則產(chǎn)生最優(yōu)個體，算法結(jié)束。反之，則返回到步驟2)。

注意，為了確保當前種群中最好的個體不被交叉或變異操作破壞，將其直接保留至下一代，覆蓋下一代種群中最差的個體。

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

適應(yīng)度函數(shù)由3種子適應(yīng)度函數(shù)組合而成，表示染色體被選擇的概率。適應(yīng)度函數(shù)值越高，染色體被選中的概率越大，反之，則被選中的概率越小。3種子適應(yīng)度函數(shù)代表著3種評價指標，分別是對物理機使用數(shù)量、負載差異度和VM遷移次數(shù)的評價。下面進行具體描述。

1)子適應(yīng)度函數(shù)Ei1

物理機數(shù)量的評價函數(shù)Ei1為

(1)

式中：pm表示云端的物理機數(shù)量；counti表示第i條染色體占用的物理機數(shù)量；p表示種群中含有的染色體數(shù)量。

2)子適應(yīng)度函數(shù)Ei2

則第k個物理機的負載差異度為

(2)

則第i個染色體負載差異度為

Si=∑Vk

(3)

因此，負載差異度的評價函數(shù)Ei2可表示為

(4)

3)子適應(yīng)度函數(shù)Ei3

遷移次數(shù)的評價函數(shù)Ei3可表示為

(5)

4)子適應(yīng)度函數(shù)Ei

Ei為總適應(yīng)度函數(shù)，其將3個子適應(yīng)度函數(shù)進行加權(quán)求和

Ei=xEi1+yEi2+zEi3

(6)

式中：x，y和z分別為Ei1，Ei2和Ei3的權(quán)重系數(shù)，且x+y+z=1。通過改變這3個系數(shù)的值來調(diào)節(jié)評價指標所占的權(quán)重。

2.3 評價函數(shù)的差異度

3 改進的評價函數(shù)

3.1 改進的適應(yīng)度函數(shù)

(7)

其中，Smax表示種群中最大的負載差異度。

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

圖3 選擇概率的示意圖

(16)

式中：Mi表示第i條染色體需要遷移虛擬機的次數(shù)；vm表示總虛擬機的個數(shù)。

而對于物理機數(shù)量的評價函數(shù)Ei1，其使用物理機數(shù)量的最大值即為物理機的總數(shù)量pm，因此不需要進行改動。

3.2 內(nèi)存適應(yīng)度函數(shù)

PM內(nèi)存利用率對衡量資源利用率是一個很重要的指標。雖然貪婪算法是以內(nèi)存最小化為目標修正無效因子，但是在選擇最優(yōu)染色體的時候，評價函數(shù)并不會因此選擇內(nèi)存空閑率低的染色體。圖4所示為更新迭代150次后，物理機數(shù)量達到最小染色體的內(nèi)存使用量。從圖中可以看出，具有物理機數(shù)量最小的染色體方案不止一種，但每種方案物理機的內(nèi)存空閑量是不同的，這表明評價函數(shù)不僅要考慮物理機數(shù)量，同時也應(yīng)該考慮到內(nèi)存使用量。所以需要選取恰當?shù)奈锢頇C以便滿足虛擬機的需求，同時還不浪費物理機的內(nèi)存資源。

圖4 物理機內(nèi)存空閑量

1)內(nèi)存利用率評價指標

(17)

式(17)為物理機內(nèi)存利用率評價函數(shù)。其中，sum_pm表示云端所有物理機的內(nèi)存和；Ri表示第i個染色體的閑置內(nèi)存量，閑置內(nèi)存量為染色體中所使用PM的總?cè)萘颗c所有虛擬機的內(nèi)存容量之差。

總的適應(yīng)度函數(shù)需要綜合所有子適應(yīng)度函數(shù)，原有的方法是將子適應(yīng)度函數(shù)進行加權(quán)求和得到總的適應(yīng)度函數(shù)Ei。但在一些情況下，這樣直接進行加權(quán)求和存在一定的問題，如物理機數(shù)量越小內(nèi)存空閑率就會越小，這樣內(nèi)存空閑率與物理機數(shù)量具有一定的相關(guān)度，如果直接進行加權(quán)，會使得總的適應(yīng)度函數(shù)值偏向物理機數(shù)量和內(nèi)存空閑率這兩個評價指標，會造成對其他評價指標的不公平性。

(18)

(19)

4 仿真結(jié)果及分析

4.1 遺傳算法收斂性

仿真參數(shù)如表1所示。

表1 仿真參數(shù)表

參數(shù)類型數(shù)值物理機數(shù)量100物理機配置類型[2048，3072，4096]虛擬機數(shù)量200虛擬機配置類型[512，1024，1536，2048]負載范圍(歸一化)[0 2，0 8]種群個數(shù)200更新代數(shù)150交叉概率0 8變異概率0 01

為了更好地分析物理機負載均衡度和虛擬機遷移度的收斂性能，分別取負載均衡加權(quán)系數(shù)為0.9和遷移度加權(quán)系數(shù)為0.9，對原始算法與改進算法的收斂曲線進行對比，如圖5、圖6所示。物理機數(shù)量變化率為最優(yōu)方案與原始方案的物理機數(shù)量之比；負載均衡變化率為最優(yōu)方案與原始方案的協(xié)方差之比；遷移次數(shù)變化率為最優(yōu)方案的遷移次數(shù)與總的VM數(shù)量之比。

圖5 負載均衡度收斂性能對比圖

圖6 遷移度的收斂曲線對比圖

從圖5、圖6可以看出，隨著遺傳迭代次數(shù)的增加，負載均衡變化率和遷移次數(shù)變化率逐漸降低。但改進后的負載均衡度和遷移次數(shù)變化率曲線整體要低于原始的收斂性曲線，說明在相同的遺傳迭代次數(shù)下，改進后的遺傳算法的收斂速度比原始方法的收斂速度快，這與理論分析一致。

圖7、圖8所示迭代150次后，負載均衡度和遷移度隨權(quán)值變化曲線。

圖7 不同加權(quán)系數(shù)下的負載均衡度曲線對比圖

圖8 不同加權(quán)系數(shù)下的遷移次數(shù)變化率曲線對比圖

從圖7中可以看出，隨著負載加權(quán)系數(shù)y的逐步增大，負載均衡度在Ei中的比重就會增大，所以負載均衡變化率會逐步降低。同時，從圖8可以看出，隨著遷移度權(quán)重z的增大，遷移次數(shù)變化率也逐步降低。但是經(jīng)過改進后得到的負載均衡度曲線和遷移次數(shù)變化率曲線整體均低于改進前的負載均衡度和遷移次數(shù)變化率曲線。這表明改進后的方法在不同的加權(quán)系數(shù)下均具有更好的收斂速度。

4.2 內(nèi)存使用率的收斂性

圖9 內(nèi)存空閑率收斂性對比圖

圖10 物理機使用率收斂性對比圖

圖11 不同加權(quán)系數(shù)下的收斂性對比曲線

5 小結(jié)

本文基于混合遺傳算法在云計算資源調(diào)度中的應(yīng)用，對其收斂性能進行了分析，并通過改進其評價函數(shù)，增加了適應(yīng)度函數(shù)值在不同染色體間的差異度，提高了染色體的擇優(yōu)性。同時提出了內(nèi)存使用率的評價函數(shù)，通過將物理機數(shù)量與內(nèi)存使用量適應(yīng)度值相結(jié)合，提升了內(nèi)存的優(yōu)化效率。最后通過仿真對比，表明算法的收斂速度得到了有效的提高。

[1] FOSTER I, ZHAO Y, RAICU I, et al. Cloud computing and grid computing 360-degree compared[C]//Proc. IEEE Grid Computing Environments Workshop (GCE'08). [S.l.]:IEEE Press，2008: 1-10.

[2] 李建鋒, 彭艦. 云計算環(huán)境下基于改進遺傳算法的任務(wù)調(diào)度算法[J].計算機應(yīng)用, 2011(1): 184-186.

[3] 劉漳輝,王曉莉. 云計算虛擬機群中帶遺傳算法的負載均衡算法[J].福州大學(xué)學(xué)報：自然科學(xué)版, 2012(4): 453-458.

[4] 李強, 郝沁汾, 肖利民, 等. 云計算中虛擬機放置的自適應(yīng)管理與多目標優(yōu)化[J].計算機學(xué)報, 2011(12): 2253-2264.

[5] 劉愉, 趙志文, 李小蘭, 等. 云計算環(huán)境中優(yōu)化遺傳算法的資源調(diào)度策略[J].北京師范大學(xué)學(xué)報：自然科學(xué)版, 2012(4): 378-384.

[6] 熊聰聰, 馮龍, 陳麗仙, 等. 云計算中基于遺傳算法的任務(wù)調(diào)度算法研究[J].華中科技大學(xué)學(xué)報：自然科學(xué)版, 2012(40):1-4.

[7] 程國建, 劉麗景, 石彩云, 等. 一種混合遺傳算法在云計算負載均衡中的應(yīng)用研究[J].西安石油大學(xué)學(xué)報：自然科學(xué)版, 2012(2): 93-123.

[8] 吳世山, 翟健宏. 基于混合遺傳算法的云計算任務(wù)節(jié)能調(diào)度算法[J].智能計算機與應(yīng)用, 2013(6): 36-43.

[9] CHEN S, WU J, LU Z. A cloud computing resource scheduling policy based on genetic algorithm with multiple fitness[C]//Proc. 12th IEEE International Conference on Computer and Information Technology (CIT). [S.l.]:IEEE Press，2012: 177-184.

[10]GKATZIKIS L, KOUTSOPOULOS I. Migrate or not? exploiting dynamic task migration in mobile cloud computing systems[J].IEEE Wireless Communications, 2013, 20(3): 24-32.

黃海芹(1989— )，女，碩士研究生，主研通信網(wǎng)絡(luò)的性能分析與優(yōu)化；

林基明(1970— )，教授，博士生導(dǎo)師，主要研究方向為無線通信技術(shù)；

王俊義(1977— )，副教授，碩士生導(dǎo)師，主要研究方向為無線通信網(wǎng)絡(luò)的性能分析與優(yōu)化。

責任編輯：許 盈

Cloud Resource Scheduling Based on Improved Hybrid Genetic Algorithm

HUANG Haiqin, LIN Jiming, WANG Junyi

(GuangxiExperimentCenterofInformationScience,GuangxiGuilinUniversityofElectronicTechnology,GuangxiGuilin541004,China)

The size of system and the number of virtual machine migration in cloud computing are very large, for which the efficient scheduling strategy is essential. The task allocation for cloud computing can be abstracted to knapsack problem, and then is solved by genetic algorithm. The traditional genetic algorithm has the shortcoming of poor local searching ability and precocious phenomenon, which can adopt the combination of genetic and greed hybrid genetic algorithm to solve. For hybrid genetic algorithm convergence speed problem in resource utilization and energy consumption, in this paper, the fitness function is changed to increase the difference of chromosomes and improve the performance of chromosome preferred in selection operator. The simulation results show that this method can effectively improve the hybrid genetic algorithm convergence speed in cloud computing resources optimization.

cloud computing; resource scheduling; hybrid genetic algorithm

國家自然科學(xué)基金項目(61172054；61362006)；廣西自然科學(xué)基金項目(2014GXNSFAA118387； 2013GXNSFAA019334)；桂林電子科技大學(xué)研究生創(chuàng)新項目(GDYCS201409)

TP393.01

A

10.16280/j.videoe.2015.18.009

2015-03-16

【本文獻信息】黃海芹，林基明，王俊義.基于改進混合遺傳算法的云資源調(diào)度算法[J].電視技術(shù),2015，39(18).