基于改進獅群算法的云計算資源調度策略

王艷紅 張革文

(中國民航大學飛行技術學院 天津 300300)

0 引 言

隨著互聯網技術的迅速發展，計算機需要處理的任務量和數據量成倍增加，計算機的處理能力和處理速度已難以滿足用戶的需求。云計算作為虛擬技術的產物，可以針對海量數據和任務進行處理。但是，由于計算量十分巨大，云環境在計算過程中需合理地將系統資源快速分配到每個客戶任務中，因此需要提高云計算對資源的利用效率和云計算速度[1]。同時，由于云資源具有自主性、異構性等特性，使得云計算資源調度優化問題具有許多非確定因素，難以優化，屬于典型的NP-Hard問題。因此如何有效提高云計算的資源利用問題，是云計算研究的核心問題[2]。

針對上述問題，國內外許多研究學者提出了不同的資源調度策略。趙宏偉等[3]利用菌群優化算法對云系統中的資源節點進行復制和消亡，以此有效地控制資源節點對用戶任務的分配情況。聶清彬等[4]通過改進蟻群的優化算法，合理優化云計算資源調度模型，提高了資源利用率，降低了資源能耗成本。喻德曠等[5]提出一種動態粒子群算法對調度模型進行求解，較高地均衡了云計算的負載，提高了云計算效率。齊平等[6]提出一類可靠性評估模型，對資源調度問題進行求解，提高了云計算資源可靠性和利用率。陳暄等[7]提出一類改進的煙花蜂群算法，并對云計算資源調度模型進行求解，實驗結果表明，該算法有效提高了云計算資源分配效率。Zhu等[8]提出一種三維虛擬資源的云計算資源調度策略。Kliazovich等[9]提出一種基于有向無環圖的云計算資源調度策略，有效提高了云計算資源調度效率，節約了計算時間。Lin等[10]提出一種快速遺傳算法的調度策略。此外還有改進粒子群算法的優化策略[11]、支持QoS的調度方法[12]、基于多租戶的云計算資源調度策略等[13]。但是單一機制的優化算法在處理較大數據量或較大用戶任務數時，難以得到有效的全局最優解，導致優化后的調度模型精度較差。因此本文提出一種改進獅群優化算法的云計算資源調度策略。

獅群優化算法是一類新的群智能優化算法，與傳統群智能優化算法不同，該算法本身具有較強的局部搜索能力，且可以在一定程度自調節算法全局收斂能力和局部收斂能力，算法調整參數較少，易于實現。但基本獅群優化算法全局收斂精度較差，常因較強的局部搜索能力導致算法在迭代后期早熟收斂，陷入局部最優。本文針對上述問題對傳統獅群算法進行改進，并將改進后的獅群優化算法優化云計算資源調度模型。

1 云計算資源調度模型

云計算在運算過程中，可利用的系統資源是有限的，并且云計算資源調度模型中的數據中心就是由有限個系統資源組成。計算機在接收用戶任務后，會將多個用戶任務同時在數據中心的多個節點上執行，因此在計算過程中，如何根據計算資源、計算能耗以及計算時間等因素為用戶任務合理分配系統資源是云計算資源調度模型優化的目標。針對上述問題，對云計算資源調度模型進行建模。

1) 定義用戶任務集合為TKs=[tk1,tk2,…,tks]，其中s為用戶所提交任務總數。

2) 定義云計算數據中心計算節點個數為m，則計算節點集合可定義為VNm=[vn1,vn2,…,vnm]，其中每個節點vnj(j=1,2,…,m)中包含多個屬性元素，例如CPU、RAM內存大小以及磁盤存儲空間等，屬性元素可根據計算要求進行增加或刪減。

3) 定義決策變量為di,j，其中i=1,2,…,s表示任務個數，j=1,2,…,m表示資源節點數。當di,j=1時，表示在第j個資源節點上執行第i個任務。當di,j=0時，表示在第j個資源節點上不執行第i個任務。因此構建決策矩陣為D=[di,j]。

