基于改進(jìn)鯨魚優(yōu)化算法的資源調(diào)度策略＊

余隆勇

(浙江理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 330018)

0 引言

群智能算法[1]自提出以來(lái)被廣泛應(yīng)用于解決各種生活和科學(xué)研究問(wèn)題，如資源調(diào)度、路徑規(guī)劃、最優(yōu)策略等。它通過(guò)模擬種群中動(dòng)物習(xí)性，通過(guò)單個(gè)個(gè)體的行為與群體的合作和組織，表現(xiàn)出群體智能行為的特征，使用隨機(jī)搜索方式來(lái)獲取算法最優(yōu)解。但隨著隨著信息化的深入發(fā)展，越來(lái)越多的應(yīng)用和任務(wù)部署在云端從而導(dǎo)致了傳統(tǒng)群智能算法不能有效快速地解決資源分配問(wèn)題。因此許多學(xué)者通過(guò)將群智能算法進(jìn)行改進(jìn)并運(yùn)用到資源調(diào)度中，如Wu Daqin[2]針對(duì)目前粒子群算法性能低效，提出一種通過(guò)引入迭代選擇算子的改進(jìn)粒子群算法并進(jìn)行實(shí)驗(yàn)，結(jié)果表明改進(jìn)后的算法可以提高優(yōu)化能力，盡可能避免陷入局部最優(yōu)，具有較好的收斂效果。孟凡超[3]等人針對(duì)云數(shù)據(jù)中心虛擬機(jī)分配存在的不均衡問(wèn)題，參考用戶對(duì)虛擬機(jī)資源需求，避免在同一臺(tái)虛擬機(jī)上部署，提出了一種蟻群優(yōu)化算法的資源調(diào)度策略，并通過(guò)實(shí)驗(yàn)證明該算法能夠快速完成虛擬機(jī)的放置并讓數(shù)據(jù)中心的虛擬機(jī)具有較低的負(fù)載不均衡度，提高資源利用率。李勛章[4]等人針對(duì)遺傳算法在資源調(diào)度中存在收斂速度過(guò)快以及陷入局部最優(yōu)解等問(wèn)題，利用多優(yōu)選保留技術(shù)選取適應(yīng)度值較大的個(gè)體放入種群，通過(guò)與普通個(gè)體進(jìn)行雜交從而使種群往更優(yōu)的方向不斷進(jìn)化，以此保證種群多樣性以及避免陷入局部最優(yōu)解的作用。程曦[5]針對(duì)云計(jì)算資源調(diào)度優(yōu)化問(wèn)題，提出改進(jìn)布谷鳥的隨機(jī)搜索策略和丟棄概率策略，來(lái)提高算法的局部搜索能力和收斂速度，并在解決云資源調(diào)度的多目標(biāo)問(wèn)題針對(duì)減少延遲，提高資源利用率和服務(wù)質(zhì)量取得很好的效果。

針對(duì)傳統(tǒng)鯨魚算法[6]在資源調(diào)度上存在的問(wèn)題，提出一種改進(jìn)的鯨魚優(yōu)化算法，該算法通過(guò)對(duì)傳統(tǒng)鯨魚算法的三個(gè)階段進(jìn)行優(yōu)化，首先通過(guò)非線性變量結(jié)構(gòu)的包圍階段和基于平均最優(yōu)解(Average Optimal Solution)的螺旋位置變化，提高了算法的局部?jī)?yōu)化能力和收斂速度；提出自適應(yīng)加權(quán)[7]搜索捕食策略來(lái)提高算法全局最優(yōu)解的速度和精度。

1 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法（Whale Optimization Algorithm,WOA）作為一種群智能算法，主要模擬座頭鯨的捕食行為，并將捕食行為分為了包圍獵物、螺旋氣泡捕食以及搜索獵物三個(gè)階段。

1.1 包圍獵物階段

鯨魚在收縮包圍階段是通過(guò)向當(dāng)前適應(yīng)度最優(yōu)的個(gè)體進(jìn)行靠攏來(lái)更新位置。其余鯨魚個(gè)體也通過(guò)這種方式來(lái)實(shí)現(xiàn)對(duì)獵物的包圍。包圍階段位置更新公式如下：

1.2 螺旋氣泡捕食階段

