基于混合優(yōu)化算法的云計(jì)算資源調(diào)度策略的研究?

阮江濤 吳海濤 錢 程 黃陳輝

（上海師范大學(xué)信息與機(jī)電工程學(xué)院 上海 200030）

1 引言

近幾年來，云計(jì)算技術(shù)的發(fā)展非常迅速，與大數(shù)據(jù)，移動(dòng)互聯(lián)網(wǎng)，物聯(lián)網(wǎng)等多種技術(shù)相互促進(jìn)，儼然已經(jīng)成為一種革命性的商業(yè)計(jì)算模式，也得到了廣泛的應(yīng)用和發(fā)展。云計(jì)算是分布式處理、并行處理和網(wǎng)格計(jì)算、虛擬化、效用計(jì)算、IaaS、PaaS、SaaS等技術(shù)融合的產(chǎn)物。云計(jì)算利用虛擬化技術(shù)，通過統(tǒng)一的調(diào)度和管理，將網(wǎng)絡(luò)中龐大的、差異性大的任務(wù)，交給云服務(wù)器，經(jīng)過分析，計(jì)算與處理將結(jié)果反饋給用戶。Hadoop 平臺(tái)作為云計(jì)算的核心，而資源調(diào)度器作為Hadoop平臺(tái)［1］的核心組件，采取不同的調(diào)度算法［2～3］對(duì)用戶提交的作業(yè)進(jìn)行資源分配和調(diào)度，不同的調(diào)度算法會(huì)對(duì)整個(gè)集群產(chǎn)生不同的影響，這直接影響著提供給用戶的服務(wù)質(zhì)量。

目前，應(yīng)用較為廣泛的作業(yè)調(diào)度算法［2］包括FIFO 調(diào)度算法、Yahoo公司研發(fā)的計(jì)算能力調(diào)度算法（Capacity Scheduler）和Facebook 公司研發(fā)的公平調(diào)度算法（Fair Scheduler）。在目前發(fā)行的Ha?doop版本中，都包含了這三種資源調(diào)度算法構(gòu)成的資源調(diào)度器，但是這些資源調(diào)度器的調(diào)度算法在實(shí)際的應(yīng)用場(chǎng)景中仍然存在一些不足和缺陷，還是不能滿足不同應(yīng)用程序的服務(wù)質(zhì)量要求。為了盡可能避免這些不足和缺陷，許多學(xué)者對(duì)hadoop的資源調(diào)度算法進(jìn)行了改善。其中劉愉，張沫等［5～9］改進(jìn)了傳統(tǒng)的遺傳算法等智能算法來優(yōu)化云計(jì)算資源調(diào)度，調(diào)度性能在一定程度上得到了提升。

遺傳算法和粒子群算法相似，其中遺傳算法具有全局搜索能力，容易陷入局部最優(yōu)，而粒子群算法局部搜索能力較強(qiáng)，收斂速度快，容易陷入局部極小，鑒于兩者互補(bǔ)的優(yōu)勢(shì)［10～11］，本文提出了一種基于改進(jìn)的遺傳算法與粒子群算法結(jié)合起來的混合優(yōu)化算法，對(duì)資源調(diào)度策略進(jìn)行相關(guān)研究。

2 云計(jì)算資源調(diào)度

2.1 MapReduce編程模型

在Hadoop 系統(tǒng)中，任務(wù)調(diào)度器是一個(gè)非常重要的組件，影響到整個(gè)平臺(tái)的系統(tǒng)資源的利用率和性能。其中Google 開發(fā)的MapReduce 模型［12］是當(dāng)前應(yīng)用最廣泛的大數(shù)據(jù)處理編程模型，該模型工作原理概述為：用戶提交作業(yè)之后，map 函數(shù)將作業(yè)分解為多個(gè)子任務(wù)，將這些子任務(wù)通過云計(jì)算資源調(diào)度算法分配到虛擬機(jī)節(jié)點(diǎn)上，等到子任務(wù)完成之后，然后由reduce 函數(shù)將中間結(jié)果匯總分析處理，最后輸出結(jié)果數(shù)據(jù)。MapReduce 編程模型執(zhí)行流程可以用圖1表示。

圖1 MapReduce編程模型流程圖

2.2 云計(jì)算資源調(diào)度原理

