基于混合策略改進的鯨魚優(yōu)化算法

李 茹，范冰冰

(華南師范大學(xué)計算機學(xué)院，廣東 廣州 510000)

0 引 言

鯨魚優(yōu)化算法(Whale Optimization Algorithm)是Mirjalili等人[1]于2016年根據(jù)座頭鯨圍捕獵物的行為提出的算法，鯨魚優(yōu)化算法具有原理簡單、參數(shù)少、易理解等優(yōu)點，已有相關(guān)研究證明了其在收斂速度和尋優(yōu)精度上優(yōu)于其他傳統(tǒng)的優(yōu)化算法，目前已廣泛應(yīng)用于解決多種工程問題[2-9]。但鯨魚算法仍同其他啟發(fā)式算法一樣存在收斂速度慢、早熟、求解精度低等問題，近年來就這些問題國內(nèi)外學(xué)者也進行了積極的改進研究。Oliva等人[10]利用混沌映射進行計算，并自動調(diào)整算法的內(nèi)部參數(shù)，改進后的算法提高了其在復(fù)雜目標函數(shù)的尋優(yōu)能力。郭振洲等人[11]提出WOAWC，通過柯西逆累積分布函數(shù)對鯨魚位置進行變異，利用自適應(yīng)權(quán)重參數(shù)提高鯨魚算法的局部搜索能力和求解精度。張永等人[12]利用分段Logistic混沌映射并考慮算法的非線性優(yōu)化過程和搜索過程中個體的差異性來改進鯨魚算法，通過仿真實驗證明了其改進效果。何慶等人[13]提出了基于非線性調(diào)整策略改進收斂因子和基于人工峰群算法limit閾值的混合策略改進鯨魚優(yōu)化算法，提出的MSWOA經(jīng)實驗表明具有較高的尋優(yōu)精度和較高的收斂速度。吳坤等人[14]將灰狼算法中的等級制度和微分進化算法中的貪婪策略引入鯨魚優(yōu)化算法，在保證了收斂速度的同時，優(yōu)化了開發(fā)和搜索能力。張水平等人[15]通過等價替換和Faure序列提高初始解的質(zhì)量，利用柯西高斯變異并動態(tài)調(diào)整搜索策略改進鯨魚優(yōu)化算法，在仿真實驗上取得了很好的結(jié)果。徐航等人[16]提出利用混沌的特性來初始化種群和基于透鏡成像反向?qū)W習(xí)等混合策略改進的IWOA，通過實驗驗證了可行性。

針對鯨魚算法收斂速度慢、尋優(yōu)精度低、早熟等問題，本文提出一種基于混合策略改進的鯨魚優(yōu)化算法(LGWOA)。

1 原始鯨魚算法

WOA是啟發(fā)于座頭鯨捕食行為而產(chǎn)生的仿生智能優(yōu)化算法[17]。在鯨魚算法中，每個可行解對應(yīng)一條鯨魚[18]。在鯨魚群捕捉獵物這一過程中，每條鯨魚有2種行為:一種是向著隨機鯨魚游動，向著隨機鯨魚游動有2種方案，一種是局部搜索，一種是全局搜索；另外一種是利用氣泡網(wǎng)驅(qū)趕獵物，鯨魚向著附近的鯨魚游動并利用氣泡網(wǎng)來包圍獵物。在每一代迭代過程中，鯨魚都會隨機選擇這2種行為進行捕獵，且每條鯨魚選擇這2種行為的概率是相等的，即p(包圍)=p(氣泡網(wǎng))。

1.1 包圍獵物策略

根據(jù)鯨魚的生物特性，隨機概率p小于0.5鯨魚在包圍獵物時會選擇向著最優(yōu)位置的鯨魚游動或者向著一只隨機鯨魚游動。

1.1.1 向著最優(yōu)位置鯨魚游動

鯨魚發(fā)現(xiàn)獵物并向著最優(yōu)位置鯨魚游動時，此時系數(shù)向量|A|<1，鯨魚采用收縮包圍機制接近獵物，該鯨魚的位置更新公式為：

