翻筋斗的改進麻雀搜索算法

歐陽城添,黃祖威,朱東林,閆少強

(1. 江西理工大學信息工程學院,江西 贛州 341000;2. 火箭軍工程大學作戰(zhàn)保障學院,陜西 西安 710038)

1 引言

隨著優(yōu)化問題的復雜度不斷提升,群智能算法應(yīng)用愈加廣泛,尤其在工程領(lǐng)域上表現(xiàn)突出。麻雀搜索算法(Sparrow search algorithm,SSA)是Xue和Shen[1]于2020年提出的新型群智能優(yōu)化算法。作者抽象了麻雀群體的覓食和反捕食行為,以食物位置為待求解,模擬麻雀覓食過程來尋找最優(yōu)解。該算法原理簡單,種群角色與參數(shù)較少,且魯棒性強,在函數(shù)優(yōu)化方面比傳統(tǒng)的粒子群算法(Particle Swarm Optimization,PSO)[2]和灰狼算法(Grey Wolf Optimizer,GWO)[3]的精度更高,尋優(yōu)能力更強。在麻雀搜索算法提出后,它也被應(yīng)用于工程領(lǐng)域中,例如提出者薛建凱[4]已經(jīng)成功地將其與無人機航跡規(guī)劃結(jié)合,并取得良好成效。但SSA也有一些弊端,比如易陷入局部最優(yōu)和依賴初始化種群等問題。

為改進麻雀搜索算法存在的缺陷,呂鑫等[5]提出了混沌麻雀搜索算法。通過引入基于隨機變量的Tent映射、混沌擾動及高斯變異機制等策略,豐富種群多樣性,防止算法陷入局部最優(yōu),加強了算法的全局搜索能力。呂鑫等[6]還提出基于改進麻雀搜索算法(ISSA)的多閾值圖像分割法。通過引入鳥群算法的思想,來加速算法收斂,提高算法的搜索能力。毛清華等[7]提出一種融合柯西變異和反向?qū)W習的改進麻雀搜索算法,利用一種折疊次數(shù)無限的sin混沌機制初始化種群,引入自適應(yīng)權(quán)重策略協(xié)調(diào)局部搜索與全局搜索,再采用融合柯西變異和反向?qū)W習策略在最優(yōu)位置上進行擾動變異,產(chǎn)生質(zhì)量更高的新解,增強算法跳出局部最優(yōu)的能力。Liu等[8]同樣引入混沌策略增加種群的多樣性,并使用自適應(yīng)慣性權(quán)重平衡算法的收斂速度與探索能力,最后采用柯西-高斯突變策略來擺脫后期算法停滯的限制。Zhang等[9]采用logistic映射、自適應(yīng)參數(shù)和變異算子等策略,增強SSA的全局搜索能力。Liang等[10]在SSA中融入均勻混沌、自適應(yīng)慣性權(quán)重等策略,還對算法中的邊界約束作出改進,增添種群多樣性,一定程度上提升了算法的全局搜索能力。

雖然關(guān)于麻雀搜索算法的改進策略不斷提出,但每種策略的提出沒有明顯改變麻雀搜索算法自身的尋優(yōu)機制,僅在鄰域空間內(nèi)提高算法的搜索能力,沒有動態(tài)調(diào)節(jié)算法的尋優(yōu)能力,導致算法仍有缺陷。例如,常見的混沌映射雖然能提高種群的多樣性,使種群分布均勻,但存在不確定性,沒有一定的學習能力。針對這些不足,本文提出翻筋斗的改進麻雀搜索算法(SISSA)。在算法初期采用Tent映射和反向?qū)W習初始化種群,具有一定的學習選擇能力,為算法尋優(yōu)提供充分的準備;之后將非線性收斂因子融入發(fā)現(xiàn)者的位置更新中,增強發(fā)現(xiàn)者的探索能力,再引入翻筋斗策略使追隨者的位置更新具有靈活性,使得算法尋優(yōu)方式更加細致,提高算法的局部搜索能力;最后利用兩個歷史最優(yōu)解的差分結(jié)果找到可靠的解。通過12個標準測試函數(shù)將SISSA與其它6種算法進行對比,證明了SISSA具有高效的尋優(yōu)能力,且在Wilcoxon統(tǒng)計檢驗上得到了有效的驗證。將SISSA和三種算法應(yīng)用于機器人路徑規(guī)劃,通過比較觀察得出,SISSA在實際應(yīng)用中也有更好的效果。

2 翻筋斗的改進麻雀搜索算法

2.1 麻雀搜索算法

麻雀種群有兩種角色,分別是發(fā)現(xiàn)者和追隨者,它們有覓食、跟隨、偵察三種行為。發(fā)現(xiàn)者具有良好的全局搜索能力,帶領(lǐng)其它個體找到最優(yōu)食物的位置,發(fā)現(xiàn)者的位置更新公式如下

