劉　峰，畢　利，楊　軍

（1.寧夏大學數(shù)學計算機學院，銀川　750021；2.寧夏大學計算機網(wǎng)絡管理中心，銀川　750021）

一種用于云計算資源調(diào)度的改進遺傳算法

劉峰1，畢利1，楊軍2

（1.寧夏大學數(shù)學計算機學院，銀川750021；2.寧夏大學計算機網(wǎng)絡管理中心，銀川750021）

針對輪詢調(diào)度算法、遺傳算法和模擬退火算法在云計算資源調(diào)度中存在收斂速度慢、易早熟和資源負載不均衡等問題，提出了一種基于模擬退火思想的改進遺傳算法（simulated annealing improved genetic algorithm：SAIGA）；改進算法設計了基于任務平均完成時間和負載均衡的雙適應度函數(shù)和自適應的交叉變異概率函數(shù)，允許算法在退火過程中以一定概率接受劣質(zhì)解從而避免早熟現(xiàn)象的發(fā)生，將虛擬資源上任務分配數(shù)的標準差作為選擇個體的依據(jù)來實現(xiàn)節(jié)點的負載均衡；仿真結(jié)果表明，改進算法與上述算法相比，在任務平均完成時間、資源利用率以及收斂速度上表現(xiàn)得更優(yōu)越，能夠較快地找到資源最優(yōu)調(diào)度方案，具有較好的可行性和實用性。

云計算；輪詢調(diào)度；模擬退火思想；改進遺傳算法；負載均衡

0　引言

云計算作為繼網(wǎng)格計算、并行計算和分布式計算之后的新興計算模式，被高校、科研機構(gòu)以及商業(yè)組織進行了大量的研究。中國網(wǎng)格計算、云計算專家劉鵬給出如下定義：“云計算將計算任務分布在大量計算機構(gòu)成的資源池上，使各種應用系統(tǒng)能夠根據(jù)需要獲取計算力、存儲空間和各種軟件服務［1］”。然而，云計算服務的核心問題是資源的調(diào)度，其服務質(zhì)量的好壞取決于調(diào)度效率的高低，因此資源調(diào)度一直是云計算研究領域重點和難點［2］。

傳統(tǒng)資源調(diào)度算法大都是一些靜態(tài)算法，如貪心算法、輪詢調(diào)度算法等，這類方法對于少量任務的調(diào)度可以獲得較好的調(diào)度方案。隨著任務數(shù)的不斷增加，云計算系統(tǒng)的復雜性增大，傳統(tǒng)方法存在任務完成時間過長、節(jié)點間負載不均衡和資源利用率低等缺點［3-4］。目前，人工智能技術的日趨成熟，智能算法越來越多地被用于資源調(diào)度中，成為當前研究的熱點。

劉瑜等［5］提出了基于最優(yōu)跨度和負載均衡改進遺傳算法的資源調(diào)度策略，考慮到云計算任務的數(shù)量大和復雜性，設計了基于資源數(shù)的編碼方式，在算法接近收斂階段自適應調(diào)節(jié)最優(yōu)跨度適應度函數(shù)來提高算法的收斂速度。袁浩等［6］提出了一種基于社會力群的智能優(yōu)化算法，通過模擬人群的擁擠退讓行為尋找使任務總時間最小的調(diào)度方案。徐文忠［7］等提出了一種新的基于遺傳算法的關于虛擬機負載均衡的調(diào)度策略，但沒有考慮到任務平均完成時間指標，不能滿足用戶對任務響應時間的需求。李建鋒等［8］設計了雙適應度函數(shù)去優(yōu)化資源調(diào)度過程，尋求使總?cè)蝿胀瓿蓵r間和任務平均完成時間都較小的調(diào)度方案，并取得了不錯的效果。薛玉［9］提出一種基于混沌粒子群算法的云資源調(diào)度模型，把資源的負載均衡度作為要優(yōu)化的目標函數(shù)，在尋優(yōu)過程中人工引入混沌機制對粒子進行擾動，通過粒子間的信息交流與共享，尋求調(diào)度最優(yōu)解。鄔海艷［10］提出了基于元胞自動機模型改進遺傳算法用于云資源調(diào)度，其主要作用于遺傳算法的選擇和交叉操作中，根據(jù)演化規(guī)則自適應調(diào)節(jié)元胞與鄰居元胞的狀態(tài)，獲取最大適應度值個體。Gao等［11］提出一種以任務完成時間、系統(tǒng)吞吐量為優(yōu)化目標的蟻群算法構(gòu)建云計算資源調(diào)度模型，在任務總完成時間上取得不錯的效果，但資源的利用率不高。Zhan Zhi-Hui等［12］提出了基于Min-min和上Max-min方法的負載均衡感知遺傳算法（LAGA），通過在適應度函數(shù)中引入時間負載均衡模型（TLB）選擇優(yōu)勢個體，生成資源節(jié)點負載更均衡的調(diào)度方案，僅考慮了資源的負載情況，卻對犧牲了算法的收斂速度。

