基于自適應決策算子的鯨魚優化算法

徐 航， 張達敏， 王依柔， 宋婷婷， 樊 英

(貴州大學 大數據與信息工程學院, 貴陽 550025)

0 引 言

群體智能優化算法是通過模擬自然界中生物的群體規律來實現尋優的元啟發式算法，許多自然啟發算法越來越受工程應用問題的青睞，其實現過程簡單且易于執行，而且這些算法也具有一定繞過局部最優區域的能力[1]，其中具有代表性的是源于座頭鯨捕獵行為的鯨魚優化算法(Whale Optimization Algorithm, WOA)[2]。由于WOA擁有出色的性能，被成功應用于許多優化問題中[3]，但和大多數啟發式算法一樣，WOA也是從一個隨機的種群開始進行搜索，由于尋優過程的隨機性，在勘探和開發之間保持適當的平衡是極其困難的，而且在算法的搜索過程中不斷改變領導者的位置，導致算法在求解優化問題時可能會迅速收斂到局部最優解而不是全局最優解，最終導致解決方案的質量下降。為了提升該算法的性能，有學者已經對WOA進行了改進研究，提出了一種基于自適應權重和柯西變異的鯨魚優化算法，且表現出較高的尋優精度和穩定性[4]；提出了混合遺傳鯨魚優化算法來優化頻譜利用率和對抗惡意用戶模擬授權用戶的攻擊行為，結果表明該算法比現有的檢測算法具有更高的性能[5]。

為了進一步深入研究WOA，筆者分別采用混沌思想、決策算子等方法對WOA進行改進，并提出一種改進鯨魚算法(Improved Whale Optimization Algorithm, IWOA)，首先利用混沌理論的特點優化算法初始種群位置，最大限度使初始種群分布均勻，并在算法中加入一個決策算子，通過對領導者的位置進行優化，增加算法跳出局部最優區域的概率，進而增加算法的尋優精度，同時結合文中提出的自適應權重，使勘探和開發之間保持適當的平衡。在實驗分析部分，通過對10個基準測試函數進行反復求解，并利用Wilcoxon檢驗、MAE等方法證明了改進算法的有效性。

1 鯨魚優化算法

WOA是基于座頭鯨捕食機理的元啟發式優化算法，它模擬了座頭鯨的捕獵模式，通過利用搜索種群在搜索空間中移動，針對適應度值大小選擇候選解。一般來說，增加搜索種群的大小和迭代次數可以尋找到更好的解，但是會耗費算法的執行時間，在WOA中通過模擬鯨魚群包圍捕食過程、螺旋行進過程和搜尋獵物過程進行數學建模。具體描述如下：

(1)包圍捕食過程。在WOA初始階段，由于鯨魚群暫時無法獲得獵物的方位，所以通過每個個體的初始位置開始搜索，認為當前的最佳候選解就是已獲得的最優解，通過不斷交流，引導整個種群向著距離最優解最近的個體移動，而距離最優解最近的個體不斷向最優解靠近，達到尋優的目的。在分配了最佳解決方案之后，其它代理嘗試向最佳搜索代理更新其它代理的位置，通過不斷的搜索，座頭鯨會將獵物包圍起來。包圍獵物的過程可以用數學公式(1)和(2)表示：

X(t+1)=X*(t)-A·D，

(1)

D=|C·X*(t)-X(t)|.

(2)

其中，D=|C·X*(t)-X(t)|;X(t)為個體的當前位置;X*(t)為當前最優位置向量;t為當前迭代次數，A、C定義為式(3)和式(4)：

A=2ar1-a，

(3)

C=2r2.

(4)

其中，r1和r2為[0,1]的隨機數;a為隨迭代次數增加由2遞減到0的參數;Tmax為最大迭代次數。

(2)螺旋行進過程。根據座頭鯨捕獵的方式，WOA中將泡泡網捕食的方式建模為收縮包圍機制和螺旋行進策略，通過模仿座頭鯨發現獵物的捕食過程，不斷以旋轉的方式靠近獵物。

值得注意的是收縮包圍機制是通過在迭代過程中將a的值從2線性降低到0來實現的，此時的A是在[-a,a]之間隨機取值的，當|A|≤1時，可得更新后的位置是在向最優位置移動的，通過改變算法參數的方式實現了對獵物的收縮包圍。其中螺旋方程(5)表示如下：

X(t+1)=D'·ebl·cos(2πl)+X*(t)，

