融合鯨魚泡泡網(wǎng)機制的SSA算法

冉 琳，潘大志，馮世強

（西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院，四川 南充 637009）

0 引 言

受大自然的啟發(fā)，群智能優(yōu)化算法（Intelligence Optimization Algorithm，IOA）一般是通過對自然界中各種生物的進化過程與物理現(xiàn)象進行研究而形成的一種迭代尋優(yōu)搜索算法。近年來，涌現(xiàn)了一些新的群智能優(yōu)化算法，比如：蛾群算法（moth swarm algorithm，MSA）、哈里斯鷹優(yōu)化算法（harris hawks optimization，HHO）、布 谷 鳥 搜 索 算 法（cukoo search algorithm，CSA）、螢 火 蟲 算 法（firefly algorithm，F(xiàn)A）、蝙蝠算法（bat algorithm，BA）等。麻雀搜索算法是受自然界中麻雀搜索食物與反捕食行為的啟發(fā)，于2019年由薛建凱提出。為使麻雀搜索算法尋優(yōu)效果更好，學(xué)者們主要通過2個方面對其進行改進。一方面，根據(jù)麻雀搜索算法本身的特性進行改進；另一方面，通過將2種或多種智能算法與麻雀搜索算法進行融合，從而達到改進SSA算法的目的。目前，已有許多學(xué)者對麻雀搜索算法展開了進一步的研究：王海瑞等人將Levy飛行策略和柯西高斯變異引入麻雀搜索算法，增加算法搜索方向的多樣性，同時也加強了局部搜索能力；呂鑫等人將高斯變異方法引入SSA算法，提高了搜索精度以及加強了算法跳出局部的能力；柳長安等人利用螢火蟲機制，對最優(yōu)解進行擾動變異，從而增加種群多樣性；湯安迪等人通過引入正余弦算法和線性遞減策略，協(xié)調(diào)局部和全局搜索能力；李敦橋?qū)⒛M退火算法的Metropolis準(zhǔn)則融入SSA算法中，使算法跳出局部最優(yōu)。針對麻雀搜索算法迭代過程中，種群多樣性減少，以及容易陷入局部最優(yōu)解等缺點，本文根據(jù)Tent混沌映射初始化麻雀種群，增加種群多樣性，融合鯨魚優(yōu)化算法中的鯨魚泡泡網(wǎng)捕食數(shù)學(xué)模型，在搜索過程中，更新麻雀種群中發(fā)現(xiàn)者的位置，最后按自適應(yīng)分布變異方式，加強了算法跳出局部的能力。

1 麻雀搜索算法

在麻雀種群中，麻雀分為發(fā)現(xiàn)者、加入者和警戒者三種類型。其中，發(fā)現(xiàn)者引導(dǎo)種群覓食，加入者通過發(fā)現(xiàn)者得到食物，發(fā)現(xiàn)者和加入者都有可能是警戒者。

在麻雀搜索算法（SSA）算法中，麻雀個體的適應(yīng)度值決定能源高低，發(fā)現(xiàn)者具有較多能源，引領(lǐng)加入者搜尋食物。發(fā)現(xiàn)者有如下位置更新：

發(fā)現(xiàn)者與加入者的身份可以根據(jù)擁有能源的多少而改變，但每種類型麻雀的占比不變。加入者的位置更新公式為：

警戒者由整個種群隨機產(chǎn)生10%到20%，位置更新的數(shù)學(xué)表達式：

2 改進麻雀算法

2.1 Tent混沌映射

基本SSA算法利用隨機初始化種群，這種方法會導(dǎo)致迭代過程中種群多樣性減少。由于混沌映射具有全局遍歷性、容易實現(xiàn)和隨機性等特點，故本文采用基于Tent混沌映射初始化種群，以提高種群多樣性和麻雀搜索的遍歷性。Tent映射數(shù)學(xué)公式如下：

2.2 基于鯨魚泡泡網(wǎng)捕食機制更新麻雀發(fā)現(xiàn)者位置

鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）是近幾年來群智能優(yōu)化算法中出現(xiàn)的一種新算法，本文結(jié)合WOA算法中泡泡網(wǎng)捕食中的收縮包圍機制和螺旋式位置更新機制，用以更新麻雀發(fā)現(xiàn)者的位置，以提高SSA算法的全局搜索能力。

融合后的麻雀發(fā)現(xiàn)者的更新位置公式為：

