混合策略改進的麻雀優(yōu)化算法

陳 俊,何 慶

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院,貴陽 550025) (貴州大學(xué) 貴州省公共大數(shù)據(jù)重點實驗室,貴陽 550025)

1 引 言

在過去的幾年里,全局優(yōu)化問題在數(shù)學(xué),經(jīng)濟,工程實踐中應(yīng)用規(guī)模不斷擴大.傳統(tǒng)優(yōu)化方法對于其中具有高維度,非線性,目標(biāo)函數(shù)不可導(dǎo),復(fù)雜的全局優(yōu)化問題,很難在合理的時間內(nèi)解決[1-3].受到生物系統(tǒng)的啟發(fā),國內(nèi)外學(xué)者開始研究群智能優(yōu)化算法.例如粒子群算法(PSO)[4]、蟻群優(yōu)化算法(ACO)[5]、蝴蝶優(yōu)化算法(BOA)[6]、差分進化算法(DE)[7]、布谷鳥算法(CS)[8]、鯨魚優(yōu)化算法(WOA)[9]、北極熊優(yōu)化算法(PBO)[10]等.

受到麻雀覓食和反捕食行為的啟發(fā),麻雀優(yōu)化算法(Sparrow Search Algorithm,SSA)[11]由薛建凱于2020年提出,該算法相比其它群智能優(yōu)化算法,具有原理簡單、靈活性好、易于實現(xiàn)等優(yōu)點,從而被學(xué)者應(yīng)用于各個領(lǐng)域中.目前麻雀優(yōu)化算法已經(jīng)成功的應(yīng)用于多閾值圖像分割[12],多目標(biāo)優(yōu)化問題[13],無人機航跡規(guī)劃問題[14],但是麻雀優(yōu)化算法同其它群智能算法一樣,在求解接近全局最優(yōu)時,仍然存在群體多樣性下降、易陷入局部最優(yōu)、求解精度不高等缺點.

針對SSA存在的問題,學(xué)者們相繼對SSA進行了改進,譬如歐陽城添[15]等人提出了一種融合K-means的多策略改進麻雀搜索算法,通過K-means算法對初始種群進行聚類,加快種群之間的交流.引入正余弦搜索策略和自適應(yīng)局部搜索方式,提高了收斂精度和尋優(yōu)能力;呂鑫[16]等人提出一種混沌麻雀搜索優(yōu)化算法,引入改進后的tent混沌序列初始化種群,其次引入高斯變異,加強局部搜索.湯安迪[14]等人提出混沌麻雀搜索算法,使用立方映射混沌算子[17],保證初始種群的均勻性;其次使用反向?qū)W習(xí)策略[18],正余弦算法[19]來增強種群的多樣性;毛清華[20]等人提出了一種融合柯西變異和反向?qū)W習(xí)的改進麻雀算法,利用sin混沌序列初始化麻雀個體位置,其次引入自適應(yīng)慣性權(quán)重,協(xié)調(diào)局部和全局搜索能力,最后融合反向?qū)W習(xí)和柯西變異算子進行變異擾動,增強跳出局部最優(yōu)的能力.上述改進策略在一定程度上改善了SSA算法的性能,但是面對求解規(guī)模較大的函數(shù)優(yōu)化問題上還需要更深入的研究.

綜上而言,本文提出一種混合策略改進的麻雀搜索算法(Mixed strategy to improve Sparrow Search Algorithm,MI-SSA),首先引入佳點集法初始化麻雀個體位置,使得初始個體盡可能的遍歷整個搜索空間.然后利用混合黃金正弦和萊維飛行策略以及t-分布擾動策略共同實現(xiàn)發(fā)現(xiàn)者位置更新,改善算法在迭代后期種群多樣性的減少的缺陷.最后通過動態(tài)調(diào)整偵察者數(shù)量,在此來保證種群的多樣性,提高算法跳出局部最優(yōu)的能力.將本文所提算法在14個經(jīng)典基準(zhǔn)函數(shù),Wilcoxon秩和檢驗以及CEC2014函數(shù)上進行數(shù)值實驗,驗證本文所提算法的魯棒性,有效性以及優(yōu)越性.

