基于遺傳蟻群算法的云資源調度問題研究

金 瑾, 何 嘉

(成都信息工程學院計算機學院,四川成都610225)

0 引言

云計算是近年新興的一種網絡應用模式。是集網格計算、分布式計算、并行計算、效用計算、網絡存儲、虛擬化、負載均衡等傳統計算機技術和網絡技術為一體,再互相融合的產物。云計算的核心思想:將大量用網絡連接的計算資源統一管理和調度,從而構成一個計算資源池。像電力資源一樣,用戶只需提出所需,云計算就能夠向提供方便快捷的服務。因此如何快速合理地對網絡資源進行調度是云計算需要解決的關鍵問題,它關系到云資源環境所能提供服務的好壞。

傳統的資源調度算法有輪詢算法(RR),基本ACO算法等,RR算法的原理是每一次把來自用戶的請求輪流分配給內部中的服務器,從1開始,直到N(內部服務器個數),然后重新開始循環。它不考慮服務器的狀態(即不關心當前服務器的連接數和響應速度),因此當請求服務間隔時間變化比較大時,輪詢調度算法容易導致調度不平衡。目前的資源調度策略大多數是通過虛擬機級別上的調度技術結合一定的調度策略為虛擬機內部應用做資源調度[1],例如文獻[2]針對計算集群中的虛擬機調度進行建模,根據虛擬機的負載動態調節處理器電壓,文獻[3-4]通過動態分配云計算數據中心的虛擬機,減少服務器的個數,文獻[5]給出基于門限的云計算資源動態調度方法,文獻[6]提出基于博弈論的云計算資源分配算法。這些資源調度方法雖在一定程度上提高了源調度的效率,然而面對數量龐大的資源時卻時常會遇到瓶頸,而智能算法的各方面優點表明其對于像云資源調度類的調度問題顯示出一定的優越性。

蟻群算法是20世紀90年代初意大利的M.Dorigo等學者提出的[7],與遺傳算法、粒子群算法等智能算法一樣,蟻群算法是模擬現實世界中真實螞蟻的覓食行為而形成的一種模擬進化算法,這些學者們充分利用蟻群搜索食物的過程與旅行商問題之間的相似性,解決了TSP問題,取得了很好的結果。大量的實驗結果還證明蟻群算法的有效性和在某些領域的優勢[8-9]。同時,蟻群算法也存在一定的缺陷,即搜索時間過長和容易陷入局部較優解[10],蟻群算法在動態環境下也表現出高度的靈活性和健壯性,成功解決了許多組合優化問題。云計算中的任務調度問題,實質上是一種尋找較優解的問題,即,從資源分配給任務的多個解中選出較優解的一種過程,從解決問題角度看,蟻群優化算法非常適合解決云環境中的資源調度問題[11]。

1 基本蟻群優化算法的原理

以MMAS應用于TSP問題的求解為例闡述基本蟻群優化算法的原理[12-15]。

為了便于描述問題,首先引入以下符號:m:螞蟻數量,dij(i,j=1,2,…,n):城市之間的距離;τij(t):t時刻在城市i,j連線的殘留信息量,一般取τij(0)=C(C常數);ηij:t時刻螞蟻由城市i轉移到城市j的啟發信息,一般取;即信息素的大小為兩城市距離的倒數。

pij(t):t時刻螞蟻由城市i轉移到城市j的概率,計算公式為:

其中reallowedk表示螞蟻k下可走的城市集,它是動態變化的,因螞蟻k的進程而改變;信息量 τij(t)會逐漸衰弱,1-p:衰減程度;α:螞蟻所積累的信息量(在運動過程中),β:啟發式因子所起的不同作用(在螞蟻選路的過程中);

蟻群算法的步驟:

(2)螞蟻根據公式(1)選擇所要走的下一個城市,并修改 tabuk;

(3)每只螞蟻走完一條邊后,按式 τij(t+1)=(1-ρ).τij(t)+ρ Δτkij更新該邊的信息素,其中 Δτkij=Q/lp,其中lp是螞蟻從初始位置到當前城市走過的路徑長度。ρ表示信息的持久性。對于所有邊(i,j)限制 τij(t)∈[τmin(t),τmax(t)];超出這個范圍的值被強制設為 τmax或者是 τmin。這樣做可以使信息素較為平均,防止信息素大小兩極分化,從而使算法更好地尋優;

(4)計算最佳路徑。當全部螞蟻走完所有城市后,按下面式計算最優路徑的長度并且保留,

lmin=minlk,k=(1,2,…,m),其中 lk:第k只螞蟻所走路徑長度;

(5)經過n個時刻。螞蟻k一次循環結束,即所有的城市都走完一遍。此時,要根據下式對這一輪遍歷的全局最優路徑上的信息量作一些更新::全局信息素揮發系數,lk:最優路徑長度;

(6)如果設置的迭代次數未完,則清空禁忌表,重復上述過程。

