余隆勇

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

0 引言

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

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

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

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

1.1 包圍獵物階段

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

1.2 螺旋氣泡捕食階段

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

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

1.3 搜索獵物階段

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

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

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

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

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

2.2 非線性變化的包圍策略

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

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

2.3 基于AOS的螺旋位置變更

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

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

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

改進(jìn)后的WOA-3 算法在搜索捕食階段中，將每一個(gè)鯨魚個(gè)體當(dāng)作一個(gè)具體的解，根據(jù)每一次迭代的結(jié)果對鯨魚個(gè)體進(jìn)行評估，在達(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è)用來進(jìn)行鯨魚的位置更新；當(dāng)P ≤0.5且A>1時(shí)，算法通過公式⒂進(jìn)行鯨魚個(gè)體的位置更新。

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

⑹根據(jù)2-5 過程更新當(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對四個(gè)測試函數(shù)在Matlab 進(jìn)行實(shí)驗(yàn)，具體函數(shù)如表1所示。得到對應(yīng)的最優(yōu)解、平均解和標(biāo)準(zhǔn)差，如表2所示。

表1 測試函數(shù)

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

由表2可知，標(biāo)準(zhǔn)WOA算法在四個(gè)函數(shù)測試的最優(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è)測試函數(shù)中的收斂情況進(jìn)行對比，結(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)度中的性能，本文通過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)行測試。Master 節(jié)點(diǎn)用于實(shí)現(xiàn)資源調(diào)度、監(jiān)控等功能，而Node 節(jié)點(diǎn)則是真正用來處理Pod 任務(wù)請求的工作節(jié)點(diǎn)。具體配置如表3和表4所示。

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

表4 Pod請求資源量

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

在本文中，為了驗(yàn)證WOA-3 算法在資源調(diào)度上的性能將其與WOA、PSO 以及Kubernetes 的默認(rèn)調(diào)度算法在資源調(diào)度性能進(jìn)行對比。相比于Kubernetes的默認(rèn)性能評價(jià)因子CPU 和內(nèi)存，在實(shí)際的應(yīng)用場景中任務(wù)的調(diào)度還需要考慮到對網(wǎng)絡(luò)寬帶的訪問和磁盤的讀寫需求，所以在本次實(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 算法。由此說明，改進(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é)束語

針對鯨魚算法在資源調(diào)度中容易出現(xiàn)收斂速度慢，陷入局部最優(yōu)解等問題，提出一種改進(jìn)的WOA-3算法。WOA-3 算法主要是針對鯨魚獵食三個(gè)階段分別進(jìn)行改進(jìn)，通過改進(jìn)非線性變化結(jié)構(gòu)的包圍策略以及基于AOS 策略改變螺旋更變位置，來加快鯨魚算法的局部收斂速度；同時(shí)，通過提出自適應(yīng)加權(quán)捕食策略來提高鯨魚算法的全局尋優(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)度更加均衡，資源利用率更高。