針對以上問題，本文結(jié)合模擬退火的思想來改進遺傳算法在云計算資源中的調(diào)度，提出了基于任務平均完成時間和負載均衡的雙適應度函數(shù)，設計自適應的交叉和變異概率函數(shù)，使算法在尋優(yōu)時以一定概率接受劣質(zhì)解，減小改進算法收斂到局部最優(yōu)解的可能性，同時采用基于資源節(jié)點數(shù)作為染色體的總長度，每個資源所映射的任務總數(shù)和任務編號作為基因值的編碼方式，加快了算法的收斂速度，提高了算法的尋優(yōu)能力。

1　云計算資源調(diào)度問題描述

在云計算平臺上，管理者利用虛擬化技術把計算機的物理資源抽象為統(tǒng)一的虛擬資源，統(tǒng)一的虛擬資源又被分配到相互獨立的虛擬機上，而云計算中的資源調(diào)度問題就是利用一種調(diào)度策略把大量的計算任務分配到虛擬機上，實現(xiàn)虛擬資源的最大化利用。具體的講，就是如何把云計算中大量的計算任務根據(jù)一定的調(diào)度策略分配到最佳虛擬資源上，保證最少的任務完成時間和最大的資源利用率，云計算資源調(diào)度管理模型如圖1。

圖1　云計算資源調(diào)度管理模型

云計算資源調(diào)度包括數(shù)據(jù)中心D=｛d1，d2，…，dm｝

虛擬資源V=｛vm1，vm2，…，vmm｝、計算任務T=｛t1，t2，…，tn｝以及它們之間的映射關系。云計算資源調(diào)度模型可描述為：S=｛T，V，D，Mtv，Mvd｝（1）式中，Mtv為任務與虛擬資源之間的映射關系，Mvd為虛擬機與數(shù)據(jù)中心的之間的映射關系。根據(jù)上述用戶任務-虛擬資源之間的映射關系，本文用二維數(shù)組統(tǒng)計每個任務在每個虛擬資源上的預計完成執(zhí)行時間ETC（Excepted Time To Completion）。

其中：ETCij=cloudlet［i］.length/vm［j］.mips，表示第i個任務在第j個資源上的預計執(zhí)行時間。設Start（i，j）為任務ti在vmj上的開始執(zhí)行時間。則ti在vmj上的完成時間見式（3）。Finish（i，j）=Start（i，j）+ETCij（3）那么vmj上全部任務的完成時間見式 （4）（5）。

式（5）中，cij=1表示任務ti在vmj上執(zhí)行，cij=0表示ti不在vmj上執(zhí)行。

對于用戶全部計算任務T= ｛t1，t2，…，tn｝的任務平均完成時間見式（6）。

對于云計算資源的調(diào)度問題，即求使式（6）值最小的解，因此本文的目標函數(shù)見式（7）。

2　遺傳算法與模擬退火思想的融合設計

2.1模擬退火思想

2.2基于模擬退火思想的改進遺傳算法設計

2.2.1染色體編碼與種群初始化

在任務調(diào)度的問題中，傳統(tǒng)遺傳算法通常將任務總數(shù)作為染色體基因串的長度，每個任務對應的資源ID作為染色體的基因值。但是云計算環(huán)境中任務的總數(shù)遠遠大于資源節(jié)點的個數(shù)，如果把任務總數(shù)作為染色體基因串的長度，會導致算法收斂速度慢，找到最優(yōu)解的時間過長。因此本文對染色體的編碼方式進行了改進，將資源節(jié)點的數(shù)量作為染色體基因串的長度，每個資源所映射的任務總數(shù)和任務編號作為染色體基因值，這種編碼方式可以加快算法的收斂速度。本文采用資源——任務的間接編碼方式，先對染色體進行預編碼，設有n個任務，M個資源節(jié)點，如下產(chǎn)生一條染色體。

｛3，1，1，2，3，…，m-1，m，m-1｝

