基于反向精英保留和Levy變異的多目標鯨魚優(yōu)化算法

梁倩

（哈爾濱商業(yè)大學(xué)，哈爾濱150028）

0 引言

多目標優(yōu)化是多準則決策的一個領(lǐng)域，它是涉及多個目標函數(shù)同時優(yōu)化的復(fù)雜問題，它更符合實際問題的需要。多目標優(yōu)化不可能將所有的目標都達到最優(yōu)值，需要再多個相互制約的目標之間做出最優(yōu)決策。因此，對于多目標相關(guān)問題的研究十分必要。

鯨魚優(yōu)化算法的出現(xiàn)相對較早，因此對于鯨魚優(yōu)化算法的研究比較全面，包含方法的改進與應(yīng)用。趙繼民等人[1]將模糊神經(jīng)PID控制器和優(yōu)化算法進行結(jié)合，采用鯨魚優(yōu)化算法去優(yōu)化神經(jīng)網(wǎng)絡(luò)的權(quán)值和偏差，降低了模糊神經(jīng)網(wǎng)絡(luò)的誤差，將混合的模型用于PID控制器。實驗數(shù)據(jù)顯示，所提出的混合模型性能得到了良好的改善。郝曉弘等人[2]提出了一種混合策略改進的鯨魚優(yōu)化算法，將混沌映射產(chǎn)生初始種群，在迭代過程中改進了收斂因子和慣性權(quán)重，并且變異程度取決于適應(yīng)度方差，阻止算法早熟收斂，研究數(shù)據(jù)表明，改進后的算法精度大大提升。伍鐵斌等人[3]提出了一種基于指數(shù)函數(shù)收斂因子的改進的鯨魚優(yōu)化算法，在算法中加入了旋轉(zhuǎn)操作的精英學(xué)習(xí)機制，并在其中加入了自適應(yīng)變異策略，降低算法陷入局部最優(yōu)的概率。經(jīng)過驗證，改進后的鯨魚優(yōu)化算法收斂速度加快，全局尋優(yōu)能力得到強。孔芝等人[4]提出一種將自適應(yīng)權(quán)重和改進搜索策略相結(jié)合的鯨魚優(yōu)化算法。在算法中，鯨魚種群的變化會使得權(quán)重與搜索機制發(fā)生變化，以適應(yīng)不同的鯨魚種群。經(jīng)仿真結(jié)果表明，所提出的算法在精度和收斂速度上有著顯著優(yōu)勢。吳澤忠等人[5]結(jié)合對立學(xué)習(xí)策略、隨機調(diào)整參數(shù)、正態(tài)變異操作等方法來改進鯨魚優(yōu)化算法，提出了一種基于改進螺旋更新位置模型的鯨魚優(yōu)化算法。對立學(xué)習(xí)策略對鯨魚每次的進化速度得到改善，隨機調(diào)整控制參數(shù)使鯨魚發(fā)生突變，降低了算法陷入局部最優(yōu)的風(fēng)險，加入正態(tài)變異和改進螺旋更新方法增大了算法的全局搜索能力，數(shù)據(jù)結(jié)果表明，在單峰、多峰以及固定維數(shù)函數(shù)上，改進后的算法具有更強的普遍適應(yīng)性和穩(wěn)定性。閆旭等人[6]利用量子物理與優(yōu)化策略改進鯨魚優(yōu)化算法，并將改進后的算法應(yīng)用在作業(yè)車間調(diào)度的問題上。在仿真實驗的結(jié)果上表明，相比于其他算法，所改進后的鯨魚優(yōu)化算法在尋優(yōu)成功率上有較明顯的改觀。由以上文獻可以看出，目前對于鯨魚優(yōu)化算法的研究仍然不夠完善，例如多目標問題的研究不夠深入。鯨魚優(yōu)化算法的搜尋機制在多目標領(lǐng)域應(yīng)該也具有較高的應(yīng)用價值，因此對于多目標鯨魚優(yōu)化算法的改進仍有許多工作要做。