(1)

其中，Xbest代表當前最優(yōu)的鯨魚位置，i代表當前鯨魚處在第i個位置，A和C為系數(shù)向量，||表示數(shù)的絕對值。向量A、C的計算公式如下：

A=2·a·r-a

(2)

C=2·r

(3)

其中，r是一個0到1的隨機數(shù)；A的每一維為均勻分布在[-a,a]內(nèi)的隨機數(shù)，a的初始值為2，隨著迭代次數(shù)線性遞減至0；C為[0, 2]內(nèi)的隨機數(shù)。

1.1.2 向著隨機鯨魚的位置游動

當系數(shù)向量|A|>1時，表明鯨魚在收縮包圍圈之外，這時鯨魚會在種群中隨機選擇一條鯨魚并向其游去，即進行全局搜索，此時鯨魚的位置更新公式為：

(4)

其中，Xrand為隨機選擇的鯨魚的位置，此時鯨魚可以在初始位置和此時最優(yōu)鯨魚位置之間的任一位置進行搜索。

1.2 螺旋上升策略

鯨魚發(fā)現(xiàn)獵物后，若此時的隨機概率p不小于0.5，則使用氣泡網(wǎng)來驅(qū)趕獵物，并與獵物之間建立一個螺旋方程，根據(jù)螺旋方程不斷地更新自身的位置，位置更新公式如下:

(5)

其中，b為常數(shù)(默認為1)，l為[-1,1]內(nèi)服從均勻分布的隨機數(shù)。

2 算法改進

鯨魚優(yōu)化算法(WOA)相比較其他元啟發(fā)式算法，具有原理簡單、參數(shù)少的優(yōu)勢，該算法僅需要對2個參數(shù)A和C進行調(diào)節(jié)[19]，搜索向量A的自適應(yīng)變化使得鯨魚算法在迭代過程中擁有良好的平衡局部搜索和全局搜索的能力。但正是由于A的自適應(yīng)原理使得原始的WOA存在求解精度低、收斂速度慢、早熟的問題。針對上述問題，本文提出LGWOA。

2.1 基于萊維飛行改進鯨魚優(yōu)化算法

萊維飛行是一種特殊類型的具有“重尾”概率分布的廣義隨機游走[20]，其服從于萊維分布，隨機搜索路徑采用一種短距離和偶爾長距離相間的方式。近年來，研究人員用萊維飛行解決搜索和優(yōu)化的問題，證明了其能夠改進優(yōu)化算法在解空間的搜索能力以及求精能力[21-26]。萊維飛行是一種非高斯隨機過程[27]，其步長服從于Levy分布：

Levy(s)～|s|-1-β, 0<β≤2

(6)

其中，s是飛行步長，β是一個指數(shù)，可以用Mantega的算法計算s：

(7)

其中，β設(shè)置為1.5，μ和υ服從正態(tài)分布。

(8)

在WOA的隨機搜索階段，每個個體的位置都通過與其他個體在小范圍內(nèi)的相應(yīng)位置交換信息來更新，這就導(dǎo)致在隨機搜索的時候解空間是有限的，將萊維飛行引入鯨魚優(yōu)化算法的隨機搜索的階段，通過萊維飛行來隨機加大鯨魚搜索的步長，擴大了搜索空間，并提高了搜索能力，甚至加快了收斂速度。用于更新鯨魚的位置可以通過如下表達式進行描述：

(9)

根據(jù)公式(7)至公式(9)可得出：

(10)

2.2 基于自適應(yīng)權(quán)重改進鯨魚優(yōu)化算法