2 麻雀優(yōu)化算法

麻雀優(yōu)化算法是一種新型群智能優(yōu)化算法,該算法主要分為3種成分,分別是發(fā)現(xiàn)者、加入者和偵察者.同時這3種成分對應(yīng)3種行為,首先具有較好適應(yīng)度的發(fā)現(xiàn)者尋找食物,以獲取食物來源,一般占到種群的10%～20%.其次是加入者,加入者緊跟隨發(fā)現(xiàn)者覓食,以爭取食物,發(fā)現(xiàn)者和加入者之間可相互轉(zhuǎn)換,該行為稱為奪取機制.最后從種群中隨機選取10%～20%的麻雀作為偵察者進行監(jiān)視,當(dāng)撲食者出現(xiàn)時以便麻雀種群及時做出應(yīng)對反映.

其中發(fā)現(xiàn)者位置更新如下:

(1)

加入者位置更新如下:

(2)

最后,麻雀優(yōu)化算法的偵察者位置更新如下:

(3)

3 混合策略改進的麻雀優(yōu)化算法

3.1 佳點集的種群初始化

優(yōu)秀的初始化種群策略能夠使種群個體更均勻的遍歷整個搜索空間,增強種群的多樣性,為算法的全局搜索奠定了基礎(chǔ).在初始化種群階段,SSA在初始化種群的過程中容易受到隨機性的干擾,發(fā)生聚集現(xiàn)象.本文引入佳點集初始化方法,有效提高算法在解空間上的遍歷能力.

佳點集最初由華羅庚[21]等人提出,根據(jù)文獻[22]佳點集產(chǎn)生原理得到點分布序列,在將初始化序列映射到解空間.該方法的構(gòu)造與空間維數(shù)無關(guān),能夠很好地適應(yīng)高維問題,且取點穩(wěn)定.理論上,使用佳點集法生成的點的偏差遠(yuǎn)小于隨機選擇的點.通過對佳點集法和隨機法生成二維初始種群進行對比,如圖1所示.在相同的取點個數(shù)下,使用佳點集初始化方法的個體比隨機初始化方法的個體更加均勻.

圖1 二維初始種群分布圖Fig.1 2-D initial population distribution

3.2 黃金萊維飛行策略

由公式(1)可以知,在R2

萊維飛行是一種步長服從萊維分布的隨機游動.由于其短距離步長與偶爾較長距離步長相間的特性,萊維飛行步長能在未知范圍內(nèi)搜索時,能夠達(dá)到更大范圍,從而加強發(fā)現(xiàn)者的全局搜索能力,又因萊維分布用程序語言表示比較困難,通常采用Mantegna算法[23]來表示.在Mantegna算法中,其步長s的計算公式為:

(4)

(5)

其中,σν通常取1,Γ(β)是Gamma函數(shù),根據(jù)文獻[24]可知,β取值影響萊維飛行的飛行軌跡.β取值越大,越能增強算法的開發(fā)能力.

其次引入正弦函數(shù)與單位圓的關(guān)系[25],使得發(fā)現(xiàn)者能遍歷圓上所有位置.并且通過引入黃金分割系數(shù)縮小解空間,以便獲取可能好結(jié)果的搜索區(qū)域,加快算法搜索速度.綜上結(jié)合萊維飛行和黃金正弦指引機制對發(fā)現(xiàn)者在R2

(6)

(7)

(8)

θ1=-π+2π·(1-τ)

(9)

θ2=-π+2π·τ

(10)

相較于SSA中發(fā)現(xiàn)者的第一段更新策略,本文提出了黃金萊維飛行策略能讓發(fā)現(xiàn)者搜索到更大范圍,如圖2(b)所示.

圖2 發(fā)現(xiàn)者搜索策略Fig.2 Search strategy of producers

3.3 t-分布擾動策略