螺旋氣泡捕食作為鯨魚獵食行為中進(jìn)行局部搜索的另一個(gè)階段，它通過(guò)一個(gè)螺旋式游動(dòng)來(lái)對(duì)食物進(jìn)行抓捕。螺旋捕食的更新公式如下：

其中，b 用來(lái)定義螺旋形狀，通常取值為常數(shù)1；l是[-1,1]之間均勻分布的隨機(jī)數(shù)。包圍階段和螺旋氣泡捕食階段同作為鯨魚算法的局部搜索階段，在標(biāo)準(zhǔn)的鯨魚算法中采用相同的概率P 來(lái)決定采用哪種策略進(jìn)行位置的更新。具體更新公式如下：

1.3 搜索獵物階段

搜索捕食是鯨魚算法在避免陷入局部最優(yōu)、求得最優(yōu)解的一個(gè)階段。在尋找最優(yōu)的行為中，它主要通過(guò)隨機(jī)搜索來(lái)進(jìn)行鯨魚獵食的位置更新。具體模型如下：

2 改進(jìn)鯨魚優(yōu)化算法

2.1 基于自適應(yīng)權(quán)重的搜索捕食

傳統(tǒng)的WOA 算法通過(guò)A的取值來(lái)控制當(dāng)前鯨魚個(gè)體是否進(jìn)入搜索捕食階段，因此當(dāng)A越大時(shí)可以使鯨魚個(gè)體保持更佳的探索能力。或者A較小時(shí)采用包圍策略時(shí)能夠?qū)崿F(xiàn)較高精度的求解，擁有更好的局部尋優(yōu)能力。因此本文針對(duì)上述情況提出了一種基于自適應(yīng)權(quán)重的方式來(lái)控制鯨魚對(duì)策略的選取，對(duì)式⑺具體的改進(jìn)如下：

其中，EMBED Equation.DSMT4是改進(jìn)自適應(yīng)搜索捕食中的控制系數(shù)，它根據(jù)當(dāng)前迭代次數(shù)t以及改進(jìn)后的正弦公式來(lái)進(jìn)行下一次迭代的位置更新。

2.2 非線性變化的包圍策略

在收縮和環(huán)繞階段，通過(guò)計(jì)算每頭鯨的適應(yīng)度值獲得當(dāng)前最優(yōu)解，并根據(jù)當(dāng)前最優(yōu)解迭代和逼近剩余的個(gè)體鯨，具體的位置更新公式如式⑴、式⑵。由式⑶中的a可以得知，鯨魚算法在進(jìn)行包圍行為的過(guò)程中是一種線性變化的策略，線性變化結(jié)構(gòu)在算法的迭代過(guò)程容器造成趨近于局部最優(yōu)解、收斂速度過(guò)快等情況。因此本文針對(duì)包圍階段提出一種非線性變化包圍策略來(lái)控制算法的收斂速度。具體更新公式為：

其中，更新后的a公式是一個(gè)余弦函數(shù)，它可以通過(guò)控制算法在迭代的前中后期實(shí)現(xiàn)非線性的變化。r1、r2是0 至1 的隨機(jī)控制系數(shù)、Tmax是最大迭代次數(shù)。在更新后的公式中，鯨魚收斂速度隨著迭代次數(shù)的增加是越來(lái)越快的，但是在后期會(huì)減緩來(lái)保證算法的收斂能力從而更好的求最優(yōu)解、減少收斂時(shí)間。

2.3 基于AOS的螺旋位置變更

鯨魚的捕食路徑是一種螺旋狀，鯨魚個(gè)體可能會(huì)向最優(yōu)個(gè)體靠攏來(lái)進(jìn)行位置的更新，這種單一的更新方式很容易導(dǎo)致陷入局部最優(yōu)解問(wèn)題，當(dāng)其余鯨魚個(gè)體也向當(dāng)次迭代最優(yōu)解靠攏時(shí)，就容易導(dǎo)致所有個(gè)體產(chǎn)生局部最優(yōu)解。在該階段本文通過(guò)借鑒灰狼算法[9]思想，提出基于AOS（Average Optimal Solution）的螺旋位置變更策略。具體的公式為：