表示第1、5個任務分配到第3個資源上，第2、3個任務分配到第1個資源上，第n-2，n-1個任務分配到第m-1資源上，第n個任務分配到第m個資源上。接著對該染色體進行二次編碼，則染色體基因串的長度為資源總數(shù)m，染色體基因值為每個資源節(jié)點分配任務的總數(shù)和任務ID，二次處理后的染色體見表1。

表1　二次處理后染色體的編碼方式

在對染色體進行編碼后，接著對種群進行初始化，本文采用隨機方式產(chǎn)生N個染色體。

2.2.2基于任務平均完成時間和負載均衡的雙適應度函數(shù)設計

基于任務平均完成時間的適應度函數(shù)見式（9）。

式（9）表示第k個染色體上所有任務在節(jié)點j上平均執(zhí)行時間。在任務調(diào)度的過程中，我們還需要考慮資源負載均衡問題，節(jié)點負載較均衡使得資源利用率較高，避免計算能力高的節(jié)點出現(xiàn)負荷同時能力低的節(jié)點被閑置。采用資源節(jié)點上任務分配數(shù)的標準差來衡量節(jié)點的負載均衡問題，設任務數(shù)為n，資源節(jié)點數(shù)為M，則每個資源節(jié)點上平均分配的任務數(shù)為資源節(jié)點任務分配數(shù)標準差的適應度函數(shù)見式（10）。

其中：Assign_tasksk，i表示第k個染色體上的第i個資源節(jié)點所分配到的任務數(shù)。

所以，本文設計基于任務平均完成時間和負載均衡的雙適應度函數(shù)見式（11）。

ω1和ω2分別是基于最小完成時間和任務分配數(shù)標準差適應度函數(shù)的權重。用戶根據(jù)自己的偏好決定每個適應度函數(shù)的權重，且滿足ω1+ω2=1。

2.2.3選擇算子設計

在選擇算子的設計采用改進的輪盤賭方法。首先根據(jù)式（9）計算每個染色體的適應度值，然后計算該適應度值相對于整個種群適應度值總和中所占的比例，即該個體被復制到下一代中的概率。則個體k被選中的概率見式（12）。

2.2.4交叉和變異算子設計

本文采用模擬退火的思想對個體進行交叉操作，種群中較優(yōu)個體以較低概率進行交叉，增加種群中“弱勢”個體的交叉可能性，提高種群的多樣性，使算法陷入局部最優(yōu)解的可能性減小。交叉概率函數(shù)見式（13）。

其中：favg表示每代群體的平均適應度值，f2，f1分別表示隨機選擇的兩個個體中適應度值的較大者與較小者。α為退火系數(shù)，T為算法當前迭代的溫度。當適應度函數(shù)值較大時 （f2＞f 1＞favg），這時讓交叉概率Pc變小，防止較優(yōu)的個體被破壞，同時較小的交叉概率能加快種群向最優(yōu)解收斂。當適應度函數(shù)值較小時（f1＜f2＜favg），使交叉概率變大，期望重組出新的個體。交叉算子有利于在全局范圍內(nèi)找到較好的個體，容易出現(xiàn)在最優(yōu)解附近徘徊的現(xiàn)象，對局部解空間的尋優(yōu)能力較差，使用變異算子可以微調(diào)個體的基因值，提高全局的收斂精度，個體的變異概率函數(shù)見式（14）。

其中，f′表示隨機選擇的個體適應度函數(shù)值，favg表示種群適應度的平均值。當隨機選擇個體的適應度值大于平均適應度值時（即f′＞favg），根據(jù)上面的公式，f′越大，種群中個體的變異概率則越小。這樣可以在很大程度上避免較優(yōu)個體的結(jié)構(gòu)被破壞。

2.2.5算法終止條件

當連續(xù)60代適應度函數(shù)值無變化或者進化代數(shù)達到200次時，終止算法的執(zhí)行。

本文使用均勻交叉、多點交叉相結(jié)合的實現(xiàn)方式，變異方式使用基因值變異。最后基于模擬退火的改進遺傳算法（SAIGA）流程圖如圖2所示。

圖2　改進算法的流程圖

3　仿真實驗

3.1仿真環(huán)境

在Intel.Core2四核2.83 GHz CPU，4 G RAM，操作系統(tǒng)為Windows7 32 bit，采用CloudSim3.0軟件對算法進行仿真，其核心是中心代理人和虛擬機調(diào)度策略，改進算法通過擴展Datacenter Broker和VMAllocationPolicy類實現(xiàn)云資源調(diào)度的模擬。