為了解決鯨魚優(yōu)化算法本身的收斂速度慢，容易陷入局部最優(yōu)的問題，本文對其進行了改進，提出了一種反向精英保留和Levy變異相結(jié)合的多目標算法。具體改進為：首先利用反向精英保留策略[7]對種群的初始化進行篩選，使得算法具有良好的初始分布；并且在種群的迭代過程中使用反向?qū)W習(xí)機制，能夠擴大每次篩選的位置，加快收斂速度；其次引入了種群引導(dǎo)[8]的策略，將種群中最優(yōu)的部分個體選擇為領(lǐng)導(dǎo)者，其他個體根據(jù)這個領(lǐng)導(dǎo)者進行移動，為算法后期迭代產(chǎn)生均勻分布打下基礎(chǔ)。在測試函數(shù)實驗下，各項指標都表明改進后的算法有較強的尋優(yōu)能力；最后在算法的迭代過程中加入了Levy變異[9]的策略，以避免過早的收斂于局部最優(yōu)。

1 基本知識

1.1 多目標優(yōu)化問題

一個具有n個維度的決策變量和M個維度的目標函數(shù)的問題就可以被描述為以下的模型：

其中，X=[ ]x1,x2,…,xn是一個n維空間中的決策變量，Y=[ ]y1,y2,…,ym是m維空間中的目標量，而[low1,low2,…,lown]和[ ]up1,up2,…,upn是分別是決策變量的下限和上限。

解x優(yōu)于解y，在所有的目標函數(shù)上x都小于等于y，并且至少在一個目標函數(shù)上，x是嚴格優(yōu)于y，記為x?y。在解集合中，不存在任何一個解嚴格優(yōu)于當(dāng)前解，這樣的解被稱為帕累托最優(yōu)解。由帕累托最優(yōu)解構(gòu)成的集合被稱為帕累托最優(yōu)解集。所有的帕累托最優(yōu)解集所對應(yīng)的目標函數(shù)值就是帕累托前沿。

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

鯨魚優(yōu)化算法[10]的核心思想是鯨魚捕食時按照某種規(guī)則進行位置的移動，最優(yōu)鯨魚對其他鯨魚有引導(dǎo)的作用，并根據(jù)數(shù)學(xué)模型所提供的位置更新公式更新每頭鯨魚的位置。所有的鯨魚進行移動后，更新相應(yīng)位置的適應(yīng)度值，當(dāng)達到最終的迭代次數(shù)，迭代停止。

自然界中，鯨魚群能夠準確識別獵物的位置并包圍它。而在解決實際問題中并不能預(yù)知最優(yōu)的解，因此在鯨魚優(yōu)化算法中，總是將當(dāng)前群體中的具有最優(yōu)適應(yīng)度的鯨魚視為最優(yōu)個體，群體中其他鯨魚個體均向最優(yōu)個體進行包圍，其位置更新公式為：

其中，t代表當(dāng)前迭代次數(shù)，Xbest(t)表示當(dāng)前鯨魚中最優(yōu)鯨魚的位置，X(t)=(x1,x2,x3,…,xd)代表當(dāng)前候選鯨魚的位置。A和C代表系數(shù)向量，定義為：

其中，r1和r2是[0，1]上的隨機數(shù)。a為收斂因子，隨著迭代次數(shù)線性從2遞減到0。a的計算公式如下：

其中，tmax是最大迭代次數(shù)。

此外，鯨魚的行為還包含螺旋更新這一階段，這一行為用一下數(shù)學(xué)模型進行表示：

其中，D= |Xbest(t)-Xt|代表當(dāng)前鯨魚與最優(yōu)鯨魚的距離，b是螺旋程度的參數(shù)，l是[-1，1]之間的隨機數(shù)。鯨魚的包圍獵物的行為可以分為以上兩種，為了實現(xiàn)這兩種行為的同時發(fā)生，引入P為發(fā)生概率，當(dāng)產(chǎn)生的隨機數(shù)大于P時，發(fā)生收縮包圍；當(dāng)隨機數(shù)小于P時，發(fā)生螺旋更新行為，在優(yōu)化過程中，P一般設(shè)置為0.5。

除了以上的包圍食物的行為外，鯨魚也可隨機搜尋食物。在搜尋食物中，鯨魚之間可根據(jù)相互之間的位置進行更新位置，數(shù)學(xué)模型表達為：

其中，Xrand(t)代表隨機從鯨魚中選擇的個體單位。