(5)

其中，D'=|X*(t)-X(t)|，表示鯨魚與獵物之間的距離；b是螺旋行進方程的常量，本文b=1；l為[-1,1]之間的隨機數。由于鯨魚的螺旋捕食者不僅在外環上移動，而且還縮小了包圍圈，因此數學模型中有一半的概率會選擇收縮包圍方式和螺旋模型行進來更新鯨魚的位置。數學公式(6)表示如下:

(6)

其中，p為[0,1]之間隨機生成的隨機數。

(3)搜索獵物過程。在搜索獵物的過程中，當參數A滿足|A|>1時，鯨魚會通過當前自身的位置隨機尋找獵物，利用這種位置更新方式，鯨魚群可以離開自身當前所在區域，一定程度上提高了WOA的優化性能。數學公式(7)和(8)表示如下：

Drand=|C·Xrand(t)-X(t)|，

(7)

X(t+1)=Xrand(t)-A·D.

(8)

其中，Xrand表示從群體中隨機選擇鯨魚的位置向量。

2 自適應決策鯨魚優化算法

2.1 混沌初始化種群

近幾年出現的大多數生物啟發算法都是基于隨機種群的算法，鯨魚優化算法也一樣，通過概率分布來實現算法種群的隨機分布，這種產生初始種群的方式則會導致種群多樣性低，往往使尋優的位置不夠廣泛，利用混沌特性來提高WOA的收斂速度和搜索精度具有重要意義[6]，目前優化領域中有多種類型混沌映射，在大部分的研究中使用Tent映射和Logistic映射等來進行種群初始化，Singer映射能產生相對均勻的混沌序列。因此，本文采用Singer映射來優化算法初始種群，數學公式描述為式(9)：

xi+1=P·(7.86xi-23.31xi2+28.75xi3-

13.302 875xi4).

(9)

其中，P∈(0.9,1.08)，本文取0.98。

在算法初始階段，通過混沌映射生成位置分布較為合理的個體，擴大了算法中個體在空間中的勘探范圍，一定程度上降低了空間中種群被局部極值吸引的可能性，從而提高了算法的性能。

2.2 決策算子

在WOA搜索方程中，種群的搜索方向對領導者有很大依賴關系，領先的鯨魚有時會在局部解決方案中陷入停滯，特別是在存在多峰的多模態問題中，在局部極值處的停滯是過早收斂的主要原因。鯨魚個體之間的協作和信息交換機制有助于緩解這一問題，為了增強算法避免早熟能力，本文在算法中加入一個決策算子，將個體的適應度和位置加入到算法的搜索機制中，通過對領8導者的位置進行處理，加強種群之間的信息交流，進而提高算法的尋優性能，具體策略如式(10)～(12)：

(10)

(11)

(12)

其中，Xtr1、Xtr2、Xtr3表示隨機選擇的第t代的3個個體位置;Xigbest表示全局最優位置，X1t、X2t、X3t表示第t代適應度值最好的前3個個體位置;k表示(0,1)之間的隨機數。DP表示受個體適應度值影響決策概率，表示為式(13)：

(13)

其中，N表示種群個體，C(t)表示第t代優化成功的個體數，表示為式(14)：

(14)

考慮到在鯨魚優化算法中，每次迭代時將適應度值最好的位置賦值給鯨魚領導者，這樣的方式導致種群個體匯聚在局部最優區域，往往導致尋優精度較低，為了降低這種缺陷對算法的影響，本文將個體的適應度值納入影響決策算子的因素中，加入決策算子后的算法領導者不是直接進行下一次迭代過程，而是記錄每個個體的適應度值和位置，通過判斷決策概率的大小選擇篩選公式，通過比較適應度值的大小挑選出一個新的領導者位置，最后引入貪婪機制，比較兩個領導者之間的適應度值大小，更新全局最優位置及適應度值，再進入到下一次的迭代過程，通過對最優位置的不斷選擇，對提高了算法的搜索精度和收斂速度具有重要意義。

2.3 分段自適應權重

WOA與當前大多數元啟發式算法一樣，慣性權重對算法性能具有很明顯的影響，在粒子群算法中已經證明，慣性權重反映的是后一個追隨者擺脫前一個位置束縛的能力，較大的慣性權重會使算法擁有較好的全局搜索能力，反之，較小的慣性權重會使算法擁有較好的局部開發能力[7]。通常情況下，較大的權重會使算法快速抵達最優區域附近，而在算法迭代后期，應該適當減小相鄰兩代之間的聯系，此時權重應該較小，因此，本文在改進算法中提出分段自適應的慣性權重，式(15)和式(16)：