由文獻[26]可知,群智能算法引入柯西變異,能增強算法的全局探索能力;而引入高斯變異可以保證算法收斂速度.綜合兩者的優(yōu)點,本文采用t-分布擾動策略對發(fā)現(xiàn)者位置進行擾動,以此來提升算法的靈活性和求解效果.

t-分布又稱學(xué)生分布,含有參數(shù)自由度n,當(dāng)t(n→∞)→N(0,1);當(dāng)t(n=1)=C(0,1),其中N(0,1)為標(biāo)準(zhǔn)的高斯分布,C(0,1)為柯西分布.即t-分布的兩個邊界既是高斯分布和柯西分布[27].本文引入該特性對發(fā)現(xiàn)者R2>ST的更新公式進行改進,改進公式如下.

(11)

式(11)中,使用當(dāng)前迭代次數(shù)t作為t分布的自由度參數(shù).增強算法在迭代初期的全局探索能力的同時,也加強了算法在迭代后期的局部開發(fā)能力.

3.4 動態(tài)分配偵察者策略

偵察者一定程度上增強了算法的全局探索能力,并且偵察者數(shù)量占整個麻雀數(shù)量占比越高,跳出局部最優(yōu)的能力越強.但是隨機挑選偵查者的方式,限制了更具有活力的麻雀個體;并且麻雀優(yōu)化算法中固定偵察者數(shù)量的機制,一定程度上減慢了算法運行速度.

為了挑選出更具有跳出局部極值的麻雀個體,本文采用了一種動態(tài)分配偵察者策略,一半的偵察者保持原有的隨機挑選機制,另一半的偵察者引入競爭機制.偵察者執(zhí)行偵察任務(wù)成功率越高,競爭能力越強.將競爭能力強的個體選入下一代的偵察者.令Ni,t表示第i個體在t代執(zhí)行偵察任務(wù)的總次數(shù),Ni,s表示第i個體在t代成功執(zhí)行偵察任務(wù)的總次數(shù),則第i個體在第t代執(zhí)行偵察任務(wù)的成功率ri,t為:

(12)

式(12)中,Ni,s的大小取決于執(zhí)行改進后偵察者位置更新公式(13)前后適應(yīng)度的比較,即若執(zhí)行偵察任務(wù)后的適應(yīng)度優(yōu)于執(zhí)行前的適應(yīng)度,則該個體執(zhí)行偵察任務(wù)成功,執(zhí)行偵察任務(wù)的成功總次數(shù)加一,否則保持不變.

將執(zhí)行偵察任務(wù)成功率進行排序,選取成功率較高的個體(占個體總數(shù)的10%)視為更具有跳出局部最優(yōu)能力的個體,并且加入下一次偵察者.

(13)

3.5 MI-SSA算法的實現(xiàn)步驟(圖3)

圖3 改進算法流程圖Fig.3 Improved algorithm flow chart

3.6 MI-SSA理論時間復(fù)雜度

假設(shè)種群規(guī)模為N,最大迭代次數(shù)M,空間維度D,求解目標(biāo)的適應(yīng)度函數(shù)時間為f(D),由文獻[20]可得,基本的SSA的時間復(fù)雜度為:O(M×N(D+f(D))),改進的MI-SSA的時間復(fù)雜度與基本的SSA相同,分析如下.

初始化階段,假設(shè)種群初始化參數(shù)比之前多x1,且每一維度產(chǎn)生佳點時間為x2.則MI-SSA種群初始階段的時間復(fù)雜度為:

O1(x1+M·N(D·x2+f(D)))=O1(M·N·(D+f(d)))

(14)

改進后的發(fā)現(xiàn)者位置更新階段,假設(shè)發(fā)現(xiàn)者比例為ξ根據(jù)公式(6),每一維度計算levy(λ)需要的時間為x3,生成Q、α、r1、r2隨機數(shù)需要的時間為x4.根據(jù)公式(11),假設(shè)生成學(xué)生分布中的隨機參數(shù),需要理論時間為x5,則MI-SSA的發(fā)現(xiàn)者位置更新公式的理論時間復(fù)雜度為:

O2(ξ·N·(x3+x4+x5)+M·N(D+f(D)))
=O2(M·N·(D+f(D)))