通過分析公式(5)可以得知，當鯨魚使用氣泡網(wǎng)驅(qū)趕獵物時同樣是局部搜索，仿真機制是鯨魚通過氣泡網(wǎng)來驅(qū)趕獵物，但隨著迭代次數(shù)，鯨魚驅(qū)趕獵物的氣泡網(wǎng)會逐漸變小，容易陷入局部最優(yōu)的問題。為了能夠自適應(yīng)地改變鯨魚驅(qū)趕獵物的范圍，提出一個基于每代鯨魚最佳適應(yīng)度變化的慣性權(quán)重w，將每代鯨魚群最佳適應(yīng)度作為反饋參數(shù)。在每次迭代中，每條鯨魚都將得到一個w。對于w值較小的鯨魚，當前鯨魚縮小驅(qū)趕獵物范圍。對于w值較大的鯨魚，當前鯨魚擴大驅(qū)趕獵物范圍。

(11)

(12)

由公式(11)可知，w參數(shù)的取值范圍是[0.5,2]。當w<1的時候，鯨魚會縮小氣泡網(wǎng)的包圍獵物范圍，當w>1的時候，鯨魚會擴大泡網(wǎng)包圍獵物范圍。由于w的取值范圍是[0.5,2]，可以知道w有1/3的概率會縮小氣泡網(wǎng)的包圍獵物范圍，有2/3的概率擴大泡網(wǎng)包圍獵物范圍。從而可以得出在迭代過程中，w有較大概率擴大氣泡網(wǎng)的搜索范圍，因此可以有效規(guī)避陷入局部最優(yōu)，提高求解精度。

2.3 基于遺傳算法改進鯨魚優(yōu)化算法

在鯨魚算法的流程中，隨著迭代次數(shù)的增加，|A|>1的比例越來越小，這就導(dǎo)致鯨魚種群的全局搜索能力不斷減弱從而使得算法過早收斂。本文提出在鯨魚算法中結(jié)合遺傳算法的交叉和變異策略擴大算法后期的全局搜索范圍，增加種群多樣性，規(guī)避后期陷入局部最優(yōu)的問題，其中，每條染色體代表一個鯨魚種群，每個基因代表一個鯨魚個體，基因上的值對應(yīng)鯨魚的位置。

遺傳算法[28]中的交叉操作有3種不同的策略，使用一個flag參數(shù)來標記是否需要進行交叉操作，flag參數(shù)是一個初始值為0，從0開始遞增的參數(shù)，每計算完一個種群flag就加1，當flag等于種群大小1/2的時候，就進行交叉變異。選擇哪一種策略是由概率Pt決定的，Pt是一個隨著迭代而變化的自適應(yīng)參數(shù)。Pt的計算公式為:

(13)

其中，t為當前代數(shù)，maxiter為最大迭代代數(shù)，Pt隨著t增大而逐漸增大。Pt的取值范圍為[e-1,1]，算法初期，算法的全局搜索能力較強，因此Pt<0.5，此時選擇交叉策略3，即單點交叉；當隨著算法的迭代，算法全局搜索能力逐漸減弱，而在算法后期，Pt的值逐漸增大，因此Pt>0.5且Pt>h,此時選擇交叉策略1進行多點交叉；否則使用交叉策略2進行多點交叉。在算法后期利用多點交叉來增加種群多樣性，增強算法跳出局部最優(yōu)的能力。

交叉策略1 隨機生成一個點，將該點到基因末尾的值都和相鄰染色體的基因交叉。例如數(shù)組長度為n，隨機生成i，交叉2個相鄰染色體的i～n的長度。

交叉策略2 隨機生成2個點，交叉兩點之間染色體的基因位，例子數(shù)組長度為n，隨機生成i、j，交叉相鄰染色體之間i～j的基因。

交叉策略3 隨機生成一個點，交叉相鄰2個染色體之間的一個基因位。

變異操作把染色體中的選擇一個基因位突變成另外一個基因位。

2.4 算法步驟

LGWOA的流程如圖1所示。

圖1 算法執(zhí)行流程圖

3 函數(shù)測試與性能分析