(15)

(16)

其中，ωmax表示最大慣性權重；ωmin表示最小慣性權重，當ω在[0.4,0.9]之間變化時，算法具有最佳的尋優性能；DP表示算法中個體優化的成功率，rank(r)表示隨機一個個體的秩序數；N表示種群大小。因此，在迭代的前半部分，權重受群體的優化成功率影響。隨著迭代的進行，慣性權重在0.4～0.9之間動態變化，使算法的全局搜索和局部開發得到較好的平衡。在迭代的后半部分，隨著種群的聚集，繼續使用優化成功率將導致權重無法更新，于是采用隨機個體的秩序數來更新權值，使迭代后期鯨魚群也擁有較大的搜索步長，一定程度上增加了算法跳出局部最優區域的概率。當t/Tmax<0.5時，加入權值的位置更新公式表示為(17)～(19)(同理可得t/Tmax≥0.5時的位置更新公式)：

X(t+1)=X*(t)-ω1·A·D|A|<1,p<0.5,

(17)

X(t+1)=Xrand-ω1·A·Drand|A|≥1,p<0.5,

(18)

X(t+1)=D'·ebl·cos(2πl)+ω1·X*(t),p≥0.5.

(19)

2.4 IWOA執行步驟

結合前文所述的改進策略，本文所提基于自適應決策算子的鯨魚優化算法步驟如下：

Step1根據混沌Singer映射生成N個初始化個體，N為種群大小，設置最大迭代次數Tmax、ωmax、ωmin；

Step2由目標函數f(x)計算出種群中每個個體的目標函數值，并記錄最優位置X(t)，根據適應度值將N個個體排序，隨機選擇個體，記錄其秩序數rank(r)，同時分別與領導者適應度進行比較，統計C(t)，更新決策概率DP；

Step3更新算法中r1、r2、k等參數，同時更新a、A、C、l等，通過(15)(16)式更新參數ω1、ω2；

Step4如果迭代次數t≤0.5Tmax，通過比較|A|的大小，用隨機生成的p值與0.5作比較，選擇相應的位置更新公式，若p<0.5且|A|<1，則按照(17)式更新當前個體位置；

Step5若p<0.5且|A|≥1，則按照(18)式搜索獵物；

Step6若p≥0.5，按照(19)式更新當前位置；

Step7將r3與決策概率進行比較選擇決策公式，同時選擇種群中適應度值最好的3個位置和隨機的3個位置，將保存下來的最優位置X*按照(11)或(12)式進行位置篩選操作，最后引入貪婪機制，通過適應度值的大小篩選出一個新的領導者位置，更新全局最優位置；

Step8若迭代次數t>0.5Tmax，將(17)～(19)式中ω1更新為ω2，重復步驟4～7；

Step9判斷算法是否滿足停止條件，若達到則停止迭代，并輸出最優解和適應度值，反之，重復執行步驟3～8。

3 仿真測試和分析

在對算法進行改進的過程中發現，不同改進策略對算法的影響各不相同。為了分析本文提出的每個改進方法的效果，將每個改進方法針對WOA進行改進，分別對應為基于混沌Singer映射的鯨魚優化算法(Whale Optimization Algorithm Based on Chaotic Singer Map，CWOA)、基于分段自適應權重的鯨魚優化算法(Whale Optimization Algorithm Based on Piecewise Adaptive Weight, WWOA)和基于決策算子的鯨魚優化算法(Whale Optimization Algorithm Based on Decision Operator, DWOA)、并將每一種改進算法與改進鯨魚優化算法(Improved Whale Optimization Algorithm, IWOA)、鯨魚優化算法(Whale Optimization Algorithm, WOA)、和灰狼算法(Grey wolf optimizer, GWO)同時在表1所示的10個基準測試函數下進行重復求解測試，記錄最優值、最差值、均值等評價指標。考慮到維度是影響求解性能的重要因素，所以將各個測試函數的維度隨機設置為2～200維，從而驗證算法求解低維和高維的能力。

本文所有測試均在Window10操作系統，Inter(R) Core(TM)i5-9400F、2.9GHz主頻、16G內存的計算機上實現，編程語言為MATLABR2014b，實驗最大迭代次數Tmax設置為1000，種群大小N為30，實驗次數為30次，各算法的參數設置見表2。

