多策略優化麻雀搜索算法及其路徑規劃的應用

梁景潤,劉麗桑,陳炯暉,張友淵,陳家煜

(1. 福建理工大學 電子電氣與物理學院,福建 福州 350118;2. 福建省工業集成自動化行業技術開發基地,福建 福州 350118)

在移動機器人領域,路徑規劃是指從起始點至目標點規劃出一條安全、平滑和最短的路徑[1]。路徑規劃在智能倉儲、智能物流、柔性制造和自動駕駛等領域應用廣泛,路徑規劃算法也一直是研究熱點。傳統的全局路徑規劃算法有Dijkstra、A*、PRM和RRT等。為了解決貨運索道的路徑規劃問題,張飛凱等[2]對Dijkstra算法進行了優化,減少了路徑搜索的計算量。謝春麗等[3]引入跳點搜索算法對A*算法進行改進,有效節省了算法的運行時間和內存開銷。為了提高路徑的安全性,程謙等[4]對PRM算法進行優化,使路徑連接更多的采樣點并增加了路徑在彎道處與障礙物的距離。為了實現移動機器人在狹隘通道上的路徑規劃,陳法法等[5]對RRT算法進行了改進,在增加道路探索成功率的同時減少了路徑成本。然而,這些傳統的全局路徑規劃算法大多存在尋路時間長、內存開銷大和復雜度較高等缺點。

近年來,一些智能優化算法如粒子群算法(PSO)、遺傳算法(GA)、螢火蟲優化算法(FA)、蟻群算法(ACO)、灰狼優化算法(GWO)和麻雀搜索算法(SSA)等也被引進移動機器人的路徑規劃領域。師瑋等[6]提出一種改進的PSO方法來優化工業機械臂的運動軌跡,減少了必需的運動時間,提高運動軌跡優化的精度。陳高遠等[7]提出了一種用于移動機器人路徑規劃的改進GA算法,并用PSO進行局部搜索,以加快GA算法的收斂速度,防止其陷入局部最優。針對移動機器人在運動過程中存在實際運動軌跡與預設軌跡偏差過大等問題,于飛等[8]通過對ACO進行改進,完成了移動機器人的按需規劃,并最小化了移動機器人的運動軌跡與預設軌跡的偏差。虞馥澤等[9]提出了一種改進的FA并用于求解多機器人的路徑規劃問題,在提高路徑安全性的同時減少路徑長度。劉志強等[10]采用多種策略對傳統的GWO進行了改進,解決了該算法收斂速度慢和容易陷入局部最優等問題,提高了算法的尋優精度,并減少了算法的規劃路徑的長度。

上述研究成果從多個角度為解決移動機器人的路徑規劃難題提供思路,但還有一些問題有待解決,如算法規劃的路徑過長、路徑轉彎次數過多和路徑不夠平滑等[11]。針對這些問題,本研究提出了一種基于Logistic混沌映射、自適應慣性因子和柯西變異等多種先進策略改進的麻雀搜索算法,以期改善麻雀初始種群的分布,提高算法初始解的質量,平衡算法的全局探索能力與局部勘探能力,增強算法跳出局部最優解的能力。

1 傳統的麻雀搜索算法

麻雀搜索算法是一種元啟發式群智能優化算法,來源于麻雀種群的捕食和反捕食行為特征具有結構簡單、調優參數少和易于實現等優點[12]。然而,麻雀搜索算法與其他智能優化算法一樣,也存在初始種群質量不高、搜索區域分布不均和易陷入局部最優等缺點[13]。

一般地,麻雀種群主要被劃分為發現者和跟隨者。其中,發現者主要幫助麻雀種群發現食物源,并引領麻雀種群向食物源靠近。除發現者外,大部分的麻雀為跟隨者,主要跟隨發現者來獲取食物[14]。此外,麻雀種群在捕食過程中還會隨機選擇一小部分的麻雀個體作為偵查者,大約占整個種群的10%～20%。當發現天敵時,偵查者會向整個麻雀群體發出警告信號,整個麻雀群體必須盡快逃到其他安全的地方。

假設麻雀種群的集合矩陣表示為:

X=[x1,x2,x3,…,xp]T

(1)

其中,xi=[xi,1,xi,2,…,xi,d],i=(1,2,…,p),p代表麻雀種群的數量,d代表變量的維數,則麻雀種群的適應度函數用式(2)表示。

F(x)=[f(x1),f(x2),…,f(xn)]T

(2)

