混合策略改進的麻雀搜索算法

張偉康，劉 升，任春慧

上海工程技術大學 管理學院，上海201620

群智能算法是模擬自然界中生物的行為特點，在一定范圍內搜索解空間中的最優解。近年來，隨著群智能算法在工程、經濟、醫學領域越來越廣泛的應用，如電容器優化選址、圖像分割、CO2排放預測以及PID參數整定等，不斷涌現出新的群智能算法。學者們通過蜜蜂、狼、鯨魚、蝴蝶、麻雀等生物的群體行為，提出了人工蜂群算法[1]（Artificial Bee Colony Algorithm，ABC）、灰狼優化算法[2]（Grey Wolf Optimization，GWO）、鯨魚優化算法[3]（Whale Optimization algorithm，WOA）、蝴蝶優化算法[4]（Butterfly Optimization Algorithm，BOA）、麻雀搜索算法[5]（Sparrow Search Algorithm，SSA）等等。

麻雀搜索算法是2020年由薛建凱[5]提出的一種新型群智能算法，該算法主要是受麻雀的覓食行為和反捕食行為的啟發，與其他算法相比具有搜索精度高、魯棒性強的特點。然而在搜索過程中，種群多樣性減少，容易陷入局部最優。針對這個缺陷，呂鑫等人[6]引入鳥群算法中發現者和加入者位置更新方式應用到麻雀搜索算法，增強了全局搜索能力。毛清華等人[7]將Sin混沌映射、自適應權重、柯西變異以及反向學習等策略應用到麻雀算法中，提升了算法的收斂精度和全局尋優能力。雖然以上學者的研究對SSA的尋優能力有所提高，但在增強全局開發能力、權衡局部探索和全局開發能力、提高收斂速度等方面仍需更加深入的研究。

本文首先利用Circle映射初始化麻雀個體位置，增加初始種群的多樣性；然后引入Arora[4]提出的蝴蝶優化算法（BOA），利用BOA中蝴蝶的位置更新策略改進麻雀搜索算法發現者的位置更新方式，提升算法全局開發能力；最后對全局最優解進行逐維變異，增加種群多樣性，提高算法跳出局部最優的能力。通過與4種基本算法和5種改進算法基于10個基準測試函數進行比較以驗證其有效性，結果表明所提算法在求解函數優化問題上表現優秀全局尋優能力得到大幅提升。

1 麻雀搜索算法

假設在D維解空間中存在N只麻雀，第i只麻雀在D維解空間的位置為Xi=[xi1,xi2,…,xid]，其適應度值為FXi=f([xi1,xi2,…,xid])。選取每次迭代中位置最好的一部分麻雀作為發現者，一般占到種群的10%～20%，剩下的作為加入者，而偵察者則在整個種群中隨機選取10%～20%。

發現者的位置更新公式如下：其中，t代表當前迭代次數，j=1,2,…,d。itermax表示最大迭代次數，Xt+1i,j表示第i個麻雀在第j維的位置，α∈(0,1)是一個隨機數，R2∈[0,1]為預警值，ST∈[0.5,1]為安全值，Q是服從正態分布的隨機數，L為1×d且元素值全為1的矩陣。當R2＜ST時，表示周圍沒有天敵，發現者將進行廣泛搜索。反之，則代表發現捕食者，此時所有麻雀都要飛往其他安全地方覓食。

加入者的位置更新公式如下：

其中，Xworst表示第t次迭代全局最差位置，表示第t+1次迭代發現者最優位置，A為1×d且元素隨機賦值值為1或-1的矩陣，且A+=AT(AAT)-1。當i＞N/2時，位置較差的加入者處于十分饑餓的狀態，此時需要飛往其他的地方覓食。

偵察者位置更新公式如下：

其中，Xtbest為當前全局最優位置，β為步長控制參數，是一個均值為0，方差為1的正態分布隨機數。K∈[-1,1]是一個隨機數，fi表示個體適應度值，fg為最佳適應度值，fw為最差適應度值，ε為最小常數，防止分母為零的情況出現。

2 麻雀搜索算法的改進

2.1 Circle混沌初始化策略

