基于改進的蝗蟲算法的云計算任務(wù)調(diào)度研究

陳 暄 程宏兵

1(浙江工業(yè)職業(yè)技術(shù)學(xué)院 浙江 紹興 312000)2(浙江工業(yè)大學(xué) 浙江 杭州 310023)

0 引 言

云計算是分布式計算、并行計算、網(wǎng)格計算、網(wǎng)絡(luò)存儲、虛擬化等技術(shù)的發(fā)展融合,是目前已經(jīng)實現(xiàn)的一種商業(yè)服務(wù)模式。它以高效、便捷的服務(wù)受到了當(dāng)前人們的歡迎。云計算中的軟硬件都是資源,它將計算任務(wù)分布在大量的計算機組成的資源池上,以網(wǎng)絡(luò)服務(wù)的方式提供給用戶。隨著云計算的發(fā)展和數(shù)據(jù)規(guī)模不斷擴大,傳統(tǒng)的調(diào)度算法已經(jīng)無法滿足當(dāng)前的需求,因此為用戶提供更為合理的資源分配方式、減少任務(wù)完成時間、設(shè)計高效負載均衡等問題是目前云計算中的研究方向。

云任務(wù)中的任務(wù)調(diào)度本質(zhì)就是一個NP完全問題[1],很多傳統(tǒng)的元啟發(fā)式算法用于解決此類問題,比如遺傳算法[2-3]、粒子群算法[4-5]、蟻群算法[6-7]、人工蜂群算法[8-9]，都取得了不錯的效果。一些學(xué)者將改進的傳統(tǒng)啟發(fā)式算法用于云計算任務(wù)調(diào)度[10-15]，取得了一定的效果。一些學(xué)者將兩種傳統(tǒng)的元啟發(fā)式算法進行融合用于云計算任務(wù)調(diào)度，例如：文獻[16]提出了基于ACO和PSO融合的云計算的任務(wù)資源調(diào)度算法;文獻[17]提出了基于GA和ACO融合的用于云計算任務(wù)資源調(diào)度算法，該算法能夠降低任務(wù)調(diào)度時間和成本，但缺乏與較新的元啟發(fā)式算法對比效果；文獻[18]提出了基于ABC和PSO融合的云計算任務(wù)調(diào)度算法；文獻[19]提出了基于SFLA和GA融合的云計算資源算法；文獻[20]提出了基于SFLA和PSO融合的用于云計算中可信任資源的調(diào)度算法。這些融合后的算法都能吸收各自算法的優(yōu)點，確實提高了云計算任務(wù)調(diào)度效率,但增加了整個調(diào)度算法的復(fù)雜度。另外一些學(xué)者專注于較新的算法用于云計算任務(wù)調(diào)度,例如：文獻[21]提出了一種基于煙花算法的云計算任務(wù)調(diào)度方案,仿真實驗說明該算法能夠優(yōu)化調(diào)度效率,但缺乏與其他較新的算法進行對比;文獻[22]提出在云計算中使用雞群算法用于云計算資源任務(wù)調(diào)度,仿真實驗說明該算法在虛擬機負載、時間和成本方面具有較好的調(diào)度效果,但缺乏對能耗指標進行考慮；文獻[23]提出將共生共物算法用于云計算任務(wù)調(diào)度中，仿真實驗說明該算法能夠提高調(diào)度效率，但增加了算法的復(fù)雜度。文獻[24]提出將細菌覓食的算法用于云計算的資源調(diào)度中，取得了不錯的效果。

蝗蟲算法[25]是2016年誕生的一種新的元啟發(fā)式算法,性能優(yōu)于部分傳統(tǒng)元啟發(fā)式算法,具有很強的開發(fā)能力。目前將該算法用于云計算相關(guān)調(diào)度的文獻非常少，文獻[26]將其用于云計算資源調(diào)度，取得了較好的調(diào)度效果。本文將改進的蝗蟲算法用于云計算任務(wù)調(diào)度,仿真實驗中通過與蟻群算法、粒子群算法以及基本蝗蟲算法在完成時間、成本消耗以及負載均衡三個指標的對比,說明了改進的蝗蟲算法在云計算中具有良好的調(diào)度效果。

1 云計算任務(wù)調(diào)度模型

