一種多策略改進(jìn)的麻雀搜索算法

張 琳，汪廷華，周慧穎

贛南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西 贛州 341000

群智能算法是受自然界生物群體社會行為模式、進(jìn)化機(jī)制、物理現(xiàn)象的啟發(fā)而開發(fā)的隨機(jī)搜索算法，具有簡單易實(shí)現(xiàn)、靈活性、魯棒性強(qiáng)、自組織性等特點(diǎn)，在圖像處理、模式識別、數(shù)據(jù)挖掘、系統(tǒng)控制等領(lǐng)域被廣泛應(yīng)用。近年來，國內(nèi)外學(xué)者相繼提出各種群智能優(yōu)化算法，如：蟻群算法（ant colony optimization，ACO）[1]、粒子群算法（particle swarm optimization algorithm，PSO）[2]、果蠅優(yōu)化算法（fruit fly optimization algorithm，F(xiàn)OA）[3]、灰狼優(yōu)化算法（grey wolf optimizer，GWO）[4]、鯨魚優(yōu)化算法（whale optimization algorithm，WOA）[5]、哈里斯鷹優(yōu)化算法（Harris hawks optimization，HHO）[6]、麻雀搜索算法（sparrow search algorithm，SSA）[7]等。其中麻雀搜索算法是由Xue和Shen于2020年提出的一種新型群智能優(yōu)化算法，源于對麻雀種群捕食行為和反捕食行為的研究。SSA有全局尋優(yōu)、可調(diào)節(jié)參數(shù)少、結(jié)構(gòu)清晰等優(yōu)點(diǎn)，被廣泛應(yīng)用于各種實(shí)際工程優(yōu)化問題且均有很好的實(shí)際效果，例如圖像分割[8-9]、航跡規(guī)劃[10-11]、車間調(diào)度[12]、發(fā)電功率預(yù)測[13]等。

然而，SSA在求解復(fù)雜優(yōu)化問題時(shí)也存在對初始值敏感，迭代后期種群趨同性嚴(yán)重，難以跳出局部最優(yōu)值的問題，限制了算法的尋優(yōu)性能。針對這些缺點(diǎn)，諸多學(xué)者對其進(jìn)行了改進(jìn)研究。Chen等人[14]通過采用Tent混沌初始化麻雀種群位置，并引入levy飛行和隨機(jī)游走策略有效改善了算法的收斂速度和探索能力。文獻(xiàn)[15]在SSA中對麻雀種群位置進(jìn)行k-means聚類分化，減小隨機(jī)性對初始種群的干擾，對加入者和最優(yōu)個(gè)體位置更新引入正余弦搜索策略、自適應(yīng)局部策略進(jìn)行優(yōu)化，提升算法的尋優(yōu)效率和收斂速度。文獻(xiàn)[16]對最優(yōu)解引入柯西變異和反向?qū)W習(xí)策略提高算法局部空間最優(yōu)值的逃逸能力。文獻(xiàn)[17]在SSA種群初始化過程中引入精英混沌反向?qū)W習(xí)機(jī)制提升初始種群質(zhì)量，并結(jié)合雞群算法的隨機(jī)跟隨策略優(yōu)化加入者位置更新增強(qiáng)算法的搜索性能，借助柯西高斯變異策略保證了種群多樣性和種群抗停滯能力，避免算法過早收斂。段玉先等[18]利用Sobol序列映射生成初始種群位置，并引入非線性慣性權(quán)重和縱橫交叉策略協(xié)調(diào)算法的局部搜索能力和全局開發(fā)能力，降低算法陷入局部最優(yōu)的可能。文獻(xiàn)[19]采用ICMIC混沌初始化種群，增加種群的多樣性和質(zhì)量，在發(fā)現(xiàn)者搜索機(jī)制中融入螺旋探索策略有效增強(qiáng)算法的全局探索能力，借助精英差分和隨機(jī)反向的混合變異機(jī)制，避免因迭代后期種群個(gè)體的快速同化導(dǎo)致算法早熟收斂。上述改進(jìn)策略雖然對SSA的尋優(yōu)性能有所提升，但尋優(yōu)后期搜索能力不足和易早熟收斂的問題依然存在。

