多策略增強型麻雀搜索算法

陳建東　聶斌　雷銀香　張玉超　陳星鑫　苗震

摘? 要：為進一步提升麻雀搜索算法（SSA）的收斂速度和求解精度，并且針對麻雀種群的全局搜索能力較弱和在迭代后期易陷入局部最優(yōu)的問題，提出一種多策略增強型的麻雀搜索算法（MESSA）。首先，采用Bernoulli映射初始化種群，保證種群的多樣性和均勻性，提升算法的收斂速度。其次，引入Levy飛行來增強麻雀種群中個體發(fā)現(xiàn)者的全局搜索能力。然后，引入交叉優(yōu)化算法，幫助麻雀種群陷入停滯時擺脫停滯狀態(tài)，跳出局部最優(yōu)的同時提升求解精度。通過9個基準函數(shù)實驗證明MESSA能提升SSA的性能。

關鍵詞：麻雀搜索算法；Bernoulli映射；Levy飛行；交叉優(yōu)化算法；特征選擇

中圖分類號：TP18? 文獻標識碼：A? ? ? 文章編號：2096-4706（2023）13-0039-08

Multi-Strategy Enhanced Sparrow Search Algorithm

CHEN Jiandong， NIE Bin， LEI Yinxiang， ZHANG Yuchao， CHEN Xingxin， MIAO Zhen

（College of Computer Science， Jiangxi University of Chinese Medicine， Nanchang? 330004， China）

Abstract： A Multi-Strategy Enhanced Sparrow Search Algorithm （MESSA） is proposed to further improve the convergence speed and solution accuracy of the Sparrow Search Algorithm （SSA）， as well as to address the problems of the sparrow population's weak global search ability and the tendency to fall into local optimum in the late iteration. Firstly， Bernoulli mapping is used to establish the population in order to ensure population diversity and homogeneity while also increasing the algorithm's convergence speed. Secondly， Levy flight is introduced to improve individual discoverers' global search ability in the sparrow population. Then， the Crossover Optimization Algorithm is introduced to assist the sparrow population in breaking free from the stagnation stage， jumping out of the local optimal， and boosting solving accuracy. Nine benchmark function experiments demonstrate that MESSA can improve the performance of SSA.

Keywords： Sparrow Search Algorithm; Bernoulli mapping; Levy flight; Crossover Optimization Algorithm; feature selection

0? 引? 言

麻雀搜索算法（Sparrow Search Algorithm， SSA）是由薛建凱等[1]在2020年提出的新型群體智能算法，靈感來源于麻雀的覓食行為和反覓食行為。麻雀搜索算法具備結構簡單、控制參數(shù)少、求解精度高等優(yōu)點。李雅麗等[2]通過對比實驗證明麻雀搜索算法的穩(wěn)定性和收斂精度領先于其他五種新型智能算法。因此，作為一種有潛力的優(yōu)化算法，SSA已經(jīng)被廣泛應用到各個研究領域中。Yuan等[3]針對光伏微電網(wǎng)系統(tǒng)局部陰影下功率失配損失的問題，提出一種基于改進麻雀搜索算法（ISSA）的分布式最大功率點跟蹤方法，能更準確、更快速地跟蹤最大功率點，具有良好的穩(wěn)態(tài)性能。Liu等[4]提出了一種改進的麻雀搜索算法 CASSA 來建立3d任務空間模型和無人機路徑規(guī)劃成本函數(shù)，將路徑規(guī)劃問題轉(zhuǎn)化為多維函數(shù)優(yōu)化問題，實驗證明在考慮各種約束條件下能更有效地解決無人機路線規(guī)劃問題。Zhu等[5]提出了一種稱為自適應麻雀搜索算法（ASSA）的新優(yōu)化算法，用于質(zhì)子交換膜燃料電池（PEMFC）電堆的最佳模型參數(shù)識別，實驗證明所提出的ASSA具有最佳效率。