其中，ω1、ω2、ω3為[0,1]的隨機(jī)數(shù)且總和為為當(dāng)前種群中最優(yōu)的三個(gè)鯨魚個(gè)體。通過(guò)不同的變更系數(shù)ω與其對(duì)應(yīng)的最優(yōu)個(gè)體向量的成積和來(lái)進(jìn)行鯨魚個(gè)體的螺旋位置更新。該算法采用三個(gè)最優(yōu)個(gè)體的組合作為更新策略，保證了求解過(guò)程中收斂速度不會(huì)過(guò)快，增加了鯨魚種群的多樣性，避免了基于單個(gè)最優(yōu)個(gè)體的位置更新陷入局部最優(yōu)解的問(wèn)題。改進(jìn)位置公式如下：

2.4 WOA-3改進(jìn)算法具體流程設(shè)計(jì)

改進(jìn)后的WOA-3 算法在搜索捕食階段中，將每一個(gè)鯨魚個(gè)體當(dāng)作一個(gè)具體的解，根據(jù)每一次迭代的結(jié)果對(duì)鯨魚個(gè)體進(jìn)行評(píng)估，在達(dá)到最大迭代次數(shù)時(shí)將在當(dāng)前最大迭代次數(shù)中的最優(yōu)鯨魚個(gè)體視為算法的全局最優(yōu)解。具體步驟如下。

⑴初始化鯨魚種群：種群規(guī)模大小n,為每個(gè)鯨魚個(gè)體隨機(jī)生成初始位置，螺旋位置更新系數(shù)ω1、ω2、ω3，最大迭代次數(shù)Tmax，參數(shù)a、A、C、r1、r2、P等。

⑶進(jìn)入迭代，更新參數(shù)參數(shù)a、A、C、r1、r2、P。根據(jù)當(dāng)前迭代結(jié)果計(jì)算每個(gè)鯨魚的適應(yīng)度值并進(jìn)行排序，得出當(dāng)前迭代中前三個(gè)最優(yōu)解以及

⑷當(dāng)P>0.5 且A>1 時(shí)，選擇公式⑽，采用隨機(jī)一個(gè)用來(lái)進(jìn)行鯨魚的位置更新；當(dāng)P ≤0.5且A>1時(shí)，算法通過(guò)公式⒂進(jìn)行鯨魚個(gè)體的位置更新。

⑸當(dāng)P >0.5 通過(guò)公式⒃確定鯨魚個(gè)體的位置更新。

⑹根據(jù)2-5 過(guò)程更新當(dāng)前迭代的種群適應(yīng)度值并重新排序，更新當(dāng)前解以及

⑺如果當(dāng)前個(gè)體的最新解優(yōu)于上次迭代的值，則進(jìn)行更新。

⑻如果當(dāng)前迭代次數(shù)達(dá)到最大值Tmax，輸出當(dāng)前鯨魚最優(yōu)解；未達(dá)到最大迭代次數(shù)，跳回步驟⑵。

3 仿真實(shí)驗(yàn)與結(jié)果

3.1 改進(jìn)鯨魚優(yōu)化算法性能實(shí)驗(yàn)

為了驗(yàn)證本文提出的改進(jìn)鯨魚優(yōu)化算法[10]性能，我們將選取WOA、POS、GSA 和本文改進(jìn)的WOA-3對(duì)四個(gè)測(cè)試函數(shù)在Matlab 進(jìn)行實(shí)驗(yàn)，具體函數(shù)如表1所示。得到對(duì)應(yīng)的最優(yōu)解、平均解和標(biāo)準(zhǔn)差，如表2所示。

表1 測(cè)試函數(shù)

表2 測(cè)試函數(shù)結(jié)果

由表2可知，標(biāo)準(zhǔn)WOA算法在四個(gè)函數(shù)測(cè)試的最優(yōu)解、平均值以及標(biāo)準(zhǔn)差在大多數(shù)情況下都是優(yōu)于PSO 和GWO 算法的，但是改進(jìn)的WOA-3算法在這些結(jié)果中相比于WOA 算法，除了在f4 函數(shù)的結(jié)果存在略微偏差，其余函數(shù)的計(jì)算精度均有著明顯的提高。為了能夠表明改進(jìn)算法的作用，本次實(shí)驗(yàn)還將各算法在這四個(gè)測(cè)試函數(shù)中的收斂情況進(jìn)行對(duì)比，結(jié)果顯示，WOA 算法比PSO 和GWO 算法有更好的收斂性，改進(jìn)的WOA-3 算法比WOA 算法有更好的收斂速度和求解精度，具體如圖1～圖4所示。