表1 基準測試函數

表2 算法主要參數

首先，為了比較本文提出的幾種改進策略是否對WOA的性能有所提升，將CWOA、DWOA、WWOA中的參數統一設置為IWOA對應的參數，分析表3中的最優值、最差值和均值等實驗結果可知，所提出的改進方法相比于原始WOA的尋優性能均有大幅度的提升，但是每個改進策略對算法的影響存在差異，其中基于分段自適應權重的改進方法對算法的影響程度是最大的，說明原始算法中個體擺脫局部最優區域的能力較弱，也證明了本文所引進權重的有效性；對比加入權重的改進方法，基于決策算子的改進方法對算法的影響程度較弱，但與原始算法相比，DWOA尋優精度均有很大程度的提升，說明鯨魚個體之間的協作和信息交換機制一定程度上緩解了算法早熟的問題，使鯨魚群可以在搜索空間中搜索更廣闊的區域；相比于其他二種改進方法，基于混沌理論的種群初始化改進方法是最差的，當與原始算法相比，CWOA也有顯著的改進效果，說明利用混沌特性對初始種群進行優化使得個體在空間中分布更加均勻，從而搜索到的解的質量也更好。從整體來看，改進過程是以決策算子和自適應權重為主導，以混沌Singer映射的種群初始化為輔助進行的，所以融合3種改進策略的IWOA比每一個種改進策略的尋優效果都要好，WWOA在求解部分函數時也能達到和IWOA同樣的效果，說明此時該函數對權重更加敏感，而伴隨著維度的增加，大部分的函數評價指標均證明融合每個改進策略的IWOA是更加優秀的。

其次，由于評價指標中的標準差常反映算法的魯棒性，分析表3中的標準差可以發現包含每個改進策略的算法都比WOA更穩定，而包含所有改進方法的IWOA的標準差都比其他算法要好，從而說明IWOA具有一定的穩定性。從平均耗時來看，GWO平均耗時最短，改進方法的CWOA、DWOA和WWOA3種算法的平均耗時相對于WOA有所增加，因為3種算法都是在WOA的基礎上加入一種改進策略，但總的來說，綜合3種改進策略的IWOA耗時是最長的，因為IWOA可以引導搜索更廣闊的區域，導致平均耗時有所增加。

表3 測試函數結果對比

再次，為了直觀體現改進算法的優勢，圖1為本文選取的部分基準測試函數運行30次的平均收斂曲線，從收斂曲線可以看出，在8個測試函數的求解過程中，IWOA相比于參與對比的其他算法，具有更快的收斂速度和收斂精度，而且可以發現IWOA可以快速搜索到最優解，證明IWOA擺脫局部最優區域的能力比其他算法更強。

(a) f1平均收斂曲線 (b) f2平均收斂曲線

(c) f3平均收斂曲線 (d) f4平均收斂曲線

(e) f5平均收斂曲線 (f) f6平均收斂曲線

(g) f7平均收斂曲線 (h) f8平均收斂曲線

為了進一步評估WOA改進策略的魯棒性和競爭性，本文選取了CEC2014單目標優化函數中部分單峰、多峰、混合和復合類型的函數進行重復求解，選取的部分函數見表4，其中種群大小為30，最大迭代次數為3000，維度為30。

表5為部分CEC2014函數獨立重復運行30次得到的平均值和標準差，分析選取的部分函數的實驗結果可知，相比于參與對比的其他幾個算法，特別是在求解復雜類型函數的時候，IWOA表現出良好的求解能力，證明IWOA具有一定跳出局部最優區域的能力，而對于每一種改進方法，只有基于混沌Singer映射的改進算法表現較為平庸，但相比于WOA，都有較大程度的提升，其他每一個改進算法均表現優異，從而進一步證明本文提出的改進策略具有較好的尋優能力和魯棒性。

表4 CEC2014基準函數

表5 CEC2014優化結果對比

4 結束語

針對鯨魚優化算法的不足，本文首先采用混沌Singer映射來優化算法中的初始種群，一定程度上加快了算法的收斂速度；提出了一個決策算子，通過對領導者位置的篩選，提高了算法的尋優精度；最后，在算法中加入自適應慣性權重，平衡了算法的全局搜索和局部開發能力。經過部分基準測試函數的求解實驗，證明了改進算法具有優秀的尋優能力和魯棒性。