與大多數(shù)智能優(yōu)化算法相比，SSA在問題優(yōu)化方面有一定優(yōu)勢，但是，依然存在尋優(yōu)精度較低，在搜索接近全局最優(yōu)時，存在種群的多樣性減少，容易陷入局部最優(yōu)等問題。針對這些問題，許多學者提出了改進策略。李愛蓮等[6]提出了一種融合正余弦和柯西變異的麻雀搜索算法，實驗結果證明改進后的SSA在收斂速度和尋優(yōu)精度有明顯增強，表現(xiàn)出良好的魯棒性。Cheng等[7]提出了一種學習麻雀搜索算法，在CEC2017測試函數(shù)和基準函數(shù)上取得了良好的效果，在一定程度上避免了算法陷入局部最優(yōu)的問題。Yan等[8]提出一種基于迭代局部搜索的改進麻雀搜索算法，在基準測試函數(shù)和 CEC2017函數(shù)上的實驗表明，該算法提升了搜索精度，并且在算法陷入局部最優(yōu)時有跳出局部最優(yōu)的能力。

雖然上述學者都對SSA提出了改進，但SSA仍然存在易陷入局部最優(yōu)和尋優(yōu)精度不高的問題。因此，本文通過引入Bernoulli映射、Levy飛行策略和交叉優(yōu)化算法對SSA進行改進，提出一種融合多策略的增強型麻雀搜索算法（Multi-strategy enhanced sparrow search algorithm， MESSA），提升SSA性能的同時增強SSA跳出局部最優(yōu)的能力。

1? 麻雀搜索算法概述

麻雀搜索算法主要模擬了麻雀群體覓食的過程，麻雀們在覓食的過程中有三種行為策略：發(fā)現(xiàn)者、跟隨者和警戒者。其中適應度較高的麻雀作為發(fā)現(xiàn)者，負責搜索食物，10%～20%的個體被隨機分配為跟隨者，跟隨發(fā)現(xiàn)者獲取食物，警戒者對環(huán)境威脅保持警惕并警告麻雀種群向安全區(qū)域靠近。麻雀搜索算法的主要步驟如下：

1）初始化麻雀種群位置。由n只麻雀種群的初始位置在d維解空間內(nèi)表達如式（1）所示：

其中，n表示麻雀個體數(shù)量，n表示待優(yōu)化問題的變量維度。通過該矩陣可求出初始種群的適應度值如式（2）所示。

其中，F(xiàn)表示適應度值，f表示求取適應度值的函數(shù)。

2）種群中發(fā)現(xiàn)者負責尋找食物的方向和位置，并帶領跟隨者向食物方向靠近。種群中發(fā)現(xiàn)者位置更新如下：

其中t表示當前迭代次數(shù)，tmax表示最大迭代次數(shù)，ST是預設的安全閾值，R2表示預警值。 表示第i個麻雀在第j維的個體位置。α ∈（0，1）是一個隨機數(shù)。Q表示服從正態(tài)分布的隨機數(shù)。當R2＜ST時，這表明此時種群環(huán)境是安全的，周圍沒有發(fā)現(xiàn)捕食者，發(fā)現(xiàn)者可以進行廣泛的搜索，當R2≥ST時，表示群內(nèi)個體已發(fā)現(xiàn)捕食者并發(fā)出警報，群內(nèi)所有個體將進行反捕食行動，發(fā)現(xiàn)者將引導追隨者至安全位置。

3）為了獲得優(yōu)質(zhì)的食物，跟隨者追隨發(fā)現(xiàn)者或獨自覓食，跟隨者的位置更新如式（4）所示：

其中， 表示第t + 1代跟隨者所處最佳位置， 表示當前適應度最差的位置，A表示一個1×d維的矩陣，這個矩陣中每個元素隨機賦值為1或-1，其中 。當i＞n/2時，這表明適應性較差的第i個跟隨者沒有得到食物，非常饑餓，需要飛到別處獲取更多能量；當i≤n/2時，追隨者監(jiān)視發(fā)現(xiàn)者并與更高的捕食者競爭食物，從而增加他們的能量。