圖1 F1函數(shù)

圖2 F2函數(shù)

圖3 F3函數(shù)

圖4 F4函數(shù)

3.2 資源調(diào)度仿真實(shí)驗(yàn)驗(yàn)證

3.2.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證改進(jìn)的WOA-3 算法在資源調(diào)度中的性能，本文通過(guò)CloudSim[8]平臺(tái)模擬在Kubernetes 集群上進(jìn)行資源調(diào)度的實(shí)驗(yàn)。集群主要包括一個(gè)主節(jié)點(diǎn)Master 和四個(gè)Node 節(jié)點(diǎn)，并使用十個(gè)Pod 任務(wù)進(jìn)行測(cè)試。Master 節(jié)點(diǎn)用于實(shí)現(xiàn)資源調(diào)度、監(jiān)控等功能，而Node 節(jié)點(diǎn)則是真正用來(lái)處理Pod 任務(wù)請(qǐng)求的工作節(jié)點(diǎn)。具體配置如表3和表4所示。

表3 實(shí)驗(yàn)配置信息

表4 Pod請(qǐng)求資源量

3.2.2 實(shí)驗(yàn)結(jié)果與分析

在本文中，為了驗(yàn)證WOA-3 算法在資源調(diào)度上的性能將其與WOA、PSO 以及Kubernetes 的默認(rèn)調(diào)度算法在資源調(diào)度性能進(jìn)行對(duì)比。相比于Kubernetes的默認(rèn)性能評(píng)價(jià)因子CPU 和內(nèi)存，在實(shí)際的應(yīng)用場(chǎng)景中任務(wù)的調(diào)度還需要考慮到對(duì)網(wǎng)絡(luò)寬帶的訪問(wèn)和磁盤的讀寫需求，所以在本次實(shí)驗(yàn)中額外添加了磁盤和網(wǎng)絡(luò)兩個(gè)性能指標(biāo)。從圖5～圖8 可以看出，相比于PSO和默認(rèn)資源調(diào)度算法相比，WOA 算法得到了改進(jìn)，但改進(jìn)后的WOA-3 算法可以使資源負(fù)載更加均衡，資源利用率高于WOA 算法。由此說(shuō)明，改進(jìn)的WOA-3算法在進(jìn)行資源調(diào)度時(shí)能夠讓各節(jié)點(diǎn)的利用率更好，使負(fù)載更加均衡。

圖5 Node1節(jié)點(diǎn)

圖6 Node2節(jié)點(diǎn)

圖7 Node3節(jié)點(diǎn)

圖8 Node4節(jié)點(diǎn)

4 結(jié)束語(yǔ)

針對(duì)鯨魚算法在資源調(diào)度中容易出現(xiàn)收斂速度慢，陷入局部最優(yōu)解等問(wèn)題，提出一種改進(jìn)的WOA-3算法。WOA-3 算法主要是針對(duì)鯨魚獵食三個(gè)階段分別進(jìn)行改進(jìn)，通過(guò)改進(jìn)非線性變化結(jié)構(gòu)的包圍策略以及基于AOS 策略改變螺旋更變位置，來(lái)加快鯨魚算法的局部收斂速度；同時(shí)，通過(guò)提出自適應(yīng)加權(quán)捕食策略來(lái)提高鯨魚算法的全局尋優(yōu)能力和收斂能力。在算法性能仿真實(shí)驗(yàn)中驗(yàn)證了算法的收斂性和優(yōu)化能力，改進(jìn)的WOA-3 算法相比于傳統(tǒng)的WOA、PSO 和GWO 算法，都有更好的收斂性，能夠在更少的迭代中趨近于最優(yōu)值；同時(shí)也在資源調(diào)度的仿真實(shí)驗(yàn)中驗(yàn)證了WOA 算法相比于Kubernetes 默認(rèn)的調(diào)度算法和PSO 算法有一定的提升，而改進(jìn)WOA-3 算法相比于傳統(tǒng)WOA 算法能夠使資源的調(diào)度更加均衡，資源利用率更高。