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

李江華,王鵬暉,李 偉

(江西理工大學信息工程學院,江西 贛州 341000)

1 引言

為在實際問題中解決最優化的問題,高效的優化算法一直是工程領域的主要研究內容之一。面對越來越復雜多樣的大型優化問題,傳統優化算法雖然簡單易行,但適用性也越來越差,無法在短時間內得到可接受的解。因此,許多受自然現象啟發的群體智能優化算法陸續被提出,如蟻群優化ACO(Ant Colony Optimization)算法[1]、粒子群優化PSO(Particle Swarm Optimization)算法[2]、螢火蟲算法FA(Firefly Algorithm)[3]和鯨魚優化算法WOA(Whale Optimization Algorithm)[4]等。這些算法相比傳統算法結構簡單,具有良好的尋優性能,并在可接受的時間內能夠提供較好的解決復雜問題的方案,在現實生活中得到了廣泛應用。但是,隨著實際問題的約束條件越來越復雜,許多算法的適用性已經不足,這就要求更高性能和更高適用性的優化算法來應對這些復雜的應用問題。其中,麻雀搜索算法SSA(Sparrow Search Algorithm)[5]在2020年被Xue等首先提出,通過模擬麻雀覓食和反捕食行為,不斷更新個體位置進行尋優,結構簡單,控制參數較少,并已成功在隨機配置網絡[6]、電池堆參數優化識別[7]、無線傳感器網絡[8]和無人機航跡規劃[9]等領域得到了應用。但受麻雀種群自然特征的限制,SSA仍然存在依賴初始種群、全局搜索能力較弱、易向最優解躍進從而陷入局部最優的缺點。

Yang等[10]在種群初始化階段加入混沌映射方法,對種群多樣性進行了增強,利用自適應加權策略平衡全局搜索與局部開發能力,通過一種自適應t分布變異算子提高算法的搜索能力。Song等[11]引入非線性遞減權重,促進搜索空間的探索和利用,采用變異策略,將混沌搜索與能量較高的搜尋麻雀的局部搜索相結合,避免陷入局部最優。黃輝先等[12]利用精英個體具有更多的進化信息從而改善算法的全局搜索能力,引入混沌動態權重因子加強算法的局部搜索能力,提高算法的收斂精度。Ouyang等[13]融合透鏡原理的對立學習策略與隨機逆向學習策略增加種群多樣性,采用改進正余弦算法的策略使搜索更加廣泛,并利用差異的局部搜索,提高解的質量。段玉先等[14]通過在種群初始化階段引入Sobel序列,提高麻雀種群的多樣性和遍歷性,利用非線性慣性權重,加速算法的收斂,應用縱橫交叉策略引導算法跳出局部最優。Liang等[15]通過自適應加權的方法加速了算法的收斂,改進的邊界處理策略在一定程度上提高了算法的收斂精度。

以上文獻提出的改進算法在一定程度上提高了全局搜索能力,改善了過早收斂的情況,但算法尋優精度不足、跳出局部最優能力欠缺、隨著搜索空間維度增加精度下降、收斂緩慢等問題依舊存在。針對以上問題,本文提出了一種混合多策略改進的麻雀搜索算法MISSA(Multi-strategy Improved Sparrow Search Algorithm)。首先,對各改進策略進行闡述,在種群初始化階段加入精英反向學習策略,提高初始解的質量與多樣性,擴大搜索范圍。對發現者的位置更新進行步長控制,采取分階段的位置公式,來提高算法的收斂精度與尋優能力。對跟隨者的位置更新加入Circle映射參數和余弦因子,進一步提高算法的遍歷性與搜索能力。利用自適應選擇機制對麻雀個體位置加入Lévy飛行,并進行貪心機制擇優更新,增強算法跳出局部最優的能力?；?3個測試函數進行了仿真實驗對比,并進行了Friedman檢驗以驗證本文所提算法的優越性。然后,對改進算法進行有效性分析,利用消融實驗測試所使用的每個策略是否能夠提高原始算法的性能,最后對提出的MISSA進行時間復雜度分析。實驗結果表明,MISSA具有更好的尋優能力和收斂精度,能夠有效避免陷入局部最優,并具有良好的穩定性。