仿真實驗基于Windows10(64 bit)操作系統(tǒng)，Intel?CoreTMi5-8250U CPU、1.8 GHz主頻及8 GB內(nèi)存，使用MATLAB R2021b編程開發(fā)。遺傳算法交叉概率為0.3、變異概率為0.1。選取了12個Benchmark函數(shù)(見表1)進行仿真實驗，把12個基準函數(shù)分2組，其中：F1～F6為單峰函數(shù)，用來測試函數(shù)的收斂速度；F7～F12為復(fù)雜的多峰測試函數(shù)，可用來測試算法的全局搜索能力和規(guī)避局部最優(yōu)的能力。

表1 基準測試函數(shù)

本文基于2個角度測試算法的優(yōu)化性能：1)針對本文對算法的3種改進策略，分別單獨測試其對算法性能的改進效果；2)將本文改進的鯨魚優(yōu)化算法(LGWOA)與原始的鯨魚優(yōu)化算法(WOA)、WOAWC[11]、MSWOA[13]、IWOA[16]在3個不同維度下進行測試。

3.1 不同改進策略的性能分析

本文采用3個不同的改進策略，分別是：1)將萊維飛行引入鯨魚隨機搜索的位置更新公式中(WOA-a); 2)將自適應(yīng)權(quán)重引入鯨魚螺旋上升位置更新公式中(WOA-b); 3)交叉變異策略(WOA-c)。為比較3種不同策略對算法性能的影響，取種群大小為30，最大迭代次數(shù)設(shè)為500，為保證實驗的可信度和數(shù)據(jù)的準確性，每次實驗運行30次并取平均值，各改進策略對12個基準函數(shù)優(yōu)化求解的結(jié)果對比如表2所示。

表2 不同改進策略下的算法性能對比

分析表2可知，在3種改進策略中，WOA-a對WOA算法性能改善最為明顯，WOA-b次之。在單峰函數(shù)中，WOA-b對WOA的性能改善明顯優(yōu)于WOA-c，但是多峰函數(shù)中，WOA-c和WOA-b算法對比，WOA-c算法的改進效果明顯優(yōu)于WOA-b算法。對于大部分基準函數(shù)，綜合了3種改進策略的LGWOA比任一僅采用一種改進策略的WOA均有更優(yōu)的尋優(yōu)精度和穩(wěn)定性。并且分別對測試函數(shù)選取同量級的尋優(yōu)精度時，LGWOA針對大部分的測試函數(shù)都有更快的收斂速度。因此，LGWOA很好地綜合了3種改進策略的優(yōu)點，證明了混合改進策略的合理有效性。

3.2 與其他優(yōu)化算法的性能比較

算法的空間復(fù)雜度主要由種群大小和搜索空間的維度決定，搜索空間的維度越大，空間復(fù)雜度越高[29]，本文采用3中不同維度對算法進行性能測試。

設(shè)定種群大小為30，最大迭代次數(shù)為1000，基準測試函數(shù)為F1～F12，同樣運行30次并取平均值，表3、表4、表5展現(xiàn)了LGWOA、WOA、MSWOA、WOAWC、IWOA這5種算法分別在維度為10、30、50下對函數(shù)的求解結(jié)果，從平均解和標準差2個方面進行分析。圖2、圖3、圖4為WOA、LGWOA、MSWOA、WOAWC、IWOA在3個不同維度下優(yōu)化benchmark函數(shù)的收斂過程對比圖。

表3 LGWOA與其他算法性能對比(D=10)

表4 LGWOA與其他算法性能對比(D=30)

(a) F1 (b) F2 (c) F3