因此，本文提出一種多策略改進(jìn)的麻雀搜索算法（multi-strategy improved sparrow search algorithm，MISSA）。根據(jù)以下策略對SSA算法進(jìn)行改進(jìn)：首先在麻雀種群初始化過程中引入立方序列映射和反向?qū)W習(xí)機(jī)制，提升初始種群的質(zhì)量和遍歷性，實(shí)現(xiàn)對搜索空間更全面徹底的搜索；其次，借鑒粒子群算法的學(xué)習(xí)策略更新發(fā)現(xiàn)者的位置，提升種群間的信息交流能力，協(xié)調(diào)全局勘探和局部開發(fā)之間的平衡；最后融合差分進(jìn)化算法（differential evolution，DE）中的差分變異、交叉操作和反向?qū)W習(xí)機(jī)制對最優(yōu)解進(jìn)行變異，增加迭代后期麻雀種群的多樣性，使得算法局部最優(yōu)值的跳出能力有所提升。通過求解8個(gè)基準(zhǔn)測試函數(shù)，并與其他算法進(jìn)行比較，驗(yàn)證了改進(jìn)算法的優(yōu)越性；并將MISSA應(yīng)用于SVR模型的參數(shù)選取之中，在UCI數(shù)據(jù)集上的實(shí)驗(yàn)進(jìn)一步驗(yàn)證了改進(jìn)算法的有效性。

1 麻雀搜索算法

在SSA中，麻雀種群可分為負(fù)責(zé)尋找食物資源并提供整個(gè)種群食物位置與方向的發(fā)現(xiàn)者和根據(jù)發(fā)現(xiàn)者提供的食物信息進(jìn)行捕食行為的加入者，同時(shí)在整個(gè)種群中隨機(jī)選取一定比例的麻雀個(gè)體對覓食區(qū)域進(jìn)行警戒偵查，一旦察覺到危險(xiǎn)，麻雀種群立即做出反捕食行為。在SSA中，種群中適應(yīng)度較好的麻雀個(gè)體被視為發(fā)現(xiàn)者，其位置更新如下所示：

式中，t為當(dāng)前迭代次數(shù)，表示在t代第i只麻雀的位置，Tmax為最大迭代次數(shù)，β1∈( )0,1的一個(gè)隨機(jī)數(shù)，β2服從正態(tài)分布的隨機(jī)數(shù)，L是一個(gè)一行多維的全一矩陣，R2∈[0,1]表示警戒值，ST∈[0.5,1]表示安全閾值。當(dāng)R2＜ST時(shí)代表覓食環(huán)境安全發(fā)現(xiàn)者可廣泛搜索，引導(dǎo)種群獲取更高的適應(yīng)度；當(dāng)R2≥ST時(shí)代表可能出現(xiàn)捕食者，需立即向安全區(qū)域靠攏。

加入者緊跟發(fā)現(xiàn)者進(jìn)行覓食行為，并可能爭奪發(fā)現(xiàn)者的食物資源來增加自身捕食率，其位置更新公式為：

在SSA中，偵查者負(fù)責(zé)監(jiān)控覓食區(qū)域，當(dāng)意識到危險(xiǎn)時(shí)會立即發(fā)出危險(xiǎn)信號，并迅速向安全區(qū)域移動或者隨機(jī)靠近別的麻雀個(gè)體來降低被捕食的可能性，其位置更新公式可表示為：

式中，Xbest t為當(dāng)前全局最優(yōu)位置，β3是步長控制參數(shù)，是一個(gè)服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)，β4∈[-1,1]的隨機(jī)數(shù)，ρ的作用是避免分母為0，通常取值為10-50，f i、f g、f w分別為當(dāng)前個(gè)體的適應(yīng)度、全局最佳適應(yīng)度及當(dāng)前全局最差適應(yīng)度。

2 改進(jìn)的麻雀搜索算法

2.1 混沌映射和反向?qū)W習(xí)策略

SSA通過隨機(jī)生成方式產(chǎn)生初始種群，使得初始種群在搜索空間分布不均勻、遍歷性較低，從而導(dǎo)致算法在搜索空間中搜索得不徹底，影響算法的尋優(yōu)性能和搜索效率?；煦缧蛄杏成湟蚓哂须S機(jī)性、遍歷性、非重復(fù)性、初值敏感性等特點(diǎn)[20]，而被廣泛應(yīng)用于優(yōu)化搜索問題。通過引入混沌序列映射初始化種群，可以增強(qiáng)初始種群的質(zhì)量和分布均勻性，有助于算法在搜索空間進(jìn)行更全面的搜索，實(shí)現(xiàn)改善算法的收斂精度和尋優(yōu)性能的目的。在諸多混沌映射中，立方混沌映射在[0，1]之間均勻分布性能更優(yōu)，其數(shù)學(xué)模型為：

