冉 琳，潘大志，馮世強(qiáng)

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

0 引 言

受大自然的啟發(fā)，群智能優(yōu)化算法（Intelligence Optimization Algorithm，IOA）一般是通過對(duì)自然界中各種生物的進(jìn)化過程與物理現(xiàn)象進(jì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個(gè)方面對(duì)其進(jìn)行改進(jìn)。一方面，根據(jù)麻雀搜索算法本身的特性進(jìn)行改進(jìn)；另一方面，通過將2種或多種智能算法與麻雀搜索算法進(jìn)行融合，從而達(dá)到改進(jìn)SSA算法的目的。目前，已有許多學(xué)者對(duì)麻雀搜索算法展開了進(jìn)一步的研究：王海瑞等人將Levy飛行策略和柯西高斯變異引入麻雀搜索算法，增加算法搜索方向的多樣性，同時(shí)也加強(qiáng)了局部搜索能力；呂鑫等人將高斯變異方法引入SSA算法，提高了搜索精度以及加強(qiáng)了算法跳出局部的能力；柳長(zhǎng)安等人利用螢火蟲機(jī)制，對(duì)最優(yōu)解進(jìn)行擾動(dòng)變異，從而增加種群多樣性；湯安迪等人通過引入正余弦算法和線性遞減策略，協(xié)調(diào)局部和全局搜索能力；李敦橋?qū)⒛M退火算法的Metropolis準(zhǔn)則融入SSA算法中，使算法跳出局部最優(yōu)。針對(duì)麻雀搜索算法迭代過程中，種群多樣性減少，以及容易陷入局部最優(yōu)解等缺點(diǎn)，本文根據(jù)Tent混沌映射初始化麻雀種群，增加種群多樣性，融合鯨魚優(yōu)化算法中的鯨魚泡泡網(wǎng)捕食數(shù)學(xué)模型，在搜索過程中，更新麻雀種群中發(fā)現(xiàn)者的位置，最后按自適應(yīng)分布變異方式，加強(qiáng)了算法跳出局部的能力。

1 麻雀搜索算法

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

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

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

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

2 改進(jìn)麻雀算法

2.1 Tent混沌映射

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

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

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

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

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

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

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

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

2.4 改進(jìn)麻雀算法

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

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

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

計(jì)算麻雀?jìng)€(gè)體適應(yīng)度值并排序。

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

利用式（2）對(duì)加入者位置進(jìn)行更新。

利用式（3）對(duì)警戒者位置進(jìn)行更新。

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

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

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

3 實(shí)驗(yàn)與仿真

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

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

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

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

在本文中，將各個(gè)算法的最大迭代次數(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）以及本文的改進(jìn)麻雀算法（WSSA）的參數(shù)設(shè)置為：發(fā)現(xiàn)者占麻雀種群的0.2，警戒者占0.1，安全閾值0.8。避免程序運(yùn)行一次出現(xiàn)誤差，本文在實(shí)驗(yàn)仿真階段運(yùn)行30次來獲得標(biāo)準(zhǔn)測(cè)試函數(shù)的最優(yōu)值、均值以及標(biāo)準(zhǔn)差，以反映算法的收斂性、精確度和穩(wěn)定性。

實(shí)驗(yà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 與其他算法對(duì)比

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

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

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

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

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

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

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

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

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

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

3.4 結(jié)果分析

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

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

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

4 結(jié)束語(yǔ)

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