(1)

追隨者跟隨發(fā)現(xiàn)者進行覓食,這一行為相當于局部搜索,適應(yīng)度較好的個體優(yōu)先獲得食物。追隨者的位置更新公式如下

(2)

麻雀種群中存在負責偵察的個體,發(fā)現(xiàn)危險時會發(fā)出警報,從而提醒發(fā)現(xiàn)者帶領(lǐng)其它個體前往安全區(qū)域。具體行為公式

(3)

2.2 Tent映射反向?qū)W習初始化種群

在群智能優(yōu)化算法中,初始化種群至關(guān)重要。其主要目的是為個體尋優(yōu)提供充分的準備與良好的尋優(yōu)空間,使種群分布密度較高,加快算法的尋優(yōu)速度。但多數(shù)初始化種群策略具有不確定性等因素,例如多種混沌映射理論,初始化過程沒有絕對的完整及均勻性。為使得種群個體更加可控,本文采用Tent映射和反向?qū)W習對種群進行初始化。Tent映射在均勻性及遍歷性較其它映射具有優(yōu)勢[11,12],所以采用Tent映射初始化麻雀群體,并采用反向?qū)W習策略[13,14]對初始種群進行提煉,篩選出更加優(yōu)秀的麻雀個體,為算法尋優(yōu)提供良好的環(huán)境,從而提升算法的收斂速度。Tent映射的表達式為

(4)

Tent映射反向?qū)W習初始化種群總共分為三步:

1)使用Tent映射產(chǎn)生的混沌序列初始化麻雀種群的位置xij(i=1,2…D,j=1,2…N),N表示種群數(shù)量;

3)將兩種方式產(chǎn)生的個體位置按照適應(yīng)度高低排序,選取適應(yīng)度排名前N個的個體作為最終的初始種群。

2.3 非線性收斂因子

發(fā)現(xiàn)者作為種群的領(lǐng)導者,需要廣泛細致的搜索機制。非線性收斂能夠平衡局部搜索與全局搜索能力,與自適應(yīng)收斂因子相比具有更高的可信度,因此本文采用如下公式更新發(fā)現(xiàn)者的位置

(5)

(6)

2.4 翻筋斗策略

麻雀搜索過程中,追隨者會緊隨發(fā)現(xiàn)者進行搜索,這種搜索方式單調(diào),且范圍較窄,容易出現(xiàn)早熟現(xiàn)象。傳統(tǒng)的反向?qū)W習策略雖能提升種群多樣性,但其只能在平行空間內(nèi)找到反向解,算法的靈敏度不佳。針對此問題,本文采用翻筋斗覓食策略[15]來解決。翻筋斗策略在搜索方式上更加多樣,通過此策略更新追隨者位置,靈活搜索可靠解,以此提升SSA跳出局部最優(yōu)的能力。翻筋斗策略是以當前最優(yōu)為中心點,每次更新位置都位于當前位置與其關(guān)于中心點對稱的位置連線之間。位置更新公式如下

i=1,2….N

(7)

式(7)中,S代表空翻因子,本文將S取值為2,目的是使每次位置更新都能在當前位置與對稱位置之間;r1,r2是區(qū)間[0,1]中的隨機數(shù)。翻筋斗策略示意圖如圖1所示。

2.5 局部搜索

每當個體找到當前最優(yōu)解時,如果遇到局部極值就會使算法尋優(yōu)能力受阻。設(shè)麻雀搜索算法尋優(yōu)過程中P1與P2分別為種群歷史最優(yōu)解及種群歷史次代最優(yōu)解。本文采取兩解的差分指導P1進行搜索,找到鄰域內(nèi)可靠的最優(yōu)解。具體實現(xiàn)方式如下:

(8)

(9)

(10)

其中,fit(x)為x的適應(yīng)度值。

2.6 翻筋斗的改進麻雀搜索算法

綜合上述策略,本文提出一種翻筋斗麻雀搜索算法。算法初始階段采用Tent混沌映射反向?qū)W習初始化種群,搜索階段采用非線性收斂因子改善發(fā)現(xiàn)者的搜索范圍,再引入翻筋斗策略使追隨者的搜索更具有靈活性,避免出現(xiàn)早熟現(xiàn)象,最后通過兩個歷史最優(yōu)解的差分進行局部搜索,并更新鄰域內(nèi)質(zhì)量更優(yōu)質(zhì)的解,從而加快算法的尋優(yōu)速度。具體偽代碼如下:

算法流程

Input

M:最大迭代次數(shù)

PD:發(fā)現(xiàn)者

SD:意識到危險的麻雀個體

R2:預警值

N:麻雀總體數(shù)量

Output:Xbest,fg