2.3 自適應(yīng)t分布變異

分布的曲線形態(tài)與自由度參數(shù)的大小有關(guān)。當(dāng)1時，分布是標(biāo)準(zhǔn)的柯西分布；當(dāng)→∞時，分布是標(biāo)準(zhǔn)的高斯分布。分布的概率密度函數(shù)為：

在算法的初始階段，分布近似于柯西分布變異，此時分布的全局搜索能力較強；在算法運行中期，分布變異逐漸由柯西分布變異向高斯分布變異過渡，提高了算法平衡全局搜索與局部開發(fā)的能力；在算法運行的后期階段，由于→∞，分布近似于高斯分布，此時分布的局部開發(fā)能力較強。

其中，X 表示分布變異后的麻雀個體位置，（）表示基于迭代次數(shù)為參數(shù)的分布。

2.4 改進麻雀算法

針對麻雀優(yōu)化算法的不足，首先利用Tent混沌映射初始化種群，提高初始解的質(zhì)量；在改進麻雀算法（WSSA）中，為提高尋優(yōu)效果，利用鯨魚泡泡網(wǎng)機制擾動發(fā)現(xiàn)者位置更新，使得改進后算法更有利于平衡局部開發(fā)和全局搜索；最后，利用自適應(yīng)分布變異更新位置，提高算法跳出局部最優(yōu)的能力。具體實現(xiàn)步驟如下：

設(shè)置參數(shù)，預(yù)警值、發(fā)現(xiàn)者比例、意識到危險麻雀的比重。

基于Tent混沌映射初始化種群。

計算麻雀個體適應(yīng)度值并排序。

利用式（5）更新麻雀發(fā)現(xiàn)者位置。

利用式（2）對加入者位置進行更新。

利用式（3）對警戒者位置進行更新。

對種群中的越界個體做越界處理。若新適應(yīng)度值優(yōu)于舊值，則更新位置和適應(yīng)度值，反之保留。

利用式（7）對麻雀個體的位置進行分布變異，對越界個體做越界處理，并更新麻雀個體位置、適應(yīng)度值以及對適應(yīng)度值排序。

判斷當(dāng)前迭代次數(shù)是否達到，若已達到，則循環(huán)結(jié)束并輸出結(jié)果，反之返回Step 3。

3 實驗與仿真

3.1 標(biāo)準(zhǔn)測試函數(shù)

表1分別給出了標(biāo)準(zhǔn)測試函數(shù)的公式、維數(shù)以及搜索區(qū)間。這些標(biāo)準(zhǔn)測試函數(shù)被用于測試算法的可行性、穩(wěn)定性。

表1 標(biāo)準(zhǔn)測試函數(shù)Tab.1 Standard test functions

3.2 參數(shù)設(shè)置

在本文中，將各個算法的最大迭代次數(shù)設(shè)置為1 000，種群規(guī)模設(shè)定為100，即100。在灰狼優(yōu)化算法（Grey Wolf Optimizer，GWO）中，是從2線性遞減至0，∈［0，1］，∈［0，1］；將引力搜索算法（Gravitation Search Algorithm，GSA）的參數(shù)設(shè)置為100，20；將麻雀搜索算法（Sparrow Search Algorithm，SSA）以及本文的改進麻雀算法（WSSA）的參數(shù)設(shè)置為：發(fā)現(xiàn)者占麻雀種群的0.2，警戒者占0.1，安全閾值0.8。避免程序運行一次出現(xiàn)誤差，本文在實驗仿真階段運行30次來獲得標(biāo)準(zhǔn)測試函數(shù)的最優(yōu)值、均值以及標(biāo)準(zhǔn)差，以反映算法的收斂性、精確度和穩(wěn)定性。

實驗環(huán)境：Windows 10，CPU為Intel（R）Core（TM）i5-10210U CPU＠1.60 GHz 2.11 GHz，內(nèi)存16 G，Matlab 2018a。

3.3 與其他算法對比

因為單峰測試函數(shù)有且僅有一個全局最優(yōu)解，并沒有局部最優(yōu)解，故用單峰測試函數(shù)檢驗算法的局部開發(fā)能力。與單峰測試函數(shù)不同的是，多峰測試函數(shù)具有多個局部極值點，搜索全局最優(yōu)值的難度較大，但是能夠測試出算法的搜索能力。表2給出了引力搜索算法（GSA）、灰狼優(yōu)化算法（GWO）、哈里斯鷹算法（HHO）、麻雀搜索算法（SSA）以及本文的改進麻雀搜索算法（WSSA），在獨立運行了30次后的實驗結(jié)果。圖1～圖8則分別給出了在測試函數(shù)上5種算法的收斂曲線。