在云計算中任務(wù)調(diào)度策略將直接影響底層系統(tǒng)的資源使用效率，因此如何分配任務(wù)成為云計算調(diào)度的關(guān)鍵問題。圖1展示了云計算系統(tǒng)中典型任務(wù)調(diào)度過程的邏輯視圖。本文中主要關(guān)注不同調(diào)度算法的性能，因此假設(shè)用戶提交的所有任務(wù)在邏輯上都是相互獨立的，云環(huán)境下的任務(wù)調(diào)度過程可以概括為以下三個步驟。首先，輸入任務(wù)的詳細信息和可用計算資源；其次將根據(jù)某些策略來映射任務(wù)和資源，按照映射進行操作，控制層的任務(wù)計劃將生成優(yōu)化的任務(wù)執(zhí)行計劃，以滿足某些已分配的要求(即優(yōu)化目標)；最后將優(yōu)化后的計劃交付給底層任務(wù)處理層以供執(zhí)行，并將輸出結(jié)果發(fā)送給用戶。采用這樣的模式優(yōu)勢在于能夠降低計算時延、降低計算成本，提高了用戶體驗效果。

圖1 云計算任務(wù)調(diào)度邏輯過程

本文將負載均衡、完成成本、執(zhí)行時間作為用戶評價云計算(Quality of Service,QoS)服務(wù)的參考依據(jù)。

設(shè)有N個任務(wù){(diào)T1,T2，…，Tn}和M個資源節(jié)點{N1,N2，…，NM}, 其中N>M,云計算下的任務(wù)調(diào)度可以通過如下矩陣表示:

(1)

矩陣A中的aij為1表示任務(wù)i在資源j上執(zhí)行,否則aij為0，i∈[1,N]，j∈[1,M]。本文定義每個資源節(jié)點的屬性包括處理能力(即處理時間)、初始內(nèi)存(即反映處理所承受的負荷)、資源帶寬(即反映了處理所需要的成本)。因此,構(gòu)建虛擬機資源三個向量分別是處理能力向量En、負載能力向量Sn、資源帶寬向量Cn。與此同時每個任務(wù)對應(yīng)也具有三個矩陣,分別是處理能力向量Et、負載能力向量St、資源帶寬向量Ct,P為單位價格。因此時間目標函數(shù)time、負載目標函數(shù)load和成本目標函數(shù)cost表示如下：

(2)

(3)

(4)

式中：Et,i表示第i個任務(wù)的Et的值；En,j表示第j個虛擬機的En值；St,i表示第i個任務(wù)的St的值Sn,j表示第j個虛擬機的Sn值；Ct,i表示i個任務(wù)的Ct值；Cn,j表示第j個虛擬機的Cn值。

由于資源節(jié)點和任務(wù)節(jié)點的三個矩陣中所表示的結(jié)果具有不同的標準,因此需要進行歸一化處理,因此上述三個目標函數(shù)表達為如下形式:

(5)

(6)

(7)

2 改進的蝗蟲算法的云計算任務(wù)調(diào)度

2.1 蝗蟲算法

Saremi等根據(jù)蝗蟲的群體行為提出了蝗蟲優(yōu)化算法(Grasshopper optimization algorithm,GOA),該算法分為探索和開發(fā)兩個部分組成,其中探索部分對應(yīng)蝗蟲的幼蟲階段,開發(fā)部分對應(yīng)蝗蟲的成蟲階段。幼蟲階段中,蝗蟲群體跳躍性運動的行為,主要進行全局搜索;成蟲階段中,蝗蟲在小范圍內(nèi)移動,有利于局部搜索。蝗蟲種群在繁衍、覓食、遷移的時候,其個體位置會受到來自種群交互力、引力和風(fēng)力的影響,因此采用數(shù)學(xué)模型對其位置更新行為描述如下:

Xi=r1Si+r2Gi+r3Ai

(8)

式中：Xi表示第i只蝗蟲的位置；Si表示第i只蝗蟲受到其他蝗蟲的交互力的影響；Gi為第i只蝗蟲受到引力的影響力；Ai為第i只蝗蟲受到風(fēng)力的影響力；r1、r2、r3分別為隨機數(shù)且取值為[0,1]。其中：

(9)

(10)