(15)

最后,動態(tài)分配偵察者策略階段的時間復(fù)雜度與基礎(chǔ)的SSA基本相同,該策略在理論上并沒有增加算法的時間復(fù)雜度.綜上所述,MI -SSA的時間復(fù)雜度為:

OSSA+O1+O2=OMI-SSA(M·N·(D+f(D)))

(16)

綜上所述,本文所提MI-SSA和標(biāo)準(zhǔn)SSA的時間復(fù)雜度屬于同一數(shù)量級,說明MI-SSA并沒有增加算法的時間復(fù)雜度.

4 MI-SSA性能實驗與分析

為了驗證本文所提MI-SSA的有效性,本文仿真實驗分為4個部分進行.

a)將MI-SSA與不同改進策略進行對比,驗證改進策略的有效性.

b)將MI-SSA與最新的改進麻雀算法進行對比,并且引入其它改進算法進行對比實驗,再次驗證,MI-SSA的有效性.

c)將本文算法與其它對比算法進行Wilcoxon秩和檢驗,以驗證不同算法之間在多個函數(shù)上的差異顯著性.

d)選取部分CEC2014單峰值,多峰值,混合和復(fù)合型函數(shù)進行函數(shù)求解測試,再次驗證本文算法的性能.

實驗采用14個基準(zhǔn)函數(shù),分為3類;第1類為單峰基準(zhǔn)測試函數(shù),F1～F6;第2類為多峰基準(zhǔn)測試函數(shù),F7～F10;第3類為固定維度的多峰基準(zhǔn)測試函數(shù),F11～F14.

算法的基本參數(shù):種群的規(guī)模30,最大迭代次數(shù)M=500.算法內(nèi)的參數(shù)如表1所示.

表1 算法參數(shù)設(shè)置Table 1 Algorithm parameter setting

4.1 MI-SSA與不同的改進策略對比

將MI-SSA于黃金萊維策略的SSA1,t-分布擾動策略的SSA2,動態(tài)分配警戒者策略的SSA3,以及基本的SSA在空間維度分別為10/30/100/500的條件下,對14個函數(shù)進行求解.獨立運行50次的數(shù)據(jù)進行統(tǒng)計分析,如表2、表3所示.

表2 單峰和多峰值基準(zhǔn)測試函數(shù)測試結(jié)果Table 2 Test results of unimodal and multimodal benchmark test function

表3 固定維度多峰基準(zhǔn)測試函數(shù)測試結(jié)果Table 3 Test results of multimodal benchmark test functions with fixed-dimension

縱向來看,MI-SSA在除去F5外的單峰值函數(shù),在10/100/30/500維度上MI-SSA的平均值均能達(dá)到理論最優(yōu)解,且標(biāo)準(zhǔn)差最小.對于函數(shù)F5,MI-SSA尋優(yōu)精度和穩(wěn)定性好于SSA.在多峰值函數(shù)上,隨著維度的上升,標(biāo)準(zhǔn)SSA的求解精度出現(xiàn)下降現(xiàn)象,但是MI-SSA的求解精度無論是在10維度,30維度,100維度還是500維度均能取得理想的效果.

具體來說,3個改進算法對基準(zhǔn)函數(shù)的求解上,無論平均值還是標(biāo)準(zhǔn)差上都好于SSA.說明改進策略的有效性.對于F1函數(shù),SSA2和SSA3均能找到理論最優(yōu)值,SSA1雖然沒能找到理論最優(yōu)值,但是相對于SSA,精確度也有近200個點的提升.對于F2函數(shù),3個策略尋優(yōu)精確度都高于SSA,其中SSA3提升最為明顯,約有200多個數(shù)量級的提升.3個策略的融合的MI-SSA,能在F2函數(shù)上找到理論最優(yōu)值,說明3個改進策略的互補,改進策略可靠有效.在10維度下,對于F5函數(shù)SSA的尋優(yōu)精度和穩(wěn)定性優(yōu)于其它算法,其次是MI-SSA,但是在30/100/500維度下,MI-SSA的表現(xiàn)更好,其次是SSA1.這是由于隨著維度的升高,搜索空間增大,求解難度加大的原因,客觀說明改進后的算法在F5函數(shù)的求解上魯棒性更好.對于F11～F14函數(shù),MI-SSA無論是平均值還是標(biāo)準(zhǔn)差都優(yōu)于SSA,提升明顯.在F12求解上,結(jié)合黃金萊維飛行策略的SSA2尋優(yōu)精度最高,且標(biāo)準(zhǔn)差最小,表現(xiàn)出較強的穩(wěn)定性.