2 麻雀搜索算法

在麻雀搜索算法中,通過麻雀群體的捕食與反捕食行為,將個體區分為發現者、跟隨者和警戒者,每只個體位置對應一個解。發現者為整個種群找尋最佳的覓食區域,跟隨者通過跟隨發現者獲取食物,警戒者負責對覓食區域進行監視。為了獲得更好的食物來源,每只麻雀個體都可以成為發現者,但總體比例不變。當警戒值高于安全值時,整個種群面臨危險,需要放棄覓食并執行反捕食行為,飛往安全區域。

將以上行為建立成模型。在SSA中,假設搜索空間為J維,存在I只麻雀,式(1)為I只麻雀在J維空間中對應的位置：

(1)

發現者的位置更新方式如式(2)所示：

(2)

跟隨者的位置更新公式如式(3)所示：

(3)

警戒者的位置更新公式如式(4)所示：

(4)

3 改進的麻雀搜索算法

3.1 精英反向學習策略

初始種群的質量和多樣性很大程度上會影響后續算法的尋優能力與收斂性能[16],因此本文將精英反向學習策略[17]應用到初始化階段,通過反向解的生成與精英個體的選擇,不僅使算法搜索范圍得到擴大,提高了全局搜索的能力,也能夠提高算法規避局部最優的能力。對于原適應度值較高的個體來說,對其進行反向區域的搜索,沒有太大價值。而對于反向解適應度值較高的個體來說,反向區域具有較高的搜索價值。通過選取更優的個體作為初始種群,能更好地提高整個種群的尋優能力與搜索效率,同時具備更快的收斂速度。

(5)

3.2 階段性控制步長策略

算法的綜合性能需要在探索與開發之間平衡。在原始麻雀搜索算法中,缺乏對步長的有效控制,在發現最優解時,其他個體迅速向最優解靠攏,過早的收斂會導致難以平衡全局探索與局部開發。

當警戒值低于閾值時,發現者采用螺旋式搜索策略,在不斷靠近最優值的同時,對附近一定范圍也進行尋優比較。這種搜索方式雖然搜索范圍更廣,但相應地也帶來了搜索精度不足的問題。因此,引入非線性衰減因子μ,使算法在前期不同區域廣泛搜索,在中后期專注于開發已知區域,提高搜索精度和收斂速度。改進后的發現者位置更新公式如式(6)～式(9)所示：

(6)

l=(a-1)×rand+1

(7)

(8)

(9)

其中,ST′∈[0.8,1]表示安全值,rand為[0,1]的隨機數,ω為一個常數,經多次實驗,取5.5;衰減因子μ與原始算法中發現者位置更新的系數exp(-i/(α×itermax))對比如圖1所示。

Figure 1 Comparison of attenuation factors圖1 衰減因子對比圖

在迭代更新的過程中,與標準SSA的系數相比,本文提出的衰減因子前期權重較大,變化速度較快,發現者不斷探索未知區域,避免了前期過早收斂;而在迭代的后期,衰減因子權重較小,變化速度較慢,發現者能夠保持較強的局部開發能力,縮小搜索范圍,加速算法收斂。

3.3 混沌余弦變化因子

在發現者尋找到最優解并引領種群收斂的情況下,其余跟隨者的迅速靠攏是跳躍式的,這會導致算法陷入局部最優,降低了算法的多樣性。因此,本文在跟隨者的位置更新中引入混沌余弦變化因子,通過在不同階段調整,加強跟隨者對未知區域的廣泛探索,降低陷入局部最優的概率。為降低當前最優位置對個體的影響,使跟隨者個體也能夠進行一定的搜索,引入隨迭代次數變化的慣性權重η,如式(10)和式(11)所示：

(10)

(11)

其中,δ為常數,本文經過多次實驗,設置為3。

在算法搜索的前期,跟隨者在靠近發現者最優位置的過程中,也能夠開展搜索,有一定幾率成為新的發現者,而不是僅僅躍進到最優位置。在算法的后期,權重較大,變化速度慢,最優個體的影響逐漸變大,提高了算法的收斂能力。為了提高跟隨者移動的遍歷性與隨機性,本文采用Circle混沌映射生成相關參數。

