基于旋轉狀態轉移的麻雀搜索算法

劉西全， 周新志

（四川大學 電子信息學院， 成都 610065）

0 引言

近年來，群體智能優化算法在智能機器學習上被廣泛應用，群體智能優化算法主要是模仿昆蟲、動物、魚類、鳥類的群體行為、根據其覓食行為啟發而提出的算法［1］。 如粒子群優化算法［2］（PSO）、蟻群優化算法［3］（ACO）、灰狼優化算法［4］（GWO）、天鷹優化器［5］（AO）和麻雀搜索算法［6］（SSA）等。 其中，麻雀搜索算法是在2020年由薛建凱提出的一種新型智能優化算法，是通過模擬麻雀在自然界的捕食行為來進行研究與開發的。 與其他智能優化算法相比，SSA 具有調節參數少、搜索精度高、收斂速度快、穩定性強等優勢。 然而，在SSA 收斂過程中，卻存在容易陷入局部最優、收斂停滯等問題，直接影響算法的優化效果。

為了提高麻雀優化算法（SSA）的性能，國內外學者提出了許多改進方法。 研究發現初始種群對尋優結果有至關重要的作用。 為了優化初始種群，呂鑫等學者［7］、Liu 等學者［8］分別提出tent 混沌映射和改進Circle 混沌映射對初始種群進行優化。 錢敏等學者［9］在麻雀初始化種群個體位置時引入反向學習策略，以提高尋優前期麻雀種群整體質量，加快全局搜索速度。 Ouyang 等學者［10］提出一種自適應搜索策略以提高局部搜索能力，避免種群陷入局部最優。 Ma 等學者［11］在文章中引用三角相似理論設計了相似擾動函數，提高算法的搜索能力。 Liang 等學者［12］對算法的邊界約束進行改進以提高算法的收斂精度。 毛清華等學者［13］通過引入柯西變異算子，來增強算法越出局部最優空間的能力。

1 麻雀搜索算法

在SSA 中，麻雀種群可分為3 類，分別為：發現者、加入者、警戒者。 其中，發現者為整個種群提供豐富食物的方向與位置；跟隨者是根據發現者提供的食物方向與位置進行食物的搜索；警戒者是為整個種群提供警戒偵察，一旦發現捕食者，群體邊緣麻雀則向安全區域移動獲取食物。

（1）發現者。 在SSA 中，發現者往往根據其自身的更高適應度發揮領導作用，其位置更新策略如下：

（2）加入者。 加入者跟隨發現者，一旦其發現其尋到更好的食物，則會離開現在位置去爭奪食物，其更新策略如下：

（3）警戒者。 警戒者為麻雀種群提供危險預知，其更新策略如下：

2 改進的麻雀搜索算法

2.1 精英旋轉搜索策略

狀態轉移算法［14］（State Transition Algorithm，STA）是由周曉君等學者于2012年提出的一種全局優化算法，包括旋轉、平移、伸縮、坐標四種狀態轉移的變換，旋轉狀態轉移變換的數學模型如下：

其中，n表示計算維度；α為旋轉因子，表示在半徑為α的半徑范圍內尋找下一組最優解；Rr是［－1，1］的隨機數；表示向量的二范數。

由于麻雀發現者在新一代的探索中是隨機狀態，脫離上一代的最優種群，容易陷入局部最優。 因此，本文對精英麻雀發現者進行旋轉狀態轉移變換，增加麻雀的種群多樣性，經狀態轉移后的新種群為：

2.2 融合萊維飛行的搜索策略

萊維飛行是服從萊維分布的一種隨機搜索方法，是一種短距離的搜索與偶爾較長距離的行走相間的行走方式，從而促使萊維飛行具有良好的全局搜索能力，萊維飛行的位置更新公式為：

其中，δ表示步長大小，δ ＞0，通常設置為δ ＝1；“⊕” 表示點對點乘法；Levy（β） 表示服從萊維分布的路徑，并且滿足：

使用Mantegna 方法來生成萊維飛行的隨機步長s為：

在這里，β設置為1.95。

本文采用萊維飛行搜索策略進行全局探測，使得全部麻雀個體廣泛分布在整個搜索空間中，提高全體麻雀的全局搜索能力。 經過對麻雀加入者位置適應度值較優的個體進行萊維擾動后，得到的新種群為：

2.3 貪婪算法尋優

雖然旋轉狀態轉移和萊維飛行可以實現位置的更新，但是其無法保證得到的新解較原解更優，因此對新解和原解的適應度值進行比較，通過貪婪算法機制來保留最優的適應度值和解。 具體公式如下：

2.4 RLSSA 算法流程

RLSSA 算法引入旋轉狀態轉移和萊維分布，增加了種群的多樣性，提高算法搜索精度、收斂速度，算法實現流程見如下：

（1）初始化種群。 參數主要包括： 麻雀的種群規模N，迭代次數M，發現者和警戒者的比例，目標函數fit，麻雀算法的搜索邊界范圍Lb和Ub。

