中圖分類號：TP301 文獻標識碼：A

摘要：通過研究云計算的編程模型和多種分布式任務調度算法，提出一種改進的遺傳蟻群算法，使用間接混合編碼方式讓每條染色體形成了單獨的任務調度方案，利用遺傳算法生成的優(yōu)化解，解決了蟻群算法的前期信息素聚集慢的問題，提高了云計算中任務調度的效率。實驗結果證明，本算法取得了不錯的的結果。

關鍵詞：云計算；遺傳算法；蟻群算法

一、引言

近年來，互聯(lián)網行業(yè)快速發(fā)展，云計算作為一種新興的商業(yè)模式應運而生。云計算的特點是超大規(guī)模、虛擬化、高可靠性和通用性好等。目前，為人們所熟知的云平臺有Google云計算、Amazon彈性計算云EC2、百度云平臺和阿里巴巴云電子商務等[8]。

云計算通過網絡將大型的計算任務拆分成較小的計算任務，交給大型分布式服務器系統(tǒng)處理，經過計算分析后將計算結果交給用戶。因為在云計算的過程需要處理大量的任務，如何保證這些大量的計算任務能夠正確、高效的被調度，成為了云計算之中的重點。本文采用遺傳蟻群混合算法（Generic Algorithm Ant Colony Optimization， GAACO），通過結合遺傳算法前期搜索速度快和蟻群算法后期搜索優(yōu)勢大的優(yōu)點，對云計算中的任務調度進行優(yōu)化，通過了仿真對比試驗，驗證了良好的性能。

二、算法

1.云計算編程模型Map/Reduce

隨著云計算的興起，越來越多的企業(yè)提出了自己的“云計劃”，大多數(shù)企業(yè)都以Map/Reduce編程模型的思想來開發(fā)自己的云，Map/Reduce特別適合產生和處理大規(guī)模的數(shù)據(jù)集。Map/Reduce首先在Map階段通過一個Map/Reduce函數(shù)把一個大型的計算任務分割成N個較小的子任務給多臺工作主機并行執(zhí)行。然后我們把在Map階段生成的中間文件在Reduce階段匯總分析處理，輸出M個（M與Reduce任務數(shù)量一致）輸出文件。

2.染色體的編碼和解碼

根據(jù)Map/Reduce編程模型的特點，在遺傳算法執(zhí)行階段本文針對云環(huán)境中的資源和在資源中對任務的分配制定了一種間接編碼方式（worker-task-subtask），利用隨機函數(shù)隨機生成一定數(shù)量的種群。每一個染色體都是對任務的子任務在資源中的分配方式的抽象。假設有m個任務，每個任務i的子任務數(shù)是subTask（i），子任務的總數(shù)n為：

第i個任務中第j個子任務的編號是：

假設云環(huán)境中資源總數(shù)為w，那么染色體的長度為w+n。前w（1，2，…w）個整數(shù)代表資源（worker），w+1到w+n代表分配給資源執(zhí)行的子任務（subtask）。本文規(guī)定任務隊列中的子任務分配到當前任務執(zhí)行總時間最少的資源中。

假設w=3，m = 3， subTask （i） = i+1（i的范圍是1到3），n的總數(shù)為9。那么對染色體實例{1，4，5，9，2，6，12，3，7，8，10，11}做出如下解釋：任務1中的包含編號為1，2的子任務，任務2中包含編號為3，4，5，的子任務，任務3中包含編號為6，7，8，9的子任務。子任務1，2，6運行在資源1中，子任務3，9運行在資源2中，子任務4，5，7，8運行在資源3中。對染色體的解碼能得到各個task的subTask在worker上的分布情況和各個worker上的任務執(zhí)行序列。對上述染色體實例的解碼為

Worker（1）：[1，2，6]， Worker（2）：[3，9]， Worker（3）：[4，5，7，8]

通過解碼后的序列和ETC（Expect Time to Compute）矩陣（ETC[i，j]代表序號為i的subTask在第j個資源上執(zhí)行完成所需要的時間）可以計算出每個資源的任務隊列中所有nSub個子任務的執(zhí)行時間：

則完成所有任務的總時間函數(shù)為：

假設第t個任務一共有s個子任務，第t個任務的完成時間為在w個資源中每個資源執(zhí)行t的子任務的時間最大值：

任務的平均時間為：

nTask表示任務數(shù)。

3.遺傳算法操作

3.1選取適應度函數(shù)

適應度函數(shù)用來度量種群之中個體在優(yōu)化計算中有可能達到或者接近最優(yōu)解的程度，它關系著算法的效率的高低。本文在選取適應度函數(shù)時，考慮到了在云計算中需要為多個用戶執(zhí)行不同的任務，在考慮到執(zhí)行所有任務的效率的同時也要保證每個任務的執(zhí)行效率在一個用戶相對滿意的范圍之內。本文選用了所有任務（task）執(zhí)行的平均時間函數(shù)avgTime作為主要衡量標準，并結合使用完所有任務完成總時間函數(shù)FTime來構造適應度函數(shù)：

