精英反向黃金正弦海洋捕食者算法*

張 磊,劉 升,高文欣,郭雨鑫

(上海工程技術(shù)大學(xué)管理學(xué)院,上海 201620)

1 引言

海洋捕食者算法MPA(Marine Predators Algorithm)[1]是一種新穎的群智能算法。該算法已被成功地用于處理多級圖形分割[2]、預(yù)測新冠肺炎的病例數(shù)[3]、提高冷熱電聯(lián)產(chǎn)系統(tǒng)在環(huán)境、熱力學(xué)和經(jīng)濟(jì)學(xué)方面的性能[4]等。

為了使海洋捕食者算法具有更加出色的性能，國外的部分研究人員對該算法進(jìn)行了有效的改進(jìn)。文獻(xiàn)[5]將海洋捕食者算法與教與學(xué)的優(yōu)化算法相結(jié)合，避免了算法過早地收斂。文獻(xiàn)[6]將高質(zhì)量解的位置通過自適應(yīng)變異操作進(jìn)行改進(jìn)，而低質(zhì)量解的位置則根據(jù)最優(yōu)解的位置和從種群中選出的高質(zhì)量解的位置進(jìn)行更新，提升了算法的性能。

由于海洋捕食者算法提出的時間還不長，人們對其的認(rèn)識和研究還不夠深入。本文針對其求解準(zhǔn)確度低和穩(wěn)定性差等特點，采用精英反向?qū)W習(xí)和黃金正弦來改進(jìn)海洋捕食者算法，使得基本算法的魯棒性和計算精度得到提升。

2 海洋捕食者算法

2.1 初始化

MPA通過式(1)生成初始種群：

X0=Xmin+rand(Xmax-Xmin)

(1)

其中，Xmax和Xmin分別是解空間的上界和下界；rand是[0,1]的隨機(jī)數(shù)。

精英捕食者的矩陣表示E和獵物的矩陣表示P分別如式(2)和式(3)所示：

(2)

(3)

其中，N表示種群規(guī)模，D為種群中個體的維度。

2.2 探索階段

當(dāng)?shù)螖?shù)小于迭代總次數(shù)的三分之一時，算法處于探索階段，主要是為了探索搜索空間。在該階段中獵物的移動速度要比捕食者快，其數(shù)學(xué)模型如式(4)所示：

(4)

2.3 探索與開發(fā)之間的轉(zhuǎn)換

當(dāng)?shù)螖?shù)處于迭代總次數(shù)的前三分之一到三分之二時，算法處于探索與開發(fā)之間的轉(zhuǎn)換階段。在該階段中，捕食者的移動速度和獵物的相同,且前一半種群進(jìn)行萊維飛行狀負(fù)責(zé)開發(fā)，后一半種群進(jìn)行布朗運(yùn)動負(fù)責(zé)探索,如式(5)～式(7)所示：

i=1,2,…,N/2,

(5)

i=N/2+1,…,N,

(6)

(7)

其中，RL表示由萊維分布生成的隨機(jī)向量；CF是自適應(yīng)參數(shù)，用于調(diào)節(jié)捕食者運(yùn)動的步長。

2.4 開發(fā)階段

當(dāng)?shù)螖?shù)處于迭代總次數(shù)的后三分之一時，捕食者使用Lévy策略進(jìn)行開發(fā)，其數(shù)學(xué)模型如式(8)所示：

(8)

2.5 渦流形成和魚類聚集裝置的作用

魚類聚集裝置FAD(Fish Aggregating Device)等環(huán)境問題會對海洋捕食者造成影響，可看作是局部極值，采用如式(9)所示的數(shù)學(xué)模型消除部分影響:

(9)

其中，F(xiàn)FADs表示影響海洋捕食者減小局部極值影響的概率,取值為0.2；U是由0和1組成的向量；r是[0,1]的隨機(jī)數(shù)；Pr1和Pr2分別是從所有獵物矩陣中隨機(jī)選取的2個獵物。

3 融合精英反向黃金正弦的海洋捕食者算法

3.1 精英反向?qū)W習(xí)機(jī)制

反向?qū)W習(xí)機(jī)制OBL(Opposition-Based Learning)[7]的主要思想是同時計算并判斷候選解決方案和對應(yīng)的反向解決方案，并通過其適應(yīng)性值從中選擇最佳的候選解決方案。OBL策略能夠更有效地提高種群多樣性，并防止算法過早收斂。

OBL可以更好地擴(kuò)展種群的搜索范圍，提高算法性能。但是，OBL在生成其相反的解時具有一定的隨機(jī)性。相較于其相反的個體，每個隨機(jī)生成的候選者都有50%的概率遠(yuǎn)離問題的最佳解。

精英反向?qū)W習(xí)EOBL(Elite Opposition-Based Learning)[8]，以提高反向?qū)W習(xí)的求解質(zhì)量為目的。EOBL的主要思想是通過評估精英解決方案的相反解決方案來產(chǎn)生更有希望的解決方案。相反的解決方案更有可能位于全局最優(yōu)值所在的位置。這一機(jī)制已經(jīng)成功應(yīng)用于鯨魚算法[9]、正余弦算法[10]和哈里斯鷹算法[11]等的改進(jìn)。