（2）初始化適應度值，并排序，得出最優適應度值fg和最差適應度值fw及其各自的種群位置

（3）根據式（1）更新發現者的位置，根據式（5）得到經旋轉策略變換的位置。

（4）根據式（2）更新加入者位置，根據式（11）得到萊維飛行擾動的位置。

（5）根據式（3）更新警戒者位置。

（6）一次迭代結束，計算適應度值，并根據式（12）選擇新一代的適應度值和麻雀位置。

（7）根據當前麻雀種群狀態，計算最優適應度值fg和最差適應度值fw及其各自的種群位置。

（8）判斷算法是否滿足最大迭代次數，滿足則退出，輸出結果，否則重復執行步驟3～7。

3 實驗結果及分析

3.1 實驗設計

為了驗證RLSSA 的有效性和優越性，采用基準測試函數進行仿真實驗，見表1。

表1 基準測試函數Tab. 1 Benchmark functions

表1 中，F1～F4為單峰測試函數，用來測試函數的收斂速度和精度；F5～F8為多峰測試函數，主要用來測試算法跳出局部最優的能力；F9～F12為固定維多峰測試函數，這類函數主要表現為工程優化問題。 為了驗證算法的有效性和優越性，將本文改進后的旋轉麻雀算法（RLSSA）與GWO、WOA、PSO、SSA 及一種基于相似變換改進的麻雀搜索算法EMSSA 進行對比求解實驗。

圖1 為部分函數的三維圖，依次分別為F1、F2、F5、F8、F9、F12。

圖1 函數三維圖Fig. 1 Three－dimensional diagram of functions

3.2 仿真實驗結果及分析

本實驗是在Windows10 系統，Intel（R） Core（TM） i5－62－－U CPU＠ 2.30 GHz，內存8.00 GB，Matlab R2016a 的環境下進行的，實驗種群規模N ＝30，最大迭代次數M ＝500，發現者和警戒者的比例分別為20%和10%，每個目標函數的維度d和邊界Lb和Ub由表1 中給出。 考慮到每次算法尋優都具有偶然性，所以對每個基準函數都運行30 次尋優運算，由此計算出的平均值和標準差作為最終的評價指標。 表2 和表3 分別給出了12 個基準測試函數在GWO、WOA、PSO、SSA、EMSSA、RLSSA 優化算法后的均值和方差。

表2 基準測試函數優化結果均值比較Tab. 2 Comparison of the mean of the optimization results of the benchmark functions

表3 基準測試函數優化結果方差比較Tab. 3 Comparison of variance of the optimization results of the benchmark functions

由表2 和表3 可知，對于高維單峰函數F1～F4，RLSSA 較其他5 種算法有較小的適應度值和較小的標準差，說明RLSSA 有較高的尋優精度和尋優穩定性。 在多峰測試函數F5～F8上，F5函數在EMSSA 上有最好的精度，RLSSA 對比其他4 種算法有較優的精準度。 而在F6～F8上，RLSSA 能跳出局部最優，穩定找到全局最優解。 對固定維多峰測試函數F9～F12，RLSSA 較其他5 種算法的均值和標準差提升并不高，但是在尋優精度和穩定性上都要優于其他5 種算法。

3.3 收斂曲線分析

為了反映出RLSSA 的收斂速度，在500 次迭代中畫出各個算法的收斂特性曲線，如圖2 所示。 在高維單峰函數F1～F4的曲線中可以看出，RLSSA的收斂速度均優于其他算法，同時還看出，RLSSA能快速跳出算法的局部最優解。 在高維多峰函數F5的曲線中看出RLSSA 的精度不如EMSSA 和WOA 算法，比其他3 種算法更優，這是因為萊維飛行策略是一種較短步長多，較長步長少的策略，算法不能通過合適的步長實現全局尋優。在F6～F8中，RLSSA 收斂速度快、精度高；在固定多峰函數F9～F12的曲線中，算法結果都趨于穩定，并且結果相近，但可以看出RLSSA 的收斂速度或者精度優于其他算法。

圖2 基準測試函數的收斂曲線Fig. 2 Convergence curve of the benchmark functions

4 結束語

針對傳統麻雀搜索算法（SSA）容易陷入局部最優、收斂停滯等問題，提出了一種融合旋轉狀態轉移的麻雀搜索算法（RLSSA），改進的算法具有收斂速度快、精度高、穩定性強等優勢。 首先，對于麻雀發現者，引入一種旋轉狀態轉移策略的搜索方法以提高算法跳出局部最優的能力；其次，引入萊維飛行策略對麻雀加入者加以改進，此方法可以提高麻雀算法的全局搜索能力；最后，通過貪婪算法的準則，對原算法和改進的算法進行擇優。通過12個基準測試函數并與其他5 個算法進行仿真測試驗證，實驗結果表明RLSSA 具有良好的收斂速度、收斂精度及魯棒性。