基于金豺優(yōu)化算法的云計算資源調度研究

李偉彥，董寶良，王 凱，廉蘭平

（1.華北計算技術研究所，北京 100083；2.中國電子科技集團有限公司，北京 100846）

云計算是一種基于互聯(lián)網的計算方式，是在虛擬化計算和分布式計算的基礎上發(fā)展而來的[1]。資源調度是云計算中的一個重要環(huán)節(jié)，具體來說就是根據云計算環(huán)境中的任務數量和資源情況，將任務分配到對應資源上并執(zhí)行的過程[2]。

執(zhí)行時間短、資源集群負載均衡一直是云計算資源調度問題中不斷追求的目標[3]。為了優(yōu)化云計算資源調度策略，國內外學者將傳統(tǒng)算法和智能優(yōu)化算法廣泛應用于這一問題[4]，傳統(tǒng)算法的代表如貪心算法[5]，較為經典的智能優(yōu)化算法則有遺傳算法[6]等，但這些算法并不是完全適配于云計算資源調度模型[7]。

金豺優(yōu)化算法由Nitish Chopra 和Muhammad Mohsin Ansari 于2022 年提出，是一種模擬金豺合作狩獵提出來的群體智能優(yōu)化算法[8]。金豺優(yōu)化算法的優(yōu)點是收斂速度快且收斂精度高，局限性是目前僅能應用于單目標優(yōu)化。實驗將該算法應用于云計算資源調度策略的單目標優(yōu)化。

1 金豺優(yōu)化算法介紹

1.1 算法思想

金豺優(yōu)化算法模擬了金豺合作狩獵的行為，通過獵物位置的更新來實現算法的尋優(yōu)過程。在金豺優(yōu)化算法中，獵物種群的初始位置在全局搜索空間上隨機產生。將每次獵物種群位置變更后處于最優(yōu)位置的個體作為雄性金豺，處于次優(yōu)位置的個體作為雌性金豺，并利用金豺夫婦的位置對獵物種群的位置進行變更。也就是說，在金豺優(yōu)化算法中，金豺對是獵物的一部分。

算法根據獵物的能量來劃分金豺搜索、包圍和攻擊獵物的過程。當獵物能量較高時，金豺搜索獵物的過程由雄性金豺帶領，雌性金豺跟隨。當獵物的能量低于某個閾值之后，金豺夫婦會包圍并攻擊獵物。

1.2 算法設計

1.2.1 種群位置初始化

每一只獵物的位置隨機分布在搜索空間上：

其中，Xi,j表示第i只獵物在第j維空間的位置，Xj,max和Xj,min分別表示第j維空間的上邊界和下邊界，random()為[0,1]內的隨機數。最終形成的獵物種群位置矩陣如下：

其中，m為獵物種群的大小，n為搜索空間的總維度。

1.2.2 確定雌雄金豺對位置

根據獵物種群位置矩陣以及特定的適應度函數計算適應度矩陣，位置具有最優(yōu)適應度的獵物記為雄性金豺，位置記為XM，適應度記為fM；位置具有次優(yōu)適應度的記為雌性金豺，位置記為XFM，適應度記為fFM。

1.2.3 搜索獵物階段

在搜索獵物階段，雄性金豺對于獵物種群中每個個體的相對位置如下：

雌性金豺對于獵物種群中每個個體的相對位置如下：

其中，t為當前迭代的次數，Xi(t)表示第t次迭代時第i個獵物的位置，YM(t)表示第t次迭代時雄性金豺的位置，YFM(t)表示第t次迭代時雌性金豺的位置。E為逃跑能量，計算公式如下：

其中，E0為初始逃跑能量；E1為一個系數，用來遞減逃跑能量E；T為總迭代次數；C1為常數，取值為1.5。E1隨著迭代次數的變化，由1.5 逐漸減小至0；E0為[-1,1]內的隨機值。

作者對E0的取值方式和對式（4）、（5）兩式的設計參考了哈里斯鷹優(yōu)化算法。