4) 定義在第j個資源節點上執行第i個任務所需的時間花費為ei,j，則構建s個任務的時間花費矩陣為TimeCost=[ei,j]，其中i=1,2,…,s，j=1,2,…,m。

5) 定義在第j個資源節點上執行第i個任務所消耗的資源成本(CPU、內存等)為Cali,j，則構建s個任務的能源消耗成本矩陣為CalCost=[cali,j]，其中i=1,2,…,s，j=1,2,…,m。

云計算資源調度目標函數的建立應根據兩個判定標準。

1) 時間成本。在云計算過程中，應使執行完全部s個任務所需時間最短，降低時間成本。

2) 資源成本。在云計算過程中，會將多個用戶任務同時在數據中心的多個節點上執行，如計算資源分配不合理，會增加資源成本的浪費，降低計算效率。所以在建立云計算目標函數時，應盡可能降低資源成本。

因此云計算資源調度模型的目標函數如式(1)所示，目的是使綜合成本f的值最小。

(1)

式中:β01和β02為慣性權重。若β01較大，則在計算過程中更加側重計算時間花費；若β02較大，則在計算過程中更加側重計算資源成本的花費。但目的是使綜合成本最小。

2 獅群優化算法

獅群優化算法是模擬自然界獅群群體捕獵的一種新的群智能優化算法。首先，自然界中獅群在狩獵過程中會分為三個部分協作捕獵，分別為雄獅、母獅、幼獅。雄獅作為首領，占統治地位，主要負責保護領地以及與外來流浪獅等威脅作斗爭。母獅主要負責捕獵，幼獅通常跟隨母獅，協助母獅進行捕獵，長大后并對獅王的位置發起挑戰。因此，該算法中，首先對整個獅群個體的位置進行初始化：

Xi=(Xi,1,Xi,2,…,Xi,D)

(2)

式中：獅群的種群規模為NP，因此i=1,2,…,NP，維數為D。因此Xi表示第i個獅子所在位置。從上述可知，獅王、母獅以及幼獅的分工各不相同，其位置更新方式也各不相同，因此，成年獅(獅王和母獅)以及幼獅在種群中的數量比在很大程度上影響了算法的收斂性能。根據大量的實驗表明，成年獅所占比例越大，算法勘探能力越強，而幼獅數量越多，則種群多樣性越強。因此定義成年獅的占比為ξ，ξ∈[0,1]。

首先，獅王為了保證食物來源以及領地的安全性，其移動范圍一直保持在食物源附近，因此獅王的位置更新方式如下：

(3)

其次，母獅通常采用協同互助的方式捕獵，在尋找到食物源后，母獅會逐步縮小對食物源的包圍圈，這種行為可被描述為：

(4)

(5)

式中:max和min為獅群個體各維度的最大均值和最小均值；Tmax為最大迭代次數。

最后，幼獅按母獅和獅王的位置進行選擇性移動，其計算方式為：

(6)

3 改進獅群優化算法

3.1 混沌映射操作

在傳統獅群優化算法中，成年獅所占比ξ為[0,1]之間的隨機數。當ξ越大，算法的勘探能力越強；當ξ越小，算法的局部開發能力越強。因此ξ在優化過程中采用隨機化處理，一定程度上影響了算法的搜索能力。并且，若參數過于隨機化，會導致算法收斂速度降低，算法運行后期的搜索區域無效。

混沌現象是非線性系統中一種普遍的現象，它的變化過程看似混亂，實際上其內在具有規律性，能夠在一定范圍之內，按照自身規律不重復地遍歷所有狀態。混沌映射的行為復雜，類似隨機運動，但相對于隨機運動，它具有遍歷性的特點，能夠很好地彌補隨機運動的缺陷，實現全局最優。因此，在本文中，將混沌理論用于LSO，以提高LSO的搜索精度，并創造新的、不同的個體。

(a) 混沌映射后參數ξ的取值曲線

(b) 無混沌映射的參數ξ的取值曲線圖1 參數ξ取值對比圖