在云計(jì)算作業(yè)中，任務(wù)與資源并不是一一對(duì)應(yīng)的關(guān)系，而是先通過任務(wù)與資源相關(guān)聯(lián)，然后將資源映射到對(duì)應(yīng)的物理設(shè)備上，從而完成作業(yè)的調(diào)度。簡(jiǎn)單的來說，下面的5元組可以描述資源調(diào)度［13］的過程：

式中，S 表示一個(gè)完整的調(diào)度過程，T={t1，t2，…，tm}表示任務(wù)數(shù)量的集合，R ={r1，r2，…，rm} 表示資源數(shù)量的集合，D={d1，d2，…，dm}表示物理設(shè)備數(shù)量的集合，Mtr表示資源與任務(wù)之間的映射關(guān)系，Mrd表示資源與物理設(shè)備之間的映射關(guān)系。

其中Mtr是由計(jì)算機(jī)中心進(jìn)行任務(wù)分配的，而Mrd是由資源調(diào)度器將資源調(diào)度到相應(yīng)的存儲(chǔ)設(shè)備上，因此資源調(diào)度解決的主要問題是資源到存儲(chǔ)設(shè)備的調(diào)度。

假設(shè)現(xiàn)在有任務(wù)ti通過映射關(guān)系Mtr映射到資源vj上，資源vj通過調(diào)度算法調(diào)度到物理設(shè)備dk上，將任務(wù)ti通過計(jì)算機(jī)中心分配資源然后到達(dá)物理設(shè)備dk的過程，其預(yù)期執(zhí)行時(shí)間記為ETD(ti，dk)，任務(wù)T對(duì)物理設(shè)備D分配矩陣記為

上面式子為一個(gè)執(zhí)行時(shí)間矩陣，表示通過資源映射關(guān)系tiMtr將m 個(gè)任務(wù)分配到n 個(gè)設(shè)備上的執(zhí)行時(shí)間矩陣。

任務(wù)ti通過映射關(guān)系Mtr在物理設(shè)備dk上最早完成時(shí)間記為

式中，Start(dk)表示物理設(shè)備dk上可以執(zhí)行任務(wù)的最早開始時(shí)間，因此，物理設(shè)備dk上分配任務(wù)需要花費(fèi)的總時(shí)間可以使用下面式子表示：

式中，cik=1 表示任務(wù)ti在物理設(shè)備dk上執(zhí)行，因此，所有的任務(wù)通過資源調(diào)度器執(zhí)行的總時(shí)間為

優(yōu)化資源調(diào)度算法，為的就是通過資源調(diào)度器使得任務(wù)執(zhí)行時(shí)間最短，即上式中的值最小，因此資源調(diào)度的目標(biāo)函數(shù)為

3 遺傳和粒子群算法

3.1 標(biāo)準(zhǔn)粒子群算法（PSO）

粒子群算法（PSO），又稱微粒子群算法［14］，是由R.C.Eberhart 和J.Kennedy 等在1995 年提出的一種演化算法，最初的目的是為了圖形化的模擬鳥群無規(guī)則的運(yùn)動(dòng)。該算法的使用背景是群體，通過對(duì)環(huán)境適應(yīng)度的計(jì)算，將群體中的個(gè)體移動(dòng)到更好的位置。PSO 算法將每個(gè)個(gè)體比作D 維空間中的一個(gè)個(gè)沒有體積的粒子，在空間中按照特定的速度飛行，飛行速度會(huì)根據(jù)同伴的和自身的飛行經(jīng)驗(yàn)動(dòng)態(tài)更新。以下公式可以粒子速度和粒子位置的更新公式：

其中，d=1，2，…，D，表示搜索空間的維度，表示第k 次迭代粒子i 飛行速度矢量的第d 維分量，示第k次迭代粒子i位置矢量的第d維分量，w為慣性權(quán)重，用于調(diào)節(jié)對(duì)解空間的搜素范圍，c1、c2為加速常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長(zhǎng)，r1、r2為兩個(gè)隨機(jī)函數(shù)，取值范圍為［0，1］，為的是增加搜索的隨機(jī)性。

3.2 經(jīng)典遺傳算法

遺傳算法［15］（Genetic Algorithm）是在1975年由美國(guó)Michigan 大學(xué)holland 教授提出來，該算法是一種模擬達(dá)爾文生物進(jìn)化論的一種自適應(yīng)的全局優(yōu)化概率搜索算法。遺傳算法類似于自然進(jìn)化，通過作用在染色體上的基因來找尋更好的染色體來求解。作為一種群體智能進(jìn)化算法，相比一般的優(yōu)化算法具備很好的收斂性，計(jì)算精度高，計(jì)算時(shí)間少以及具備較好的魯棒性。