當求解維度為10維時，算法LGWOA、MSWOA、WOAWC以及IWOA在F1～F4上均取得了理論最優(yōu)值，但由圖2(a)～圖2(d)可知，其具有更快的收斂速度，例如在對函數(shù)F2的求解中，LGWOA取得理論最優(yōu)值的迭代次數(shù)明顯少于其余4種算法。在求解F5時，LGWOA相較于其余4個算法尋優(yōu)精度高出了5個數(shù)量級，在求解單峰函數(shù)F6上略優(yōu)于相較于在F1～F4上同樣表現(xiàn)良好的MSWOA、WOAWC、IWOA，但由圖2可知，LGWOA的收斂速度顯著提高且具有更高的穩(wěn)定性。在多峰函數(shù)中，在函數(shù)F7、F8、F9、F10、F12求解中，LGWOA的收斂速度均明顯提升，在函數(shù)F11的優(yōu)化過程中LGWOA的收斂速度稍劣于其他函數(shù)，但是在求解精度上更勝一籌，可以看出LGWOA有更強的跳出局部最優(yōu)的能力。

當求解維度為30維時，針對大部分的benchmark函數(shù)，LGWOA求解精度比MSWOA、WOAWC、IWOA更高，更是遠優(yōu)于原始的WOA。其中在求解單峰函數(shù)F1～F6時，LGWOA求解F1～F4時均取得了函數(shù)理論最優(yōu)值0；對于函數(shù)F5、F6的求解結(jié)果逼近理論值0，對于函數(shù)F6尋優(yōu)精度優(yōu)化效果不夠明顯，但是通過圖3(f)可以看出其收斂的速度相較于WOA、WOAWC、MSWOA、IWOA顯著提升，通過圖3(g)～圖3(l)和表2可以看出，對于有多個局部極值的多峰函數(shù)來說，LGWOA對于函數(shù)F7～F10尋優(yōu)精度以及收斂速度均顯著優(yōu)于原始WOA，其收斂速度優(yōu)于同樣在求解精度上表現(xiàn)良好的MSWOA、WOAWC和IWOA，對于函數(shù)F11，算法LGWOA收斂速度稍劣于WOAWC，但有更高的求解精度。

表5 LGWOA與其他算法性能對比(D=50)

(a) F1 (b) F2 (c) F3

當求解維度為50維時，結(jié)合圖4從收斂速度、求解精度以及穩(wěn)定性3個方面綜合來看，LGWOA的表現(xiàn)優(yōu)于其余4個算法，可以看出在求解高維空間的函數(shù)時，LGWOA的收斂速度與尋優(yōu)精度相較于其他4種算法均明顯提升。

(a) F1 (b) F2 (c) F3

上述實驗結(jié)果表明，本文提出的3種改進策略明顯提升了算法的求解精度和收斂的速度，能夠很好地平衡算法全局搜索和局部搜索的能力。通過萊維飛行擴大全局搜索空間，并引入自適應(yīng)權(quán)重提高求解精度，在鯨魚算法的后期結(jié)合遺傳算法的交叉變異擴大算法后期的全局搜索能力，有效規(guī)避了算法后期早熟現(xiàn)象的出現(xiàn)。

綜上，對benchmark函數(shù)的求解中，本文所改進的LGWOA在求解精度及穩(wěn)定性上均較其他算法有明顯提升，而在尋優(yōu)速度上，除了在F11的求解中，函數(shù)的收斂速度稍劣于MSWOA和WOAWC，該算法對函數(shù)的優(yōu)化性能均較其他4種算法有明顯的提升，從而驗證了LGWOA算法中改進策略的優(yōu)越性和有效性。

4 結(jié)束語

本文首先將萊維飛行策略引入原始WOA中擴大鯨魚優(yōu)化算法在全局搜索時的搜索范圍，提高了全局搜索能力；然后，在鯨魚螺旋更新位置的階段，加入一個自適應(yīng)權(quán)重參數(shù)來加快鯨魚包圍獵物的速度，提高算法尋優(yōu)精度；最后利用遺傳算法的交叉變異思想，平衡算法的全局和局部搜索能力，增加種群的多樣性來解決傳統(tǒng)鯨魚優(yōu)化的過早收斂的問題。選取12個benchmark函數(shù)從2個角度進行仿真實驗，結(jié)果表明，本文提出的混合策略改進的鯨魚優(yōu)化算法在收斂速度和求解精度上均有明顯提升。