一種混合麻雀搜索算法

李敦橋

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

關鍵詞：麻雀搜索算法;反向?qū)αW習;Metropolis準則;混合算法;函數(shù)優(yōu)化

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

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

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

1 SSA

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

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

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

2 HSSA

2.1 基于反向?qū)αW習的種群初始化

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

在產(chǎn)生初始種群后，選擇適應度較高的[n2]個麻雀個體并通過反向?qū)αW習獲取其對立位置，產(chǎn)生新的初始種群[Xnew=Xn2?Xn2]。

2.2 Metropolis準則

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

2.3 HSSA算法描述

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

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

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

③利用反向?qū)αW習計算麻雀對立點[Xn2];

④產(chǎn)生新初始種群[Xnew=Xn2?Xn2];

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

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

⑦根據(jù)適應度值判斷是否更新全局最優(yōu)位置;

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

⑨判定是否達到最大迭代次數(shù)，若滿足，輸出最優(yōu)麻雀位置，若不滿足，跳轉(zhuǎn)至步驟⑤。

3 仿真實驗

3.1測試函數(shù)

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

3.2實驗結(jié)果與分析

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

4 結(jié)論

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

參考文獻：

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

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

[3] 王林，呂盛祥，曾宇容.果蠅優(yōu)化算法研究綜述[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]. 計算機集成制造系統(tǒng). 2018， 24（9）： 2210-2222.

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

[10] 劉秀梅. 動態(tài)系統(tǒng)中粒子群優(yōu)化算法綜述[J]. 軟件導刊. 2016， 15（10）： 43-46.

【通聯(lián)編輯：唐一東】