基于遺傳算法的云計(jì)算任務(wù)分配

王 倩，周書臣

（1.周口師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 周口 466001;2.黃淮學(xué)院 國際學(xué)院，河南 駐馬店 463000）

目前，云計(jì)算成為信息技術(shù)領(lǐng)域所討論的熱點(diǎn)[1-2].關(guān)于云計(jì)算，文獻(xiàn)3里這樣描述：基礎(chǔ)設(shè)施（用來構(gòu)造應(yīng)用程序，相當(dāng)于微型計(jì)算機(jī)的OS）和云計(jì)算應(yīng)用（建立在基礎(chǔ)設(shè)施之上）.與網(wǎng)格計(jì)算相比，網(wǎng)格程序是把大的任務(wù)分解成許多個(gè)小的任務(wù)并行運(yùn)行在不同的集群以及服務(wù)器上，看重的是科學(xué)地進(jìn)行計(jì)算應(yīng)用程序的運(yùn)行.對于云計(jì)算而言，它是一個(gè)具有更廣泛定義的計(jì)算平臺，不僅能夠支持網(wǎng)格的應(yīng)用，還支持非網(wǎng)格的應(yīng)用，比如，支持網(wǎng)絡(luò)服務(wù)程序中的前臺網(wǎng)絡(luò)服務(wù)器、數(shù)據(jù)庫服務(wù)器和應(yīng)用服務(wù)器這三層應(yīng)用程序架構(gòu)模式等.云計(jì)算是能夠提供虛擬化、動態(tài)資源池和高可用性的下一代計(jì)算平臺[3].當(dāng)前，云計(jì)算服務(wù)可分基礎(chǔ)設(shè)施即服務(wù)（如Amazon的彈性計(jì)算云等）、平臺即服務(wù)（如Google的Google AppEngine等）和軟件即服務(wù)（如Salesforce公司的客戶關(guān)系管理服務(wù)等）為這3個(gè)層次[4].

云計(jì)算的核心思想是將大量計(jì)算資源（用網(wǎng)絡(luò)連接的）進(jìn)行統(tǒng)一的管理和調(diào)度，形成一個(gè)計(jì)算資源池，以便按照用戶的需要進(jìn)行服務(wù).云的含義是提供資源的網(wǎng)絡(luò).在用戶看來，“云”中的資源是能夠無限擴(kuò)展的，還能隨時(shí)獲取，按使用付費(fèi).總的來說，云計(jì)算是并行計(jì)算和網(wǎng)格計(jì)算的進(jìn)一步的發(fā)展.企業(yè)數(shù)據(jù)中心的運(yùn)行將與互聯(lián)網(wǎng)更相似，使計(jì)算分布在大量的分布式計(jì)算機(jī)上.這樣能夠使企業(yè)將資源切換到所需的應(yīng)用上，按照需求去訪問計(jì)算機(jī)和存儲系統(tǒng).它意味著計(jì)算能力也能作為一種商品進(jìn)行流通，像煤氣、水電一樣，取用方便，費(fèi)用低廉.與煤氣、水電相比，最大的不同之處是通過互聯(lián)網(wǎng)傳輸.

對于云計(jì)算服務(wù)提供商來說，其核心技術(shù)是如何對用戶申請的計(jì)算資源進(jìn)行分配和管理，其效率直接影響整個(gè)云計(jì)算環(huán)境的工作性能以及企業(yè)效益.因此，為云計(jì)算環(huán)境找到一個(gè)合理的任務(wù)分配方法迫在眉睫.本文提出了一種基于遺傳算法的任務(wù)調(diào)度算法，實(shí)驗(yàn)證明了該算法有效地提高了資源的分配和管理.

1 遺傳算法

近些年仿生學(xué)迅猛發(fā)展，仿生技術(shù)也備受各界學(xué)者的關(guān)注，已經(jīng)用于解決復(fù)雜的問題（如：任務(wù)分配、路徑等）.遺傳算法（簡稱GA）研究歷史比較短，它是模擬生物界中的遺傳和進(jìn)化的一種最優(yōu)化的方法.1975年，John Holland等人出版了《自然與人工系統(tǒng)中的自適應(yīng)》專著，標(biāo)志著GA正式誕生.現(xiàn)今，GA已成功應(yīng)用于生物、計(jì)算機(jī)科學(xué)、圖像處理等領(lǐng)域.由于其并行性、全局搜索以及高求解精度且易于和其他方法相結(jié)合的特點(diǎn)，能在龐大的解空間中最大限度地尋找全局最優(yōu)，在解決組合優(yōu)化問題方面顯示出了較大優(yōu)勢.其核心思想是：通過隨機(jī)方式產(chǎn)生若干個(gè)所求解問題的數(shù)字編碼，即染色體，形成初始種群，通過適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過遺傳操作后的個(gè)體集合形成下一代新的種群.再對這個(gè)新種群進(jìn)行下一輪進(jìn)化.