鯨魚優(yōu)化算法的完整流程為：首先在搜索空間中隨機生成N個鯨魚的位置，之后進行種群的位置更新過程，根據(jù)當(dāng)前種群中最優(yōu)鯨魚的位置或者隨機選擇的鯨魚位置進行更新，之后再根據(jù)概率P選擇是螺旋更新還是包圍更新公式，直至整個算法的迭代次數(shù)完成或者達到停止條件。

2 反向精英保留和Levy變異的多目標鯨魚優(yōu)化算法（RLMOWOA）

2.1 帕累托等級排序

通過非支配排序?qū)⒎N群數(shù)為N的種群分類為分級的帕累托前沿。首先將種群中所有的帕累托前沿求出，標記帕累托前沿等級為1。之后將帕累托等級為1的個體忽略，在剩下的個體中求帕累托前沿，并記錄帕累托等級記為2，之后循環(huán)進行，直至將所有的解都分類。通過引入帕累托等級[11]和擁擠度的計算，能夠?qū)⑺械慕膺M行排序，以便在種群混合時能夠選擇出較優(yōu)的前N個解。

2.2 擁擠距離

用來描述非支配解分布的特征，以便選出帕累托最優(yōu)集合中的10%的優(yōu)質(zhì)解。在帕累托解集中，每個非支配解都有一個擁擠距離，來表示離它最近的非支配解在各個目標函數(shù)維度上的距離之和。擁擠距離值越大說明離當(dāng)前解最近的帕累托解位置較遠，即帕累托解分布較為稀疏。相反，擁擠距離越小說明離當(dāng)前解最近的帕累托解位置較近，也即帕累托解越密集。引入擁擠距離目的是可以通過當(dāng)前帕累托最優(yōu)解的分布情況來選擇最優(yōu)帕累托解，以引導(dǎo)種群向更均勻分布解進化。在帕累托前沿中的邊界解中，擁擠距離被設(shè)定為inf，其他解的擁擠距離的計算公式如下:

其中，I[i-1].m表示非支配解集I中將第m個目標函數(shù)值進行排序后，僅次于該i解的第m維目標函數(shù)值，fmmax和fmmin分別表示第m個目標函數(shù)值的最大值和最小值。

2.3 反向精英保留機制

為了更好地學(xué)習(xí)反向?qū)W習(xí)機制，首先來解釋反向點的概念，圖1顯示了a的反向點z。

圖1 反向點

一維標量a的上下限分別是Zmax和Zmin，則稱Zmin+Zmax-a為向量a的反向點。在高維向量中，每個維度均采用這種方法獲得的點為反向點。在每次位置更新后，求出所有解的反向點，將所有的反向點種群和當(dāng)前解種群混合。根據(jù)帕累托等級和擁擠距離選擇前N個個體作為當(dāng)前這一代的位置更新，優(yōu)先選擇帕累托最優(yōu)解上的個體，當(dāng)帕累托等級相同時選擇位置比較稀疏的個體。本文不僅在種群初始化中應(yīng)用反向?qū)W習(xí)機制，還將反向?qū)W習(xí)機制應(yīng)用于鯨魚的迭代更新過程。

2.4 Levy變異

Levy分布是法國著名數(shù)學(xué)家萊維提出的概率分布，在自然界中有許多的飛行動物的飛行軌跡都遵循Levy分布。在Levy分布的基礎(chǔ)上產(chǎn)生了Levy飛行，它是一種長短步相間的飛行方式，這種隨機的飛行方式使得飛行動物的運行軌跡范圍加大，找到食物的概率也相應(yīng)增加。目前這種變異方式已經(jīng)廣泛應(yīng)用于各種優(yōu)化領(lǐng)域，Levy變異的更新公式是：

其中，α是步長比例因子，xti代表第t代第i維的位置，⊕代表點對點乘法，Levy(β)代表服從參數(shù)為β的Levy分布的隨機數(shù)。Levy的計算方法如下：

其中，u和v均服從正態(tài)分布，定義為：

β的取值范圍一般是（1，3]，本文中β取1.5。

2.5 種群引導(dǎo)

