一種混合麻雀搜索算法

李敦橋

摘要：元啟發式算法由于可產生多樣的解決方案在科學及工業領域受到了廣泛的應用，麻雀搜索算法（SSA）是一種相對新穎的基于群體的元啟發式算法，已被證明具有較好的尋優求解性能。由于在某些情況下麻雀種群多樣性不足，導致算法尋優精度低，易陷入局部最優，因此提出了一種混合麻雀搜索算法（HSSA），首先利用反向對立學習策略提高初始種群質量，其次混合了模擬退火算法的Metropolis準則，避免算法陷入局部最優。為了驗證算法的性能，利用HSSA對多個單峰和多峰測試函數進行求解，實驗結果表明，與WOA、SSA和IPSO相比，HSSA具有更快的收斂速度和更高的求解精度。

關鍵詞：麻雀搜索算法;反向對立學習;Metropolis準則;混合算法;函數優化

Abstract： Meta-heuristic algorithm has been widely used in science and industry because it can produce a variety of solutions. The sparrow search algorithm （SSA） is a relatively new population-based meta-heuristic algorithm， which has been proved to have good performance in optimization. Due to the insufficient diversity of sparrow population in some cases， the optimization precision of the algorithm is low and it is easy to fall into the local optima. Therefore， the hybrid sparrow search algorithm （HSSA） is proposed， which firstly improves the initial population quality by using the Opposition-based learning strategy， and secondly the algorithm mixes the Metropolis criterion of simulated annealing algorithm to avoid the algorithm falling into local optimal. In order to verify the performance of the algorithm， HSSA was used to solve some unimodal and multimodal test functions. The experimental results show that compared with WOA， SSA and IPSO， the proposed HSSA has faster convergence rate and higher solution accuracy.

Key words： sparrow search algorithm; opposition-based learning; metropolis criterion; hybrid algorithm; function optimization

群智能優化算法已被廣泛應用于現實生活中各種優化問題求解，通過模仿飛蛾、蜜蜂、狼和鳥類等自然界各種物理或生物行為構造出數學模型，利用多次迭代獲取最佳解決方案[1-3]。麻雀搜索算法（Sparrow Search Algorithm， SSA）[4]是由沈波等在2020年提出的一種新型群智能優化算法，該算法通過模擬麻雀群體智慧、覓食和抗捕食行為來獲取最優解，經實驗證明，SSA在精度、收斂速度、穩定性和魯棒性都具有較強的性能。但由于種群多樣性不足，SSA算法在迭代過程中極易跳過最優解而陷入局部最優，導致全局搜索能力較差，No Free Lunch（NFL）定理[5]表明，沒有任何一種算法可以在每個優化問題上都表現出色，因此，研究群智能優化算法的改進依舊具有很強的實際意義。

針對上述問題，本文提出了一種混合麻雀搜索算法（Hybrid Sparrow Search Algorithm， SSA），利用反向對立學習優化麻雀初始種群，優化種群的質量可以極大程度的提高收斂速度和收斂精度，其次，混合了模擬退火優化算法[6]中的Metropolis準則，利用一定的概率接受麻雀尋優過程中的惡化解，使得算法能夠跳出局部最優而避免過早收斂。通過多個測試函數驗證了HSSA具有更高的精度，證明了本文提出改進方法的有效性。

1 SSA

麻雀是雜食性群居鳥類，與其他鳥類相比，麻雀相對聰穎，具有較好的記憶力。在日常生活中，麻雀被分為生產者和乞討者兩類，生產者積極尋找食物，而乞討者從生產者那里獲取食物。通過這種生產者與乞討者的策略，麻雀得以獲得食物從而生存，這種策略的數學模型描述如下：

在迭代尋優過程中，麻雀種群中的生產者負責尋找食物和指導整個種群的移動，如果發現危險，會發出警報并引導乞討者至安全區域，在每次迭代中，生產者的位置更新如下：

式中，[Xtbest ]表示第[t]代種群中的最優位置，[β]是符合正態分布的步長控制參數，均值為0，方差為1，[K]是[-1，1]的隨機數，[fi]表示麻雀當前位置的適應度，[fg]與[fw]分別為全局最優和最差適應度，[ε]為不為零的極小值。

2 HSSA

2.1 基于反向對立學習的種群初始化

由于SSA的初始種群都是隨機產生的，很容易聚集于某一區域或過于分散，對后續的迭代尋優有很大的影響，極易陷入局部最優，因此，本文引入反向對立學習[7]提高初始種群質量，該策略通過計算當前位置在搜索空間內的對立點來改善初始種群，在[d]維空間內，若麻雀的初始位置為[X=x1，x2，...，xd]，其對立點[X]位置計算方法如下：