(10)

(11)

3.2 黃金正弦算法

黃金正弦算法GSA(Golden Sine Algorithm)[12]結(jié)合使用正弦函數(shù)與黃金分割系數(shù)來進(jìn)行迭代搜索，具有優(yōu)秀的尋優(yōu)能力。

(12)

將黃金正弦算法融入到海洋捕食者算法中，按照式(13)更新海洋捕食者個體的位置：

Pi+1=Pi×|sin(R1)|+R2×sin(R1)×

|h1×Ei-h2×Pi|

(13)

其中，i=1,2,…,N/2;0≤it≤Max_iter。

綜上所述，融合精英反向?qū)W習(xí)和黃金正弦算法的海洋捕食者算法EGMPA(Elite opposition-based Golden-Sine Marine Predators Algorithm)的偽代碼如下所示：

EGMPA偽代碼

1.初始化種群;

2.While終止條件不滿足

3. 計算適應(yīng)度，構(gòu)造精英矩陣;

4. 生成反向種群OP={};

5. 根據(jù)lbj=min(Xi,j)和ubj=max(Xi,j), 計算個體的搜索邊界;

7. 從當(dāng)前種群和OP種群中選擇適應(yīng)值較好的個體作為新一代種群；

8.IfIter

9. 根據(jù)式(4)和式(13)更新獵物矩陣;

10.ElseifMax_Iter/3≤Iter<2*Max_Iter/3

11.對于前半部分種群(i=1,…,N/2), 根據(jù)式(5)和式(13)更新獵物矩陣;

12.對于后半部分種群(i=N/2,…,N), 根據(jù)式(6)和式(13)更新獵物矩陣;

13.ElseifIter≥2*Max_Iter/3

14.根據(jù)式(8)和式(13)更新獵物矩陣;

15.Endif

16. 完成精英矩陣的更新；

17. 應(yīng)用FADs效果和基于式(9)進(jìn)行更新；

18.Endwhile

3.3 EGMPA的時間復(fù)雜度分析

海洋捕食者種群規(guī)模是N，搜索空間的維度是D，最大迭代次數(shù)是Max_iter，那么原始的海洋捕食者算法的時間復(fù)雜度是O(N×D×Max_iter)。EGMPA算法中，精英反向?qū)W習(xí)策略的時間復(fù)雜度是O(N×D)，計算適應(yīng)度值的時間復(fù)雜度是O(N×D)，計算個體位置更新的時間復(fù)雜度是O(N×D)，則EGMPA的時間復(fù)雜度為O(N×D×Max_iter)。EGMPA算法的時間復(fù)雜度與基本的MPA算法的相同，說明2種改進(jìn)策略沒有增加海洋捕食者算法的計算負(fù)擔(dān)。

4 仿真實驗與結(jié)果分析

4.1 初始參數(shù)設(shè)置

本文選取鯨魚優(yōu)化算法WOA(Whale Optimization Algorithm)[13]、哈里斯鷹優(yōu)化算法HHO(Harris Hawks Optimization)[14]、海洋捕食者算法MPA、僅引入精英反向?qū)W習(xí)的海洋捕食者算法EMPA(EOBL Marine Predators Algorithm)、僅引入黃金正弦的海洋捕食者算法GMPA(GSA Marine Predators Algorithm)與精英反向?qū)W習(xí)和黃金正弦的海洋捕食者算EGMPA進(jìn)行比較。初始種群數(shù)量都設(shè)定為30，最大迭代次數(shù)都設(shè)定為500。

4.2 測試函數(shù)

本文選取12個常用的基準(zhǔn)測試函數(shù)對各算法進(jìn)行性能測試，函數(shù)的相關(guān)屬性如表1所示。

Table 1 Test functions表1 測試函數(shù)

4.3 實驗結(jié)果分析

上述每種算法在每個基準(zhǔn)測試函數(shù)上分別運(yùn)行30次求平均值，實驗結(jié)果如表2所示。

Table 2 Test results表2 測試結(jié)果

從表2可以看到，對于12個測試函數(shù)，EGMPA在最優(yōu)值、平均值和標(biāo)準(zhǔn)差的求解結(jié)果上比MPA、EMPA、GMPA、WOA和HHO都要好。對于測試函數(shù)f1，EGMPA可計算得到最優(yōu)值0；對于測試函數(shù)f2～f4，EGMPA計算得到的最優(yōu)值和平均值要比其他5種算法高出100多個數(shù)量級，標(biāo)準(zhǔn)差為0，魯棒性更好；對于測試函數(shù)f5，很難計算得到全局最優(yōu)值，EGMPA計算的平均值比EMPA高出13個數(shù)量級，比HHO高出18個數(shù)量級，比MPA、GMPA和WOA高出22個數(shù)量級；對于測試函數(shù)f6和f7，EGMPA的尋優(yōu)結(jié)果比其他5種算法都要好。對于函數(shù)f8～f12，EGMPA尋優(yōu)的精度和魯棒性是最優(yōu)的。上述表明精英反向?qū)W習(xí)和黃金正弦2種方法對MPA的優(yōu)化效果是明顯的。