4）警戒者是在種群中隨機選擇的個體。當感知到危險時，它們會發(fā)出信號讓麻雀逃到安全的位置。警戒者的位置更新公式如式（5）所示：

式（5）中， 表示當前全局最優(yōu)值，α為控制步長參數(shù)，服從標準正態(tài)分布，β表示-1和1之間的隨機數(shù)，fi表示當前麻雀的適應度值，fg和fw分別表示當前搜索范圍內(nèi)的最佳和最差適應度值，ε是防止分母為0的最小實數(shù)。當fi ≠ fg時，表示麻雀是處于種群邊界，容易受到捕食者的攻擊，因此需要調(diào)整位置。當fi = fg時，這表明種群中的麻雀個體意識到了危險，需要靠近其他麻雀以避免危險。

2? 融合多種策略的增強型麻雀搜索算法

2.1? Bernoulli映射

Kazimipour等人[9]指出一個好的初始種群會影響著演化算法尋找全局最優(yōu)的進程，如加速種群收斂，提高最終解的精度。現(xiàn)有的種群初始化技術主要分為隨機性、組合性和通用性這三類。而大多數(shù)群體智能算法都采用隨機性算法生成初始種群。

隨機性算法進一步分為兩類，分別是偽隨機數(shù)生成和混沌映射。在原始麻雀搜索算法中，就是采用偽隨機數(shù)的方式產(chǎn)生初始種群，但是這種方法遍歷性較低，并且個體分布不均勻，具有不可預測性，在一定程度上影響了算法的性能[10]?；煦缋碚撝饕芯繉Τ跏紶顟B(tài)特別敏感的動力系統(tǒng)的行為，其主要屬性包括：遍歷性、隨機性和規(guī)律性。和偽隨機數(shù)相比，混沌映射產(chǎn)生的混沌序列進行種群初始化可以生成更多樣化、更均勻的種群，能夠在種群多樣性、收斂性等方面提高群體智能算法的性能。

在圖1中展示了9種混沌映射經(jīng)過105迭代后的直方圖分布，可以發(fā)現(xiàn) Bernoulli映射相比其他混沌映射在[0，1]之間分布更加均勻。因此，本文在SSA 算法的初始化階段引入Bernoulli混沌映射，通過Bernoulli映射來初始化種群的位置，使得初始解盡可能均勻地分布在解空間內(nèi)。Bernoulli映射的數(shù)學表達式為：

其中λ = 0.4，z0 = 0.152，z = （x1，x2，x3，…，xd）表示Bernoulli映射產(chǎn)生的混沌系列，d表示維度。

結合Bernoulli映射生成的混沌序列，進一步生成搜索區(qū)域內(nèi)的麻雀個體初始位置序列 ：

其中? 和? 分別表示? 序列的最大值與最小值。

2.2? Levy飛行策略

注意到原始麻雀搜索算法式（3）中，當R2＞ST時，麻雀按正態(tài)分布隨機移動到最優(yōu)值附近，這種移動方式缺乏對于步長的有效控制，使得算法難以有效控制全局探索和局部開發(fā)進程。針對上述缺點，本文通過引入Levy飛行策略[11]來增強麻雀種群中個體發(fā)現(xiàn)者的隨機運動能力，使用隨機高頻短距離和低頻長距離步長來取代原有的移動到最優(yōu)解的方式，擴大麻雀種群在全局搜索中的搜索能力。結合Levy飛行后，麻雀發(fā)現(xiàn)者位置更新公式如下：

式（8）中，σ表示步長大小， 表示點乘。Levy（β）使用Mantegna算法進行模擬。由下式計算：

2.3? 交叉優(yōu)化算法