式（3）、（4）中的rl表示一個m×n維的基于levy分布的隨機向量，其公式如下：

其中，u和v均為[0,1]內的隨機值，β為常數，設為1.5。

1.2.4 包圍攻擊獵物階段

在包圍攻擊獵物階段，雄性金豺對于獵物種群中每個個體的相對位置如下：

雌性金豺對于獵物種群中每個個體的相對位置如下：

1.2.5 獵物種群位置變更

在金豺優(yōu)化算法中，金豺對搜索獵物階段和包圍攻擊獵物階段，獵物種群位置變更所使用的公式相同，如下：

其中，Xi(t+1)表示第t+1 次迭代，即下一次迭代時第i個獵物的位置。

2 云計算資源調度模型

2.1 基本概念

Map/Reduce 分布式處理框架是當前云計算的關鍵技術之一，主要用于云計算中對大數據的處理[9]。Map/Reduce 的核心思想是將龐大的任務分割成若干個簡單的任務，分別在不同的處理機上執(zhí)行，最終對分布式處理的結果進行匯總[10]。

在基于Map/Reduce 思想的云計算資源調度模型中，由數據中心生成虛擬任務集，再由調度中心通過算法對任務集進行調度，分配至各虛擬機節(jié)點執(zhí)行，即Map/Recude“分而治之”的思想[11]。而對調度算法優(yōu)化的目標，一般是針對所有任務執(zhí)行結果的全局目標，即Map/Reduce分布式處理框架中“合”的思想[12]。

2.2 數學模型

設虛擬機用戶節(jié)點共有n個，分別用Vi表示每個虛擬機的處理能力，構成集合V={V1,V2,…,Vn}，單位為MIPS。由數據中心生成m個任務，分別用Ti表示每個任務的指令數，構成集合T={T1,T2,…,Tm} 。則第j(1 ≤j≤m) 個任務在第i(1 ≤i≤n) 個虛擬機上處理的時間為：

式中，t的單位為微秒(μs)。

在對任務分配完成后，每個虛擬機的執(zhí)行總時間為：

式（11）中的j為在第i個虛擬機上執(zhí)行任務的編號集合。

實驗是單目標優(yōu)化，目標為減少云計算任務的執(zhí)行總時間，故適應度函數應設置為執(zhí)行總時間最長的虛擬機的執(zhí)行時間的倒數：

3 仿真過程及結果

3.1 實驗配置

文中實驗基于Cloudsim仿真環(huán)境[13]。利用Python產生[100,999]內的整數共100 個，作為100 個虛擬機的執(zhí)行能力；利用Python 產生[10 000,99 999]內的整數共10 000 個，作為10 000 個任務的大小。

將貪心算法、遺傳算法和金豺優(yōu)化算法分別在Datacenter Broker 類中實現[14]。設置遺傳算法的參數如下:種群大小為20，迭代次數為50，交叉概率為0.8，變異概率為0.01，這是遺傳算法在云計算資源調度模型下以任務總完成時間為優(yōu)化目標的實驗結果較好的參數配置[15]。

在金豺優(yōu)化算法中，將獵物位置類比為所有任務對虛擬機的選擇序列，在每次獵物位置變更后對獵物位置都進行四舍五入取整操作，并對超出搜索空間范圍的獵物位置進行修正，將獵物的種群規(guī)模設置為40。

3.2 實驗流程

首先，在不同迭代次數、相同虛擬機個數以及相同任務個數下調度金豺優(yōu)化算法進行實驗，求得金豺優(yōu)化算法在云計算資源調度模型下以任務完成總時間為優(yōu)化目標的最優(yōu)迭代次數。然后，對金豺優(yōu)化算法使用最優(yōu)迭代次數，在不同虛擬機個數和任務個數的條件下對三個算法分別進行調度，分別做10 次重復實驗，結果取10 次實驗的平均值[16]。對比實驗數據，判斷金豺優(yōu)化算法相較于其他算法所適用的數據規(guī)模。