3.2對比算法

本文選擇輪詢調(diào)度算法（RR）、遺傳算法（GA）和模擬退火算法（SA）做對比實驗，分析比較4種算法在任務總完成時間、任務平均完成時間、負載均衡以及收斂速度方面的優(yōu)劣性。GA、SA和SAIGA算法的參數(shù)設置見表2。

表2　GA、SA及SAIGA算法參數(shù)設置表

3.3結(jié)果與分析

實驗中模擬任務的長度MI取1 000～20 000之間，資源的運算能力MIPS取500～5 000之間，分析任務數(shù)和虛擬資源數(shù)的變化對任務總完成時間、平均完成時間以及資源負載均衡的影響。

1）將任務分配到10個資源節(jié)點，改變?nèi)蝿盏臄?shù)量從10到200，記錄任務的總完成時間（ms），結(jié)果見表3，圖3。

表3　資源數(shù)一定，不同任務數(shù)下的完成時間

圖3　資源數(shù)一定，不同任務數(shù)下的總完成時間

從圖3可以看出，在任務數(shù)不多時，4種算法下任務的完成時間差別不大，這是由于初期資源節(jié)點的數(shù)量和任務的數(shù)量差別不大，節(jié)點有足夠的能力去處理這些任務。隨著任務數(shù)的增多，特別地當任務數(shù)大于150時，SAIGA算法調(diào)度下的任務總完成時間明顯優(yōu)于其他3種算法。

2）當任務數(shù)量固定為1 000時，改變虛擬資源的數(shù)量，從10到50，記錄任務的平均完成時間如圖4。

從圖4可以看出，在虛擬資源數(shù)較少時，SAIGA的任務完成時間遠遠小于RR、GA和SA。隨著虛擬資源數(shù)量的增加，4種算法下任務的完成時間都在不斷減少，最后SAIGA、GA和SA算法的任務平均完成時間大致接近，這是由于隨著資源節(jié)點數(shù)量的增加，其處理能力能夠逐漸滿足任務的執(zhí)行需求，任務搶占資源的情況減少。

3）任務數(shù)為1 000時，將任務分配到5個資源節(jié)點（R1，R2，R3，R4，R5）上，設置其處理能力分別為：（1 200， 900，600，1800，800）MIPS，記錄5個資源節(jié)點上的負載情況如圖5。

圖4　不同資源數(shù)下任務的平均完成時間

圖5　大量任務下資源節(jié)點的負載情況

從圖5可以看出，在資源計算能力有較大差異的情況下，SAIGA算法的分配的任務數(shù)更加均衡，而RR沒有考慮到節(jié)點能力的差異性，采取了均分任務的方式，GA、SA中則出現(xiàn)計算能力高的節(jié)點分配到任務數(shù)較多，計算能力低的節(jié)點分配到的任務數(shù)較少的現(xiàn)象?？傊?，SAIGA算法在資源節(jié)點的負載均衡方面表現(xiàn)出較好的優(yōu)越性。

4）任務數(shù)為1 000時，資源節(jié)點為40時，GA和SAIGA算法的迭代收斂情況如圖6。

圖6　SAIGA和GA算法收斂結(jié)果比較

從圖6可以看出，在算法迭代初期GA和SAIGA性能差不多，但由于SAIGA采用任務總數(shù)加編號的方式作為染色體的基因值，使它后期的收斂速度加快。SAIGA算法在迭代120次后開始收斂，而GA算法在接近160代時才出現(xiàn)收斂的趨勢，在收斂精度上改進算法提高了近130秒。另外，GA算法迭代大約至60代時出現(xiàn)一些適應度值超常的個體誤導了種群進化的方向，但這些個體并不是算法最優(yōu)解。由于SAIGA采用自學習的交叉概率函數(shù)，在算法接近收斂的階段對超常適應度值的個體進行了一定概率的調(diào)整，避免誤導了種群的進化方向，使得改進算法更快地收斂到最優(yōu)解。

4　結(jié)束語

針對云資源調(diào)度的動態(tài)性、實時性等特點，提出了一種基于模擬退火思想的改進遺傳算法SAIGA。該算法比GA、SA和RR在任務平均完成時間上分別縮短了11%，25%和56%，在算法的收斂精度和速度上都有顯著的提高，收斂速度上提高了40代左右，能夠有效避免超常個體誤導種群的進化方向和算法陷入局部最優(yōu)，同時改進算法能夠較均衡地分配任務到各個節(jié)點上，提高了資源的利用率。因此，改進算法更加適合云環(huán)境下的資源調(diào)度，具有較好的實用性。