圖1(a)為無混沌映射處理的參數ξ的取值曲線。圖1(b)為在同一組隨機數下，按照式(7)的ξ的取值曲線。可以看出，在同一組隨機數下，原參數ξ的波動幅度較大，大大增加了優化過程中的不穩定性。在改進的參數調整中，減小了完全隨機的波動幅度，能使算法在小范圍內隨機波動，能夠提高LSO的局部搜索能力。

ξ=2rand2·sin(π·rand)

(7)

式中：rand為[0,1]之間的隨機數。利用混沌映射進行參數調整，增加了參數ξ的規律性，從而在避免搜索過程中陷入局部最優的基礎上，避免了隨機盲目搜索可能導致的收斂慢，搜索區域無效的問題。

3.2 周期性遞減控制因子

根據式(5)可知，控制因子αf在迭代過程中，非線性單周期減小。目的是使算法在迭代前期具有較高的全局搜索能力，在迭代后期擁有較高的局部搜索能力。但傳統LSO中，控制因子αf并不能滿足母獅在捕獵過程中，需要多次協調圍捕，最終完成狩獵的現象。

根據研究表明，算法在迭代過程中，全局搜索能力和局部搜索能力的大小應周期性多輪交替，保證算法在迭代前期，可以頻繁地轉變全局搜索能力和局部搜索能力的大小，但應更偏向全局搜索能力。在迭代后期，算法的全局勘探能力和局部開發能力之間的轉換速度應相應減小，且更應偏向局部開發能力。目的是保證算法在平衡全局勘探能力和局部開發能力的同時，避免算法在迭代后期因局部搜索能力過強導致算法陷入局部最優的情況。因此改進后的控制因子αf的數學表達式如下：

(8)

式中:K為算法全局搜索能力和局部搜索能力調節頻率。K越大，調節頻率越高；K越小，調節頻率越小。

3.3 模擬退火操作

(9)

式中:f(Xi)為飛蛾粒子在第i次迭代的適應度值；t為第i次迭代時的溫度。將LSO中的所有粒子的初始適應度最大值和最小值的差值定義為初始溫度，當f(Xi+1)>f(Xi)時，按概率P接受劣質解。將LSO與模擬退火算法結合后，將在LSO求解之后再進行退火處理，退火時會產生一個新的獅群種群并調整原種群位置，提高全局收斂精度。因此式(9)可修改為：

(10)

式中:fnew(Xi)是新種群第i個獅群個體的適應度，fold為原始種群第i個獅群個體的適應度。式(10)通過新舊位置適應度的差值調整接受概率P。

3.4 改進獅群優化算法優化流程

改進后的獅群優化算法可記為ILSO(Improved Lion Swarm Optimization, ILSO)。ILSO的優化過程如下：

Step1初始化獅群種群，包括種群S1的種群規模SN、最大迭代次數Tmax、維數D、調節頻率K。

Step2通過式(7)對成年獅占比ξ進行混沌映射處理，并對種群中全部個體進行位置初始化。

Step3計算獅群中全部個體的適應度值，并按適應度值的大小進行排序。

Step4通過式(3)對獅王的位置進行更新。

Step6通過式(6)對幼獅的位置進行更新。

Step7模擬退火處理。定義一個新的獅群種群S2并隨機初始化粒子位置，計算S2的適應度。

Step8若新種群S2中個體的適應度值優于種群S1中個體的適應度，則將兩個個體進行交換處理。否則，將有P概率接受S2中獅子個體的位置，并進行退火降溫處理：t=0.99×t。

Step9判斷是否達到最大迭代次數。是則輸出最優個體，即算法找到的最優解；否則返回Step3。

3.5 數值仿真實驗

為了驗證本文所提ILSO的優化性能，本文選取10個基準測試函數作為評價函數，對ILSO進行數值仿真驗證，并記錄結果的平均值和標準差。10個基準測試函數如表1所示。其中函數f1-f4為單峰測試函數，f5-f8為多峰測試函數，f9-f10為固定維數測試函數。

表1 10個基準測試函數