2 GA-ACO與云計算資源調度

2.1 問題描述

采用所提出的GA-ACO算法尋找當前策略中的最優或較優的策略。由于云計算環境的特殊性和復雜性,需先對云資源調度問題與傳統的應用蟻群算法的TSP問題進行關聯,以供改進蟻群算法來適合云資源調度問題的使用[16],云資源調度問題與傳統的TSP問題的差異主要體現在以下3個方面:

(1)在TSP問題中,城市之間會有固定的拓撲結構。而云環境中的資源并不是固定不變的,所以也不存在固定的網絡拓撲結構。

(2)在TSP問題中,城市之間的信息素用城市之間的距離的倒數表示。而在云計算環境中則需要用資源的通信能力和計算能力等相關系數表示信息素。

(3)啟發信息也起著非常重要的作用,在云環境中,需要以資源固有屬性(如計算和通信能力)表示在蟻群算法中的啟發信息。

把云計算資源調度的問題描述如下:設有 T個需要執行的任務,P個可用的資源。用集合表示為:任務集合T={T1,T2,…,Tn};資源集合 P={P1,P2,…,Pm};用 Ti表示第i個子任務,Pj表示第j個處理機資源。資源調度就是將n個子任務分配給m個處理機資源,從而使所有任務的完成時間最短,資源的利用率最高。

云資源調度的目標即是求(2)式的最小值[17]:

(2)式中,∑imi=M,M是給定時間內交給云計算環境的總任務量,mi表示資源i上分配mi個任務,0≤表示資源i上反能執行的最大任務并行數。

2.2 GA-ACO算法及在云資源調度中的應用

設第i個資源的處理能力為Pi,資源負載平衡能力為Li,任務節點與調度節點的通信能力為Ci,則每個資源的初始信息素表示為:τi(0)=α Pi+βCi+θ Li,其中 α,β,θ表示資源的處理能力初始化因子、資源節點間通信能力初始化因子和負載平衡能力初始化因子。

t時刻,第i個螞蟻選擇資源j的概率由下面的公式確定:

基中參數α 1代表信息素的重要程度,β1代表資源屬性的重要程度,τj(t)表t時刻資源j的信息素濃度,ωu表示能見度因素。

遺傳算法的全局搜索能力很強,但是局部搜索能力較弱[18],此算法運算簡單,收斂速度快,但是求解到一定程度時往往出現收斂停滯現象。而蟻群算法采用正反饋原理[19],加快了進化速度,但是其全局搜索能力較差,容易限入局部解。兩個算法優缺點具有互補的特性。文中所提出的GA-ACO算法即是將遺傳算法和蟻群算法進行交叉融合,從而克服各自的缺點,達到較好的優化性能。GA-ACO算法對于蟻群算法的每個解,用局部搜索算法來精煉,并更新每個資源的信息素。然后,用GA算法的進化算子進化出新的解,再利用MMAS的轉移概率建立GA算法的交叉算子。

GA-ACO算法步驟如下:

(1)初始化 nk個解;

(2)對每個個體的解 xk(k=1,2,…,nk)執行局部搜索;根據(1)式對更新信息素;

(3)對于 k=1,2,…,nk/2,隨機選擇兩個父代 xa和xb,對 xa和xb進行交叉操作得到x′,如果 U(0,1)≤pm,則對 x′進行變異;

(4)用子代代替群體中較差的那一半;再根據(1)式更新信息素。

(5)若迭代未完成,則一直重復上述步驟,直到迭代完成。

其中交叉算法如下:

輸入:xa和xb

令 x′=xa;

For所有的(i,j)∈x′and(i,j)?xb

do從 x′中刪除(i,j);

End

基于公式(3)連接各個部分。

3 仿真實驗結果與討論

所做的算法應用于云計算資源調度中,因此分別用MATLAB軟件和云計算仿真軟件(cloudsim)進行仿真。MATLAB軟件是常用的仿真軟件,具有用法靈活、程式結構性強、延展性好等優點,自帶了很多智能計算的工具箱,方便進行計算機仿真。而CloudSim是一個新的、通用的和可擴展的仿真框架,用于新的云計算基礎設施和應用服務的無縫建模、仿真和試驗。

為驗證GA-ACO算法的收斂性,用ACO算法與GA-ACO算法在MATLAB仿真平臺下的收斂性進行對比,結果如圖1和圖2所示。GA-ACO算法當迭代次數為100次時,其精度為10-5,而基本的ACO算法迭代資數為3000次時精度不足10-2。實驗結果表明,改進后的GA-ACO算法收斂度和精度相較于ACO算法都有所提高。

圖1 ACO算法的性能

圖2 GA-ACO算法的性能