圖4給出了MI-SSA、SSA、SSA1、SSA2、SSA3,以及PSO、BOA的F1～F10函數(shù)的收斂曲線圖.由于部分函數(shù)收斂精度較高,本文對尋優(yōu)適應(yīng)度值(縱坐標(biāo))取10為底的對數(shù),為了方便觀察函數(shù)的收斂情況.由圖可知,無論是單峰值函數(shù)和多峰值函數(shù),相比SSA,MI-SSA體現(xiàn)了更快的尋優(yōu)速度和更高的尋優(yōu)精度.對于F1,F3,F6,F8,F10函數(shù)的求解,MI-SSA能在300代以內(nèi)找到理論最優(yōu)值,證明了算法具有很好的收斂性能.從改進的策略上來看,SSA3的尋優(yōu)效果最好,其次是SSA2,SSA1次之.3個改進策略的收斂曲線大部分在SSA的收斂曲線的下方,說明3個改進策略改進的有效性.最后加入BOA,和PSO進行對比,整體來說,SSA的收斂曲線大部分都在BOA和PSO下方,說明SSA在求解F1～F10上的能力.綜合MI-SSA在表3、表4和圖4上的表現(xiàn),充分證明3種改進策略的有效性,以及MI-SSA對于本文多種基準(zhǔn)函數(shù)具有較強的尋優(yōu)能力,特別是對于高維的函數(shù).

圖4 基準(zhǔn)函數(shù)平均收斂曲線Fig.4 Function average convergence curve

表4 CSSA與MI-SSA算法性能比較Table 4 CSSA and MI-SSA algorithm performance comparison

4.2 與最新的群智能算法比較

目前該算法的相關(guān)文獻較少,且改進麻雀算法的基本參數(shù)設(shè)置各不相同.為了進一步體現(xiàn)MI-SSA的有效性,本文首先引入了文獻[20]中,最大迭代次數(shù)500代,種群規(guī)模為30的條件下,對其中的八個測試函數(shù)進行算法性能比較,實驗結(jié)果如表2所示(“——”表示參考文獻未給出相應(yīng)數(shù)據(jù)).由表2可知,MI-SSA在F1,F2上的尋優(yōu)精度是高于ISSA.在其他的函數(shù)上,MI-SSA尋優(yōu)精度與ISSA持平.

其次將MI-SSA算法與文獻[16]中的CSSA進行性能上的比較,與CSSA同一條件下獨立運算50次后,對數(shù)據(jù)進行統(tǒng)計分析,如表5所示.由表可知,MI-SSA在其中F1～F5無論是尋優(yōu)精度還是穩(wěn)定性都優(yōu)于CSSA算法.對于函數(shù)F8～F10,MI-SSA,CSSA優(yōu)化效果相當(dāng).綜上,在對于以上基本測試函數(shù),MI-SSA均表現(xiàn)出較優(yōu)的穩(wěn)定性和尋優(yōu)能力.

表5 與4種群智能算法在100維度下的結(jié)果比較Table 5 Comparison with the results of the four-species intelligent algorithm in 100 dimensions

將MI-SSA算法與PSO,BOA,WOA,GOW進行性能比較,比較結(jié)果如表5所示.對該5種算法在最大迭代次數(shù)500代,空間維度100dim,種群規(guī)模為30的條件下進行仿真實驗.由表可知,MI-SSA在10個基準(zhǔn)函數(shù)的表現(xiàn),都優(yōu)于其它4種算法.進一步說明改進算法的有效性.