為了使實驗結果更加具有說服性，本文將ILSO的實驗結果與其他三種用于優化云計算資源調度模型的優化算法的實驗結果進行對比。對比算法分別為動態粒子群算法[5](DRDPSO)、改進蜂群優化算法[16](IABC)，以及改進蛙跳優化算法[17](ACO-SFLA)。為了保證算法的公平性，四種算法的種群規模均為50，最大迭代次數均為100，維數為100。DRDPSO中c1=c2=1，k1=k2=1，σ=0.7，μ1=4，μ2=1，εe=0.01，ετ=0.01。ACO-SFLA中A=1,B=5,τmax=0.000 9，τmin=0.000 1，r=5，t=0.5，r1=r2=0.3，r3=0.4，F1=F2=0.5。四種算法獨立運行30次，取其結果的平均值和標準差，具體實驗結果如表2所示，其中最優解用加粗字體表示。

表2 數值實驗對比結果

從表2中可得，對于單峰測試函數而言，ILSO取得的平均值明顯優于IABC算法、DRDPSO、ACO-SFLA。證明ILSO相較其他三種算法而言，整體尋優性能更優。這是由于周期性收斂控制因子很好地平衡了算法的全局收斂能力和局部開發能力，使得算法全局/局部搜索性能極為平均。此外，算法通過混沌映射對算法中成年獅占比進行合理分配，極大地豐富了種群多樣性。最后，ILSO取得的標準差同樣優于其他三種算法，說明ILSO具有較強的尋優穩定性，算法魯棒性更強。

對于多封測試函數而言，ILSO取得的平均值同樣優于其他三種算法，說明ILSO的全局收斂精度更強。同時對于測試函數f8而言，DRDPSO以及ACO-SFLA陷入局部最優，早熟收斂，IABC的收斂精度雖然同樣不高，但遠優于其他三種算法，說明ILSO跳出局部最優的概率遠大于其他三種算法，在迭代后期，ILSO依然具有較高的全局收斂能力。此外，對于多峰測試函數而言，ILSO取得的標準差同樣優于其他三種算法，說明在多次迭代過程中，ILSO的尋優穩定性極強，在陷入局部最優時，會通過模擬退火策略，有效幫助算法跳出局部最優。

對于固定維函數而言，四種算法的收斂精度均有很大程度的提高，且對于測試函數f9而言，ILSO以及ACO-SFLA可以取得理論最優解，這是由于測試函數維數較低，尋優復雜度不高的原因導致。但ILSO的標準差更小，說明ILSO的尋優穩定性更強。

為了驗證ILSO具有較強的整體尋優性能，本文通過Wilcoxon秩和檢驗分析了ILSO和其他三種算法在優化性能方面的差異性。在D=100時，在選定5%的顯著性水平下IABC、DRDPSO和ACO-SFLA所得的pvalue分別為0.032 7、0.049 7和0.010 9。

本文算法主要由混沌映射初始化、位置更新、模擬退火操作組成。設種群規模N為50，優化問題維度D為100時，ILSO的時間復雜度分析如下：種群混沌映射初始化的計算復雜度為O(2ND)，位置更新為O(3ND)，模擬退火操作為O(2N)。因此，ILSO的時間復雜度為O(N+5ND)。IABC算法、DRDPSO、ACO-SFLA的時間復雜度分別為O(N+2ND)、O(N2+2ND)、O(N2+ND)。根據大O的定義，ILSO時間復雜度的量級要略低于DRDPSO以及ACO-SFLA，與IABC算法的量級相同。

4 實驗仿真

本文將ILSO用于云計算資源調度模型優化，實驗所需仿真平臺為MATLAB 2014b，CPU為Inter Core i5-5200U，主頻為2.20 GHz。為了驗證ILSO可以有效優化云計算資源調度模型，本文分別針對小規模任務量和大規模任務量兩種情況進行優化實驗，并對比兩組實驗結果中資源調度所需的時間花費和能耗花費，對ILSO的整體優化性能進行驗證。

其中實驗參數和實驗過程如下所述：實驗過程中，以任務量為單一變量，小規模任務量設定為100，大規模任務量設定為25 000。四種算法的種群規模設定為50，最大迭代次數為100。經多次計算β01和β02分別為4和1時，實驗效果最佳。其余參數與3.5節所述一致。實驗過程如下：

Step1依照云計算資源調度問題對ILSO進行種群初始化。