在實際實驗過程中，發(fā)現原本的金豺優(yōu)化算法的實驗效果不佳，于是調整了式（6）的參數，并取得了較好的實驗效果[17]。下文所有基于金豺優(yōu)化算法的實驗數據均是調整參數后的實驗結果。

3.3 GJO迭代次數實驗

設置參加仿真的任務為1-1 000 號的1 000 個任務，設置參加仿真的虛擬機為1-10 號的10 臺虛擬機，設置金豺優(yōu)化算法的迭代次數分別為20、40、60、80、100、120、140、160、180、200，僅使用金豺優(yōu)化算法參與仿真實驗，得到圖1 所示的實驗結果。

圖1 GJO在不同迭代次數下的實驗結果

由圖1 中的實驗結果可知，金豺優(yōu)化算法的效果在迭代次數小于100 時會隨著迭代次數增加而優(yōu)化，在迭代次數大于100 時隨著迭代次數增加并無明顯優(yōu)化，即可以認為100 為金豺優(yōu)化算法在云計算資源調度模型下以任務完成總時間為優(yōu)化目標的較優(yōu)迭代次數。

3.4 三種算法不同任務數量下的實驗

設置參加仿真的虛擬機為1-10 號的10 臺虛擬機，設置金豺優(yōu)化算法的迭代次數為100，先取前20、40、60、80、100、120、140、160、180、200 個任務參與實驗，再取前1 000、2 000、3 000、4 000、5 000、6 000、7 000、8 000、9 000、10 000 個任務參與實驗，分別代表小數據規(guī)模和大數據規(guī)模下的仿真，同時使用貪心算法、遺傳算法和金豺優(yōu)化算法進行仿真實驗，得到圖2 和圖3 所示的實驗結果。

圖2 小數據規(guī)模下三種算法仿真結果

圖3 大數據規(guī)模下三種算法仿真結果

由圖2 中的實驗結果可知：1）在任務數量為20時，金豺優(yōu)化算法在資源調度時的效果是最差的；2）當數據量逐漸增大時，金豺優(yōu)化算法在資源調度時的效果逐漸變好，但在任務數量小于80 時效果仍不明顯；3）在任務量達到200 左右時，金豺優(yōu)化算法的效果已完全優(yōu)于貪心算法，但對于遺傳算法的優(yōu)越性仍不明顯。

由圖3 中的實驗結果可知：1）在任務數量大于1 000 時，貪心算法相較于其他兩種算法效率較低；2）金豺優(yōu)化算法相較于遺傳算法的優(yōu)勢逐漸明顯，且優(yōu)化程度趨于穩(wěn)定；3）在數據量足夠大時，金豺優(yōu)化算法相對于遺傳算法對云計算任務執(zhí)行的效率提高了約20%。

3.5 三種算法不同虛擬機數量下的實驗

設置參加仿真的任務為1-1 000 號的1 000 個任務，設置金豺優(yōu)化算法的迭代次數為100，分別取前10、20、30、40、50、60、70、80、90、100 臺虛擬機參與實驗，同時使用貪心算法、遺傳算法和金豺優(yōu)化算法進行仿真實驗，得到圖4 所示的實驗結果。

圖4 不同虛擬機數量下三種算法仿真結果

由圖4 中的實驗結果可知：1）虛擬機個數對三種算法的仿真結果有很大影響；2）在虛擬機個數相對較少，即單個虛擬機分配云計算任務個數相對較多時，金豺優(yōu)化算法的優(yōu)勢更明顯。

4 結論

針對云計算環(huán)境下資源分配不均的問題，以任務總完成時間為優(yōu)化指標，可以簡單直接地提升資源利用效率，使任務得到及時處理。金豺優(yōu)化算法是一種單目標優(yōu)化算法，在云計算資源調度實驗場景下，以大規(guī)模任務為前提，設置特定迭代次數，以任務總完成時間為優(yōu)化指標，金豺優(yōu)化算法相較于其他很多算法實驗效果更好。綜上，金豺優(yōu)化算法對真實的云計算資源調度場景具有很高的實際應用價值。