圖1展示了所用測試函數(shù)的收斂曲線，更清楚地表明了EGMPA的尋優(yōu)效果。

Figure 1 Convergence curves圖1 收斂曲線圖

從圖1可知，改進(jìn)的EGMPA收斂精度和收斂速度都要優(yōu)于MPA、EMPA、GMPA、WOA和HHO,說明引入2種策略的EGMPA優(yōu)于單一策略改進(jìn)的海洋捕食者算法，具有優(yōu)秀的尋優(yōu)能力。

4.4 統(tǒng)計檢驗與MAE 排序

在對上述6種算法的計算能力的比較中，只采用最優(yōu)值、平均值和標(biāo)準(zhǔn)差這3個指標(biāo)來評價是不充分的，因此本文采用了Wilcoxon秩和檢驗來檢驗,結(jié)果如表3所示。當(dāng)p<0.05時，說明2種算法的尋優(yōu)效果有差異，反之則沒有。

Table 3 Test results of Wilcoxon rank sum 表3 Wilcoxon秩和檢驗結(jié)果

從表3可以看出，對于除了函數(shù)f7、f8、f9和f10外的所有函數(shù)，EGMPA與其他算法之間的p值都遠(yuǎn)小于0.05，說明EGMPA具有更好的尋優(yōu)性能;對于函數(shù)f7，EGMPA的尋優(yōu)結(jié)果略優(yōu)于GMPA的。表3中出現(xiàn)的NaN，表示相應(yīng)算法都找到了全局最優(yōu)值。

平均絕對誤差MAE(Mean Absolute Error)[15]表示結(jié)果與實際值之間差值的絕對值的平均值。MAE的數(shù)學(xué)定義如式(14)所示:

(14)

其中，mi是每種算法在每個測試函數(shù)上計算得到最優(yōu)解的平均值，ki是每個測試函數(shù)的理論最優(yōu)值，n是測試函數(shù)的個數(shù)。MAE的數(shù)值越小，算法的計算性能越高。根據(jù)MAE值對各算法的排序結(jié)果如表4所示。

Table 4 Sort results by MAE 表4 MAE排序結(jié)果

從表4可知，EGMPA的MAE值最小，說明EGMPA的尋優(yōu)性能更優(yōu)。

4.5 求解CEC2017實驗

IEEE CEC 2017測試集的具體信息見參考文獻(xiàn)[16]。不失一般性，本文在CEC 2017 基準(zhǔn)函數(shù)中選取部分單峰、多峰、混合和復(fù)合類型的函數(shù)來驗證本文算法的性能。將精英反向?qū)W習(xí)黃金正弦的海洋捕食者算法EGMPA與基本的海洋捕食者算法MPA、基于教與學(xué)的海洋捕食者算法TLMPA(Teaching-Learning-based Marine Predators Algorithm)[3]、粒子群優(yōu)化PSO(Particle Swarm Optimization)算法[17]、黃金正弦算法GSA[12]的結(jié)果進(jìn)行比較。為了提高可靠性并產(chǎn)生具有統(tǒng)計意義的結(jié)果，在該驗證測試中，所有算法的種群規(guī)模都設(shè)置為20，維數(shù)為30，每種算法都運(yùn)行30次，函數(shù)的最大迭代次數(shù)為50 000。表5顯示了5種算法在12個CEC2017函數(shù)上的實驗結(jié)果，加粗?jǐn)?shù)據(jù)表示每個測試函數(shù)對應(yīng)的最佳結(jié)果。

Table 5 Comparison of optimization results of benchmark functions in CEC 2017表5 CEC 2017中基準(zhǔn)函數(shù)的優(yōu)化結(jié)果對比

由表5可知，EGMPA在大多數(shù)CEC2017函數(shù)上的尋優(yōu)結(jié)果都優(yōu)于其他4種對比算法的，且取得了較小的標(biāo)準(zhǔn)差，表明了EGMPA的有效性和魯棒性。

5 結(jié)束語

本文提出了精英反向?qū)W習(xí)黃金正弦的海洋捕食者算法，融入精英反向?qū)W習(xí)機(jī)制，使得海洋捕食者算法中的種群質(zhì)量得到大幅提高，提高了尋優(yōu)的精度；將海洋捕食者算法和黃金正弦算法相融合，采用黃金分割系數(shù)減小海洋捕食者的搜索空間，提高了尋找到最優(yōu)值的效率。采用經(jīng)典基準(zhǔn)函數(shù)和CEC2017函數(shù)對改進(jìn)后的海洋捕食者算法進(jìn)行了驗證。實驗結(jié)果顯示，精英反向?qū)W習(xí)和黃金正弦2種策略大幅提升了海洋捕食者算法的尋優(yōu)精度和魯棒性。