云計算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究

張雨，李芳，周濤

上海理工大學(xué)管理學(xué)院，上海 200090

云計算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究

張雨，李芳，周濤

上海理工大學(xué)管理學(xué)院，上海 200090

對云計算中任務(wù)調(diào)度進行了研究，針對云計算的編程模型框架，提出一種融合遺傳算法與蟻群算法的混合調(diào)度算法。在該求解方法中，遺傳算法采用任務(wù)-資源的間接編碼方式，每條染色體代表一種具體調(diào)度方案；選取任務(wù)平均完成時間作為適應(yīng)度函數(shù)，再利用遺傳算法生成的優(yōu)化解，初始化蟻群信息素分布。既克服了蟻群算法初期信息素缺乏，導(dǎo)致求解速度慢的問題，又充分利用遺傳算法的快速隨機全局搜索能力和蟻群算法能模擬資源負載情況的優(yōu)勢。通過仿真實驗將該算法和遺傳算法進行比較，實驗結(jié)果表明，該算法是一種云計算環(huán)境下有效的任務(wù)調(diào)度算法。

云計算；蟻群算法；遺傳算法；任務(wù)調(diào)度

1 引言

云計算是一種新興的商業(yè)計算模式，由網(wǎng)格計算脫胎而來，但更注重商業(yè)化，近年來受到各行各業(yè)的青睞。云計算在許多方面只是互聯(lián)網(wǎng)的一個比喻詞，亦即計算和數(shù)據(jù)資源日益遷移到Web上的比喻詞[1]。云計算代表網(wǎng)絡(luò)計算價值的一個新的臨界點。它提供更高的效率、巨大的可擴展性和更快、更容易的軟件開發(fā)。其中心內(nèi)容為新的編程模型、新的IT基礎(chǔ)設(shè)施以及實現(xiàn)新的商業(yè)模式。

目前，IBM、Google、Amazon、Microsoft等巨頭紛紛涉足云計算，提供了很多基于云計算的服務(wù)，比如Google Docs、Google Earth、Gmail、Google App Engine、Amazon EC2（Elastic computing cloud）和S3（Simple storage service）、Microsoft的Windows Live Web及Hotmail等，未來還將有各種各樣的云服務(wù)呈現(xiàn)[2]。

迄今為止，針對云計算的任務(wù)調(diào)度問題仍屬于一個比較前沿的課題?，F(xiàn)有的一些理論還不是十分成熟完善，缺乏一個系統(tǒng)的科學(xué)方法。如果采用簡單的分配調(diào)度方法，例如常用的輪轉(zhuǎn)法、加權(quán)輪轉(zhuǎn)法、最小負載（或鏈接數(shù)）優(yōu)先、加權(quán)最小負載優(yōu)先法、哈希法等，很難達到物理服務(wù)器負載均衡，進而會造成服務(wù)性能不均衡和其他相關(guān)問題。啟發(fā)式智能化方法近年來愈來愈引起了眾多學(xué)者的關(guān)注和興趣，諸如神經(jīng)網(wǎng)絡(luò)、模擬退火、禁忌搜索、遺傳算法、螞蟻算法等，它們毫無爭議地成為解決組合爆炸及NP類問題的銳利工具。文獻[3]提出了一種具有雙適應(yīng)度的遺傳算法（DFGA），在傳統(tǒng)調(diào)度算法專注任務(wù)的總完成時間最小的同時，也考慮到任務(wù)的平均完成時間，但該類算法對系統(tǒng)中的反饋信息利用不夠，求解效率不高；文獻[4]提出一種基于蟻群優(yōu)化的計算資源分配算法，根據(jù)云計算環(huán)境的特點，分析了諸如帶寬占用、線路質(zhì)量和響應(yīng)時間等因素對分配的影響；文獻[5]以云計算計價標(biāo)準(zhǔn)為切入點，提出了一種改進蟻群算法，力圖達到整體網(wǎng)絡(luò)負載均衡，延長網(wǎng)絡(luò)壽命并獲得利潤。但由于蟻群算法初始階段缺乏信息素，存在搜索時間過長，易于停滯的問題，因此該算法在搜索效率上有待提高。