4 改進(jìn)的遺傳算法

4.1 編碼

標(biāo)準(zhǔn)的遺傳算法使用的是二進(jìn)制編碼，該編碼方式是由字符集｛0，1｝組成，所組成的個(gè)體基因?yàn)槎M(jìn)制編碼字符串。本文研究的問題是將作業(yè)按照調(diào)度算法將

放入作業(yè)隊(duì)列中，具有連續(xù)性。如果采用二進(jìn)制編碼的話，會(huì)使得連續(xù)的函數(shù)變成離散型函數(shù)。二進(jìn)制編碼顯著的缺點(diǎn)是較大的Hamming距離，在交叉和突變變得難以跨越，而且準(zhǔn)確度不高。實(shí)數(shù)編碼使用的是Euclidean 距離，使得遺傳算法更能接近問題空間，因此本文打算使用實(shí)數(shù)編碼。

4.2 適應(yīng)度函數(shù)

云計(jì)算中所有任務(wù)完成時(shí)間長(zhǎng)短是衡量云計(jì)算資源調(diào)度算法的好壞的標(biāo)準(zhǔn)，適應(yīng)度值越大，則表明調(diào)度算法更好，因此適應(yīng)度函數(shù)［16］可以表示為

本文適應(yīng)度函數(shù)中引入動(dòng)態(tài)懲罰函數(shù)，對(duì)于不符合約束條件的個(gè)體，給出一個(gè)小的適應(yīng)值，其懲罰函數(shù)可以表示為

式中，t表示進(jìn)化的次數(shù)，通常情況下c=0.5 ，α=β=2。因此加上動(dòng)態(tài)懲罰函數(shù)的適應(yīng)度函數(shù)可以表示為

4.3 選擇算子

本文采用比例模型方法，即輪盤賭方式，它是一種回放式的隨機(jī)采樣方法，基于的是適者生存的思想。假設(shè)種群大小為M，其中某個(gè)染色體個(gè)體的適應(yīng)度為fi，它被選擇的概率Pi可以表示為

4.4 交叉算子

在遺傳算法中，在交叉計(jì)算前需要進(jìn)行個(gè)體的配對(duì)，通常使用隨機(jī)配對(duì)模式。假設(shè)在一個(gè)有W個(gè)個(gè)體的種群中，隨機(jī)組成W/2 對(duì)，在這隨機(jī)組成的兩兩個(gè)體之間配對(duì)。

本文采用實(shí)數(shù)編碼方式，因此可以使用算數(shù)交叉方式，進(jìn)行交叉的兩個(gè)父代個(gè)體Xi和Xj通過算數(shù)交叉后得到兩個(gè)子代個(gè)體和，交叉操作可以表示為

式中，i，j=1，2，..，W/2 ，γ取值為區(qū)間[ ]0，1 上均勻分布的隨機(jī)數(shù)。

4.5 變異算子

由于本文采用的是實(shí)數(shù)編碼方式，因此使用非均 勻 變 異 算 子 。 假 設(shè) 變 異 個(gè) 體 為W=[w1，w2，…，wk，…，wL]T，以概率為Pm進(jìn) 行 變異，其中wk的取值范圍為(wk_min，wk_max)，變異后可以用式（15）表示：

圖2 云計(jì)算資源調(diào)度算法工作流程圖

式中，t表示進(jìn)化的代數(shù)，α表示在區(qū)間(0，1)上均勻分布的隨機(jī)數(shù)，那么?(t，x)表示在區(qū)間[0 ，x] 上非均勻分布的隨機(jī)數(shù)，其表達(dá)式可以描述為

式中，b 表示的是確定非均勻度的參數(shù)，β取值為區(qū)間[0 ，1] 上的隨機(jī)數(shù)，T 表示的是最大進(jìn)化的代數(shù)。

5 混合優(yōu)化算法

本文采用串行式混合優(yōu)化算法，將遺傳算法進(jìn)化得出的種群作為粒子群算法進(jìn)化的初始種群，結(jié)合遺傳算法的全局搜索能力和粒子群算法局部搜索能力的優(yōu)點(diǎn)，可以得出較優(yōu)的云計(jì)算資源調(diào)度方案。根據(jù)改進(jìn)的混合優(yōu)化算法，云計(jì)算資源調(diào)度流程圖如圖2所示，執(zhí)行步驟如下所示。