麻雀搜索算法對種群進行初始化時，采用的是隨機生成的方式，這種方式會使得麻雀種群分布不均勻，影響后期的迭代尋優。而混沌映射具有隨機性、遍歷性和規律性等特點[8]，可以利用混沌序列對麻雀個體的位置進行初始化。目前常用來初始化種群的混沌映射有Logistic映射、Tent映射、Circle映射等，其分布直方圖如圖1～圖3所示。然而楊迪雄等人[9]指出Logistic映射在[0,1]范圍內呈切比雪夫型分布，即在[0,0.1]和[0.9,1]范圍內取值概率較高，在[0.1,0.9]范圍內取值概率較低，這種不均勻性對算法的尋優速度和精度有很大的影響；單梁等人[10]研究表明Tent映射的分布更加均勻，但存在小周期和不穩定周期，容易陷入不動點；而Circle映射更加穩定且具有與Tent映射相似的均勻性[11]，因此本文采用Circle混沌映射對麻雀種群進行初始化，其表達式如下式：

圖1 Logistic映射分布直方圖Fig.1 Logistic map distribution histogram

圖2 Tent映射分布直方圖Fig.2 Tent map distribution histogram

圖3 Circle映射分布直方圖Fig.3 Circle map distribution histogram

其中，i表示維度。

2.2 蝴蝶優化策略

BOA是受到蝴蝶在覓食和求偶過程中，通過嗅覺來辨別方向的啟發所提出的群智能算法。在迭代時，當蝴蝶可以聞到來自其他蝴蝶的氣味時，它將朝著氣味最濃的方向移動，該階段被稱為全局搜索階段；當蝴蝶不能從周圍嗅到味道時，它將隨機移動，該階段被稱為局部搜索階段。其兩階段的位置更新方式如式（5）、（6）所示：

根據SSA算法發現者位置更新公式可知，當R2＜ST時，發現者的每一維都在變小并收斂于0，當R2≥ST時，發現者會按照正態分布隨機移動到當前位置。這樣一來算法在迭代初就會出現收斂于0點以及向全局最優解靠近的趨勢，容易導致算法出現早熟收斂，陷入局部最優。因此，本文引入BOA的全局搜索階段位置更新策略改進SSA中發現者的位置更新公式，改進后的位置更新方式如公式（7）所示：

改進后的位置更新公式中，一方面，在每一次迭代時麻雀個體都會與最優個體進行信息交流，以便充分利用當前最優解的信息，改善了原算法中缺乏個體間信息交流的缺陷；另一方面，BOA的引入在一定程度上擴大了搜索空間，改進前后發現者的更新策略如圖4、5所示。然而，一味地擴大搜索空間并不能保證提升算法的全局尋優能力，還需要對搜索空間的擴展幅度進行一定的控制。本文受到文獻[12]中隨機縮小搜索空間策略的啟發，提出一種自適應縮小搜索空間的策略；通過控制搜索空間的上下限，將搜索空間限制在一定范圍內，加快種群收斂速度。其具體方式如下：

圖4 改進前發現者搜索策略Fig.4 Search strategy of discoverers before improvement

其中，Xj,lb、Xj,ub分別為第j維的搜索下限、上限，Xj,min、Xj,max分別為目前第j維的最小值、最大值，Xtbest,j代表當前全局最優個體在第j維的位置，rt為空間縮小系數。在迭代過程中隨著空間縮小系數的增大，搜索空間在全局最優個體的指引下不斷縮小；這不僅控制了搜索空間的擴展幅度，也提高了算法的收斂速度。

圖5 改進后發現者搜索策略Fig.5 Search strategy of discoverers after improvement

2.3 逐維變異策略

在基本麻雀搜索算法中，發現者、加入者和偵察者的位置更新方式分別如公式（1）～（3）所示，發現者在R2＜ST時的位置更新方式存在逐維減小并最終收斂于0的問題；加入者在i≤N/2時會隨機更新到當前最優位置的附近，且每一維距最優位置的方差不斷減小；偵察者在fi≠fg時會逃離到當前位置與最優位置附近，其值收斂于最優解。因此，如果當前最優位置為局部最優，那么麻雀種群會集中在局部最優位置進行搜索，降低種群多樣性，且難以跳出局部最優。針對這一問題，一般采用變異操作對個體進行干擾以增加種群多樣性，跳出局部最優。最常用的手段是通過高斯變異算子、柯西變異算子等對所有維度進行同時變異，但是對于高維函數來說會存在維間干擾問題[13]，即某些維度變異效果較差，且覆蓋了變異效果較好的維度，最終導致變異效果不佳，進而影響算法的收斂速度和精度。采用逐維變異策略則可以有效避免維間干擾問題[14]，從而提高變異解的質量。