在啟發(fā)式任務(wù)調(diào)度算法中，無論單純利用遺傳算法還是蟻群算法都無法獲取較好的實際效果，而且還存在不能滿足資源節(jié)點的負載均衡要求和不能滿足用戶對服務(wù)質(zhì)量要求的問題，所以實現(xiàn)不同算法的融合非常必要和有意義[6]。因此本文提出了一種遺傳蟻群算法對云計算的任務(wù)調(diào)度策略進行改進，以最大限度地提高云計算環(huán)境的效率。

2 問題描述

2.1 云計算中的編程模型分析

目前的云計算環(huán)境中大多采用Google提出的MapReduce分布式計算模式[7]，將任務(wù)自動分成多個子任務(wù)，通過Map和Reduce兩步實現(xiàn)任務(wù)在大規(guī)模計算節(jié)點中的調(diào)度與分配。大部分信息技術(shù)廠商提出的云計劃中采用的編程模型，都是基于MapReduce的思想開發(fā)的編程工具。MapReduce特別適用于產(chǎn)生和處理大規(guī)模的數(shù)據(jù)集。其執(zhí)行過程如圖1所示。

圖1 MapReduce的具體執(zhí)行過程

從圖1可看出，MapReduce有7個過程，經(jīng)總結(jié)可分為兩個主要階段：

（1）Map階段：把一個較大的任務(wù)首先通過用戶程序里的MapReduce庫分割成M個片，每個片的大小一般16～64 MB。然后配給多個worker并行執(zhí)行，輸出處理后的中間文件。

（2）Reduce階段：將Map階段處理后的結(jié)果進行匯總分析，輸出最后的處理結(jié)果：R個輸出文件。

在MapReduce編程模型下，如何對眾多的子任務(wù)進行調(diào)度是個復(fù)雜的問題。每個任務(wù)被細分成Map階段的M片，Reduce階段R片。M和R應(yīng)當(dāng)比worker機器的數(shù)量大許多，每個worker要執(zhí)行許多不同的工作。如何對眾多的任務(wù)進行調(diào)度，來達到資源的動態(tài)負載均衡，同時也要考慮響應(yīng)時間，這是本文所要考慮的主要問題。本文依據(jù)云計算環(huán)境下調(diào)度模型的特點，提出一種適用于大規(guī)模并行處理系統(tǒng)的新的調(diào)度算法，即充分利用遺傳算法的群體性、快速搜索能力，同時利用蟻群算法的正反饋性、并行性等優(yōu)勢，把這兩種算法結(jié)合起來，以建立一個較優(yōu)的分配調(diào)度策略。并通過仿真實驗，驗證應(yīng)用遺傳蟻群算法進行任務(wù)調(diào)度可以在減少任務(wù)總完成時間的同時，均衡系統(tǒng)負載，提高任務(wù)調(diào)度的效率。

2.2 有關(guān)概念的引入

首先，引入資源能見度的概念，即資源本身的屬性。云計算系統(tǒng)的后臺有成千上萬的普通或高級的服務(wù)器，任務(wù)調(diào)度中心的調(diào)度器（或中間服務(wù)器）統(tǒng)計各個資源的屬性信息，用來衡量資源節(jié)點的計算能力和通信能力，主要參數(shù)包括CPU的個數(shù)m及處理能力p（MIPS），另外還有其所處網(wǎng)絡(luò)的帶寬B（決定作業(yè)從分配到傳送到節(jié)點所用時間）。同時還要引入一個負載平衡因子，它的數(shù)值采用資源的負載完成率，也就是已經(jīng)完成的任務(wù)量和分配的任務(wù)量之比，計算公式為：Lr=La/Lf，其中Lγ表示負載完成率，La表示完成的任務(wù)量，Lf表示分配到的任務(wù)計算量之和。調(diào)度中心的調(diào)度器應(yīng)不斷地探測資源的負載及其任務(wù)的完成情況，以便對后續(xù)任務(wù)的分配產(chǎn)生積極的影響。每當(dāng)有新任務(wù)完成后，任務(wù)完成率高的資源信息素增加一些，完成率低的信息素降低一些[8]。