采用Tent映射反向?qū)W習初始化種群

t=1;

While(t

根據(jù)適應(yīng)度值找到最優(yōu)及最差麻雀個體的位置。

R2=rand(1)

For i=1:PD

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

End for

For i=(PD+1):N

根據(jù)式(2)和(7)更新追隨者的位置

End for

For i=1:SD

根據(jù)式(3)意識到危險的麻雀個體位置

End for

得到新的最優(yōu)個體的位置

根據(jù)式(8)-(10)更新最優(yōu)個體的位置

t=t+1

End while

Return:Xbest,fg

2.7 時間復雜度分析

時間復雜度是衡量算法質(zhì)量的重要指標。從宏觀上來看,設(shè)算法的種群規(guī)模為P,最大迭代次數(shù)為M,問題的維度為D,SSA與其它智能優(yōu)化算法一樣,時間復雜度為O(P×M×D),而SISSA僅在初始化階段增加了時間復雜度為O(P)的反向?qū)W習策略,對整個算法尋優(yōu)而言,并沒有時間增量,因此增加的O(P)可以忽略不計。

從微觀上來看,設(shè)追隨者的比例為r,計算反向解的時間為t1,計算最優(yōu)的前20個體的時間忽略不計,引入翻筋斗策略的位置更新計算時間為t2,最優(yōu)解的局部搜索的計算時間為t3,且Tent映射初始化與原算法時間復雜度相同。從算法偽代碼可以看出,SISSA算法在初始化階段增加了O(P*(t1)),在追隨者位置更新階段增加了O(M×r×P×t2),在最優(yōu)解更新階段增加了O(M×t3),可見SISSA較SSA增加了O(P×(t1)+M×r×P×t2+M×t3),但在數(shù)量級上并沒有提升,且能使算法的尋優(yōu)效率與精度有效地提高,所以時間復雜度的些許增加有積極意義。

3 實驗測試與分析

為了檢驗 SISSA的性能,選取表1 中的 12個標準測試函數(shù)進行測試,其中包括復雜單峰測試函數(shù) F1-F8 和復雜多峰測試函數(shù)F9-F11,F10及F11是來自于CEC2017中的復雜函數(shù),其邊界范圍較廣,F12為固定維度的復雜函數(shù)。具體測試函數(shù)信息如表1 所示。

表1 測試函數(shù)信息表

將SISSA與CSSA,ISSA,BSO,SSA,PSO,GWO各算法進行對比,BSO[16]是近幾年研究比較熱門的融合算法。為保證算法的公平性,所有的仿真在 CPU 為 Intel(R) Core(TM) i5-10200H,主頻為 2.40GHz,內(nèi)存為16 GB 的 PC 上,采用 MATLAB R2019a實現(xiàn)。參數(shù)設(shè)置與各文獻中參數(shù)設(shè)置保持一致,種群規(guī)模為100,最大迭代次數(shù)100,PSO兩個學習因子c1=c2=1.4962;權(quán)重w=0.729;BSO與文獻[16]保持一致;每個算法獨立運行 30 次,統(tǒng)計各算法運行結(jié)果的最優(yōu)值,平均值,標準差三項指標,衡量算法的尋優(yōu)性能及穩(wěn)定性。實驗結(jié)果如表2。由表2可看出,SISSA具有較強的尋優(yōu)能力,尤其是在F5及F11中,只有SISSA找到理論最優(yōu)值,其它算法的尋優(yōu)效果基本落后于SISSA;在復雜邊界問題中,PSO、BSO與GWO表現(xiàn)較差,不適用此類問題。綜上可說明,SISSA在打破了原算法尋優(yōu)機制的束縛,存在一個合理的尋優(yōu)手段。

表2 各算法尋優(yōu)效果對比表

為更好的體現(xiàn)SISSA較強的收斂能力,圖2展現(xiàn)出了各算法在12個函數(shù)上的收斂對比圖。如圖2所示,SISSA具有較強的收斂能力,在單峰函數(shù)上具有較快的收斂速度,尤其在F1-F4和F7-F8中,收斂速度和精度與其它算法相比具有較大優(yōu)勢;在多峰函數(shù)上具有較好收斂精度,僅在F9中稍微落后于BSO,且與其它算法相比具有更好的跳出局部最優(yōu)能力;在固定維函數(shù)中,SISSA的優(yōu)化效果總體來看也較有優(yōu)勢,證明SISSA的有更強的局部搜索和全局搜索能力。綜上所述,多策略的SISSA算法在函數(shù)優(yōu)化上具有更加優(yōu)秀的表現(xiàn),證明其函數(shù)優(yōu)化能力更強。

圖2 各算法尋優(yōu)軌跡圖