在SSA迭代后期，麻雀種群將快速聚集在最優(yōu)解附近，導致種群趨同性嚴重，算法停滯不前，進而增大算法陷入局部最優(yōu)值的概率[12]。交叉優(yōu)化算法（crisscross optimization algorithm）是2014年由An-bo Meng等人[13]提出的基于種群的隨機搜索算法，由橫向交叉和縱向交叉組成，在迭代過程中按順序執(zhí)行。CSO中的橫向交叉以一定的概率搜索每個超立方體的外圍，其次，引入縱向交叉的動機是為了在種群陷入停滯時擺脫停滯狀態(tài)。一旦個體的某個停滯維度在縱向交叉操作中跳出局部最小值，它將通過橫向交叉迅速傳播到整個群體。這反過來又有助于其他停滯維度在縱向交叉操作中盡快跳出局部最小值。因此，為進一步增強麻雀搜索算法跳出局部最優(yōu)的能力，提升求解精度，本文引入交叉優(yōu)化算法。下面將對橫向交叉和縱向交叉進行介紹。

2.3.1? 橫向交叉

橫向交叉是對群體中的兩個不同個體在相同維度上的算術交叉，在本文中，第i個警戒者麻雀父體? 和第j個警戒者麻雀父體? 在第d維上進行橫向交叉，它們的后代將由下式計算：

式（10）中，m1和m2是在[0，1]之間按照均勻分布隨機生成的值，n1和n2是[-1，1]之間按照均勻分布隨機生成的值。 和? 分別是? 和? 的第d維。 和? 分別是? 和 在第d維交叉后產(chǎn)生的后代。產(chǎn)生的后代將與父代進行競爭，最終保留適應度更高的麻雀個體。

2.3.2? 縱向交叉

縱向交叉是在兩個不同維度之間對個體進行的算術交叉，需要注意的是，此時縱向交叉搜索的父種群是來自橫向交叉后更優(yōu)的種群。由于個體解的每個維度可能具有不同的上界和下界，因此需要根據(jù)每個維度的上界和下界進行歸一化操作，以確保縱向交叉產(chǎn)生的后代能夠位于每個維度的邊界內(nèi)，并且縱向交叉每次只對其中一維進行更新既能夠使陷入局部最優(yōu)的維度跳出局部最優(yōu)，而又盡可能不破壞另一正常維度包含的信息。假設橫向交叉后更優(yōu)的麻雀個體為 ，此時對? 的第d1維和d2維進行縱向交叉，它們的后代將由下式計算：

式（10）中，m是[0，1]之間按照均勻分布隨機生成的值， 為父代? 的第d1維和第d2維通過縱向交叉產(chǎn)生的后代。同橫向交叉的競爭機制一樣，最終保留適應度更高的麻雀個體。

2.4? MESSA的算法步驟

融合多種策略之后的增強型麻雀搜索算法（Multi-strategy enhanced sparrow search algorithm， MESSA）的具體實現(xiàn)步驟為：

1）算法相關參數(shù)初始化，設定種群規(guī)模pop，最大迭代次數(shù)tmax，搜索范圍上下界ub，lb。預警值ST，發(fā)現(xiàn)者的比例PD，警戒者的比重SD。

2）根據(jù)式（6）初始化種群

3）計算初始適應度值并進行排序找到當前最優(yōu)適應度值，記錄此時的最優(yōu)位置和最差位置。

4）在PD中選取適應度較高的麻雀個體通過式（8）更新發(fā)現(xiàn)者位置，剩下的作為跟隨者通過式式（4）更新位置。

5）在SD中根據(jù)式（5）更新麻雀位置

6）隨機選取麻雀個體通過式（10）進行橫向交叉，保留此時適應度更高的麻雀個體 ，橫向交叉結束后，根據(jù)式（11）進行縱向交叉，更新當前最優(yōu)麻雀個體。

7）比較縱向交叉后的麻雀個體適應度值，得出全局最優(yōu)解。記錄當前麻雀個體位置。

8）判斷當前迭代次數(shù)是否達到設置的tmax，若達到則輸出最優(yōu)麻雀個體適應度值和最優(yōu)麻雀個體位置，否則返回3）。

3? MESSA實驗與討論

3.1? 實驗設計