Step2設定云計算資源調度方案初始解數目為50，因此ILSO的種群規模為50。

Step3以式(1)為目標函數，通過式(3)、式(4)和式(6)計算目標函數值，并更新最優解。

Step4判斷ILSO是否達到最大迭代次數，若達到最大迭代次數，則返回全局最優位置，否則跳轉到Step3繼續優化。

Step5輸出全局最優解，即為云計算資源調度的最優方案。

4.1 小規模任務性能對比

圖2和圖3分別為四種算法在小規模用戶任務下，對云計算資源調度模型優化所得時間花費和能源花費的實驗對比結果，其云計算資源數量為30。

圖2 四種算法完成時間對比圖

圖3 四種算法能量消耗對比圖

首先對于時間花費而言，ILSO所需時間最短，僅為IABC算法的60%。說明ILSO具有較強的收斂速度以及收斂精度。很大程度降低了計算時間，提高了計算效率。其次，對于能源消耗而言，IABC算法、DRDPSO以及ACO-SFLA的消耗曲線隨任務量增加，波動較大，但ILSO的能源消耗曲線上升坡度較為平緩，波動不大。此外，ILSO的能源消耗僅為22.7 kNJ，遠低于其他三種優化策略所消耗的能源花費。說明ILSO相較其他三種算法而言，可以更加有效地分配資源節點，合理地對每個節點分配計算任務，尋優穩定性更強。

4.2 大規模任務性能對比

圖4和圖5分別為四種算法在大規模用戶任務下，對云計算資源調度模型優化所得時間花費和能源花費的實驗對比結果，其云計算資源數量為60。

圖4 四種算法完成時間對比圖

圖5 四種算法能量消耗對比圖

從圖中可得，ILSO在時間花費和能耗花費上的優化結果均優于其他三種優化算法的優化結果。此外，隨任務量的急劇增加，四種算法的時間花費曲線和能耗花費曲線的上升趨勢均較為明顯，但ILSO的曲線斜率要更低于其他三種算法，說明ILSO相較其他三種算法而言，更加適合用于具有大規模用戶任務量的云計算資源調度優化，這是由于ILSO的全局勘探能力和局部開發能力較為平衡，在處理具有復雜性、多約束性等特性的數學問題上，算法整體收斂性能更優，收斂精度更高，不會出現早熟收斂的問題。

4.3 負載均衡對比

為了更加突出ILSO的高效性，將四種算法進行負載均衡對比實驗。實驗中，客戶任務數量為5 000，資源節點個數為5，分別為s1、s2、s3、s4和s5，每個節點的處理能力為{100,300,500,600,700}。實驗結果如圖6所示。

圖6 四種算法負載均衡對比圖

由于5個資源點處理能力各不相同，導致每個節點的負載也各不相同。從圖6中可得，ILSO的負載均衡度遠優于其他三種算法，對于節點s2而言，ACO-SFLA所分配給節點的任務數遠大于節點最大處理任務數量，導致處理能力較差的資源節點獲得了較大的任務量。對于節點s5而言，IABC算法所分配給節點的任務數遠少于節點最大處理任務數量，導致處理能力較強的節點，獲得的任務量較少，極大地浪費了計算資源。因此，ILSO相較其他三種算法，對于云計算中的資源分配更加均衡、合理，很大程度提高了計算效率。

5 結 語

針對云計算資源調度不平衡，導致時間成本以及能量成本過度消耗的問題，本文提出一種改進的獅群優化算法，對云計算資源調度問題進行優化。首先，針對傳統獅群優化算法全局收斂精度低以及算法在迭代后期易早熟收斂陷入局部最優的問題，通過混沌映射、周期性遞減控制因子以及模擬退火策略進行改進。其次通過數值仿真實驗，對改進后的獅群優化算法進行對比驗證，結果表明，ILSO的整體性能有很大程度提高，收斂精度更高。最后，將ILSO用于云計算資源調度模型優化實驗，實驗結果表明，ILSO優化后的資源調度模型，很大程度降低了計算過程中的時間成本和能源消耗成本，提高了資源利用率。