本文采用自適應t分布變異算子對最優個體進行變異，主要是由于t分布綜合了柯西分布和高斯分布的特點，根據參數自由度n的大小，其分布曲線表現出不同的形態。t(n→∞)→N(0,1)，一般n≥30兩者偏離可以忽略不記，，其中N(0,1)為高斯分布，C(0,1)為柯西分布。換言之標準高斯分布和柯西分布是t分布的兩個邊界特例分布[15]。

變異操作的結果具有不確定性，若對所有個體均進行逐維變異操作必然會增加計算量且降低算法的搜索效率，因此本文僅對最優個體進行變異，一方面充分利用最優個體的信息，另一方面增加種群多樣性，擴大搜索范圍。

逐維變異策略的具體實現方式為：設搜索空間具為d維，當前全局最優解為，逐維變異后得到的新解為，計算方式如下：

其中，iter為當前迭代次數，t(iter)是自由度參數為t的t-分布。所提更新公式在的基礎上，增加了隨機干擾項，既充分利用了當前位置信息，又增加了隨機干擾信息，有利于算法跳出局部最優；而且隨著迭代次數iter增加，t分布逐漸向高斯分布靠攏，有利于增強算法的收斂速度；同時，克服了高維問題下的維間干擾問題。

2.4 混合策略有效性初步驗證

為初步驗證以上三種策略在提高SSA性能方面的有效性，本文將SSA算法與MSSSA算法在種群規模為30的情況下，對Booth函數進行尋優。通對過兩種算法在不同迭代時期種群分布圖的比較，對所提策略有效性進行初步判斷。Booth函數基本信息如表1所示，不同時期兩種算法種群分布圖如圖6所示。

表1 Booth函數基本信息Table 1 Basic information of Booth function

由圖6可以看出，在迭代初期SSA就有收斂于0的傾向，并且種群多樣性較差；而MSSSA的種群多樣性更優、搜索空間更大，且收斂于0的傾向得到很大程度改善。這主要是由于混沌初始化策略很大程度地提高了初始種群的多樣性，且蝴蝶優化策略改變了發現者逐維縮小的搜索方式。當迭代到30次時，在逐維變異策略的作用下MSSSA的搜索空間明顯要大于SSA，且前者一部分種群開始聚集到(1,3)附近。當迭代到60次時，MSSSA的個體大部分已經集中到(1,3)點，而SSA的個體仍有很大一部分未集中到最優個體附近。綜上所述，在本文所提三種策略的作用下，MSSSA的尋優性能和收斂速度較SSA均有所提高，由其體現在不同時期種群多樣性和搜索空間大小方面。

圖6 不同迭代時期種群分布圖Fig.6 Population distribution graph in different iteration periods

2.5 改進算法的流程描述

MSSSA的具體執行步驟如下：

步驟1利用Circle混沌映射初始化種群并設置各個參數。

步驟2計算麻雀個體的適應度值并排序，找出最優適和最差適應度值及其對應的位置。

步驟3從位置較優的麻雀種選出部分作為發現者，按照公式（7）進行位置更新，并以公式（8）、（9）、（10）對其搜索空間進行限制。

步驟4剩下的麻雀作為加入者，并按照公式（2）進行位置更新。

步驟5隨機從整個種群中選出部分麻雀作為偵察者，并按照公式（3）進行位置更新。

步驟6計算更新后的整個麻雀種群的適應度，并找到全局最優麻雀，對其進行逐維變異。

步驟7判斷是否達到結束條件，若是，則進行下一步，否則跳轉至步驟2。

步驟8程序結束，輸出最優解。

2.6 時間復雜度分析