式中，yi為立方序列。若X i∈[lb,ub],lb、ub為搜索空間的上界和下界，將立方序列按式（5）映射到麻雀個(gè)體上：

反向?qū)W習(xí)策略[21]評估問題的可行解及其反向解，選擇較優(yōu)的個(gè)體作為算法可行解，擴(kuò)大搜索空間，進(jìn)而實(shí)現(xiàn)提升初始解的質(zhì)量，增加算法找到最優(yōu)解的可能性，降低算法在迭代尋優(yōu)時(shí)的盲目性的目的。個(gè)體Xi的反向解OP i可表示為：

式中，k∈(0,1)的隨機(jī)數(shù)。

立方序列映射和反向?qū)W習(xí)策略初始化種群的具體過程為：

（1）通過式（4）產(chǎn)生立方映射序列，通過式（5）將立方序列映射至麻雀個(gè)體上，并計(jì)算立方映射種群的適應(yīng)度值。

（2）通過式（6）尋求立方映射后種群的反向解種群，計(jì)算反向解種群的適應(yīng)度值。

（3）合并立方映射種群和反向解種群后，根據(jù)適應(yīng)度值進(jìn)行評估，選擇適應(yīng)度值較優(yōu)的前N個(gè)麻雀個(gè)體作為初始種群。

2.2 改進(jìn)發(fā)現(xiàn)者的位置更新

在SSA尋優(yōu)初期，發(fā)現(xiàn)者快速收斂于0且向全局最優(yōu)值的位置聚攏，導(dǎo)致種群多樣性驟降，容易出現(xiàn)早熟收斂的狀況，從而造成搜索準(zhǔn)確性不高的問題。針對這種情況，本文借鑒粒子群算法[2，22]的學(xué)習(xí)策略，引入全局最優(yōu)值和個(gè)體歷史最優(yōu)值來改進(jìn)發(fā)現(xiàn)者的位置，使得其不僅受全局最優(yōu)個(gè)體位置的影響，還受個(gè)體歷史最優(yōu)位置的影響，提升麻雀種群之間的信息交流能力，從而提高算法的搜索速度和尋優(yōu)精度。改進(jìn)后的發(fā)現(xiàn)者位置更新公式如下：

在尋優(yōu)初期，權(quán)重因子大，算法的全局勘探性能強(qiáng)搜索范圍廣；尋優(yōu)后期，權(quán)重因子快速減小，算法局部開發(fā)能力強(qiáng)，有利于快速收斂。

2.3 差分變異策略

在SSA迭代后期，麻雀種群將快速聚集在最優(yōu)解附近，導(dǎo)致種群趨同性嚴(yán)重，算法停滯不前，進(jìn)而增大算法陷入局部最優(yōu)值的概率。為解決此問題，融合差分進(jìn)化思想[23]至SSA中，通過隨機(jī)選擇兩個(gè)麻雀個(gè)體計(jì)算差值與全局最優(yōu)個(gè)體進(jìn)行變異操作產(chǎn)生新的個(gè)體，并對新個(gè)體引入反向?qū)W習(xí)策略，評估比較保留適應(yīng)度更好的個(gè)體，從而改善種群的多樣性提升算法局部最優(yōu)值的逃逸能力，新個(gè)體的數(shù)學(xué)模型可表示為：

式中，X r1、X r2是隨機(jī)選擇的麻雀位置，λ為縮放因子。

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

3.1 基準(zhǔn)測試函數(shù)上的實(shí)驗(yàn)

3.1.1 基準(zhǔn)測試函數(shù)說明和參數(shù)設(shè)置

為了驗(yàn)證多策略改進(jìn)麻雀搜索算法的優(yōu)化效果，選取了8個(gè)基準(zhǔn)測試函數(shù)對改進(jìn)算法進(jìn)行測試檢驗(yàn)，具體函數(shù)信息如表1所示。

表1 基準(zhǔn)測試函數(shù)信息Table 1 Benchmark function information

另選取PSO、DE、灰狼優(yōu)化算法、鯨魚優(yōu)化算法、SSA及MISSA進(jìn)行尋優(yōu)對比，其中PSO的參數(shù)設(shè)置為w=0.75,c1=1.5,c2=1.5；DE的參數(shù)設(shè)置為pcr=0.5,Fmin=0.2,Fmax=0.8；GWO的參數(shù)設(shè)置為ainitial=2,aend=0；WOA的參數(shù)設(shè)置為ainitial=2,aend=0,p=0.5,b=1；SSA的參數(shù)設(shè)置為ST=0.8,PD=0.2,SD=0.2。所有算法的種群規(guī)模為30，最大迭代次數(shù)為200，每個(gè)測試函數(shù)獨(dú)立運(yùn)行30次來降低算法實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)誤差。表2顯示的是30次獨(dú)立實(shí)驗(yàn)中每種算法求解各測試函數(shù)的最優(yōu)解（Best）、最差值（Worst）、平均值（Mean）和標(biāo)準(zhǔn)差（Std）。

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