4.3 Wilcoxon秩和檢驗

本文采用Wilcoxon秩和檢驗驗證MI-SSA與其它算法的顯著性差異.每次運行結(jié)果在P=5%的顯著性水平下,當(dāng)p值小于5%時候,拒絕H0假設(shè),說明兩種算法的差異性顯著,否則就是接受H0假設(shè),說明兩種算法在整體上是相同的.由于算法不能和自身比較,所以表中的標(biāo)記為“Na”表不適用,表示無法進行顯著判斷,“R”為顯著性判斷結(jié)果,“+”,“-”,“=”分別表示MSBOA算法的性能優(yōu)于,劣于和相當(dāng)對比算法.從表6中可以觀察到大部分的p值是小于5%,“R”為“+”表示拒絕H0假設(shè).

表6 基準(zhǔn)Wilcoxon秩和檢驗P值Table 6 P-value for Wilcoxon′s rank-sum test on benchmark function

4.4 CEC2014測試函數(shù)尋優(yōu)對比

為了進一步驗證MI-SSA的有效性和魯棒性,本文在CEC2014目標(biāo)優(yōu)化函數(shù)中選取部分單峰值(Unimodal Functions,UN)、多峰值(Multimodal Functions,MF)、混合(Hybrid Function,HF)和復(fù)合型(Composition Function,CF)的函數(shù)進行優(yōu)化求解.由于CEC2014函數(shù)具有復(fù)雜的特征,大多數(shù)算法都很難找到函數(shù)最優(yōu)解,所以本文選取部分函數(shù)進行測試,總結(jié)如表7所示.實驗在最大迭代次數(shù)上設(shè)置為1000,算法的參數(shù)設(shè)置與前面保持一致.

表7 部分CEC2014函數(shù)介紹Table 7 Part of the CEC2014 function

將MI-SSA與SSA1,SSA2,SSA3,PSO,BOA,進行比較.部分函數(shù)獨立運行30次后的結(jié)果如表8所示.在選取的10個CEC2014函數(shù)中,結(jié)合黃金萊維飛行策略的SSA1在前4個CEC測試函數(shù)上取得更優(yōu)結(jié)果,MI-SSA在CEC5、CEC12、CEC16、CEC23、CEC29、CEC30上的表現(xiàn)優(yōu)于其它5個算法.對于CEC05、CEC12、CEC13和CEC30測試函數(shù),MS-SSA基本收斂到了理論最優(yōu)值;對于復(fù)合特征CEC23、CEC29和CEC30函數(shù),MS-SSA尋優(yōu)標(biāo)準(zhǔn)差為0,說明其對于復(fù)合特征函數(shù)尋優(yōu)穩(wěn)定性很高.

表8 CEC2014 優(yōu)化結(jié)果比較Table 8 Comparison of optimization results of CEC 2014

5 結(jié)束語

本文針對基本麻雀優(yōu)化算法存在容易陷入局部最優(yōu),收斂速度慢等問題,提出了一種混合策略改進麻雀優(yōu)化算法.算法初期,引入佳點集構(gòu)造初始化麻雀位置來保證初始種群分布更加均勻.迭代過程中,本文提出了黃金萊維飛行策略,有效的加快收斂速度同時改善算法在迭代后期種群多樣性的減少的缺陷;引入t-分布擾動策略,提升算法的靈活性和求解效果;最后提出動態(tài)分配偵察者策略,平衡偵察者全局探索與局部開采的能力.通過對14個基準(zhǔn)測試函數(shù)和10個CEC2014基準(zhǔn)函數(shù)仿真測試.結(jié)果表明,本文的算法在求解高維復(fù)雜函數(shù)問題上具有速度快、精度高和魯棒性強的優(yōu)勢.另外通過Wilcoxon秩和檢驗,本文的算法表現(xiàn)出更優(yōu)的顯著性差異性.

在將來的的研究中,準(zhǔn)備將本文提出了算法應(yīng)用于實際工程優(yōu)化問題.獲取更好的算法性能是下一步的研究方向和重點.