設種群規模為N，偵察者比例為r，問題維度為D，最大迭代次數為T，求解目標適應度函數時間為f(D)，根據MSSSA算法的實現步驟可知，MSSSA算法初始化時間復雜度為O(N·(f(D)+D))，蝴蝶優化策略只是改變發現者的更新方式并未增加流程，因此發現者和跟隨者位置更新階段時間復雜度為O(N·D)，偵察者位置更新階段時間復雜度為O(rN·D)，逐維變異策略時間復雜度為O(N·f(D)+D)，算法的整體時間復雜度為O(N·D·T)，與基本SSA算法相同，并沒有增加計算負擔。

3 仿真實驗與結果分析

3.1 仿真實驗環境

本文的仿真實驗基于Intel?CoreTMi7-7500U CPU＠2.70 GHz 2.90 GHz，12 GB內存，以及Win10操作系統，仿真軟件為MATLAB R2018b。

3.2 比較對象和參數設置

本文選取基本麻雀搜索算法（SSA）、粒子群算法[16]（PSO）、蝴蝶算法（BOA）、鯨魚算法（WOA），兩種改進的其他算法：文獻[17]改進的蝴蝶算法（CWBOA）和文獻[18]改進的鯨魚算法（EGolden-SWOA），兩種單一策略改進的麻雀搜索算法：BOASSA（只引進本文第2章中的蝴蝶優化策略）和t-SSA（只引進本文第2章中的逐維變異策略），以及文獻[6]改進的麻雀搜索算法（ISSA）與本文所提的MSSSA進行對比。為保證實驗的公平性，所有算法的種群規模設為30，迭代次數設為200，其他參數設置如表2所示。

表2 各算法的實驗參數Table 2 Experimental parameters of each algorithm

3.3 測試函數

為了驗證改進算法具有更好的尋優性能，本文選取了10個不同特點的基準測試函數進行函數優化的對比實驗，具體函數信息見表3。

表3 基準測試函數Table 3 Benchmark function

3.4 與其他群智能算法的對比分析

將本文所提的MSSSA，與SSA、PSO、BOA、CWBOA、WOA、EGolden-SWOA分別在10個基本測試函數上獨立運行30次，用于分析本文所提算法相比于其他群智能算法在尋優性能以及穩定性方面存在的優勢，具體結果如表4所示。

由表4可知，對于高維單峰函數f1到f5，本文所提出的MSSSA的尋優效果明顯優于SSA、PSO、BOA、CWBOA、WOA以及EGolden-SWOA，其中對f1和f3的尋優效果達到100%，對f2的尋優效果高出其他算法幾十個數量級；并且標準差普遍小于其他算法，說明Circle映射保證了初始種群的多樣性，使得MSSSA的穩定性具有顯著的提高。對于高維多峰函數f6到f8，MSSSA與SSA、CWBOA以及EGolden-SWOA具有相同的尋優性能，其中對f6和f8可以直接搜索到最優值，且尋優效果達到了100%，相較于PSO、BOA和WOA這些未經過改進的算法有較大的提升。這說明MSSSA通過蝴蝶優化策略改善發現者的搜索方式，擴大了搜索空間，并通過逐維變異策略提高了種群多樣性，使得算法能夠跳出局部最優值。對于低維多峰函數中的f9，MSSSA可以直接找到最優值，且標準差小于其他算法，相比于其他算法具有較好的穩定性和尋優精度；對于低維多峰函數中的f10，MSSSA可以直接搜索到最優解，且尋優效果達到100%。

表4 函數測試結果Table 4 Function test result