另外,采用CloudSim仿真平臺驗證改進算法相較于其它調度算法的優越性,用云資源調度算法中傳統算法輪詢調度算法(RR)、ACO算法及GA-ACO算法分別進行調度。實驗主要參數取值為:時間長度 T為24小時,利用率閾值為80%,預測時間間隔為200s,改進蟻群算法中 α為1,β為4,ρ為0.5,螞蟻數量為80,最大迭代次數為120。假定數據中心有50臺宿主機,CPU數在[1,5]內隨機產生,MIPS為800,虛擬機所需CPU數為1,MIPS在[100,900]內隨機產生,實驗的任務數量分別是[50,100,150,200,250,300,350,400]。實驗結果如圖3所示,當任務數量250時,GA-ACO算法相的平均時間比ACO和RR算法分別少50和100s,而且隨著任務數量越來越多,改進的GA-ACO算法后期隨著信息素的增加,正反饋性增強,時間增加的幅度要遠小于RR和ACO算法。因此所提出的GA-ACO算法在任務數量較多的時候執行效率要高,而執行時間要短。

圖3 任務執行的平均時間對比

4 結束語

利用遺傳算法對蟻群算法進行改進,并且引入最大最小蟻群算法對基于蟻群算法進行優化,從而使兩種算法融合,改善原來算法的缺陷。形成新的GA-ACO算法,用實驗討論了新算法的精度和收斂度,相較于基于的ACO算法,新算法的精度和收斂度都有顯著的提高,結合云計算資源調度的一些特點,將新算法應用于云資源調度中,與傳統算法相比,新算法大大縮短了任務的平均運行時間,提高了資源的利用效率。

[1] Ge R,Feng X,Cameron K.Performance-constrained distributed dvs scheduling for scientific applications on power-aware clusters[A].Proceedings of the 2005 ACM/IEEE conference on Supercomputing[C].IEEE Computer Society,Washington DC,USA,2005:34-35.

[2] Von L G,Wang L,Younge A J,et al.Power-Avare Scheduling of Virtual Machines in DVFS-enabled Clusters[A].Proc.Of IEEE International Conference on Cluster Computing 2009[C].New Orleans,LA,USA,2009:1-10.

[3] Beloglazov A,Abawajy J,Buyya R.Energy-Aware Resource Allocation Heuristics for Efficient Management of Data Centers for Cloud computing[J].Future Generation Computer Systems,2012,28(5):755-768.

[4] Buyya R,Beloglazov A,Abawajy J.Energy-Efficient Management of Data Center Resources for Cloud Com-puting:A Vision,Architectural Elements,and Open Challenges[C].Proceedings of the 2010 International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA2010),Las Vegas,USA,July 2010:215-224.

[5] Lin Wei-Wei,Wang J Z,Liang Chen.et al.A Threshold-based Dynamic Resource Allocation Scheme for Cloud Computing[J].Procedings Engineering,2011,23(8):695-703.

[6] Wei Gui-yi,Visilakos A,Zheng Yao,et al.A gametheoretic method of fair resource allocation for cloud computing services[J].The Jounal of Supercomputing,2010,54(2):252-269.

[7] Dorigo M,Maniezzo V.Colorni A.Ant system:optimization by a colony of cooperating aigents[J].IEEE Transactions on SMC,1996,26(1):29-41.

[8] Dorigo M,Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutional Comutation,1997,1(1):53-66.

[9] Dorigo M,Gambardella L M.A study of some properties of ant-Q[A].Voigt H-M,Ebeling W,Rechenberg I,etal.Proceedings of the PPSN 44th International Conference on Parallel Problem Solving from Nature[C].Berlin:Springer-Verlag,1996:656-665.

[10] Dorigo M,Maniezzo V,Colorni A.Ant system:an autocatalytic optimizing process[J].Tech Rep,1991:91-106.

[11] 王天擎,謝軍,曾洲.基于蟻群算法的網格資源調度策略研究[J].計算機工程與設計,2007,28(15):3611-3613.

[12] 段海濱.蟻群算法原理及其應用[M].北京:科學出版社,2005:385-390.

[13] 譚營.計算群體智能基礎[M].北京:清華大學出版社,2009:263-265.

[14] 王永貴,韓瑞蓮.基于改進蟻群算法的云環境任務調度研究[J].計算機測量與控制,2011,19(5):1203-1211.

[15] 曹文梁,康嵐蘭.基于遺傳算法的混合蟻群算法及其在TSP中的應用研究[J].2011,33(1):91-93.

[16] McKerrow P.Modelling the dragan-f lyer Four-Rotor Helicopter[A].Proceedings of IEEE International Conference on Robotics Automation[C].2004:3596-3601.

[17] 李士勇.蟻群算法及其應用[M].哈爾濱:哈爾濱工業大學出版社,2004:101-108.

[18] RowlinsG,ed.Foundations of Genetic Algorithm[J].Los Altos Morgan Kan fmann,1991:767-777.

[19] C M White,G G Yen.A Hybrid Evolutionary Algorithm for TSP[J].In Proceedings of the IEEE Congress on Evolutionary Computation.2004,12(2):1473-1478.