基于改進混合遺傳算法的云資源調度算法

黃海芹，林基明，王俊義

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

基于改進混合遺傳算法的云資源調度算法

黃海芹，林基明，王俊義

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

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

云計算；資源調度；混合遺傳算法

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

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

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

1 總體架構調度系統模型

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

圖1 調度系統模型示意圖

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

2 混合遺傳算法

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

2.1 混合遺傳算法

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

圖2 混合遺傳算法流程圖

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

2)計算種群中每個個體的適應度函數值。

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

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

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

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

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

8)是否達到最大進化代數，如果已是最大代數，則產生最優個體，算法結束。反之，則返回到步驟2)。

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

2.2 適應度函數

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

1)子適應度函數Ei1

物理機數量的評價函數Ei1為

(1)

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

2)子適應度函數Ei2

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

(2)

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

Si=∑Vk

(3)

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

(4)

3)子適應度函數Ei3

遷移次數的評價函數Ei3可表示為

(5)

4)子適應度函數Ei

Ei為總適應度函數，其將3個子適應度函數進行加權求和

Ei=xEi1+yEi2+zEi3

(6)

式中：x，y和z分別為Ei1，Ei2和Ei3的權重系數，且x+y+z=1。通過改變這3個系數的值來調節評價指標所占的權重。

2.3 評價函數的差異度

3 改進的評價函數

3.1 改進的適應度函數

(7)

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

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

圖3 選擇概率的示意圖

(16)

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

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

3.2 內存適應度函數

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

圖4 物理機內存空閑量

1)內存利用率評價指標

(17)

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

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

(18)

(19)

4 仿真結果及分析

4.1 遺傳算法收斂性

仿真參數如表1所示。

表1 仿真參數表

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

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

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

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

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

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

圖7 不同加權系數下的負載均衡度曲線對比圖

圖8 不同加權系數下的遷移次數變化率曲線對比圖

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

4.2 內存使用率的收斂性

圖9 內存空閑率收斂性對比圖

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

圖11 不同加權系數下的收斂性對比曲線

5 小結

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

[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] 李建鋒, 彭艦. 云計算環境下基于改進遺傳算法的任務調度算法[J].計算機應用, 2011(1): 184-186.

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

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

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

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

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

[8] 吳世山, 翟健宏. 基于混合遺傳算法的云計算任務節能調度算法[J].智能計算機與應用, 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— )，女，碩士研究生，主研通信網絡的性能分析與優化；

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

王俊義(1977— )，副教授，碩士生導師，主要研究方向為無線通信網絡的性能分析與優化。

責任編輯：許 盈

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

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

TP393.01

A

10.16280/j.videoe.2015.18.009

2015-03-16

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