Step1：確定云計(jì)算資源調(diào)度數(shù)量，并且初始化種群，確定迭代次數(shù)，種群大小N，加速常數(shù)c1，c2等參數(shù)。

Step2：通過加入懲罰函數(shù)的適應(yīng)度函數(shù)，對(duì)每個(gè)染色體進(jìn)行適應(yīng)度評(píng)估，得出對(duì)應(yīng)的適應(yīng)度值。

Step3：通過比例模型方式選擇策略在當(dāng)前種群中選擇個(gè)體，然后通過算數(shù)交叉方式和非均勻變異算子執(zhí)行。

Step4：根據(jù)是否滿足終止條件，如果滿足則將優(yōu)化后的種群作為粒子群算法的初始化種群。如果不滿足則轉(zhuǎn)到Step2。

Step5：選擇改進(jìn)的遺傳算法中最優(yōu)的解作為粒子群算法的初始粒子，并且對(duì)每個(gè)粒子進(jìn)行初始化。

Step6：更新群極值和個(gè)體極值。

Step6：更新每個(gè)粒子的速度和位置。

Step7：根據(jù)是否滿足終止條件，如果滿足則作為輸出相應(yīng)的粒子位置，得出最優(yōu)云計(jì)算資源調(diào)度方案。如果不滿足則轉(zhuǎn)到Step6。

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

為了驗(yàn)證改進(jìn)的資源調(diào)度算法在云計(jì)算中的效果，本文通過CloudSim 仿真平臺(tái)對(duì)本文改進(jìn)的算法和其他算法進(jìn)行資源調(diào)度比較。

在同樣的實(shí)驗(yàn)條件下，選擇遺傳算法（GA）和改進(jìn)后的混合優(yōu)化算法（GA-PSO）進(jìn)行實(shí)驗(yàn)。其中資源數(shù)量為20 個(gè)，任務(wù)數(shù)量范圍為［1000，4000］，交叉概率設(shè)為0.8，變異概率設(shè)為0.2。其仿真結(jié)果如圖3所示。

由圖3 可知，在任務(wù)數(shù)較多的情況下，改進(jìn)的混合優(yōu)化調(diào)度算法比傳統(tǒng)的遺傳調(diào)度算法還有具有一點(diǎn)優(yōu)勢(shì)的。接下來的任務(wù)是在指定的大數(shù)據(jù)大量任務(wù)數(shù)為4000 的情況下，研究算法迭代次數(shù)與執(zhí)行時(shí)間的關(guān)系，其仿真結(jié)果如圖4所示。

圖3 大數(shù)據(jù)量下算法的任務(wù)完成對(duì)比圖

圖4 兩種算法種群收斂對(duì)比圖

由上圖可知，迭代初期兩種算法的效果其實(shí)差別不明顯，到后期隨著迭代次數(shù)的增加，優(yōu)化后的算法在120 代之后已經(jīng)接近成熟，而傳統(tǒng)的遺傳算法具有異常的適應(yīng)值，可能是種群向著錯(cuò)誤的方向進(jìn)化的結(jié)果，在優(yōu)化后的改進(jìn)的資源調(diào)度算法比傳統(tǒng)的調(diào)度算法效果更好。

綜上所述，改進(jìn)的混合優(yōu)化調(diào)度算法克服了傳統(tǒng)調(diào)度算法缺點(diǎn)，得到了一種更優(yōu)的云計(jì)算調(diào)度策略，既縮短了作業(yè)完成時(shí)間，又提高了系統(tǒng)資源利用率。

7 結(jié)語

針對(duì)云計(jì)算中資源調(diào)度問題，本文引入了遺傳算法和粒子群算法，將改進(jìn)后的算法進(jìn)行融合，進(jìn)行資源的調(diào)度，結(jié)合了遺傳算法的全局搜索能力和粒子群算法的局部搜索能力，相比傳統(tǒng)的算法在調(diào)度效果上有了明顯的進(jìn)步。接下來的研究任務(wù)可以從將更多智能算法和機(jī)器學(xué)習(xí)算法與云計(jì)算資源調(diào)度結(jié)合，從而優(yōu)化調(diào)度效率不高或者負(fù)載不均衡的問題。