圖8 函數(shù)f8的對比曲線Fig.8 Comparison curve of function f8

表2 測試函數(shù)優(yōu)化結(jié)果Tab.2 Test function optimization results

圖1 函數(shù)f1的對比曲線Fig.1 Comparison curve of function f1

圖2 函數(shù)f2的對比曲線Fig.2 Comparison curve of function f2

圖3 函數(shù)f3的對比曲線Fig.3 Comparison curve of function f3

圖4 函數(shù)f4的對比曲線Fig.4 Comparison curve of function f4

圖5 函數(shù)f5的對比曲線Fig.5 Comparison curve of function f5

圖6 函數(shù)f6的對比曲線Fig.6 Comparison curve of function f6

圖7 函數(shù)f7的對比曲線Fig.7 Comparison curve of function f7

3.4 結(jié)果分析

表2中給出了灰狼優(yōu)化算法（GWO）、引力搜索算法（GSA）、麻雀搜索算法（SSA）、哈里斯鷹算法（HHO）以及本文的改進麻雀搜索算法（WSSA），對于8個標(biāo)準(zhǔn)測試函數(shù)在獨立運行了30次后的優(yōu)化結(jié)果，、、分別表示運行30次后所得到的最優(yōu)解、均值以及標(biāo)準(zhǔn)差，最優(yōu)解在表2中已加粗。

從表2可以得出，引力搜索算法（GSA）的解的質(zhì)量較差，灰狼優(yōu)化算法（GWO）對于函數(shù)、可獲得最優(yōu)解，就收斂速度而言，GWO算法對于函數(shù)、、，優(yōu)于HHO算法和GSA算法，次于SSA算法和WSSA算法。哈里斯鷹算法（HHO）相較于GSA算法、GWO算法的尋優(yōu)結(jié)果更好，對于函數(shù)，HHO算法尋優(yōu)結(jié)果比SSA算法的好，說明此時HHO算法的局部開發(fā)能力更優(yōu)，且對于函數(shù)，雖然HHO算法的收斂速度次于SSA算法和WSSA算法，但也能搜索到最優(yōu)解。SSA算法相比于GSA算法、GWO算法和HHO算法，總體來說，收斂速度更快、尋優(yōu)結(jié)果更好，這說明SSA算法在跳出局部極值點和全局搜索能力方面都要強于GWO算法、GSA算法和HHO算法。WSSA算法對于函數(shù)，成功地找到了全局最優(yōu)解，且最優(yōu)解、最優(yōu)解均值、標(biāo)準(zhǔn)差都比GSA算法、GWO算法、HHO算法以及SSA算法好，表現(xiàn)出了很好的平衡局部與全局、跳出局部極值的能力。

為說明算法的收斂性，圖1～圖8中給出了5種算法對于標(biāo)準(zhǔn)測試函數(shù)在獨立運行30次后所得最優(yōu)結(jié)果的收斂性能對比圖。在基本麻雀搜索的基礎(chǔ)上，因為改變了麻雀發(fā)現(xiàn)者的位置更新和加入了自適應(yīng)分布變異，改進后的算法不僅能夠平衡局部和全局搜索，在收斂速度方面也優(yōu)于其他4種算法。綜上所述，WSSA算法具有穩(wěn)定性較強、收斂速度較快等特點。

4 結(jié)束語

本文針對基本SSA算法易陷入局部極值、后期種群多樣性減少等缺陷，提出了一種融合鯨魚優(yōu)化算法和自適應(yīng)分布變異的麻雀搜索算法（WSSA）。在SSA算法中，基于Tent混沌映射初始化種群，對發(fā)現(xiàn)者的位置融入鯨魚優(yōu)化算法的泡泡網(wǎng)捕食機制進行更新，以平衡局部開發(fā)與全局搜索能力；加入自適應(yīng)分布變異，增強算法跳出停滯的能力。但對于發(fā)現(xiàn)者、加入者、意識到危險麻雀的位置更新公式可做進一步改進。還可以將算法運用到實際問題中，如背包問題等，這也是接下來要解決的問題。