從表2分析可知：在這8個(gè)基準(zhǔn)測試函數(shù)的尋優(yōu)實(shí)驗(yàn)中，MISSA算法的統(tǒng)計(jì)結(jié)果明顯優(yōu)于其他5種對比算法。對于單峰函數(shù)f1、f2、f3、f4，MISSA算法能夠找到其理論最優(yōu)解，尋優(yōu)效果遠(yuǎn)超PSO、DE、GWO、WOA、SSA，對于函數(shù)f3、f4，SSA雖也能找到最優(yōu)值，但最差值、平均值、標(biāo)準(zhǔn)差遠(yuǎn)遠(yuǎn)不如MISSA算法；對于單峰函數(shù)f5，這幾種算法結(jié)果表現(xiàn)差別不大，但MISSA算法尋優(yōu)效果和收斂效率稍微優(yōu)于其他5種算法。對于多峰函數(shù)f6、f7，SSA和MISSA都能穩(wěn)定地尋找到最優(yōu)值，說明了該算法本身的優(yōu)越性；對多峰函數(shù)f8，MISSA算法在最優(yōu)值、平均值和標(biāo)準(zhǔn)差相比于其他算法有所提升。綜合分析表明，在尋優(yōu)過程中MISSA的平均值和標(biāo)準(zhǔn)差均略優(yōu)于其他算法，表明MISSA算法的尋優(yōu)精度和魯棒性明顯優(yōu)于其他算法，說明改進(jìn)后的麻雀搜索算法能更充分高效地探尋搜索空間，并具備較強(qiáng)的全局尋優(yōu)能力和局部探索能力。

表2 基準(zhǔn)測試函數(shù)優(yōu)化結(jié)果對比Table 2 Comparison of benchmark function optimization results

為了更好地說明MISSA有著更好的尋優(yōu)精度以及收斂速度，在8個(gè)基準(zhǔn)測試函數(shù)上進(jìn)行仿真實(shí)驗(yàn)，各算法優(yōu)化測試函數(shù)的收斂曲線對比如圖1～圖8所示。

從圖1至圖8可以看出，不論是單峰函數(shù)還是多峰函數(shù)，在收斂到相同精度的情況下，改進(jìn)后的MISSA所需迭代次數(shù)最少，說明該算法的收斂速度有所提高。在相同的尋優(yōu)次數(shù)，MISSA的求解精度略高于其他算法的求解精度。

圖3 f3函數(shù)收斂曲線Fig.3 Convergence curve of f3 function

圖4 f4函數(shù)收斂曲線Fig.4 Convergence curve of f4 function

圖5 f5函數(shù)收斂曲線Fig.5 Convergence curve of f5 function

圖6 f6函數(shù)收斂曲線Fig.6 Convergence curve of f6 function

圖8 f8函數(shù)收斂曲線Fig.8 Convergence curve of f8 function

3.2 SVR模型參數(shù)優(yōu)化對比實(shí)驗(yàn)

為進(jìn)一步驗(yàn)證MISSA的優(yōu)化性能，將其應(yīng)用于SVR[24]模型的參數(shù)優(yōu)化選取之中。SVR是建立在統(tǒng)計(jì)學(xué)習(xí)理論上的一種機(jī)器學(xué)習(xí)算法，常用來處理函數(shù)擬合和回歸預(yù)測問題。SVR模型的性能與參數(shù)選取緊密相關(guān)，參數(shù)選擇不恰當(dāng)會降低算法的學(xué)習(xí)能力和泛化性能[25]。為提高模型性能，本文利用MISSA對SVR中的懲罰系數(shù)和核函數(shù)中的參數(shù)進(jìn)行優(yōu)化選擇。

3.2.1 MISSA優(yōu)化SVR參數(shù)流程圖

利用MISSA對SVR參數(shù)進(jìn)行尋優(yōu)的流程圖如圖9所示。首先將數(shù)據(jù)集進(jìn)行歸一化處理并劃分訓(xùn)練集和測試集，然后利用MISSA對SVR模型參數(shù)進(jìn)行優(yōu)化選擇，獲得優(yōu)化模型MISSA-SVR，最后通過優(yōu)化模型得到預(yù)測結(jié)果。