Circle映射如式(12)所示：

(12)

混沌狀態下的Circle映射分布與隨機分布如圖2所示。

Figure 2 Comparison of random distribution and Circle map distribution圖2 隨機分布與Circle映射分布對比圖

從圖2可以看到,Circle映射分布的隨機數更為均勻,具有更好的隨機性與遍歷性,能更好地擴大搜索范圍到整個區域。

改進后的跟隨者位置更新如式(13)所示：

(13)

其中,k為Circle映射生成的0～1之間的隨機數。在引入混沌余弦變化因子后,慣性權重η隨著迭代次數的增加而增加,不斷調整跟隨者向最優個體移動的位置,前期以盡可能大的螺旋式范圍搜索最優個體周圍區域并逐漸靠近最優個體,若有更優值,則跟隨者個體成為新發現者,并轉換位置更新;后期在小范圍內開發,加速向最優個體靠近,提升算法的尋優精度。

3.4 自適應選擇機制的Lévy飛行

針對SSA算法在陷入局部最優時,種群搜索陷入停滯的情況,本文設計了一種自適應選擇機制的Lévy飛行策略,通過隨迭代次數不斷減小的自適應因子p,隨機選擇麻雀個體進行Lévy飛行擾動,增強麻雀位置的多樣性,改善算法容易陷入局部最優的缺陷。自適應選擇因子公式如式(14)所示：

(14)

該因子在前期較大,以較高的概率對麻雀個體進行擾動,增強前期種群的廣泛搜索能力;在后期較小,有利于算法的收斂能力。

Lévy飛行在隨機行走的過程中會以較大的概率出現大范圍的移動,具有較為平穩、獨立的增量。

Lévy飛行的位置更新公式如式(15)所示：

(15)

由于Lévy分布十分復雜,在Mantegna等[18]提出的算法中將Lévy飛行路徑定義為式(16)：

(16)

(17)

其中,參數β取值范圍為(0,2),一般β=1.5,Γ(x)=(x-1)!。

Lévy飛行示意圖如圖3所示。

Figure 3 Schematic diagram of Lévy flight圖3 Lévy飛行示意圖

很多研究工作都基于Lévy飛行策略改進并取得了較好的效果[19-22]。盡管Lévy飛行可以對個體的位置進行更新,但無法保證更新后位置的新適應度值優于原位置的適應度值。因此,本文利用貪心機制的特性,通過更新前后位置的適應度值比較,保留更優的解,貪心機制如式(18)所示：

(18)

通過執行策略前后的適應度值大小對比,選取更優的位置進行更新,以提高全局尋優的能力,最大程度地避免陷入局部最優。

4 MISSA算法步驟

步驟1初始化參數：種群規模為n,最大迭代次數為itermax,空間維度為J,發現者數量為PD,警戒者數量為SD,報警閾值為ST,初始上下界為lb和ub,適應度函數為F(·);

步驟2種群初始化：根據式(5)生成隨機性、遍歷性強的初始精英種群;

步驟3對每只麻雀個體的適應度值進行計算并排序,記錄最優適應度值pfit、最優個體位置xbest;

步驟4通過式(12)生成隨機參數R2,根據式(7)～式(9)更新相應的參數l、a、μ;

步驟5根據式(6)更新發現者位置;

步驟6通過式(12)生成隨機參數,根據式(9)和式(10)更新相應的參數μ、η;

步驟7根據式(13)更新跟隨者位置;

步驟8通過式(12)生成隨機參數K,根據式(4)更新警戒者位置;

步驟9根據式(14)更新自適應選擇概率p,通過式(16)和式(17)對麻雀個體位置加入Lévy飛行擾動,依據式(18)進行適應度值的比較,擇優更新位置;

步驟10輸出最優個體適應度值及其位置。

5 實驗與結果分析

5.1 實驗設計與測試函數

為了充分測試本文改進算法MISSA的尋優能力,本節在13個測試函數上(如表1和表2所示)進行仿真實驗,分別將其與PSO[2]、GWO[23]、WOA[4]、SSA[5]和CLSSA[24]進行對比實驗。并在實驗對比后加入Friedman檢驗,對所有算法進行綜合比較。上述實驗均在AMD RyzenTM5 3400GE,3.30 GHz,16 GB內存,Windows 11(64位)的測試環境下進行,使用MATLAB R2019a軟件編寫所有程序。