其中,f(xi)=[f(xi,1),f(xi,2),…,f(xi,d)],表示第i個麻雀的適應度值。

一般地,優先獲得食物的麻雀將成為發現者,其適應度值也會相應變好,從而幫助整個麻雀種群獲得食物。發現者的位置更新方式[15]可用式(3)表示。

(3)

表1 4種算法的性能對比Tab.1 Comparison performance of four algorithms

除了發現者,大多數麻雀都是跟隨者,跟從發現者獲取食物。跟隨者的位置更新方式[15]如式(4):

(4)

式中,Xworst代表麻雀種群中適應度最差的麻雀個體,Z為1×d的矩陣,且Z′=ZT(ZZT)-1。當i≤(n/2)時,表明第i個跟隨者的適應度值較好,可以獲得充足的食物;反之,則代表其適應度值較差,需要到其他地方去補充食物。

為了安全起見,麻雀種群中通常會被選擇一小部分的麻雀個體作為警戒者。警戒者的位置更新方式[15]如式(5):

(5)

式中,Xbest表示全局最佳位置。λ是一個服從[0,1]正態分布的步長可控的隨機數。k代表麻雀的行進方向,是[-1,1]范圍的均勻隨機數。fi和fg分別代表當前的全局最佳和最差的適應度值。ε為避免分母為0的最小常數。fi=fg表示麻雀處于種群的邊緣,容易受到天敵的襲擊。

綜上,傳統的麻雀搜索算法有以下缺點:

(1)麻雀種群在初始化時是隨機創建的,導致種群分布不均,種群多樣性較差,算法的初始解質量較低。

(2)發現者的位置更新方式具有一定的局限性,無法平衡全局搜索能力和局部挖掘能力。當預警值小于所設定的安全閾值時,發現者的搜索能力將會隨著算法的迭代次數的增加而慢慢降低,導致算法的空間搜索區域不足,算法收斂效率較低。

(3)最差和最優麻雀個體缺乏交流反饋,面對復雜的工程優化問題時容易陷入局部最優解。

2 基于多策略優化的麻雀搜索算法

2.1 Logistic混沌映射

針對麻雀種群在后期迭代過程中存在種群多樣性較差等問題,本研究采用Logistic混沌映射生成初始麻雀種群來豐富其多樣性,提高算法初始解的質量。

混沌現象是一種可自主產生的特定非線性現象,具有確定規律的隨機性和周期性等特點,可以不重復地搜索其整個工作空間范圍。而Logistic混沌映射作為一種典型的混沌映射模型,與Tent混沌映射和Sine混沌映射等相比,具有更均勻的分布特征和可控的隨機性。因此,本研究采用Logistic混沌映射初始化麻雀種群來豐富其多樣性,從而提高算法初始解的質量。Logistic混沌映射的數學表達式[16]如式(6):

Xt+1=μ·Xt·(1-Xt)

(6)

其中,Xt+1為t+1代的麻雀個體,Xt為t代的麻雀個體。μ∈(0,4],且當μ=4時,Logistic混沌映射達到完全映射狀態。經過Logistic混沌映射構建麻雀的初始種群,增加了麻雀初始種群的規模和多樣性。相較于由隨機策略產生的麻雀初始種群,使用Logistic混沌映射形成的麻雀種群的分布更加均勻,種群多樣性更高。Logistic混沌映射方法不僅改善了麻雀種群的邊緣聚集情況,而且使得麻雀種群在非邊緣地區的分布更加均勻,擴大了算法的搜索范圍,提高了算法的搜索效率。

2.2 自適應慣性因子

傳統的麻雀搜索算法由于在算法迭代初期就開始逼近全局最優解,可能導致其在后期迭代過程中全局空間的搜索能力下降、探索范圍變窄、容易落入局部最優值。針對這一問題,本研究采用了自適應慣性因子法更新麻雀種群的發現者的位置。通過引入自適應慣性因子,在算法迭代初期增大自適應慣性因子,集中探索全局空間區域;在算法迭代后期減小自適應慣性因子,專注于發現者的最佳位置的挖掘,使得算法能在全局搜索能力和局部勘探能力之間得到均衡,降低了算法陷入局部最優的風險。

利用自適應慣性因子改進發現者的位置更新方式如式(7):

(7)

其中,自適應慣性因子λ可表示如式(8):

(8)

式中相關變量已在公式(3)中闡明,不再贅述。

2.3 柯西變異算法