圖7 f7函數(shù)收斂曲線Fig.7 Convergence curve of f7 function

圖9 MISSA-SVR參數(shù)優(yōu)化流程圖Fig.9 Flow chart of MISSA-SVR parameter optimization

3.2.2 實(shí)驗(yàn)數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

從UCI機(jī)器學(xué)習(xí)庫[26]中選取了5個(gè)數(shù)據(jù)集來驗(yàn)證MISSA優(yōu)化SVR模型參數(shù)的綜合性能，關(guān)于數(shù)據(jù)集的詳細(xì)信息見表3所示（其中Garments數(shù)據(jù)集去除包含缺失值的樣本后剩余691個(gè)數(shù)據(jù)樣本）。

表3 數(shù)據(jù)集的統(tǒng)計(jì)信息Table 3 Statistics for datasets

將數(shù)據(jù)集去除缺失值后歸一化到[0，1]區(qū)間，訓(xùn)練集和測試集按照1∶2的比例隨機(jī)劃分，核函數(shù)選擇徑向基核函數(shù)，懲罰參數(shù)C∈[10-2,25]，核參數(shù)γ∈[10-3,24]。為驗(yàn)證改進(jìn)模型的泛化效果，構(gòu)建了SVR、PSO-SVR、DE-SVR、SSA-SVR與MISSA-SVR模型進(jìn)行對比，各模型參數(shù)設(shè)置如上文所示。通過平均絕對誤差（mean absolute error，MAE）、均方根誤差（root mean square error，RMSE）、決定系數(shù)（R-square，R2）三個(gè)評價(jià)指標(biāo)來評估各模型的預(yù)測精度，評價(jià)指標(biāo)的計(jì)算公式如下所示：

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

表4顯示的是5種算法在5組數(shù)據(jù)集上優(yōu)化SVR算法參數(shù)的實(shí)驗(yàn)結(jié)果，其中粗體數(shù)字表示這些方法在每個(gè)數(shù)據(jù)集上的最佳性能。

通過表4可知，本文提出的MISSA-SVR模型在預(yù)測性能上有一定的提升，相比較于其他算法優(yōu)化參數(shù)的SVR模型具有更高的預(yù)測精度。從表4分析可得，MISSA-SVR模型在選定的5種數(shù)據(jù)集上的RMSE、R2取得的效果最好，在4種數(shù)據(jù)集上MAE表現(xiàn)最好，其中在Servo數(shù)據(jù)集上，SVR模型達(dá)到了和MISSA-SVR模型一樣的MAE評價(jià)指標(biāo)，但MISSA-SVR的RMSE和R2略微優(yōu)于SVR模型。綜合分析表明MISSA-SVR模型在相同條件下，泛化性能有明顯的提升。

表4 各算法優(yōu)化SVR的實(shí)驗(yàn)結(jié)果Table 4 Experimental results of optimizing SVR for each algorithm

4 結(jié)語

針對SSA在求解優(yōu)化問題時(shí)存在的缺點(diǎn)，本文提出了一種多策略改進(jìn)的麻雀搜索算法。通過立方序列映射和反向?qū)W習(xí)策略改進(jìn)SSA初始種群的質(zhì)量，借鑒粒子群算法的學(xué)習(xí)策略提高種群間信息交流能力，利用差分變異操作和反向?qū)W習(xí)機(jī)制增加SSA迭代后期的種群多樣性，提高算法陷入局部最優(yōu)值的逃逸能力，從而提升算法的尋優(yōu)精度和收斂效率。通過對8個(gè)基準(zhǔn)測試函數(shù)的尋優(yōu)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明MISSA具有更好的求解精度、收斂速度和魯棒性，相較于麻雀搜索算法綜合性能有明顯的提升，驗(yàn)證了MISSA算法的改進(jìn)效果。采用MISSA算法對SVR模型中核參數(shù)和懲罰參數(shù)進(jìn)行優(yōu)化選擇，進(jìn)而構(gòu)建了MISSA-SVR預(yù)測模型。通過對5個(gè)UCI數(shù)據(jù)集進(jìn)行預(yù)測分析，結(jié)果表明改進(jìn)模型具有較好的預(yù)測精度，進(jìn)一步驗(yàn)證了改進(jìn)算法的有效性和應(yīng)用可行性。在未來研究中，可將MISSA用于解決更加復(fù)雜的實(shí)際問題。