Table 1 Unimodal test functions

Table 2 Multimodal test functions

在這13個測試函數中,F1(x)～F6(x)為單峰函數,用于重點檢測算法的求解精度;F7(x)～F10(x)為復雜多峰函數,含有較多的局部極小值,用于檢測算法跳出局部極小值的能力,表中最優值的J表示維度;F11(x)～F13(x)為固定低維多峰測試函數,且最優值不同,用于檢測算法的綜合尋優能力。

為使各算法在公平條件下進行對比,實驗參數設置如表3,各算法的種群規模設置為50,最大迭代次數設置為500,均分別獨立運行30次,統計各算法求解各測試函數的最優值、平均值和標準差,用以檢驗算法的尋優能力、尋優精度以及穩定性。

Table 3 Algorithm parameters setting

5.2 算法對比分析

為檢驗算法MISSA在不同維度下的性能,除了固定維度的測試函數,對其余測試函數分別設置維度為30,50和100,以進行更加全面的對比。實驗結果見表4～表6,表中的最優值均已加粗顯示。

Table 4 Experimental results of MISSA and contrastive algorithms on test functions with dimension 30

從表4可以發現,MISSA在單峰函數上能獲得更高的求解精度,尋優能力明顯強于WOA、GWO、PSO、SSA和CLSSA的,且標準差也均為最小,說明算法的穩定性強于其他算法的。在復雜多峰函數上,對于函數F8和F9,SSA、CLSSA與MISSA均找到了最優值,且精度都達到了最高;對于函數F10,MISSA的收斂精度明顯高于其他算法的,且穩定性也最好。在固定低維多峰函數上,雖然各算法都有不錯的性能,但SSA在函數F11上表現不夠優秀,MISSA很好地改善了這一點;在函數F12和F13上,MISSA都達到了更高的尋優精度與穩定性。上述結果說明在同等30維的情況下,MISSA具有更強的搜索能力、更優的搜索精度與穩定性。

表5展示了當維度為50時,除去固定低維函數后各算法的實驗結果?？梢钥吹?MISSA在單峰函數F1～F6上各方面性能依然明顯高于其他算法的,而PSO、WOA和GWO隨著維度增加,算法的精度明顯下降。而在更高維度的多峰函數上,MISSA依舊穩定,CLSSA次之?？傮w來說,MISSA具備更強的解決高維問題的能力,并具有較強的穩定性。

Table 5 Experimental results of MISSA and contrastive algorithms on test functions with dimension 50

在100維的情況下,實驗情況與50維的基本類似,如表6所示,進一步驗證了MISSA相比于其他算法在高維情況下的優勢。

Table 6 Experimental results of MISSA and contrastive algorithms on test functions with dimension 100

為使實驗結果更具有說服力,本文對以上算法的平均值與標準差進行了Friedman檢驗,檢驗結果如表7所示。從表7可以看出,不同維度和不同函數下,算法性能具有差異,但排名均為：MISSA>CLSSA>SSA>WOA>GWO>PSO,這表明MISSA相比其他算法具有很強的競爭力。

Table 7 Friedman test on test functions with different dimensions

為了反映MISSA的動態收斂特征,圖4給出了各算法在30維情況下13個測試函數的平均收斂曲線圖。測試函數迭代收斂曲線可以較為直觀地對比出各個算法的收斂性和尋優能力。通過圖4a～圖4f可以看出,MISSA比其他算法能夠更快地收斂到最優值;在圖4f和圖4g中,多峰函數存在多個局部最優值,為函數尋優增加了難度,各算法都一定程度地陷入停滯,但MISSA能夠及時跳出局部最優,擴大搜索,向更優值收斂;在圖4i和圖4j中,MISSA達到了更快的收斂速度和更高的收斂精度;在固定低維函數上,圖4k和圖4l中CLSSA與MISSA的收斂曲線相近,都達到了較好的收斂效果。

Figure 4 Convergence curves of MISSA and contrastive algorithms圖4 MISSA和比較算法收斂曲線圖