精英個(gè)體是指具有較高適應(yīng)度值的個(gè)體.在群體里，文獻(xiàn)[5]指出：全局最優(yōu)解和精英個(gè)體的親和度要大于全局最優(yōu)解和非精英個(gè)體的親和度，并與精英個(gè)體有較大親和度的個(gè)體也應(yīng)該具有較高的適應(yīng)度值.所以，在種群的進(jìn)化過程中精英個(gè)體起著非常重要的推動作用.

協(xié)同進(jìn)化與傳統(tǒng)遺傳算法相比，它具有強(qiáng)搜索能力和漸進(jìn)學(xué)習(xí)能力，能夠克服傳統(tǒng)遺傳算法的早熟收斂現(xiàn)象.能夠有效地解決遺傳算法中進(jìn)化模式單一性的問題，從而較好地保持種群個(gè)體的多樣性，避免了未成熟收斂和收斂速度慢等問題.

近年來，GA的研究仍然被眾多學(xué)者所關(guān)注，并取得了顯著的成果.文獻(xiàn)[7]結(jié)合遺傳算法與線性鑒別分析提出了一種玉米品種的快速鑒別方法，與常用的PCA等方法相比，運(yùn)算時(shí)間更短，正確率更高.文獻(xiàn)[8]針對噪聲環(huán)境下多模函數(shù)的優(yōu)化，本文理論上分析了噪聲對多模函數(shù)優(yōu)化的收斂精度和全局收斂性的影響，并對全局區(qū)域收斂精度和全局區(qū)域搜索率進(jìn)行分析噪聲對算法的影響程度.噪聲的強(qiáng)度和加多模函數(shù)尋優(yōu)的難度，遺傳算法的全局區(qū)域搜索率都在下降，全局區(qū)域收斂精度總體變差；重采樣的方法能夠有效提高算法的全局區(qū)域搜索率，總體改善算法的全局區(qū)域收斂精度.遺傳算法被應(yīng)用各個(gè)領(lǐng)域.文獻(xiàn)[9]提出了一種混合競爭協(xié)同進(jìn)化遺傳算法(htCGA)，其基本思想是，將局部搜索方法引入到協(xié)同進(jìn)化遺傳算法中，提高了算法局部搜索的能力.但上述兩種算法都采用了對解空間進(jìn)行分割的策略.因此較容易陷入局部極小值的問題.文獻(xiàn)[1]提出了一種蜜蜂進(jìn)化型遺傳算法，該算法充分利用了精英個(gè)體的信息.但該算法中隨機(jī)種群的比例參數(shù)需要通過人為經(jīng)驗(yàn)來確定，一定程度上增加了算法的隨機(jī)性.遺傳算法容易陷入局部最優(yōu)解，而且收斂速度和尋優(yōu)精度有待提高.為此，本文提出了的算法對云計(jì)算中的任務(wù)調(diào)度策略進(jìn)行改進(jìn)，通過對任務(wù)的優(yōu)化調(diào)度來最大限度地提高云計(jì)算環(huán)境的效率.

2 基于遺傳算法的云任務(wù)分配

2.1 云計(jì)算中的模型

目前，云計(jì)算的環(huán)境大多數(shù)采用Map/Reduce模型[10].本文采用基于Map/Reduce的思想開發(fā)的編程工具，這模型適用于產(chǎn)生和處理大規(guī)模的數(shù)據(jù)集.

圖1 Map/Reduce的執(zhí)行過程

圖1看出，Map/Reduce主要分兩個(gè)階段：

第一個(gè)階段（Map階段）：通過Map/Reduce函數(shù)將一個(gè)大的任務(wù)劃分多個(gè)小的任務(wù)，然后并行執(zhí)行（執(zhí)行Map操作的worker），輸出處理后的中間文件.

第二個(gè)階段（Reduce階段）：將第一個(gè)階段處理后的結(jié)果匯總分析并處理，輸出最后結(jié)果.

目前一些任務(wù)調(diào)度的算法過多地關(guān)注總?cè)蝿?wù)的完成時(shí)間(造成潛在優(yōu)良基因丟失).既要關(guān)注總?cè)蝿?wù)的完成時(shí)間，又要關(guān)注平均完成時(shí)間，所以，本文提出了一種對云計(jì)算中任務(wù)調(diào)度的改進(jìn)算法，最大限度地提高云計(jì)算環(huán)境的效率.