為了綜合驗證MESSA的有效性，實驗選取已發(fā)表文獻中的9個基準測試函數(shù)測試MESSA的性能，并與原始麻雀搜索算法SSA、李愛蓮等提出的融合正余弦和柯西變異的麻雀搜索算法（Sine-cosine and cauchy mutation sparrow search algorithm， SCSSA）、經(jīng)典優(yōu)化算法PSO和GWO進行對比?；鶞蕼y試函數(shù)的相關信息如表1所示。包括：單模態(tài)測試函數(shù)F1～F3，只有一個全局最優(yōu)解，主要用于測試算法的尋優(yōu)精度；多模態(tài)測試函數(shù)F4～F6，具有多個局部最優(yōu)解，用于檢驗算法的全局搜索性能和避免早熟的能力；固定維度復合測試函數(shù)F7～F9，這些函數(shù)的特點是維度比較低，只有一個全局最優(yōu)解的同時，還有許多局部最優(yōu)解，要求算法在優(yōu)化低維問題具有一定的能力。其中F1～F6分別在10維、30維和100維中運行，每個算法均獨立運行100次，驗證MESSA在不同維度下的求解能力。實驗結果如表3和表4所示，在F7～F9中運行固定維度的測試結果如表1所示，實驗采用最優(yōu)值（Best）、平均值（Mean）和標準差（Std）來評估MESSA的性能，其中最優(yōu)值和平均值反映算法的求解質(zhì)量和求解精度，標準差反映算法的穩(wěn)定性。為了展示不同算法的收斂性能，繪制了不同算法在30維的收斂曲線圖，如圖5所示，其中縱坐標代表適應度值以10為底的對數(shù)。

本節(jié)所有實驗仿真測試環(huán)境為AMD R7-5800H、3.4 GHz CPU、16 GB RAM和Windows 11（64 位）操作系統(tǒng)，所有算法實驗均在Matlab R2021a上運行。

3.2? 實驗結果與分析

由表2、表3和表4可知：

1）在函數(shù)F1～F3上，SCSSA和MESSA在維度為10維、30維、100維均取得了函數(shù)理論最優(yōu)值，并且在平均值和標準差上都最優(yōu)。

2）在函數(shù)F4上，SSA、BSSA、LSSA、CSSA、SCSSA和MESSA在10維、30維和100維都取得了近似最優(yōu)結果，其中SCSSA和MESSA在平均值和標準差上都有著最佳的表現(xiàn)，SSA在30維時相比其他五個算法在平均值和標準差上略微遜色，但依舊好于GWO和PSO。

3）在函數(shù)F5，F(xiàn)6上，在維度為10維、30維和100維時，MESSA在三個指標上相比其他算法均有著更優(yōu)的表現(xiàn)，且遠優(yōu)于SSA和SCSSA。

4）在F7和F8上，MESSA在三個指標上相比其他算法均有著更優(yōu)的表現(xiàn)。在函數(shù)F9上，除了SSA和SCSSA，其余算法均取得了函數(shù)理論最優(yōu)值，GWO、PSO在平均值上均取得了最優(yōu)結果，PSO在標準差上取得了最優(yōu)結果。

由圖2可知，在a～h的圖像中可以發(fā)現(xiàn)，隨著迭代次數(shù)的增加，MESSA相比其他算法收斂速度更快，并且在相同迭代次數(shù)的情況下有著更高的精度。其中在圖2（g）中，其他算法都陷入了局部最優(yōu)，只有MESSA收斂于全局最優(yōu)，表明MESSA有著更強的跳出局部最優(yōu)的能力。雖然在圖2（i）中CSSA收斂更快，但MESSA達到了次優(yōu)，依然領先SSA和SCSSA。

因此，綜合上述分析，融合三種改進策略的MESSA相比其他算法在三個評價指標上表現(xiàn)更好，說明三種策略之間的融合能最大程度地提升算法的性能，說明了改進策略的可行性。這是因為MESSA通過Bernoulli映射使得麻雀種群更加均勻，保證了種群的多樣性，提升了算法的收斂速度和尋優(yōu)精度。而引入萊維飛行后MESSA搜索范圍變得更大，提升了算法的尋優(yōu)精度，同時交叉優(yōu)化算法中的交叉算子大大提高了SSA跳出局部最優(yōu)的能力。表明多種策略的融合能進一步提升SSA的性能，改進是有效的。