針對引言提出的隨著搜索空間維度增加尋優精度下降、收斂緩慢等問題,除去固定維函數,圖5給出了50維情況下算法的收斂情況：在50維情況下,MISSA同樣很好地解決了算法在高維單峰條件下尋優精度不足的問題,在函數F1～F4上大幅度加速了算法整體的收斂;在函數F5與F6上及時地跳出局部最優,提高了搜索能力;在函數F10上,不僅達到了更高的精度,也具備更快的收斂速度?？梢?MISSA很好地解決了SSA隨著搜索空間維度增加尋優精度下降、收斂緩慢的問題。

Figure 5 Convergence curves of high-dimensional algorithms圖5 高維算法收斂曲線圖

5.3 改進算法有效性分析

為了驗證改進策略的有效性,使實驗更具說服力,本節對算法進行消融實驗,使用表1和表2中的測試函數對標準SSA、僅使用精英反向學習策略的SSA(ESSA)、僅使用階段性控制步長策略的SSA(SSSA)、僅使用混沌余弦變化因子的SSA(CSSA)、僅使用自適應選擇機制的Lévy飛行(LSSA)和MISSA進行實驗,各算法參數設置與標準SSA的保持一致,種群數量為50,迭代次數為500,結果如表8所示。從表8可以看出,在單峰函數F1～F6上,與標準SSA相比,所使用策略皆對算法的尋優能力有較大提升;在高維多峰函數上,雖然在F7上的尋優能力類似,但各改進算法穩定性都有所提高,在F10上各算法的性能提升明顯,至少提升2個量級,而MISSA效果最好;在固定低維多峰函數上,在函數F11上,除ESSA效果一般,其余算法均有效提高了SSA的尋優能力,同時提高了算法的穩定性;在函數F12上,MISSA和ESSA收斂于最優值附近,表現穩定;在函數F13上,各算法性能相近。綜上所述,消融實驗驗證了所使用策略都對標準SSA的尋優性能有所提高,驗證了策略的可行性,結合改進策略后的MISSA具有更高的優越性。

5.4 MISSA時間復雜度分析

假設SSA算法中種群規模為n,維度為J,初始化種群參數時間為α1,求個體適應度值的時間為F(J),發現者數量為pNum,每一維更新時間為α2,跟隨者數量sNum,每一維更新時間為α3,警戒者每一維更新時間為α4。因此初始階段時間復雜度T1=O(α1+n(F(J)+J×α1));發現者更新時間復雜度T2=O(pNum×J×α2);跟隨者更新復雜度T3=O(sNum×J×α3);警戒者位置更新復雜度T4=O((n-pNum-sNum)×J×α4)。綜上,SSA時間復雜度T=T1+(T2+T3+T4)。

在MISSA中,假設求取反向種群時間為β1,因此初始階段MISSA的時間復雜度T′1=O(α1+n(β1+F(J)+J×β1));發現者更新公式產生參數時間為β2,發現者更新時間復雜度T′2=O(pNum×J×β2);跟隨者改進公式產生混沌因子時間為β3,產生余弦變化因子時間為β4,跟隨者更新時間復雜度T′3=O(sNum×J×(β3+β4));警戒者的時間復雜度不變,依舊為T′4=T4;自適應選擇機制的Lévy飛行產生自適應因子時間為β5,位置更新比較時間為β6,其時間復雜度T′5=O(β5+β6)。

綜上MISSA時間復雜度T′=T′1+(T′2+T′3+T′4+T′5)=T。以上分析表明,相對于標準SSA,MISSA的優越性沒有以時間復雜度的增加為代價。

6 結束語

(1) 通過仿真實驗測試,對于13個測試函數在30,50和100維度下進行對比,可以發現,MISSA相較于標準SSA在高維情況下尋優精度和收斂速度均有較大提高,改善了易陷入局部最優的情況,與其他算法相比具有很強的競爭力。

Table 8 Ablation experimental results of algorithm 表8 算法消融實驗結果

(2) 通過改進算法的有效性與時間復雜度分析可知,各個策略都一定程度上改進了算法的性能且混合策略使性能提高最明顯。與標準SSA相比,MISSA在具備更強性能的同時并沒有增加時間復雜度。