針對傳統的麻雀搜索算法在面對復雜的工程優化問題時易陷入局部最優解等缺點,本研究采用柯西變異算法進一步增強最差麻雀個體與最優麻雀個體的交流反饋,提高了算法的收斂效率和躍出局部最優解的能力。

傳統的算法在更新跟隨者的位置后,適應度值最差的麻雀個體一般很難定位到獵物的位置。若在實際的捕食過程中有目的地增強最差個體與最優個體的交流反饋,既能進一步降低最差麻雀個體的適應度值,又能對最優麻雀個體的位置起擾動作用,有助于算法躍出局部最優解。因此,在傳統算法的基礎上,通過融合柯西變異算法的交流反饋階段可以提高算法的尋優精度以及收斂速度,用公式表達[17]如式(9):

(9)

通過融合柯西變異算法增強了麻雀種群中最差麻雀個體與最優麻雀個體的交流反饋,使得最差麻雀個體能快速飛往獵物的位置,進一步降低了最差麻雀個體的適應度值,提高了算法的收斂效率。

此外,通過柯西變異算法的隨機小步長對當前的局部最優麻雀個體的位置進行擾動,實現全局最優解附近的不斷搜索,持續更新當前最優麻雀個體的位置和適應度值,擴大了算法的搜索區域,增強了算法的全局搜索能力和規避局部最優的能力。

3 基于LAFSSA的全局最優路徑規劃

3.1 LAFSSA流程

將基于多策略改進的麻雀搜索算法(LAFSSA)應用于移動機器人的全局路徑規劃,基本流程如圖 1所示。

圖1 LAFSSA路徑規劃流程圖Fig.1 Flow chart of LAFSSA for path planning

3.2 LAFSSA的適應度函數

對于移動機器人的全局路徑規劃尋優問題,適應度函數的構造通常需要考慮路徑規劃的兩個特性:一是移動機器人不能與障礙物發生碰撞;二是移動機器人在當前環境模型中規劃的全局路徑是最短的。因此,本研究從路徑長度和避障函數兩個方面構造LAFSSA的適應度函數。

假設Pi(xi,yi)和Pi+1(xi+1,yi+1)分別是算法規劃的路徑點序列P′={P0,P1,…,Pi,Pi+1,…,Pm-1}中相鄰的兩個路徑點,則算法規劃的全局最短路徑可由路徑點序列P′中相鄰的路徑點的歐式距離求得,表示如式(10):

(10)

式中,(xi,yi)和(xi+1,yi+1)分別為路徑點Pi和Pi+1對應環境模型中的橫坐標和縱坐標。m代表路徑點序列P′對應環境模型中的路徑點個數。

除了需要考慮移動機器人的全局最優路徑長度最短,還需要避免移動機器人的路徑穿過障礙物。因此,本研究提出一個懲罰函數F2,當移動機器人的路徑將與障礙物發生碰撞時,對其進行懲罰,從而避免了移動機器人的路徑穿過障礙物,與障礙物保持一定的距離,用公式(11)表示:

F2=φ·Q

(11)

式中,φ為懲罰因子,Q為障礙物在環境模型中的位置。

綜上可知,LAFSSA的移動機器人全局路徑規劃的總的適應度函數公式為:

(12)

4 仿真實驗與分析比較

4.1 實驗環境

為方便模擬出移動機器人周圍的真實環境,構建了兩個地圖環境模型如圖2所示。其中,x,y分別表示地圖環境模型的長和寬。環境模型1的地圖大小為20×20,上三角形表示移動機器人的起點位置,其坐標為(1,1);五角星表示移動機器人的終點位置,其坐標為(20,20)。環境模型2的地圖大小為40×40,上三角形表示移動機器人的起點位置,其坐標為(1,1);五角星表示移動機器人的終點位置,其坐標為(40,40)。通過比較可知,圖 2(b)的環境模型比圖 2(a)的更加復雜,這對移動機器人的路徑規劃將是一個挑戰。

圖2 地圖環境模型Fig.2 Environmental model mapping

實驗的仿真環境為處理器Intel(R) Core(TM) i7-5500 @ 2.40 GHz、內存8 GB和裝有MATLAB R2017b軟件的Windows7 64位系統的筆記本電腦。

4.2 實驗結果

為驗證所提的LAFSSA的有效性,分別使用蟻群優化算法(ACO)、鯨魚優化算法(WOA)、麻雀搜索算法(SSA)和所提的改進麻雀搜索算法(LAFSSA)在環境模型1、2中進行移動機器人的全局路徑規劃。仿真實驗中,ACO、WOA和SSA的種群規模設置為50,最大迭代次數設置為200。