當(dāng)s(r)大于0的時候,蝗蟲之間會相互吸引,因此r的取值范圍稱作吸引域；當(dāng)s(r)小于0的時候,蝗蟲之間相互排斥,因此r的取值范圍稱作排斥域;當(dāng)s(r)為0的時候,蝗蟲之間既不吸引又不排斥,因此r為舒適的距離。另外,f和l分別表示吸引強度參數(shù)和尺度參數(shù),它們的取值情況影響到吸引域,排斥域和適度的分布距離,一般l取值為1.5,f取值為0.5。

Gr=-geg

(11)

Ai=uew

(12)

式中：g表示引力常數(shù)；eg表示指向地心的單位向量;u表示風(fēng)向常數(shù)；ew表示風(fēng)向單位向量。因此蝗蟲個體位置更新如下:

(13)

雖然式(13)是用來對蝗蟲群體進行模擬的,但是從實際應(yīng)用的方面進行考慮,通常不考慮引力因素,認定風(fēng)向指向目標位置,因此求出最佳的蝗蟲個體位置即為求解最優(yōu)化問題。公式如下所示：

(14)

(15)

式中：ubd和lbd分別對應(yīng)第i只蝗蟲在第d維度變量的上界和下界；Td為蝗群的目標位置；c為遞減系數(shù)，一方面用于平衡全局搜索和局部開發(fā)能力,另一方面用于排斥域及吸引域；t為當(dāng)前迭代次數(shù)；cmax和cmin分別為最大值和最小值。

2.2 改進的蝗蟲算法

像其他的元啟發(fā)式算法一樣，蝗蟲算法也存在易陷入局部最優(yōu)、全局搜索能力不足的問題。文獻[27]提出在蝗蟲算法中引入自適應(yīng)策略來優(yōu)化參數(shù)，提高了算法的收斂速度,但增加了算法運行時間;文獻[28]提出了曲線自適應(yīng)和模擬退火蝗蟲優(yōu)化算法,提高了蝗蟲算法的收斂精度，但增加了算法復(fù)雜度;文獻[29]提出了一種基于量子計算思想的混合蝗蟲優(yōu)化算法,具有更強的全局搜索能力,更好的收斂精度,能夠有效跳出局部最優(yōu),但增加了算法運行時間。

針對蝗蟲算法中的種群無初始化以及線性遞減參數(shù)需優(yōu)化的問題，本文提出了采用反向?qū)W習(xí)和柯西分布分別進行優(yōu)化的策略。

(1) 種群初始化?；认x算法中初始解是隨機產(chǎn)生的,因此容易導(dǎo)致算法產(chǎn)生最優(yōu)解無法均勻地分布在空間中,從而限制了算法的求解效率,降低了算法的性能。反向?qū)W習(xí)[30]是一種適合種群優(yōu)化的機器學(xué)習(xí)策略,它通常在算法的每一次迭代中得到這些當(dāng)前解的反向解,并從每一次的當(dāng)前解和反向解中選擇出有利于進化的解,進一步降低算法的盲目性,擴大了搜索空間,提高算法的全局搜索能力。算法過程如下:

步驟1隨機生成初始種群。隨機生成蝗蟲算法的初始種群NP1={x1(t),x2(t),…，xW(t)},其中對應(yīng)的個體的解計算為：

(16)

(17)

(18)

由式(18)可知反向?qū)W習(xí)法使得算法能在更大的搜索空間中進行搜尋,且能夠引導(dǎo)個體向著最優(yōu)值方向進化,從而提高了算法的整體收斂速度。

(2) 線性遞減系數(shù)優(yōu)化。線性遞減參數(shù)的作用主要用于平衡局部和全局開發(fā)能力,其表達式中除迭代變量k以外,其余都是固定的數(shù)值。因此該線性遞減參數(shù)的數(shù)值隨著迭代次數(shù)的變大而逐漸變小,如果遞減參數(shù)數(shù)值過小或者過大都不利于局部和全局能力的平衡,因此需要對迭代遞減系數(shù)進行優(yōu)化,使得該系數(shù)能夠很好地進行平衡。柯西分布[31]是一種具有兩翼均衡特性的函數(shù),公式如下：

(19)

在線性遞減表達式中對迭代次數(shù)引入柯西分布,能夠更好平衡和全局之間的能力,因此,線性遞減參數(shù)表達式優(yōu)化如下:

(20)

2.3 個體編碼