2.2 算法流程

2.2.1 個(gè)體評價(jià)策略

本文對群體中的個(gè)體進(jìn)行適應(yīng)度評價(jià)采用以下策略.定義：

其中，P={a1,a2,…,an}是群體所包含的個(gè)體集合，n是表示群的規(guī)模分別表示i和j個(gè)體第l位的值.這個(gè)策略引入了差異度作為其權(quán)系數(shù)，能夠有效地保持種群的多樣性，從而避免因有效模式缺失而導(dǎo)致的早熟收斂問題.

2.2.2 交叉操作

傳統(tǒng)的遺傳算法采用統(tǒng)一的交叉、變異策略，很大程度上增加了算法的隨機(jī)性，降低了算法的收斂速度.本文受MECA算法[11]的啟發(fā)，采用兩種交叉算子：單點(diǎn)交叉算子和兩點(diǎn)算子（兩點(diǎn)交叉是設(shè)置兩個(gè)交叉點(diǎn)，為選定父代基因鏈上的兩個(gè)位置進(jìn)行交叉）.當(dāng)個(gè)體i,j的差異度時(shí)，產(chǎn)生新個(gè)體采用單點(diǎn)交叉算子x=(x1,x2,…,xn)和y=(y1,y2,…,yn).當(dāng)個(gè)體i,j相似時(shí)，使用兩點(diǎn)交叉算子(如表1所示)產(chǎn)生新個(gè)體.

表1 兩點(diǎn)交叉

2.2.3 精英進(jìn)化

對于種群的進(jìn)化，精英個(gè)體起著非常重要的作用.遺傳算法采用精英策略能夠較快地收斂到全局最優(yōu)解.DECGA算法采用雙精英進(jìn)化策略.這一算法的核心操作是以精英個(gè)體作為進(jìn)化的，在進(jìn)化過程中充分地發(fā)揮了精英個(gè)體的推動作用，使個(gè)體有方向地朝好的方向進(jìn)化.

初始種群生成時(shí)，首先組成精英庫種群（隨著種群的進(jìn)化而不斷更新），精英種群是從種群中前M個(gè)適應(yīng)度值最高的不同個(gè)體中選擇出來的，每一代中的兩個(gè)精英個(gè)體都是也是這樣選擇的，用EliteA（提高算法收斂速度，能夠有效避免因種群個(gè)體過于相似而導(dǎo)致的無效交叉，從而提高算法的進(jìn)化效率）和EliteB（避免出現(xiàn)算法由于選擇壓力而造成的過早收斂現(xiàn)象）來表示兩個(gè)精英個(gè)體，這兩個(gè)精英個(gè)體協(xié)同進(jìn)化，最終完成算法的整個(gè)進(jìn)化操作.

算法的流程描述如下：

（1）隨機(jī)產(chǎn)生初始種群，計(jì)算每個(gè)個(gè)體的適應(yīng)度函數(shù)并排序.

（2）選擇前M個(gè)適應(yīng)度值相異的優(yōu)秀個(gè)體作為精英庫Best(0)成員，并令 t=0；

（3）選擇Best(t)中的最優(yōu)個(gè)體作為EliteA，并利用種群分割策略得到分割種群P0Pe和P0Pc.

（4）按比例選擇法選擇與EliteA相異的個(gè)體EliteA，種群個(gè)體評價(jià)函數(shù).

（5）將 A(t+1)和 B(t+1)種群合并，得到種群 Temp(t+1)，并計(jì)算Temp(t+1)的適應(yīng)度值；

（6）精英庫Best(t)與temp(t+1)中的個(gè)體競爭，并計(jì)算Temp(t+1)中不存在此精英個(gè)體，則用此精英個(gè)體替代Temp(t+1)中的最差個(gè)體；否則不進(jìn)行任何操作.得到下一代種群P(t+1)，并將種群按適應(yīng)度降序排列；

（7）若P(t+1)中的最優(yōu)個(gè)體 bestlndividual大于Best(t)中的最優(yōu)個(gè)體，則用最優(yōu)個(gè)體bestlndividual替代Best(t)中的最差個(gè)體.得到更新后的精英庫Best(t+1)；

（8）是否滿足終止條件：若是，則結(jié)束；否則，轉(zhuǎn)到Step3.

3 仿真實(shí)驗(yàn)結(jié)果與分析