4? 結? 論

本文通過對SSA的分析，針對其不足之處提出一種融合多種策略的增強型麻雀搜索算法（MESSA），在9個基準測試函數(shù)上的實驗驗證了MESSA的性能。在接下來的研究中，將嘗試使用本文提出的MESSA更多地應用到工程優(yōu)化問題和特征選擇問題中。

參考文獻：

[1] XUE J K，SHEN B.A novel swarm intelligence optimization approach：sparrow search algorithm [J].Systems Science & Control Engineering，2020，8（1）：22-34.

[2] 李雅麗，王淑琴，陳倩茹，等.若干新型群智能優(yōu)化算法的對比研究 [J].計算機工程與應用，2020，56（22）：1-12.

[3] YUAN J，ZHAO Z，LIU Y，et al. DMPPT control of photovoltaic microgrid based on improved sparrow search algorithm[J]. IEEE Access，2021，9：16623-16629.

[4] LIU G，SHU C，LIANG Z，et al. A modified sparrow search algorithm with application in 3d route planning for UAV [J].Sensors，2021，21（4）：1224.

[5] ZHU Y，YOUSEFI N. Optimal parameter identification of PEMFC stacks using adaptive sparrow search algorithm [J].International journal of hydrogen energy，2021，46（14）：9541-9552.

[6] 李愛蓮，全凌翔，崔桂梅，等.融合正余弦和柯西變異的麻雀搜索算法 [J].計算機工程與應用，2022，58（3）：91-99.

[7] OUYANG C，ZHU D，WANG F. A learning sparrow search algorithm [J].Computational intelligence and neuroscience，2021，2021：1-17.

[8] YAN S，YANG P，ZHU D，et al. Improved Sparrow Search Algorithm Based on Iterative Local Search[J/OL].Computational Intelligence and Neuroscience，2021，2021：（2021-12-15）.https：//doi.org/10.1155/2021/6860503.

[9] KAZIMIPOUR B，LI X，QIN A K. A review of population initialization techniques for evolutionary algorithms [C]//2014 IEEE congress on evolutionary computation （CEC）.New York：IEEE，2014：2585-2592.

[10] 段玉先，劉昌云.基于Sobol序列和縱橫交叉策略的麻雀搜索算法 [J].計算機應用，2022，42（1）：36-43.

[11] 王慶喜，郭曉波.基于萊維飛行的粒子群優(yōu)化算法 [J].計算機應用研究，2016，33（9）：2588-2591.

[12] 張琳，汪廷華，周慧穎.一種多策略改進的麻雀搜索算法 [J].計算機工程與應用，2022，58（11）：133-140.

[13] MENG A，CHEN Y，YIN H，et al. Crisscross optimization algorithm and its application [J].Knowledge-Based Systems，2014，67：218-229.

作者簡介：陳建東（1997—），男，漢族，江西贛州人，碩士研究生，研究方向：數(shù)據(jù)挖掘；通訊作者：聶斌（1972—），男，漢族，江西吉安人，教授，碩導，CCF會員，研究方向：數(shù)據(jù)挖掘;雷銀香（1989—），女，漢族，江西井岡山人，碩士，講師，研究方向：信息安全；張玉超（1998—），男，漢族，重慶人，碩士研究生，研究方向：數(shù)據(jù)挖掘；陳星鑫（1999—），男，漢族，江西贛州人，碩士研究生，研究方向：數(shù)據(jù)挖掘；苗震（1997—），男，漢族，吉林遼源人，碩士研究生，研究方向：數(shù)據(jù)挖掘。

收稿日期：2023-02-15

基金項目：江西中醫(yī)藥大學星火傳承培養(yǎng)計劃（2252000111/4004）；江西省教育廳科學技術項目（GJJ2200925）；江西省中醫(yī)藥管理局科技計劃項目（2020B0412）；江西中醫(yī)藥大學校級科技創(chuàng)新團隊發(fā)展計劃（CXTD22015）