由于鯨魚優(yōu)化算法需要定義最優(yōu)鯨魚的位置作為領(lǐng)導(dǎo)者，引導(dǎo)其他的鯨魚大致的移動方向，因此最優(yōu)解的選取對于種群的進化至關(guān)重要。但是由于偶然性的存在，有時最優(yōu)解的選擇并不夠合格，并且全局最優(yōu)解只局限于某個固定的解比較片面，最優(yōu)解應(yīng)該是從多個較優(yōu)解中隨機選擇。本文所提出的種群引導(dǎo)正是基于這樣的目的，每次從帕累托等級為1的個體中選取10%作為最優(yōu)解的集合，每個鯨魚在向最優(yōu)鯨魚移動時從最優(yōu)10%中隨機選取一個作為目標，經(jīng)過種群引導(dǎo)方式所獲得的解擁有更均勻的分布。

2.6 算法流程

本文提出的算法為反向精英保留和Levy變異的多目標鯨魚優(yōu)化算法。首先通過反向精英保留制度來初始化種群，利用種群中帕累托解中的10%作為引導(dǎo)者進行位置更新，更新位置后的種群為候選種群，結(jié)合反向精英保留機制產(chǎn)生候選反向種群，混合候選種群和候選反向種群選擇前N個個體作為子代解，并以一定的概率產(chǎn)生Levy變異，將最終產(chǎn)生的子代與父代混合，根據(jù)帕累托等級和擁擠度篩選出較優(yōu)解進入下一代。此過程不斷進行直至最大迭代次數(shù)。

算法1 RLMOWOA算法

輸入：種群數(shù)量，最大迭代次數(shù)，突變概率。

輸出：帕累托最優(yōu)解。

步驟1初始化種群并計算反向點及其適應(yīng)度值；

步驟2將初始種群與反向種群合并后計算帕累托等級和擁擠距離。根據(jù)帕累托等級和擁擠度選取前N個個體作為初始種群；

步驟3從帕累托前沿個體中選擇10%作為種群引導(dǎo)；

步驟4將所有的鯨魚根據(jù)條件進行位置更新，選擇最優(yōu)解為領(lǐng)導(dǎo)者時從10%中隨機選擇；

步驟5計算候選反向種群與當(dāng)前候選種群混合后的擁擠度，根據(jù)帕累托等級和擁擠度選擇前N個個體作為子代；

步驟6對種群中每個鯨魚產(chǎn)生一個隨機數(shù)，當(dāng)隨機數(shù)小于p時對該鯨魚位置進行Levy變異；

步驟7將子代與父代進行合并，重新計算帕累托等級和擁擠距離，根據(jù)步驟2的篩選規(guī)則選擇前N個個體進入下一代，以保證種群數(shù)量維持不變；

步驟8判斷是否滿足最大迭代次數(shù)，不滿足最大迭代次數(shù)則重新執(zhí)行步驟3-步驟8。

3 實驗結(jié)果與分析

3.1 實驗設(shè)置

為了進一步測試所提出的改進后的多目標鯨魚優(yōu)化算法，本文選取了四種算法與RLMOWOA進行比較，分別是多目標粒子群算法[12]（MOPSO）、多目標布谷鳥算法[13]（MOCS）、非支配快速排序遺傳算法[14]（NSGAⅡ），經(jīng)典多目標鯨魚優(yōu)化（MOWOA）[15]，在兩個目標的測試函數(shù)ZDT1、ZDT3[16]，以及三個目標函數(shù)的VNT2、VNT3[17]函數(shù)上進行測試。多個維度目標函數(shù)對于帕累托前言的求解帶來的困難成幾何倍數(shù)增長，無論是時間復(fù)雜度還是空間復(fù)雜度難度都會有所上升，但是實驗數(shù)據(jù)表明MOWOA的表現(xiàn)依舊出色。實驗環(huán)境為32位Win7系統(tǒng)，CPU為Intel Core i3 4170，內(nèi)存為8GB，編程語言為MATLAB 2018a。每個算法獨立運行25次并記錄每個指標的均值與方差。

3.2 性能指標

（1）反轉(zhuǎn)世代距離

反轉(zhuǎn)世代距離（Inverted Generational Distance，IGD）[18]每個從真實帕累托前沿上獲取的參考點到最近的算法所求得的解的距離的平均值。

