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

（1.華北計(jì)算技術(shù)研究所，北京 100083；2.中國(guó)電子科技集團(tuán)有限公司，北京 100846）

云計(jì)算是一種基于互聯(lián)網(wǎng)的計(jì)算方式，是在虛擬化計(jì)算和分布式計(jì)算的基礎(chǔ)上發(fā)展而來(lái)的[1]。資源調(diào)度是云計(jì)算中的一個(gè)重要環(huán)節(jié)，具體來(lái)說(shuō)就是根據(jù)云計(jì)算環(huán)境中的任務(wù)數(shù)量和資源情況，將任務(wù)分配到對(duì)應(yīng)資源上并執(zhí)行的過(guò)程[2]。

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

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

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

1.1 算法思想

金豺優(yōu)化算法模擬了金豺合作狩獵的行為，通過(guò)獵物位置的更新來(lái)實(shí)現(xiàn)算法的尋優(yōu)過(guò)程。在金豺優(yōu)化算法中，獵物種群的初始位置在全局搜索空間上隨機(jī)產(chǎn)生。將每次獵物種群位置變更后處于最優(yōu)位置的個(gè)體作為雄性金豺，處于次優(yōu)位置的個(gè)體作為雌性金豺，并利用金豺夫婦的位置對(duì)獵物種群的位置進(jìn)行變更。也就是說(shuō)，在金豺優(yōu)化算法中，金豺?qū)κ谦C物的一部分。

算法根據(jù)獵物的能量來(lái)劃分金豺搜索、包圍和攻擊獵物的過(guò)程。當(dāng)獵物能量較高時(shí)，金豺搜索獵物的過(guò)程由雄性金豺帶領(lǐng)，雌性金豺跟隨。當(dāng)獵物的能量低于某個(gè)閾值之后，金豺夫婦會(huì)包圍并攻擊獵物。

1.2 算法設(shè)計(jì)

1.2.1 種群位置初始化

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

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

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

1.2.2 確定雌雄金豺?qū)ξ恢?/p>

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

1.2.3 搜索獵物階段

在搜索獵物階段，雄性金豺?qū)τ讷C物種群中每個(gè)個(gè)體的相對(duì)位置如下：

雌性金豺?qū)τ讷C物種群中每個(gè)個(gè)體的相對(duì)位置如下：

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

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

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

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

其中，u和v均為[0,1]內(nèi)的隨機(jī)值，β為常數(shù)，設(shè)為1.5。

1.2.4 包圍攻擊獵物階段

在包圍攻擊獵物階段，雄性金豺?qū)τ讷C物種群中每個(gè)個(gè)體的相對(duì)位置如下：

雌性金豺?qū)τ讷C物種群中每個(gè)個(gè)體的相對(duì)位置如下：

1.2.5 獵物種群位置變更

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

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

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

2.1 基本概念

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

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

2.2 數(shù)學(xué)模型

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

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

在對(duì)任務(wù)分配完成后，每個(gè)虛擬機(jī)的執(zhí)行總時(shí)間為：

式（11）中的j為在第i個(gè)虛擬機(jī)上執(zhí)行任務(wù)的編號(hào)集合。

實(shí)驗(yàn)是單目標(biāo)優(yōu)化，目標(biāo)為減少云計(jì)算任務(wù)的執(zhí)行總時(shí)間，故適應(yīng)度函數(shù)應(yīng)設(shè)置為執(zhí)行總時(shí)間最長(zhǎng)的虛擬機(jī)的執(zhí)行時(shí)間的倒數(shù)：

3 仿真過(guò)程及結(jié)果

3.1 實(shí)驗(yàn)配置

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

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

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

3.2 實(shí)驗(yàn)流程

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

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

3.3 GJO迭代次數(shù)實(shí)驗(yàn)

設(shè)置參加仿真的任務(wù)為1-1 000 號(hào)的1 000 個(gè)任務(wù)，設(shè)置參加仿真的虛擬機(jī)為1-10 號(hào)的10 臺(tái)虛擬機(jī)，設(shè)置金豺優(yōu)化算法的迭代次數(shù)分別為20、40、60、80、100、120、140、160、180、200，僅使用金豺優(yōu)化算法參與仿真實(shí)驗(yàn)，得到圖1 所示的實(shí)驗(yàn)結(jié)果。

圖1 GJO在不同迭代次數(shù)下的實(shí)驗(yàn)結(jié)果

由圖1 中的實(shí)驗(yàn)結(jié)果可知，金豺優(yōu)化算法的效果在迭代次數(shù)小于100 時(shí)會(huì)隨著迭代次數(shù)增加而優(yōu)化，在迭代次數(shù)大于100 時(shí)隨著迭代次數(shù)增加并無(wú)明顯優(yōu)化，即可以認(rèn)為100 為金豺優(yōu)化算法在云計(jì)算資源調(diào)度模型下以任務(wù)完成總時(shí)間為優(yōu)化目標(biāo)的較優(yōu)迭代次數(shù)。

3.4 三種算法不同任務(wù)數(shù)量下的實(shí)驗(yàn)

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

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

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

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

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

3.5 三種算法不同虛擬機(jī)數(shù)量下的實(shí)驗(yàn)

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

圖4 不同虛擬機(jī)數(shù)量下三種算法仿真結(jié)果

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

4 結(jié)論

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