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

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

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

1 引言

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

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

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

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

2.1 麻雀搜索算法

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

(1)

追隨者跟隨發現者進行覓食,這一行為相當于局部搜索,適應度較好的個體優先獲得食物。追隨者的位置更新公式如下

(2)

麻雀種群中存在負責偵察的個體,發現危險時會發出警報,從而提醒發現者帶領其它個體前往安全區域。具體行為公式

(3)

2.2 Tent映射反向學習初始化種群

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

(4)

Tent映射反向學習初始化種群總共分為三步:

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

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

2.3 非線性收斂因子

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

(5)

(6)

2.4 翻筋斗策略

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

i=1,2….N

(7)

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

2.5 局部搜索

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

(8)

(9)

(10)

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

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

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

算法流程

Input

M:最大迭代次數

PD:發現者

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

R2:預警值

N:麻雀總體數量

Output:Xbest,fg

采用Tent映射反向學習初始化種群

t=1;

While(t

根據適應度值找到最優及最差麻雀個體的位置。

R2=rand(1)

For i=1:PD

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

End for

For i=(PD+1):N

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

End for

For i=1:SD

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

End for

得到新的最優個體的位置

根據式(8)-(10)更新最優個體的位置

t=t+1

End while

Return:Xbest,fg

2.7 時間復雜度分析

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

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

3 實驗測試與分析

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

表1 測試函數信息表

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

表2 各算法尋優效果對比表

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

圖2 各算法尋優軌跡圖

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

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

表3 Wilcoxon秩和檢驗P值

4 仿真結果與分析

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

4.1 機器人路徑規劃

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

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

(11)

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

4.2 仿真環境設置

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

4.3 實驗結果與分析

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

表4 各算法優化路徑統計表

圖3 各算法最短路徑規劃圖

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

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

5 結束語

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