本文制作仿真實(shí)驗(yàn)并對結(jié)果進(jìn)行分析，目的是在云計(jì)算任務(wù)分配上改進(jìn)遺傳算法和遺傳算法有更好的對比以及預(yù)測時(shí)間與實(shí)際執(zhí)行時(shí)間的比較.

3.1 實(shí)驗(yàn)?zāi)Ｐ?/h3>

為了驗(yàn)證上述遺傳算法在云計(jì)算任務(wù)分配上的可行性以及較好的穩(wěn)定性，本文需要選擇一個(gè)有意義的測試環(huán)境.本文選用2.40GHz的CPU和2GB的RAM作為硬件環(huán)境，Windows XP的操作系統(tǒng)，JDK7.0的基礎(chǔ)環(huán)境及Ant1.8.2的編譯工具.

首先設(shè)置參數(shù)：worker為50，task為50；每個(gè)task劃分為子任務(wù)數(shù)范圍為[20,80].

終止條件：達(dá)到最大迭代數(shù)或如果連續(xù)50代總?cè)蝿?wù)完成時(shí)間與任務(wù)平均完成時(shí)間都沒有變化時(shí)，終止算法.

3.2 實(shí)驗(yàn)結(jié)果

在增加流量負(fù)載和暫時(shí)飽和的情況下，本文算法的平均完成時(shí)間與GA算法進(jìn)行比較（如圖2所示）.橫坐標(biāo)為任務(wù)的申請數(shù)量.縱坐標(biāo)為兩種算法分別進(jìn)行處理申請作業(yè)所消耗的時(shí)間.

圖2 云計(jì)算環(huán)境下的算法比較

通過實(shí)驗(yàn)，可以看出：本文算法（藍(lán)線）的平均完成時(shí)間在任務(wù)較少時(shí)優(yōu)勢較小而任務(wù)較多時(shí)遠(yuǎn)遠(yuǎn)小于GA算法（紅線），主要原因是：采用了雙精英策略思想，隨著任務(wù)數(shù)量的增多預(yù)測時(shí)間逐漸接近實(shí)際時(shí)間.

4 結(jié)束語

本文提出了一種基于遺傳算法的任務(wù)調(diào)度算法，減少了處理請求任務(wù)的平均完成時(shí)間，保證云服務(wù)的質(zhì)量.通過本算法可以對云計(jì)算環(huán)境下這種模型實(shí)現(xiàn)較為理想的任務(wù)調(diào)度，它是一種有效的任務(wù)調(diào)度算法.

〔1〕FOSTER I,YONG ZHAO,RAICU I,et al.Cloud computing and grid computing 360-degree compared[C]//Proceedings of the 2008 Grid Computing Environments Workshop.Washington, DC:IEEE Computer Society,2008:1-10.

〔2〕ARMBRUST M,Fox A,GRIFFITH R,et al.Above the clouds:A Berkeley view of cloud computing[EB/OL].[2010-01-25].http://www.eecs.berleley.edu/Pubs/Techrpts/2009/EECS-2009-28.pdf.

〔3〕陳康.云計(jì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀[D].軟件學(xué)報(bào),2009.

〔4〕馮登國，等.云計(jì)算安全研究[D].軟件學(xué)報(bào),2011.

〔5〕Meng W,Han XD,Hong BR.Bee evolutionary genetic algorithm.Acta Electronica Sinica,2006,34(7):1294-1300(in Chinese with English abstract).

〔6〕Eglover,Tabu search:Part I.ORSA Journal on Computing.1989,1(3):1 90-206.

〔7〕王徽蓉，等.基于遺傳算法與線性鑒別的近紅外光譜玉米品種鑒別研究[D].光譜學(xué)與光譜分析,2011（3）.

〔8〕李軍華，等.噪聲環(huán)境下多模態(tài)函數(shù)優(yōu)化的遺傳算法[D].電子學(xué)報(bào),2012（2）.

〔9〕Danoy G.Bouvry P,Martins T.Hlcga:A hybrid com-petitive coevolutionary genetic algorithm.In:Hoes L,ed.Proc.of the 6th Int,I Conf.on Hybrid Intelligent Systems.Com-puter Society Press,2006.48-51.[doi:10.1109/HIS.2006.264931].

〔10〕DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[C]//Proceedings of the 6th Symposium on Operating System Design and Implementation.New York:ACM,2004:137-150.

〔11〕Mu CH.Jiao LC,Liu Y.M-Elite coevolutionary algorithm for numerical optimization.Journal of Softwar-e,2009,20(11):2925-2938(in Chinese with English abstrac-t).http://www.jos.org.cn/1000-9825/3496.htm[doi-:10.3724/SP.J.1001.2009.03496].