王 倩，周書臣

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

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

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

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

1 遺傳算法

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

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

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

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

2 基于遺傳算法的云任務分配

2.1 云計算中的模型

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

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

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

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

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

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

2.2 算法流程

2.2.1 個體評價策略

本文對群體中的個體進行適應度評價采用以下策略.定義：

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

2.2.2 交叉操作

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

表1 兩點交叉

2.2.3 精英進化

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

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

算法的流程描述如下：

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

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

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

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

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

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

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

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

3 仿真實驗結(jié)果與分析

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

3.1 實驗模型

為了驗證上述遺傳算法在云計算任務分配上的可行性以及較好的穩(wěn)定性，本文需要選擇一個有意義的測試環(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；每個task劃分為子任務數(shù)范圍為[20,80].

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

3.2 實驗結(jié)果

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

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

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

4 結(jié)束語

本文提出了一種基于遺傳算法的任務調(diào)度算法，減少了處理請求任務的平均完成時間，保證云服務的質(zhì)量.通過本算法可以對云計算環(huán)境下這種模型實現(xiàn)較為理想的任務調(diào)度，它是一種有效的任務調(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〕陳康.云計算：系統(tǒng)實例與研究現(xiàn)狀[D].軟件學報,2009.

〔4〕馮登國，等.云計算安全研究[D].軟件學報,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].光譜學與光譜分析,2011（3）.

〔8〕李軍華，等.噪聲環(huán)境下多模態(tài)函數(shù)優(yōu)化的遺傳算法[D].電子學報,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].