通過資源能見度和負載平衡因子的引入，充分利用蟻群算法的正反饋優(yōu)勢，蟻群算法能更好地模擬云計算系統(tǒng)的實時負載情況。

3 遺傳算法的優(yōu)化機理與模型描述

遺傳算法是由美國密執(zhí)安大學(xué)的John Holland教授于1975年首先提出的一類仿生型優(yōu)化算法，并行性和全局解空間搜索是GA的兩個最顯著特性。但是遺傳算法對系統(tǒng)中的反饋信息利用不夠，求解到一定范圍時往往產(chǎn)生大量的冗余迭代，求解效率不高，不一定找到最優(yōu)的分配方案[3，6]。

3.1 染色體編碼與解碼

染色體編碼有很多種方式，可以采用直接編碼，即直接對任務(wù)的執(zhí)行狀態(tài)編碼，也可以采用間接編碼。本文針對云計算環(huán)境下MapReduce編程模型的特點，采用任務(wù)-資源（task-worker）的間接編碼方式[9]，并用十進制實數(shù)編碼。利用rand函數(shù)隨機生成一定數(shù)量的十進制實數(shù)編碼種群，每條染色體代表問題的一種解。假設(shè)有n個相互獨立的任務(wù)（task），m個可用的資源（worker），染色體的長度為n+m，前n（1，2，…，n）個整數(shù)表示任務(wù)，n+1到n+m代表可用的資源（任一n+i對應(yīng)可用資源i）。定義如下規(guī)則：隊列中臨近的任務(wù)被分配到右邊最近的資源執(zhí)行。

如假設(shè)n=5，m=3，以下一條染色體解釋如下：

16237458：任務(wù)1分配給資源1執(zhí)行，任務(wù)2，3分配給資源2執(zhí)行，任務(wù)4，5分配給資源3執(zhí)行。

之后就是對染色體進行解碼，得到各個worker上的task分布情況，生成多組以資源編號的task序列，如將上述染色體16237458解碼為：

3.2 遺傳操作

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

3.2.2 個體選擇

3.2.3 交叉與變異操作

交叉：采用Davis提出的順序交叉方法，先進行常規(guī)的雙點交叉，再進行維持原有相對訪問順序的巡回路線修改。

變異：采用逆轉(zhuǎn)變異方法。

交叉概率和變異概率分別為常數(shù)c1，c2，在實際操作中利用random生成r∈[0，1]，若r小于交叉概率，則進行交叉操作，反之不然；同變異操作。如此進行，比較生成個體的適應(yīng)度函數(shù)值，只有適應(yīng)值有改進的才接受下來，否則操作皆為無效。經(jīng)遞歸迭代數(shù)次，生成若干組優(yōu)化解，為蟻群算法做準(zhǔn)備。

4 遺傳算法與蟻群算法的融合

蟻群算法（ant colony algorithm）是由意大利學(xué)者M.Dorigo等人于20世紀(jì)90年代初期通過模擬自然界中蟻群集體尋徑的行為而提出的一種基于種群的啟發(fā)式仿生進化算法，它又是一種全局優(yōu)化方法，特別適合并行計算，而且具有正反饋機制，能模擬負載情況。缺點是初期信息素缺乏，導(dǎo)致搜索初期積累信息素占用的時間較長。研究表明，蟻群算法有60%以上的時間都是用在初期信息素的積累[10-11]。

4.1 遺傳算法與蟻群算法銜接

遺傳算法后期求解效率不高，容易造成大量的冗余迭代，故遺傳算法與蟻群算法的銜接是一個難題，傳統(tǒng)策略將遺傳算法設(shè)置為運行固定的迭代次數(shù)，但過早或過晚結(jié)束都會影響算法的效果。為此本文借鑒了一種動態(tài)融合策略，確保遺傳算法與蟻群算法在最佳時機融合。具體如下：

