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

李江華,王鵬暉,李 偉

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

1 引言

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

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

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

2 麻雀搜索算法

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

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

(1)

發(fā)現(xiàn)者的位置更新方式如式(2)所示：

(2)

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

(3)

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

(4)

3 改進的麻雀搜索算法

3.1 精英反向學習策略

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

(5)

3.2 階段性控制步長策略

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

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

(6)

l=(a-1)×rand+1

(7)

(8)

(9)

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

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

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

3.3 混沌余弦變化因子

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

(10)

(11)

其中,δ為常數(shù),本文經(jīng)過多次實驗,設置為3。

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

Circle映射如式(12)所示：

(12)

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

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

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

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

(13)

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

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

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

(14)

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

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

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

(15)

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

(16)

(17)

其中,參數(shù)β取值范圍為(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飛行可以對個體的位置進行更新,但無法保證更新后位置的新適應度值優(yōu)于原位置的適應度值。因此,本文利用貪心機制的特性,通過更新前后位置的適應度值比較,保留更優(yōu)的解,貪心機制如式(18)所示：

(18)

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

4 MISSA算法步驟

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

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

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

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

步驟5根據(jù)式(6)更新發(fā)現(xiàn)者位置;

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

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

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

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

步驟10輸出最優(yōu)個體適應度值及其位置。

5 實驗與結果分析

5.1 實驗設計與測試函數(shù)

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

Table 1 Unimodal test functions

Table 2 Multimodal test functions

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

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

Table 3 Algorithm parameters setting

5.2 算法對比分析

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

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

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

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

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

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

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

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

Table 7 Friedman test on test functions with different dimensions

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

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

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

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

5.3 改進算法有效性分析

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

5.4 MISSA時間復雜度分析

假設SSA算法中種群規(guī)模為n,維度為J,初始化種群參數(shù)時間為α1,求個體適應度值的時間為F(J),發(fā)現(xiàn)者數(shù)量為pNum,每一維更新時間為α2,跟隨者數(shù)量sNum,每一維更新時間為α3,警戒者每一維更新時間為α4。因此初始階段時間復雜度T1=O(α1+n(F(J)+J×α1));發(fā)現(xiàn)者更新時間復雜度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));發(fā)現(xiàn)者更新公式產生參數(shù)時間為β2,發(fā)現(xiàn)者更新時間復雜度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的優(yōu)越性沒有以時間復雜度的增加為代價。

6 結束語

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

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

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