對于環境模型1,使用ACO、WOA、SSA和LAFSSA規劃出移動機器人的全局路徑如圖3所示。

圖3 4種算法在環境模型1中的規劃路徑Fig.3 Path planned by four algorithms in environmental model 1

由圖3可知,在環境模型1中,算法規劃的路徑長度從短到長依次為:LAFSSA、ACO、WOA、SSA。算法規劃的路徑轉向次數從少到多依次為:LAFSSA、SSA、WOA、ACO。因此,綜合考慮路徑長度和路徑轉折次數作為算法的衡量標準時,所提的LAFSSA均是最優的。

從圖4可以更加直觀地看到ACO、WOA、SSA和LAFSSA在環境模型1中移動機器人全局路徑的尋優效果表現。算法的收斂精度從高到低依次為LAFSSA、ACO、WOA和SSA。算法的收斂速度從快到慢依次為LAFSSA、SSA、ACO和WOA。因此,綜合考慮算法的收斂精度和收斂速度,LAFSSA在環境模型1中的路徑尋優效果比ACO、WOA和SSA等算法更好。

圖4 4種算法在環境模型1中的收斂曲線圖Fig.4 Convergence curve of four algorithms in environmental model 1

為進一步驗證LAFSSA的可靠性,使用ACO、WOA、SSA和LAFSSA等算法在環境模型2中規劃出移動機器人的全局路徑,如圖 5所示。

由圖5可知,在環境模型2中,算法規劃的路徑長度從短到長依次為:LAFSSA、WOA、SSA、ACO。算法規劃的路徑轉向次數從少到多依次為:LAFSSA、WOA、SSA、ACO。因此,對于更加復雜的環境模型2,LAFSSA在路徑長度和路徑轉折次數等方面的性能均優于ACO、WOA和SSA等算法。

圖5 4種算法在環境模型2中的規劃路徑Fig.5 Path planned by four algorithms in environmental model 2

ACO、WOA、SSA和LAFSSA等4種算法在環境模型2中的收斂曲線如圖6所示。

圖6 4種算法在環境模型2中的收斂曲線圖Fig.6 Convergence curve of four algorithms in environmental model 2

由圖6可得知,所提4種算法的收斂精度從高到低依次為LAFSSA、WOA、SSA和ACO,收斂速度從快到慢依次為LAFSSA、ACO、SSA和WOA。因此,從算法的收斂精度和收斂速度等方面綜合考慮,與ACO、WOA和SSA等算法相比,LAFSSA在環境模型2中的全局路徑規劃效果更好。此外,地圖環境越復雜,LAFSSA的競爭力越顯著。

綜上,與ACO、WOA和SSA等算法相比,LAFSSA在路徑長度和路徑轉折次數等方面均表現出較好的性能。為更突出LAFSSA的優越性,綜合考慮路徑長度、路徑轉折次數和算法耗時等3個指標,總結了ACO、SSA、WOA和LAFSSA等算法的性能如表1所示。

由表1的結果可知,在環境模型1和環境模型2中,與ACO、WOA和SSA等算法相比,本研究所提LAFSSA規劃的移動機器人的路徑長度更短,路徑轉折次數更少,算法耗時更低,移動機器人的路徑尋優時間更少,規劃路徑的平滑性也被有效提升。

5 結論

針對傳統的SSA在求解移動機器人的路徑規劃問題時存在路徑長度長、路徑轉折次數多和路徑搜索耗時等問題,本研究提出了一種基于多種先進策略改進的SSA,稱為LAFSSA。該算法引入Logistic混沌映射策略生成麻雀初始種群,增加麻雀種群的多樣性,提高算法初始解的質量。此外,本研究提出一種自適應慣性因子法用于改進SSA中發現者的位置更新策略,進一步平衡算法的全局搜索能力和局部勘探能力。為防止陷入局部最優,該算法融合柯西變異算法增強最差麻雀個體與最優麻雀個體的交流反饋。在環境模型1和環境模型2中進行的移動機器人的路徑規劃仿真實驗,驗證了所提LAFSSA的有效性。與SSA相比,LAFSSA規劃的路徑長度平均縮短了45.49%,路徑轉折次數平均減少了36.11%,算法耗時平均減少了29.04%,具有較高的尋優精度和較好的路徑平滑效果,在解決移動機器人的路徑規劃問題時具有更加顯著的優勢。