［1］劉鵬.云計算［M］.北京：電子工業(yè)出版社，2011.

［2］Armbrust M，F(xiàn)ox A，Griffith R，et al.A View of Cloud Computing［J］.Communications of the ACM，2010，53（4）：50-58.

［3］Caballer M，Blanquer I，MoltóG，et al.Dynamic Management of Virtual Infrastructures［J］.Journal of Grid Computing，2015，13（1）：53-70.

［4］林偉偉，齊德昱.云計算資源調(diào)度研究綜述［J］.計算機科學，2012，39（10）：1-6.

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

［6］袁浩，李昌兵.基于社會力群智能優(yōu)化算法的云計算資源調(diào)度［J］.計算機科學，2015，42（04）：206-208.

［7］徐文忠，彭志平，左敬龍.基于遺傳算法的云計算資源調(diào)度策略研究［J］.計算機測量與控制，2015，23（5）：1653-1656.

［8］李建鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務調(diào)度算法［J］.計算機應用，2011，31（1）：184-186.

［9］薛玉.云計算環(huán)境下的資源調(diào)度優(yōu)化模型研究［J］.計算機仿真，2013，30（5）：362-365.

［10］鄔海艷.基于云計算環(huán)境下資源調(diào)度算法研究 ［D］：贛州：江西理工大學，2012.

［11］Gao Y，Guan H，Qi Z，et al.A multi-objective ant colony system algorithm for virtual machine placement in cloud computing［J］.Journal of Computer and System Sciences，2013，79（8）：1230-1242.

［12］Zhan Z H，Zhang G Y，Ying L，et al.Load Balance Aware Genetic Algorithm for Task Scheduling in Cloud Computing［A］.In：Dick G，Browne W，Whigham P，Zhang M，Bui L，Ishibuchi H，Jin Y，Li X，Shi Y，Singh P，Tan K，Tang K，editors.Simulated Evolution and Learning［C］.Springer International Publishing，2014：644-655.

［13］Gall J，Rosenhahn B，Seidel H P.An Introduction to Interacting Simulated Annealing［A］.In：Rosenhahn B，Klette R，Metaxas D，editors.Human Motion［C］.Springer Netherlands，2008：319-345.

［14］S K，P VM.Optimization by simmulated annealing［J］.science，1983，220（4598）.

An Improved Genetic Algorithm for Cloud Computing Resource Scheduling

Liu Feng1，Bi Li1，Yang Jun2
（1.School of Mathematics and Computer Science，Ningxia University，Yinchuan750021，China；2.Network Administration Center，Ningxia University，Yinchuan750021，China）

For Round-Robin scheduling algorithm and genetic algorithm and simulated annealing algorithm in cloud resource scheduling having shortcomings，such as slow convergence speed，easy to premature and the imbalance of the resource load，the paper proposed the improved genetic algorithm combined with simulated annealing thought（Simulated Annealing Improved Genetic Algorithm：SAIGA）.The improved algorithm gave a dual fitness function based on task average completion time and load balance and adaptive crossover mutation probability function.It allowed the algorithm in the annealing process to accept inferior solution with a certain probability to avoid prematurity phenomenon occurs.We regarded the virtual machine task allotment standard deviation as the basis of individual choice to realize the resource node load balancing.Simulation experiments showed that the improved algorithm is more superior on average task completion time，resource load balancing，and the convergence rate.It can rapidly find the optimal scheduling scheme and has good feasibility and practicability.

cloud computing；round robin scheduling；simulated annealing thought；improved genetic algorithm；load balancing

1671-4598（2016）05-0202-05

10.16526/j.cnki.11-4762/tp.2016.05.057

TP393

A

2015-11-09；

2015-12-11。

國家自然科學基金項目（61261001）；教育部科學技術研究重點項目（212189）。

劉峰（1989-），男，山東菏澤人，碩士研究生，主要從事智能調(diào)度算法方向的研究。

畢利（1968-），女，寧夏銀川人，教授，碩士生導師，主要從事數(shù)據(jù)挖掘及組合優(yōu)化控制方向的研究。

楊軍（1972-），男，寧夏吳忠人，教授，碩士生導師，主要從事云計算資源調(diào)度及無線傳感器網(wǎng)絡方向的研究。