（1）設(shè)置最小遺傳迭代次數(shù)Genemin和最大遺傳迭代次數(shù)Genemax。

（2）在遺傳迭代過程中統(tǒng)計子代群體的進化率，并以此設(shè)置子代群體最小進化率Genemin-impro-ratio。

（3）在設(shè)定的迭代次數(shù)范圍內(nèi)，如果連續(xù)Genedie代(Genemin≤Genedie≤Genemax)，子代群體的進化率都小于Genemin-impro-ratio，說明這時遺傳算法優(yōu)化速度較低，因此可終止遺傳算法過程，進入蟻群算法。

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

真實蟻群通過在覓食路徑上釋放信息素（Pheromone）最終可以在蟻穴和食物之間找到一條最短路徑，蟻群算法正是通過模擬真實蟻群的這一特征工作的。本文借鑒比利時學(xué)者Thomas Stutzle提出的MMAS（Max-Min Ant System）算法中信息素的設(shè)置[12]：

信息素的初值設(shè)為：τS=τC+τG，τC是一個根據(jù)具體求解問題規(guī)模給定的一個信息素常數(shù)，τG是遺傳算法求解結(jié)果轉(zhuǎn)換的信息素值。

4.2.1 遺傳算法向信息素的轉(zhuǎn)換

遺傳算法求解結(jié)果向信息素值轉(zhuǎn)換：選取遺傳算法終止時種群中適應(yīng)值最好的前10%個體作為遺傳優(yōu)化解集合，記為開始時，設(shè)置τG為0，對于中每個解，τG自加常數(shù)k（自設(shè)）。

4.2.2 確定資源選擇概率

在t時刻，任務(wù)被分配到每個資源上去的概率可表示為：

其中η是資源的能見度，定義為η=amP+bB，a，b分別表示資源處理能力和帶寬在資源能見度中所占的比重，α是信息素權(quán)重，β是資源能見度權(quán)重。

5 算法仿真結(jié)果

由于云計算的局部可以看作一個特殊的網(wǎng)格環(huán)境，所以本文采用Gridsim[13-15]網(wǎng)格仿真工具來模擬云計算的一個局部，以驗證本算法在這種特殊網(wǎng)格環(huán)境下的運行情況。其中，采用遺傳算法作為比較，設(shè)置初始參數(shù)如表1。

表1 兩種算法的主要參數(shù)

遺傳蟻群算法中各路徑信息素初值τC設(shè)為60，遺傳算法求解結(jié)果轉(zhuǎn)換的信息素值是經(jīng)過路徑加2，Genemin為50，Genemax為200。

基于表1的設(shè)定，兩種算法搜尋20%可用節(jié)點的仿真結(jié)果如下（顯示的均為平均后的結(jié)果）：

搜尋10%可用節(jié)點的仿真結(jié)果如下：

對比以上仿真結(jié)果發(fā)現(xiàn)，可用節(jié)點比率減小時，本算法更具優(yōu)勢，說明本算法在云計算中任務(wù)調(diào)度中的應(yīng)用是正確的。

現(xiàn)改變算法的參數(shù)，參數(shù)設(shè)置如表2。

表2 兩種算法的主要參數(shù)

再次執(zhí)行搜尋10%可用節(jié)點的仿真，結(jié)果如下：

經(jīng)對比發(fā)現(xiàn)，本算法在搜索規(guī)模擴大的情況下，優(yōu)勢較明顯。

圖2為基于表1設(shè)定的兩種算法的模擬結(jié)果的連續(xù)曲線圖。

圖2 仿真結(jié)果曲線圖

總結(jié)：云計算環(huán)境的特點之一即節(jié)點數(shù)多，而節(jié)點的失效是一種常態(tài)。經(jīng)以上對比發(fā)現(xiàn)，本算法在節(jié)點多，而有效節(jié)點少時工作效率較高，所以是云計算環(huán)境下一種有效的調(diào)度算法。

6 結(jié)束語

