基于改進的蝗蟲算法的云計算任務調度研究

陳 暄 程宏兵

1(浙江工業職業技術學院 浙江 紹興 312000)2(浙江工業大學 浙江 杭州 310023)

0 引 言

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

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

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

1 云計算任務調度模型

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

圖1 云計算任務調度邏輯過程

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

設有N個任務{T1,T2，…，Tn}和M個資源節點{N1,N2，…，NM}, 其中N>M,云計算下的任務調度可以通過如下矩陣表示:

(1)

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

(2)

(3)

(4)

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

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

(5)

(6)

(7)

2 改進的蝗蟲算法的云計算任務調度

2.1 蝗蟲算法

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

Xi=r1Si+r2Gi+r3Ai

(8)

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

(9)

(10)

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

Gr=-geg

(11)

Ai=uew

(12)

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

(13)

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

(14)

(15)

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

2.2 改進的蝗蟲算法

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

針對蝗蟲算法中的種群無初始化以及線性遞減參數需優化的問題，本文提出了采用反向學習和柯西分布分別進行優化的策略。

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

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

(16)

(17)

(18)

由式(18)可知反向學習法使得算法能在更大的搜索空間中進行搜尋,且能夠引導個體向著最優值方向進化,從而提高了算法的整體收斂速度。

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

(19)

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

(20)

2.3 個體編碼

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

P={p1,p2,…，pm}

(21)

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

表1 蝗蟲個體編碼示例

表2 蝗蟲個體解碼示例

2.4 優化目標函數設計

(22)

(23)

(24)

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

(25)

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

2.5 調度流程

步驟1初始化蝗蟲算法及其他相關參數,將云計算任務調度方案與蝗蟲個體進行一一對應,設定最大的迭代次數。

步驟2對蝗蟲算法的種群按照反向學習進行初始化。

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

步驟4計算蝗蟲個體對應的任務的目標函數值。

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

步驟6當迭代次數小于最大迭代次數,轉步驟3,否則轉步驟7。

步驟7輸出最優適應度蝗蟲個體位置,即為最佳的云計算任務方案。

3 仿真實驗

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

表3 對比算法的參數

3.1 云計算任務調度評價函數對比

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

圖2 四種算法的任務評價函數值

3.2 實驗結果

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

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

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

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

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

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

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

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

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

4 結 語

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