一種多策略改進的麻雀搜索算法

張 琳，汪廷華，周慧穎

贛南師范大學 數學與計算機科學學院，江西 贛州 341000

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

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

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

1 麻雀搜索算法

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

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

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

在SSA中，偵查者負責監控覓食區域，當意識到危險時會立即發出危險信號，并迅速向安全區域移動或者隨機靠近別的麻雀個體來降低被捕食的可能性，其位置更新公式可表示為：

式中，Xbest t為當前全局最優位置，β3是步長控制參數，是一個服從標準正態分布的隨機數，β4∈[-1,1]的隨機數，ρ的作用是避免分母為0，通常取值為10-50，f i、f g、f w分別為當前個體的適應度、全局最佳適應度及當前全局最差適應度。

2 改進的麻雀搜索算法

2.1 混沌映射和反向學習策略

SSA通過隨機生成方式產生初始種群，使得初始種群在搜索空間分布不均勻、遍歷性較低，從而導致算法在搜索空間中搜索得不徹底，影響算法的尋優性能和搜索效率。混沌序列映射因具有隨機性、遍歷性、非重復性、初值敏感性等特點[20]，而被廣泛應用于優化搜索問題。通過引入混沌序列映射初始化種群，可以增強初始種群的質量和分布均勻性，有助于算法在搜索空間進行更全面的搜索，實現改善算法的收斂精度和尋優性能的目的。在諸多混沌映射中，立方混沌映射在[0，1]之間均勻分布性能更優，其數學模型為：

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

反向學習策略[21]評估問題的可行解及其反向解，選擇較優的個體作為算法可行解，擴大搜索空間，進而實現提升初始解的質量，增加算法找到最優解的可能性，降低算法在迭代尋優時的盲目性的目的。個體Xi的反向解OP i可表示為：

式中，k∈(0,1)的隨機數。

立方序列映射和反向學習策略初始化種群的具體過程為：

（1）通過式（4）產生立方映射序列，通過式（5）將立方序列映射至麻雀個體上，并計算立方映射種群的適應度值。

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

（3）合并立方映射種群和反向解種群后，根據適應度值進行評估，選擇適應度值較優的前N個麻雀個體作為初始種群。

2.2 改進發現者的位置更新

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

在尋優初期，權重因子大，算法的全局勘探性能強搜索范圍廣；尋優后期，權重因子快速減小，算法局部開發能力強，有利于快速收斂。

2.3 差分變異策略

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

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

3 實驗

3.1 基準測試函數上的實驗

3.1.1 基準測試函數說明和參數設置

為了驗證多策略改進麻雀搜索算法的優化效果，選取了8個基準測試函數對改進算法進行測試檢驗，具體函數信息如表1所示。

表1 基準測試函數信息Table 1 Benchmark function information

另選取PSO、DE、灰狼優化算法、鯨魚優化算法、SSA及MISSA進行尋優對比，其中PSO的參數設置為w=0.75,c1=1.5,c2=1.5；DE的參數設置為pcr=0.5,Fmin=0.2,Fmax=0.8；GWO的參數設置為ainitial=2,aend=0；WOA的參數設置為ainitial=2,aend=0,p=0.5,b=1；SSA的參數設置為ST=0.8,PD=0.2,SD=0.2。所有算法的種群規模為30，最大迭代次數為200，每個測試函數獨立運行30次來降低算法實驗結果的統計誤差。表2顯示的是30次獨立實驗中每種算法求解各測試函數的最優解（Best）、最差值（Worst）、平均值（Mean）和標準差（Std）。

3.1.2 實驗結果與分析

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

表2 基準測試函數優化結果對比Table 2 Comparison of benchmark function optimization results

為了更好地說明MISSA有著更好的尋優精度以及收斂速度，在8個基準測試函數上進行仿真實驗，各算法優化測試函數的收斂曲線對比如圖1～圖8所示。

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

圖3 f3函數收斂曲線Fig.3 Convergence curve of f3 function

圖4 f4函數收斂曲線Fig.4 Convergence curve of f4 function

圖5 f5函數收斂曲線Fig.5 Convergence curve of f5 function

圖6 f6函數收斂曲線Fig.6 Convergence curve of f6 function

圖8 f8函數收斂曲線Fig.8 Convergence curve of f8 function

3.2 SVR模型參數優化對比實驗

為進一步驗證MISSA的優化性能，將其應用于SVR[24]模型的參數優化選取之中。SVR是建立在統計學習理論上的一種機器學習算法，常用來處理函數擬合和回歸預測問題。SVR模型的性能與參數選取緊密相關，參數選擇不恰當會降低算法的學習能力和泛化性能[25]。為提高模型性能，本文利用MISSA對SVR中的懲罰系數和核函數中的參數進行優化選擇。

3.2.1 MISSA優化SVR參數流程圖

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

圖7 f7函數收斂曲線Fig.7 Convergence curve of f7 function

圖9 MISSA-SVR參數優化流程圖Fig.9 Flow chart of MISSA-SVR parameter optimization

3.2.2 實驗數據集與實驗設置

從UCI機器學習庫[26]中選取了5個數據集來驗證MISSA優化SVR模型參數的綜合性能，關于數據集的詳細信息見表3所示（其中Garments數據集去除包含缺失值的樣本后剩余691個數據樣本）。

表3 數據集的統計信息Table 3 Statistics for datasets

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

3.2.3 實驗結果與分析

表4顯示的是5種算法在5組數據集上優化SVR算法參數的實驗結果，其中粗體數字表示這些方法在每個數據集上的最佳性能。

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

表4 各算法優化SVR的實驗結果Table 4 Experimental results of optimizing SVR for each algorithm

4 結語

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