僅憑三項指標確定改進算法的性能具有片面性,為體現(xiàn)其合理性及公平性,通過統(tǒng)計檢驗對改進算法相比于其它算法的優(yōu)越性進行評估。本文采用Wilcoxon秩檢驗顯示每個算法的是否存在顯著性差異,在5%的顯著水平下進行試驗,當P<0.05時,可認為拒絕零假設(shè),即存在顯著性差異;P>0.05時,則表明兩算法之間的差異性不明顯,則用N/A表示。

由表3可看出,改進的算法SISSA僅在F6函數(shù)上與其它算法差異不明顯,剩余函數(shù)上均具有顯著性的差異。由此可見,SISSA較其它算法具有更高的精度,進一步驗證了SISSA的有效性。

表3 Wilcoxon秩和檢驗P值

4 仿真結(jié)果與分析

為了進一步驗證SISSA的實用性與可靠性,本文將其運用到機器人路徑規(guī)劃的仿真當中。

4.1 機器人路徑規(guī)劃

機器人路徑規(guī)劃本質(zhì)上就是對于給定的起點與終點,通過算法決定躲避障礙的策略,選擇出一條最佳路徑。這里采用柵格化[17]的方法來模擬機器人路徑規(guī)劃的環(huán)境。柵格化法用l×l個小方格代替真實環(huán)境,并且每一個小方格的值為0或1,1代表障礙物,0表示可通行。此方法不僅有效地簡化了路徑規(guī)劃的環(huán)境創(chuàng)建過程,還能夠更便捷地觀察算法路徑規(guī)劃的效果。

SISSA應(yīng)用于機器人路徑規(guī)劃仿真時,每只麻雀代表著一條可行路徑,每只麻雀位置的維度D由柵格數(shù)l決定。根據(jù)適應(yīng)度值選擇路徑,適應(yīng)度值計算公式如下

(11)

其中,j是麻雀個體的第j個維度。

4.2 仿真環(huán)境設(shè)置

實驗通過與CSSA、SSA、GWO在15×15的柵格環(huán)境下作對比來驗證SISSA的可行性。設(shè)置種群數(shù)量為50,迭代次數(shù)為20,其它實驗參數(shù)與上述實驗一致。每個算法執(zhí)行15次以消除偶然性。

4.3 實驗結(jié)果與分析

各算法的最優(yōu)路徑如圖3所示。本實驗采用三個指標——最佳路徑、平均路徑和最差路徑來衡量各算法的穩(wěn)定性和可行性。各算法的優(yōu)化統(tǒng)計表如表4,平均路線收斂圖如圖4。

表4 各算法優(yōu)化路徑統(tǒng)計表

圖3 各算法最短路徑規(guī)劃圖

圖4 各算法的平均路徑收斂圖

如圖3所示,SISSA規(guī)劃出的路徑最簡單、最清晰,其次是CSSA,而SSA和GWO從它們繞行的路徑能明顯發(fā)現(xiàn)陷入了局部最優(yōu)。由表4可以看出,SISSA的最佳路徑和平均路徑在四種算法中最小,并且其最佳路徑和最差路徑的差距最小,這展現(xiàn)出了SISSA良好的搜索能力和穩(wěn)定性。從圖4中可以看出,GWO的收斂性不足,收斂速度慢且不穩(wěn)定;SSA及其改進算法都表現(xiàn)出良好的性能,收斂速度快;總體來說,SISSA的表現(xiàn)最好。由此可見,多策略的SISSA算法在搜索時更加靈活,大大提高了算法的搜索能力,在路徑規(guī)劃上表現(xiàn)優(yōu)異。

5 結(jié)束語

針對新提出的麻雀搜索算法的不足,本文提出了翻筋斗的改進麻雀搜索算法,采用Tent映射反向?qū)W習初始化種群,使算法具有判斷選擇能力,為麻雀尋優(yōu)提供良好的空間;提出非線性收斂因子使得發(fā)現(xiàn)者的位置更新質(zhì)量更高;引入翻筋斗策略更新追隨者的位置,使其更新方式更加靈活細致,最后通過兩個歷史最優(yōu)解的差分進行局部搜索,使算法找到的解的質(zhì)量得到有效的提升。在12個標準測試函數(shù)與其它算法的尋優(yōu)能力進行對比,證實了SISSA的尋優(yōu)效果,同時在Wilcoxon秩和檢驗中進一步驗證了SISSA的有效性。通過對機器人路徑規(guī)劃的仿真,驗證了SISSA的可行性和實用性。SISSA規(guī)劃的路徑清晰,代價函數(shù)最小?？梢钥闯?多策略的引入有效地提高了基本麻雀搜索算法的優(yōu)化能力。但SISSA算法在個別函數(shù)上存在穩(wěn)定性不足情況,如何減小每次尋優(yōu)結(jié)果的差異性是接下來的工作重點。