在這里我們取u=0.7。在云計算中，所有任務執(zhí)行的平均時間和任務完成的總時間不成正比，所以我們利用任務完成的總時間的平均值來調整平均任務執(zhí)行時間的值，u就是調整系數(shù)。

3.2交叉與變異操作

本文在這里先進行普通的雙點交叉處理，再進行維持原有訪問順序和編碼格式的修改，并同時采用均勻交換變異方法對個體進行變異處理。利用隨機數(shù)生成函數(shù)生成r∈[0， 1]，若r小于交叉概率x1，則進行交叉操作，否則什么也不做。與交叉類似，若r小于變異概率x2，則進行變異操作，否則保持原狀。交叉和變異操作完成之后，比較生成的新個體的適應度函數(shù)值，留下新個體中適應度增加的個體，拋棄適應度降低的個體。經過多次迭代，生成若干組優(yōu)化解，為蟻群算法做準備。

三、蟻群算法與遺傳算法的融合

蟻群算法是根據(jù)蟻群集體尋找路徑的行為提出的仿生進化算法，它具有提供正反饋，適合并行計算等特點，所以蟻群算法很適合來優(yōu)化云計算中的并行任務調度效率。本文先采用遺傳算法對Map/Reduce模型上的任務進行迭代調度，得到一些較優(yōu)解，減少蟻群算法前期階段積累信息素占用的時間。另外，蟻群算法在運行后期的高效率也能彌補遺傳算法后期容易造成大量冗余迭代的缺點。

1.遺傳算法與蟻群算法的銜接時機選擇

遺傳算法的后期易產生冗余迭代，在遺傳算法運行合適的迭代次數(shù)后融合蟻群算法會優(yōu)化算法的效率。在選擇遺傳算法和蟻群算法的銜接時機時，本文在這里借鑒了一種動態(tài)算法，首先設定遺傳算法的最小迭代次數(shù)Gmin和最大迭代次數(shù)Gmax，并規(guī)定迭代后必須達到的子代種群進化率P，若迭代Gmin次后連續(xù)X代（0

2.蟻群算法的信息素設置

信息素更新模型：τjnew=ρ·τjold + Δτj，其中ρ是信息揮發(fā)系數(shù)（0≤ρ≤1）。在搜索過程中，蟻群算法根據(jù)每個資源上的信息量及啟發(fā)信息來計算任務在t時刻分配到每個資源上的概率：

其中α是信息啟發(fā)因子，β是期望啟發(fā)因子，表示資源能見度的相對重要性。η作為啟發(fā)函數(shù)，反映了任務分配到指定資源上的期望程度。

四、小結

本文根據(jù)云計算模型的特點，優(yōu)化了遺傳算法的編碼方案；并改進了遺傳蟻群算法的融合方法，讓兩者融合點的定位更加動態(tài)化。通過讓云計算模型上各個資源節(jié)點上的負載更加均衡，任務調度更加高效。

參考文獻：

[1]段海濱. 蟻群算法原理及其應用[ M ]. 北京： 科學出版社， 2 005： 385- 390.

[2]王小平， 曹立明. 遺傳算法 [ M ]. 西安： 西安交通大學出版社，2002 .

[3]丁建立，陳增強，袁著址. 遺傳算法與螞蟻算法的融合[J].計算機研究與發(fā)展1999，36 （10）：1240-1245.

[4]康嵐蘭.基于遺傳算法的混合蟻群算法研究[D].江西理工大學工學碩士學位論文.2008.

[5]彭建，于曉翠. 基于遺傳算法與蟻群算法動態(tài)融合的網格任務調度[J].計算機應用與軟件，2009，26（7）：121-124.

[6]吳吉義，平玲娣，潘雪增，等.云計算： 從概念到平臺[J]. 電信科學，2009，25（ 12） ：23-30.

[7]田文洪，趙勇.云計算—資源調度管理[M].北京：國防工業(yè)出版社，2011.

[8]張為民，唐劍鋒，羅治國，錢嶺.云計算：深刻改變未來[M].北京：科學出版社，2009.

[9]房秉毅，張云勇，程瑩.云計算國內外發(fā)展現(xiàn)狀分析[J].電信科學.2010，8A：1-5.

[10]王慶波，金涬，何樂，等.虛擬化與云計算[M]. 北京：電子工業(yè)出版社，2010.

作者簡介：

許樹堃（1991—），男，漢族，內蒙古呼倫貝爾人，工學碩士，單位：大連交通大學計算機科學與技術專業(yè)，研究方向：計算機管理信息系統(tǒng)。