本文提出了一種融合了遺傳算法與蟻群算法的任務(wù)調(diào)度算法，該算法不但把任務(wù)完成時間作為一個重要的判斷標(biāo)準(zhǔn)，而且也把資源的能見度及負載均衡作為直接的參考量。通過本算法可以實現(xiàn)云計算環(huán)境下有效的任務(wù)調(diào)度。

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

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

[3]李建鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務(wù)調(diào)度算法[J].計算機應(yīng)用，2011，31（1）：184-186.

[4]華夏渝，鄭駿，胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法[J].華東師范大學(xué)學(xué)報，2010（1）：127-134.

[5]范杰，彭艦，黎紅友.基于蟻群算法的云計算需求彈性算法[J].計算機應(yīng)用，2011，31（1）：1-4.

[6]王靜宇，譚躍生，陳振江.基于遺傳蟻群混合算法的網(wǎng)格任務(wù)調(diào)度研究[J].計算機與信息技術(shù)，2008，9（3）：53-55.

[7]周敏.MapReduce綜述[D].廣州：暨南大學(xué)信息科技學(xué)院，2008.

[8]魏東.基于混合蟻群算法的網(wǎng)格任務(wù)調(diào)度研究[D].哈爾濱：哈爾濱工程大學(xué)，2008.

[9]林劍檸，吳慧中.基于遺傳算法的網(wǎng)格資源調(diào)度算法[J].計算機研究與發(fā)展，2004（12）：2195-2199.

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

[11]熊志輝，李思昆，陳吉華.遺傳算法與螞蟻算法動態(tài)融合的軟硬件劃分[J].軟件學(xué)報，2005，16（4）：503-511.

[12]丁建立，陳增強，袁著祉.遺傳算法與螞蟻算法的融合[J].計算機研究與發(fā)展，2003，40（9）：1352-1356.

[13]The Clouds Lab.Gridsim[EB/OL].（2010-06-25）.http：// www.cloudbus.org/gridsim.

[14]Foster I，Zhao Yong，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.

[15]Armbrust M，F(xiàn)ox A，Griffith R，et al.Above the clouds：a Berkeley view of cloud computing[EB/OL].（2010-01-25）. http：//www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.pdf.

ZHANG Yu,LI Fang,ZHOU Tao

College of Management,University of Shanghai for Science and Technology,Shanghai 200090,China

How to schedule masses of tasks efficiently is an important issue to be resolved in cloud computing environment.An algorithm combining Genetic Algorithm（GA）and Ant Colony algorithm（ACO）is brought up for the programming framework of cloud computing.In the algorithm,the GA adopts task-worker coding method,every chromosome representing a specific scheduling scheme,and chooses the average completing time of all tasks as its fitness function.Then the ACO adopts Genetic Algorithm to give initial information pheromone to distribute.This combination not only overcomes the slow speed of ACO caused by lack of information pheromone on the path early,but also takes full use of GA, that is fast-speed,randomly and global search.There is a contrast between GA and the combined algorithm through simulation experiment,and the result shows the proposed algorithm is efficient in the cloud computing environment.

cloud computing;ant colony algorithm;Genetic Algorithm（GA）;task scheduling

A

TP301.6

10.3778/j.issn.1002-8331.1206-0039

ZHANG Yu,LI Fang,ZHOU Tao.Task scheduling algorithm based on genetic ant colony algorithm in cloud computing environment.Computer Engineering and Applications,2014,50（6）：51-55.

上海市重點學(xué)科建設(shè)資助項目（No.S30504）。

張雨（1987—），女，碩士研究生，主要研究方向為科技管理、云計算；李芳（1966—），女，博士研究生，副教授，主要研究方向為工業(yè)工程、生產(chǎn)運作管理；周濤（1989—），男，碩士研究生，主要研究方向為工業(yè)工程、供應(yīng)鏈管理。E-mail：zhangyu627253082@163.com

2012-06-04

2012-08-16

1002-8331（2014）06-0051-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2012-09-25,http://www.cnki.net/kcms/detail/11.2127.TP.20120925.1001.047.html