在產生初始種群后，選擇適應度較高的[n2]個麻雀個體并通過反向對立學習獲取其對立位置，產生新的初始種群[Xnew=Xn2?Xn2]。

2.2 Metropolis準則

Metropolis準則[8]由模擬退火算法產生，受啟發于退火原理，利用該準則對當前解與新解進行比較替換，避免尋優迭代過程產生停滯和陷入局部最優，本文將Metropolis準則與SSA混合，避免麻雀種群在尋優過程中早熟，提高其全局搜索能力，Metropolis準則的描述如下：

2.3 HSSA算法描述

綜上所述，HSSA算法的流程如圖1所示。具體步驟為：

①初始化HSSA算法的[R2]，[n]，[T]，[Te]等參數;

②生成初始種群并獲取適應度較高的前[n2]只麻雀[Xn2];

③利用反向對立學習計算麻雀對立點[Xn2];

④產生新初始種群[Xnew=Xn2?Xn2];

⑤獲取當前最好與最差的麻雀;

⑥利用公式（2）-（5）更新麻雀位置并計算適應度;

⑦根據適應度值判斷是否更新全局最優位置;

⑧利用公式（7）Metropolis準則判定是否接收新解;

⑨判定是否達到最大迭代次數，若滿足，輸出最優麻雀位置，若不滿足，跳轉至步驟⑤。

3 仿真實驗

3.1測試函數

為了評估提出HSSA算法的性能，本文選用了6種不同的單峰和多峰函數進行測試，測試函數如表1所示，設置種群數量[n]為100，最大迭代次數[T]為1000，在相同實驗條件下，將HSSA與WOA[9]、SSA和IPSO[10]進行30次對比實驗，證明提出改進的有效性。

3.2實驗結果與分析

為了驗證提出HSSA的優越性，比較4種算法30次運行結果的平均值（Mean）和標準差（Std），表2中的結果表明，HSSA在求解6個單峰和多峰函數時都表現出了優秀的性能，均優于其他對比算法。此外，F1-F6測試函數的收斂曲線如圖2所示，由圖可知，與其他算法相比，提出的HSSA在6種情況下具有明顯優勢，證明本文提出的改進能改善算法的全局搜索能力，避免過早收斂，防止麻雀種群在迭代過程中陷入局部最優。

4 結論

本文提出了一種混合麻雀優化算法，通過反向對立學習策略改善了隨機初始種群的質量，利用Metropolis準則提高了麻雀種群的全局搜索能力，提高了收斂精度，加快了搜索速度，避免迭代過程中陷入局部最優。利用6種不同的函數驗證了HSSA的性能，與WOA，IPSO和SSA相比，本文提出的HSSA具有更快的收斂速度和更高的精度，證明了提出改進策略的有效性。

參考文獻：

[1] 陳堂功，劉超，王夢瑩，等.基于動態參數的人工搜索群算法[J].控制與決策，2019，34（9）：1923-1928.

[2] 黃海松，范青松，魏建安，等.基于CEEMDAN-IGWO-SVM的軸承故障診斷研究[J].組合機床與自動化加工技術，2020（3）：22-25，31.

[3] 王林，呂盛祥，曾宇容.果蠅優化算法研究綜述[J].控制與決策，2017，32（7）：1153-1162.

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

[5] Wolpert D H， Macready W G. No free lunch theorems for optimization[J]. IEEE Transactions on Evolutionary Computation. 1997， 1（1）： 67-82.

[6] 楊飛. 模擬退火算法在物流線路選擇方面的研究[J].電腦知識與技術，2019， 15（4）： 270-271.

[7] Liang Z， Zhang J， Feng L， et al. A hybrid of genetic transform and hyper-rectangle search strategies for evolutionary multi-tasking[J]. Expert Systems with Applications. 2019， 138： 112798.

[8] 鄒賓森，張則強，蔡寧，等. 工具約束下多目標拆卸線平衡問題的貓群模擬退火算法[J]. 計算機集成制造系統. 2018， 24（9）： 2210-2222.

[9] Mirjalili S， Lewis A. The Whale Optimization Algorithm[J]. Advances in Engineering Software. 2016， 95.

[10] 劉秀梅. 動態系統中粒子群優化算法綜述[J]. 軟件導刊. 2016， 15（10）： 43-46.

【通聯編輯：唐一東】