本文將改進后的蝗蟲算法用于云計算任務(wù)調(diào)度中,對蝗蟲個體進行編碼,將任務(wù)調(diào)度與蝗蟲個體的位置結(jié)合起來,對蝗蟲個體采用自然數(shù)編碼方式,該方式簡單易懂，能夠在操作過程中降低算法的復(fù)雜度?；认x個體位置的編碼長度為子任務(wù)的數(shù)量,蝗蟲個體的維度等于調(diào)度的任務(wù)數(shù)。設(shè)有task個任務(wù),劃分為m個子任務(wù),云計算下n個資源,因此蝗蟲編碼表示為n維向量：

P={p1,p2,…，pm}

(21)

式中：pi∈[1,n],蝗蟲個體每一維縱坐標表示一個子任務(wù)的編號,pi表示分配給此子任務(wù)的資源編號。設(shè)定task=4,m=10,n=5,即4個任務(wù)被劃分為10個子任務(wù),分配到5個資源上時,蝗蟲個體的編碼為(1,2,5,3,3,4,2,1,5,4)。如表1所示,該蝗蟲個體代表了一個可行的調(diào)度方案,因此對蝗蟲個體的解碼能夠知道任務(wù)分配情況,如表2所示。

表1 蝗蟲個體編碼示例

表2 蝗蟲個體解碼示例

2.4 優(yōu)化目標函數(shù)設(shè)計

(22)

(23)

(24)

由于本文所求的云計算任務(wù)目標函數(shù)要獲得最小值，因此需要個體的適應(yīng)度函數(shù)越大(即優(yōu)秀的個體)，本文的目標的適應(yīng)度函數(shù)值如下：

(25)

該目標函數(shù)強調(diào)了虛擬機負載、成本和時間三個指標在云計算任務(wù)中具有相等的作用，因此能夠較為客觀地反映出用戶對云計算任務(wù)調(diào)度服務(wù)進行評價，通過求解最優(yōu)的蝗蟲個體位置而獲得最優(yōu)的云計算任務(wù)調(diào)度方案。

2.5 調(diào)度流程

步驟1初始化蝗蟲算法及其他相關(guān)參數(shù),將云計算任務(wù)調(diào)度方案與蝗蟲個體進行一一對應(yīng),設(shè)定最大的迭代次數(shù)。

步驟2對蝗蟲算法的種群按照反向?qū)W習(xí)進行初始化。

步驟3對蝗蟲算法的遞減系數(shù)采用柯西分布思想進行更新。

步驟4計算蝗蟲個體對應(yīng)的任務(wù)的目標函數(shù)值。

步驟5將任務(wù)目標函數(shù)值和上一次迭代中的目標函數(shù)值進行對比，如果小于上一次迭代的結(jié)果則取代原來蝗蟲個體位置，否則保持不變。

步驟6當(dāng)?shù)螖?shù)小于最大迭代次數(shù),轉(zhuǎn)步驟3,否則轉(zhuǎn)步驟7。

步驟7輸出最優(yōu)適應(yīng)度蝗蟲個體位置,即為最佳的云計算任務(wù)方案。

3 仿真實驗

為了進一步說明IGOA在云計算任務(wù)調(diào)度下的效率,選擇與基本GOA、PSO、ACO進行對比。一方面對比了任務(wù)適應(yīng)評價函數(shù)值中的優(yōu)劣,另一方面對比了不同任務(wù)數(shù)量下的虛擬機負載、花費時間和成本花費等指標。硬件選擇CPU為酷睿i3,內(nèi)存為4 GB/DDR3,硬盤容量為1 000GB,軟件環(huán)境為Windows 7系統(tǒng),MATLAB 2012仿真軟件。設(shè)置最大迭代次數(shù)為200,種群規(guī)模為20,搜索維度為90,對比算法的主要參數(shù)如表3所示。設(shè)定兩種任務(wù)集合,分別是大任務(wù)數(shù)量為[1 000,10 000],小任務(wù)數(shù)量為[10,100]。

表3 對比算法的參數(shù)

3.1 云計算任務(wù)調(diào)度評價函數(shù)對比

圖2顯示了四種算法的云計算任務(wù)調(diào)度評價函數(shù)的對比結(jié)果。IGOA相比于其他三種算法首先趨于穩(wěn)定,這說明了IGOA具有良好的性能,同時在評價函數(shù)結(jié)果的對比上，IGOA明顯低于其他三種算法,這說明IGOA用于云計算下的任務(wù)調(diào)度具有良好的效果。