其中，P為分布在真實帕累托前沿上的點的集合，|P|代表集合P中的點的個數(shù)，Q為算法獲取的帕累托最優(yōu)解的集合，d(v,Q)代表v到集合Q中的點的最小歐氏距離。當(dāng)算法獲得的解比較集中時，d(v,Q)的值較大，導(dǎo)致整個IGD值較大。當(dāng)獲得的解離帕累托真實前沿比較遠時，求和之后的參考點到獲得的解之間的距離之和則會相對較大。因此IGD能夠同時評價多樣性和收斂性。IGD值越小越說明算法所求的解離真實帕累托前沿越近或者解的分布越均勻。

（2）超體積指標

超體積指標（Hypervolume，HV）[19]算法獲得的非支配解集與參照點圍成的目標空間中區(qū)域的體積。

其中，δ表示Lebesgue測度，用來測量體積。|S|表示非支配解集的數(shù)目，vi表示參照點與解集中第i個解構(gòu)成的超體積。HV值越大算法的綜合性能越好。

3.3 實驗結(jié)果與分析

（1）種群引導(dǎo)、Levy變異、反向精英保留機制的驗證

為了進一步體現(xiàn)算法中引入種群引導(dǎo)，Levy變異和反向精英保留機制的作用，本文將所提出的算法與經(jīng)典的多目標鯨魚優(yōu)化算法進行對比。在ZDT1、ZDT3和ZDT6測試函數(shù)上進行了實驗，實驗采用控制變量法，相同測試函數(shù)在不同的算法下的迭代次數(shù)相同，以便觀察出所做出的改進對算法的提升。實驗結(jié)果分別運行30次，取各個指標的均值進行比較，記引入種群引導(dǎo)改進的算法為PG-MOWOA，引入Levy變異改進的算法為L-MOWOA，引入反向精英保留機制的算法為R-MOWOA。在各對比圖中，經(jīng)典的多目標鯨魚優(yōu)化算法記為MOWOA。各實驗結(jié)果對比圖如圖2-圖4所示。

圖2 種群引導(dǎo)的對比圖

在ZDT3測試函數(shù)中，經(jīng)典MOWOA在多次運行后的IGD和HV的均值分別是3.493E-01，5.004E-01，引入改進后的算法PG-MOWOA均值分別是6.112E-03、5.866E-01，種群引導(dǎo)對算法的提升效果十分明顯。結(jié)合圖2可以看出，未引入種群引導(dǎo)的經(jīng)典MOWOA所求的帕累托前沿還未完全收斂于真實帕累托前言，并且所求帕累托前言之間的分布在左上角比較密集，右下相對稀疏。而PG-MOWOA所求的帕累托前沿分布均勻，這驗證了種群引導(dǎo)對于多目標優(yōu)化算的提升。

在ZDT6測試函數(shù)中，經(jīng)典MOWOA的IGD和HV的均值分別是1.955E-02、3.731E-01，引入改進后的L-MOWOA的均值分別是3.879E-03、3.881E-01，Levy變異的引入使得各指標值都有了改善。從圖3可以看出，L-MOWOA算法仍有部分點并未收斂于真實帕累托前言，這些點已經(jīng)陷入局部最優(yōu)，而Levy變異的引入完美的解決了這個問題，從而使算法的全局尋優(yōu)能力得到大幅提升。

圖3 Levy變異的對比圖

在ZDT1的測試函數(shù)中，經(jīng)典的MOWOA算法的IGD和HV的均值分別是2.546E-01、4.932E-01，引入改進后R-MOWOA算法的均值分別是6.728E-03、7.163E-01。從圖4也可以看出，反向精英保留機制的引入對算法有著一定程度的提升。在算法中，反向精英保留機制不僅在種群初始化中引入，也在種群的更新迭代過程中得到應(yīng)用。初始化時的引入使得算法的初始分布更加全面，便于種群的進化，迭代更新過程中的應(yīng)用使算法每次搜索范圍更廣，加快了收斂的速度。

圖4 反向精英保留機制的對比圖

（2）與其他算法的比較

