一種混合麻雀搜索算法

李敦橋

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

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

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

1 SSA

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

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

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

2 HSSA

2.1 基于反向?qū)αW(xué)習(xí)的種群初始化

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

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

2.2 Metropolis準(zhǔn)則

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

2.3 HSSA算法描述

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

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

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

③利用反向?qū)αW(xué)習(xí)計(jì)算麻雀對立點(diǎn)[Xn2];

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

⑤獲取當(dāng)前最好與最差的麻雀;

⑥利用公式（2）-（5）更新麻雀位置并計(jì)算適應(yīng)度;

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

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

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

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

3.1測試函數(shù)

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

3.2實(shí)驗(yàn)結(jié)果與分析

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

4 結(jié)論

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

參考文獻(xiàn)：

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

[2] 黃海松，范青松，魏建安，等.基于CEEMDAN-IGWO-SVM的軸承故障診斷研究[J].組合機(jī)床與自動(dòng)化加工技術(shù)，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].電腦知識與技術(shù)，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] 鄒賓森，張則強(qiáng)，蔡寧，等. 工具約束下多目標(biāo)拆卸線平衡問題的貓群模擬退火算法[J]. 計(jì)算機(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] 劉秀梅. 動(dòng)態(tài)系統(tǒng)中粒子群優(yōu)化算法綜述[J]. 軟件導(dǎo)刊. 2016， 15（10）： 43-46.

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