圖2 四種算法的任務(wù)評價函數(shù)值

3.2 實驗結(jié)果

(1) 虛擬機負載。本文設(shè)定10個資源對應(yīng)分別處理兩種情況下的任務(wù),四種算法使用虛擬機的負載對比情況如圖3-圖4所示。圖3中的四種算法在不同的資源節(jié)點的情況下負載率數(shù)值幾乎相差不大,甚至在有些資源節(jié)點的調(diào)度中,IGOA并不具備十分明顯的優(yōu)勢,這說明小任務(wù)情況下的四種算法虛擬機負載差別不大。圖4中的四種算法在不同資源節(jié)點下的負載比例相差比較大,IGOA相對于GOA、PSO和ACO的負載率比例分別提高了9.06%、24.2%和26.7%,這說明經(jīng)過種群初始化和遞減系數(shù)優(yōu)化的IGOA的性能明顯優(yōu)于以上三種算法,能夠在處理大任務(wù)的時候能夠發(fā)揮虛擬機的性能,提高任務(wù)調(diào)度效率。

圖3 小任務(wù)下的四種算法虛擬機負載對比

圖4 大任務(wù)下的四種算法虛擬機負載對比

(2) 完成時間對比。圖5-圖6顯示了四種算法在不同任務(wù)數(shù)量下完成時間的對比結(jié)果。圖5中的四種算法的執(zhí)行時間都會隨著任務(wù)數(shù)量的增加而呈現(xiàn)上升趨勢,四條曲線總體上比較平穩(wěn),而且相互之間時間差別不大,IGOA占據(jù)微弱的優(yōu)勢。圖6顯示了大任務(wù)下的四種算法的完成時間對比,可以發(fā)現(xiàn)IGOA的時間曲線的增加趨勢相比于其他三種算法更加平緩,完成時間明顯優(yōu)于其他三種算法,這說明遞減系數(shù)采用了柯西分布優(yōu)化后,提高了局部搜索和全局搜索能力,因此在完成時間具有一定的優(yōu)勢,IGOA相比于GOA、PSO和ACO時間分別節(jié)省了17.15%、37.8%和54.8%,這說明IGOA在大任務(wù)調(diào)度中的完成時間上獲得比較滿意的結(jié)果。

圖5 小任務(wù)下的四種算法完成時間對比

圖6 大任務(wù)下的四種算法完成時間對比

(3) 成本消耗對比。圖7-圖8顯示了四種算法在不同任務(wù)數(shù)量下的成本消耗結(jié)果,圖7中四種算法的成本消耗曲線隨著任務(wù)數(shù)量的增加而逐漸上升,四種算法之間成本消耗數(shù)值相差不大。圖8中四種算法的成本消耗曲線隨著任務(wù)數(shù)量不斷增大而逐步上升,IGOA在任務(wù)數(shù)量的初期與其他三種算法相差不大,隨著任務(wù)數(shù)量不斷地增加,IGOA成本消耗曲線數(shù)值上升趨勢低于其他三種算法,這說明IGOA通過種群初始化后提高了算法性能,降低了自身的成本消耗，相比于GOA、PSO、ACO分別降低了9.13%、12.4%和24.6%,這說明IGOA在大任務(wù)條件下具有一定的成本優(yōu)勢。

圖7 小任務(wù)下的四種算法消耗成本對比

圖8 大任務(wù)下的四種算法消耗成本對比

4 結(jié) 語

針對云計算中任務(wù)調(diào)度存在效率低的問題,本文提出了采用改進的蝗蟲算法進行調(diào)度。從實驗結(jié)果來看,相比于蟻群算法、粒子群算法和基本蝗蟲算法而言,IGOA在均衡負載、完成時間和消耗成本上都具有一定的優(yōu)勢,尤其是在大任務(wù)方面的優(yōu)勢比較明顯。這主要是由于在種群初始化和線性遞減系數(shù)兩個方面進行了優(yōu)化使得算法性能得到了提高。但是當(dāng)任務(wù)數(shù)量較小的時候,IGOA在成本消耗上處于一定的劣勢,這將是下一步研究突破的重點,縱觀整個調(diào)度過程,本文提出改進的蝗蟲算法比較適合大任務(wù)下的云計算任務(wù)調(diào)度。