從IGD指標來看，RLMOWOA算法在ZDT系列測試函數(shù)上的表現(xiàn)比較好，在ZDT1上的IGD指標達到了4.895E-03，比其他算法性能高很多，并且方差也達到了最小值，為4.051E?04。在ZDT2上的表現(xiàn)也十分優(yōu)秀，IGD均值為5.478E-03，方差也穩(wěn)定在3.541E?04左右。RLMOWOA在三個目標函數(shù)值的VNT系列測試函數(shù)上的表現(xiàn)雖然達到了最優(yōu)值，但性能提升并不大，在VNT2上的IGD指標為1.798E-02，相比于其他四種算法的提升就顯得并不突出，但在VNT2上的方差較小，為7.371E?04，表現(xiàn)相對穩(wěn)定。在VNT3上的IGD指標僅為4.401E-02，方差相對較大，僅有微弱的提升效果?？傮w來說，RLMOWOA相比于另外四種算法有著不錯的優(yōu)勢。

從HV指標上來看，RLMOWOA算法在ZDT系列測試函數(shù)上的表現(xiàn)較好，在VNT系列測試函數(shù)上則表現(xiàn)平庸。經(jīng)典MOWOA的HV在ZDT1上的均值達到了6.799E-01，而OPMOWOA均值方差分別是7.194E-01、4.246E?04，均值和方差均達到了更高的水平。并且在ZDT2上也有著同樣的表現(xiàn)?？梢奟LMOWOA在MOWOA得基礎(chǔ)上得到了顯著的提升。在VNT2測試函數(shù)上，RLMOWOA算法并未達到最優(yōu)，但是五種算法的指標值都相差不大，性能表現(xiàn)相近。這是由于不同的指標表現(xiàn)不同方面的性能，單純的用HV指標來衡量算法的優(yōu)劣不夠充分，IGD的指標充分驗證了這一點。在VNT3上，RLMOWOA的HV值達到了最大值，為1.842E-01，相比于其他算法提升也并不明顯，但從穩(wěn)定性上來看，RLMOWOA達到了最小，僅為6.274E?05，這種穩(wěn)定的表現(xiàn)使得算法有一定的優(yōu)勢。

表1 IGD值

表2 HV值

ZDT3 VNT2 VNT3 4.518E-02±2.182E-02 2.017E-00±9.641E-02 1.838E-01±1.410E-04 2.147E-02±3.303E-02 2.033E-00±9.275E-03 1.840E-01±1.000E-04 5.790E-01±1.778E-02 2.038E-00±3.473E-03 1.841E-01±1.130E-04 5.319E-01±1.146E-01 2.015E-00±4.387E-02 1.839E-01±1.729E-04 5.830E-01±1.792E-04 1.983E-00±5.979E-02 1.842E-01±6.274E-05

4 結(jié)語

隨著大數(shù)據(jù)時代的來臨，多樣化的信息數(shù)以萬計的產(chǎn)生，多目標優(yōu)化問題越來越多，各種約束條件越來越復(fù)雜，搜索空間也越來越大，這對多目標優(yōu)化而言是一個巨大的挑戰(zhàn)，也是一個發(fā)展的機遇。本文所提出的多目標鯨魚優(yōu)化算法將反向精英保留機制應(yīng)用到產(chǎn)生初始解和迭代進化，將帕累托最優(yōu)解集中的優(yōu)質(zhì)解用于種群的進化引導(dǎo)，再應(yīng)用帕累托等級排序和擁擠度距離對種群進行排序，以便選出前N個個體維持種群數(shù)量的穩(wěn)定，最后在鯨魚捕食和移動的過程中增加Levy變異。研究數(shù)據(jù)結(jié)果表明，本文的RLMOWOA算法相對于其他四種算法在IGD和HV上都有著顯著的優(yōu)勢，三種改進機制的引入極大改善了算法的全局尋優(yōu)能力，證明了多目標鯨魚優(yōu)化算法有著較大的探索價值。未來的研究工作將從以下兩個方面進行：①研究RLMOWOA與其他模型的結(jié)合，將多目標鯨魚優(yōu)化算法應(yīng)用到模型中去改善其他模型的不足。②對多目標鯨魚優(yōu)化算法進行多方面的改進，使其適應(yīng)未來更加復(fù)雜的多目標問題。