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

張偉康，劉 升，任春慧

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

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

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

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

1 麻雀搜索算法

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

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

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

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

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

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

2 麻雀搜索算法的改進

2.1 Circle混沌初始化策略

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

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

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

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

圖4 改進前發(fā)現(xiàn)者搜索策略Fig.4 Search strategy of discoverers before improvement

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

圖5 改進后發(fā)現(xiàn)者搜索策略Fig.5 Search strategy of discoverers after improvement

2.3 逐維變異策略

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

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

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

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

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

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

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

表1 Booth函數(shù)基本信息Table 1 Basic information of Booth function

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

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

2.5 改進算法的流程描述

MSSSA的具體執(zhí)行步驟如下：

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

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

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

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

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

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

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

步驟8程序結束，輸出最優(yōu)解。

2.6 時間復雜度分析

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

3 仿真實驗與結果分析

3.1 仿真實驗環(huán)境

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

3.2 比較對象和參數(shù)設置

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

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

3.3 測試函數(shù)

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

表3 基準測試函數(shù)Table 3 Benchmark function

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

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

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

表4 函數(shù)測試結果Table 4 Function test result

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

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

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

3.5 Wilcoxon秩和檢驗

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

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

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

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

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

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

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

4 結論

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