基于遺傳蟻群算法的云計(jì)算任務(wù)調(diào)度優(yōu)化策略

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A

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

關(guān)鍵詞：云計(jì)算；遺傳算法；蟻群算法

一、引言

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

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

二、算法

1.云計(jì)算編程模型Map/Reduce

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

2.染色體的編碼和解碼

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

第i個(gè)任務(wù)中第j個(gè)子任務(wù)的編號(hào)是：

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

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

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

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

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

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

任務(wù)的平均時(shí)間為：

nTask表示任務(wù)數(shù)。

3.遺傳算法操作

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

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

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

3.2交叉與變異操作

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

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

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

1.遺傳算法與蟻群算法的銜接時(shí)機(jī)選擇

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

2.蟻群算法的信息素設(shè)置

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

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

四、小結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[9]房秉毅，張?jiān)朴?，程?云計(jì)算國內(nèi)外發(fā)展現(xiàn)狀分析[J].電信科學(xué).2010，8A：1-5.

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

作者簡(jiǎn)介：

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