為了更加直觀地對比算法的收斂精度和收斂速度，本文根據迭代次數和適應度值繪制了測試函數的收斂曲線圖，此處選取6個基準測試函數的迭代收斂曲線圖進行展示，具體如圖7所示。觀察測試函數收斂曲線可知，本文所提算法MSSSA在收斂速度上要普遍優于SSA、PSO、BOA、CWBOA、WOA以及EGolden-SWOA。f1、f2和f4為高維單峰函數，主要用來檢測算法的局部開發能力；由這三個函數的收斂曲線可以看出，MSSSA具有較高的收斂速度和收斂精度，局部開發能力遠高于其他算法。f7和f8屬于高維多峰函數，很難找到其最優值，主要用來檢測算法的全局探索能力；由其收斂曲線可以看出，MSSSA相較于PSO、BOA和WOA算法具有更高的收斂精度和收斂速度；MSSSA與SSA、CWBOA、EGolden-SWOA有著同一數量級的收斂精度，但MSSSA在20次迭代以內搜索到最優值，而后三者在迭代次數多出幾十次后才達到最優，并且后期的適應度值頻繁波動。這說明后三者在尋優高維函數時頻繁陷入局部最優，大大降低了收斂速度；而MSSSA首先利用Circle映射保證初始種群多樣性，其次通過蝴蝶優化策略改進發現者位置更新方式，進而防止了算法在迭代初期就陷入局部最優的情況；最后以逐維變異策略對最優個體進行擾動，使得算法具備快速跳出局部最優的能力，最終收斂到全局最優值。對于函數f10，所有算法的收斂曲線最終都趨于平穩，但是MSSSA和EGolden-SWOA具有更高的收斂精度；MSSSA的收斂精度和收斂速度與EGolden-SWOA維持在同一數量級，但相較SAA有一定程度的提高。

圖7 測試函數收斂曲線Fig.7 Convergence curve of test function

綜上所述，MSSSA對10基準測試函數的尋優性能有明顯的提高，并且具有較強的穩定性，尤其對函數f1到f4，MSSSA表現出良好的性能，較其他6個算法高出數10個數量級；此外，在高維多峰函數尋優中MSSSA能夠迅速跳出局部最優值，并迅速收斂到全局最優值。至此，MSSSA的可行性和有效性得以證明。

3.5 Wilcoxon秩和檢驗

雖然本文對比算法性能時是在獨立運行30次的情況下進行的，但為了更加全面地體現檢驗算法性能，仍需做進一步的統計檢驗。本文采用Wilcoxon秩和檢驗驗證MSSA每次運行結果在P=5%顯著水平下是否與其他算法存在顯著差異，原假設H0為：兩種算法不存在顯著差異。當P＜5%時，拒絕原假設，表明兩算法之間存在顯著性差異；當P＞5%時，接受原假設，表明兩算法之間差異不明顯，也即算法性能相當。MSSSA分別與各算法的具體檢驗結果如表5所示，其中N/A表示二者性能相當，無法進行比較。

根據表5可知，大部分的P值均小于0.05，表明MSSSA算法的尋優性能與其他算法存在顯著差異，對于f6到f8，MSSSA與SSA、CWBOA，以及EGolden-SWOA的尋優效果差異不顯著，尋優效果相當。

表5 Wilcoxon秩和檢驗結果Table 5 Results of Wilcoxon signed rank test

3.6 與其他策略改進麻雀搜索算法的對比分析

將本文所提的MSSSA，與ISSA、t-SSA、BOASSA分別在10個基本測試函數上獨立運行30次，用于分析本文所提算法相比于最新改進的麻雀搜索算法的優勢，以及本文所用單一策略的有效性，具體結果如表6所示。

表6 改進算法的函數測試結果Table 6 Function test results of improved algorithm

觀察表6可知，相比于文獻[6]所提出的ISSA，本文所提MSSSA對f1至f5以及f9至f10具有更好的尋優精度和穩定性，其中對f1、f3、f10尋優效果達到100%，對f2、f4尋優效果高出ISSA幾十個數量級。相比于本文單一策略改進的t-SSA和BOASSA，混合策略改進的MSSSA效果明顯更優，單一策略雖然能夠在一定程度上改進SSA，但仍有較大提升空間，多樣的改進策略可以最大程度地提高算法的尋優性能。

4 結論

為了增強麻雀搜索算法跳出局部最優和全局探索能力，本文提出了一種基于自混合策略改進的麻雀搜索算法，首先通過Circle映射初始化種群，保證了初始種群多樣性；然后采用蝴蝶優化算法位置更新方式，改善原更新方式在迭代初期即開始收斂的缺陷，擴大搜索空間；最后引入逐維變異策略，對全局最優個體進行逐維擾動，增加種群多樣性，防止陷入局部最優，提高全局探索性能。通過與其他9種算法在10個基準測試函數上的比較，以及Wilcoxon秩和檢驗證實了改進算法的有效性。下一步可以考慮將改進后的MSSSA應用到實際問題的優化中，擴展本算法的應用領域。