改進海洋捕食者算法的機器人路徑規劃研究

黃訓愛,楊光永,樊康生,徐天奇

(1.云南民族大學 電氣信息工程學院, 昆明 650500;2.云南省無人自主系統重點實驗室, 昆明 650500)

0 引言

海洋捕食者算法(marine predators algorithm,MPA)是Faramarzi等于2020年提出的一種新型元啟發式智能算法[1]。受到海洋中捕食者獲得獵物方式的啟發,通過對捕食者覓食行為的簡化和模擬,在反演過程中結合Lévy飛行和布朗運動選擇最佳覓食策略,具有尋優能力強、參數少、易于實現、計算精確等優點。被廣泛應用于特征選擇[2]、參數優化[3]、車間調度[4]、故障診斷[5]等領域。

王逸文等[6]提出了一種基于反向差分變異的種群變異機制和最優個體自適應擾動策略的改進海洋捕食者算法并將其應用于壓力容器設計問題;Guo等[7]提出了一種改進海洋捕食者算法的原位標定方法,取得良好標定效果;于涵等[8]提出了一種改進混沌初始化,引入自適應步長和精英競賽機制的改進海洋捕食者算法;周放歌等[9]采用改進二進制海洋捕食者算法搜索故障饋線,通過分組學習策略以及自適應t分布提高算法搜索能力;Durmus等[10]利用海洋捕食者算法對CEAA單元的電流幅值和角位置值進行優化,得到最優輻射方向圖,并與其他元啟發優化算法比較,取得良好效果;馬馳等[11]將混沌映射與對立學習相結合,進一步提高種群質量和搜索精度,并將改進算法應用于無線傳感器網絡覆蓋優化;李代華等[12]提出一種將海洋捕食者算法與自適應神經模糊推理系統相結合的徑流預測方法;張貝等[13]提出一種融合趨向全局最優的反向學習策略,更新捕食者位置,采用三階段最優引導最差策略,提高搜索能力,并應用于插值平滑的機器人路徑規劃。

隨著人工智能技術的發展,機器人廣泛應用在倉庫貨物搬運、救援、物流、智慧農業等領域[14]。而路徑規劃是移動機器人研究的重點,其目的是保證機器人不與障礙物碰撞的前提下規劃出一條從起點到目的地的最優路徑[15]。移動機器人路徑規劃方法可以分為傳統路徑規劃算法和智能路徑規劃算法。傳統路徑規劃方法有人工勢場法[16]、模擬退火算法[17]、禁忌搜索算法等。此類方法存在搜索效率不高、路徑冗余等問題。常用的智能路徑規劃方法有A*算法[18]、粒子群算法[19]、蟻群算法[20]、遺傳算法[21]、灰狼優化算法[22]等,其搜索能力強,但極易陷入局部最優,計算比較復雜。

針對上述問題,本文提出一種多策略改進海洋捕食者算法(IMPA),引入Logistic混沌映射初始化種群,增加捕食者種群多樣性;基于當前迭代次數t的自適應移動步長動態調整策略,增強算法逃離局部最優能力;在IMPA迭代后期,加入中垂線算法(MA),基于中垂線策略的游離粒子位置更新方法,能夠加快捕食者的位置更新,增強算法的尋優速度和尋優精度,避免算法陷入局部最優。最后通過改變IMPA階段轉換尋優過程,進一步平衡搜索過程,加強全局與局部適應性。最后選用基準測試函數對改進算法性能進行測試,并應用于機器人路徑規劃,證明本文改進算法的有效性。

1 海洋捕食者算法

海洋捕食者算法(MPA)是一種新型元啟發式優化算法,該算法主要靈感來自于海洋捕食者覓食策略,即海洋捕食者的萊維(Lévy )和布朗(Brownian)運動,以及捕食者和獵物之間的最佳相遇率策略,模擬了海洋中適者生存理論。

MPA優化過程主要分為3個階段,考慮不同的速度比,同時模仿捕食者的整個生命過程:

1) 高速比階段(t≤tmax/3),即獵物移動速度快于捕食者時;

2) 等速比階段(tmax/3

3) 低速比階段(t≥2tmax/3),即捕食者速度快于獵物時。

1.1 MPA初始化精英矩陣和獵物矩陣

隨機在搜索空間范圍內初始化獵物位置來啟動優化過程。數學描述如下:

獵物矩陣(Prey)每一個元素Xij的初始化方法:

Xi, j=xmin+rand(Xmax-Xmin)

(1)

最終得到Prey矩陣如式(2)所示:

(2)

式中:n為種群規模;d為每個維度的位置。

對每一個Prey個體Xi=[Xi,1,Xi,2,…,Xi,d],計算其適應度,然后使用適應度最優個體XI,復制n份構成精英矩陣(Elite):

(3)

1.2 探索階段

高速比階段,當捕食者速度遠小于獵物速度時,(t≤tmax/3),算法處于探索階段,基于勘探策略的MPA優化過程數學描述如下:

i=1,2,…,n

(4)

式中:t為迭代次數;tmax為最大迭代次數;Elitei為由頂級捕食者構造的精英矩陣;Preyi為與精英矩陣具有相同維數的獵物矩陣;RB為呈正態分布的布朗游走隨機向量,stepsizei為移動步長;?為逐項乘法運算符;P等于0.5;R為[0 1]內均勻隨機向量;n為種群規模。

1.3 探索與開發之間的轉換

等速比階段,捕食者速度與獵物速度相同;(tmax/3

i=1,2,…,n/2

(5)

i=n/2,…,n

(6)

式中:RL為呈Lévy分布的隨機向量;η=(1-t/tmax)(2t/tmax)為控制捕食者移動步長的自適應參數,其他參數意義同上。

1.4 開發階段

低速比階段,捕食者速度快于獵物速度時,(t≥2tmax/3),捕食者基于Lévy游走采用開發策略,其數學描述如下:

i=1,2,…,n

(7)

式中其他參數意義同上。

1.5 魚類聚集裝置或渦流效應作用

魚類聚集裝置(SFAD)等環境問題會對海洋捕食者造成影響,可看作局部最優,采用式(8)消除影響:

(8)

式中:SFAD表示海洋捕食者減小局部極值影響的概率,取值為0.2;U為二進制向量;r為[0 1]內隨機數;Preyr1,Preyr2分別為從獵物矩陣中隨機選取的2個獵物。

2 改進海洋捕食者算法

2.1 Logistic混沌映射初始化種群

傳統的隨機數生成器初始化MPA時存在遍歷性不足,會影響后續搜索;而均勻分布的種群可以適度擴大算法的搜索范圍,從而提高收斂速度和求解精度,Logistic混沌映射是混沌映射中的典型代表,可以用于增加種群多樣性,比使用隨機數生成器初始種群方式更加可靠、優越。本文將Logistic混沌映射應用于海洋捕食者算法的種群初始化階段,其數學表達式如式(9)所示:

Xn+1=μXn(1-Xn)

(9)

式中:Xn為第n代混沌序列產生的值,Xn∈[0,1],參數μ一般取值是1≤μ≤4,當參數μ增大時,映射序列的取值范圍也增大,映射分布變得更加均勻,當μ=4時,系統處于完全混沌狀態下,此時映射分布均勻性達到巔峰,所以本文μ取值為4。

2.2 自適應移動步長動態調整策略

MPA的種群位置更新階段中,獵物位置的變化決定算法能否快速收斂到更好的位置。本文通過動態調整移動步長,進一步控制算法的勘探與開發能力,促進局部快速收斂,從而提高算法收斂精度。傳統MPA的移動步長主要是通過自適應參數η=(1-t/tmax)2t/tmax控制,算法前期更注重勘探,開發能力較弱,導致算法收斂速度較慢;因此,本文通過構造基于指數函數的自適應移動步長控制參數實現對移動步長的動態調整,如式(10)、式(11)所示:

τ=(1-(tmax+t)/(tmax-t))β

(10)

η1=eτ+c1

(11)

式中:c1取常數,為0.05;β=3。在算法迭代初期,η1數值較大且變化速率較快,能夠增強其開發能力,加快算法收斂;在算法迭代中后期,η1平緩減小逐漸趨于穩定,算法能夠進行局部精細搜索找尋到更優質潛藏獵物,提高算法的收斂精度。自適應移動步長控制參數變化曲線如圖1所示。

圖1 自適應移動步長控制參數收斂曲線

2.3 融合中垂線算法的捕食者位置更新策略

2.3.1 中垂線策略原理

為提高算法收斂速度,本文結合中垂線原理[23],提出中垂線算法(MA)收斂策略,一條線段的中垂線上任一點到這條線段兩端的距離相等,粒子根據這一幾何性質,不斷縮小最優解的搜索范圍,從而找到最優解。如圖2(a)所示,假設在一個二維空間內,在矩形圍成的范圍內(如圖中陰影區域所示)僅存在一個最優點P,存在隨機的2個點A和B,將兩點連接起來形成一條線段AB,作線段L為AB的中垂線,定義|PA|<|PB|,則P點必存在于線段L靠A側區域。中垂線算法把最優點到P點的距離用其適應度值來代替,因AP的距離小于BP的距離,即A點適應度比B點更優。P點具有最佳適應度,如圖2(a)所示,中垂線算法收斂過程如下:

圖2 中垂線算法原理圖

1) 判定|PA|是否小于|PB|,若是,則判定最優值位于中垂線靠A側區域內(圖1網格區域);

2) 丟棄B點,在中垂線L靠A側區域重新隨機生成一點B′;

3)A點和B′點構成線段AB′,作其中垂線L′,此時B′點離P點更近,即B′點適應度更好,則MA判定最優值位于L′靠近B′點區域內(左圖陰影區域);

4) 重復上述步驟不斷生成新的A點,通過MA方法即可不段縮小最優點所處空間。

2.3.2 融合中垂線算法的捕食者位置更新策略

在圖2(a)中加入一個隨機粒子C(圖中粒子即代表捕食者),并且C位于L靠A側區域,如圖2(b)所示,若采用傳統的粒子位置更新策略更新B點和C點位置,要經過多次迭代才能到達中垂線靠A側區域。

如圖2(b)所示,將粒子B和C移動到B′點和C′點上,再采用MPA的位置更新策略,可以加快MPA的位置更新。上述策略實現方式為:首先判斷粒子是否位于中垂線靠B側區域,設

(12)

若粒子x在線段L靠B側區域,則x的第j維變量滿足式(13)、式(14):

(13)

其中

(14)

為了減小算法的時間復雜度和全局尋優能力,判定x僅需有兩維變量不符合上述策略,則粒子位于A側區域,粒子位置更新不采用上述策略。

若MA判定,若粒子位于中垂線靠B側區域,則B點更新公式為:

(16)

2.4 改進MPA階段轉換尋優過程

傳統MPA算法采用均分3階段的尋優策略,優化過程中,三階段分別占據總迭代次數的1/3,沒有考慮階段尋優速度的影響。隨著總迭代次數的改變,每一階段迭代次數也會改變。本文采用李帝銓等[24]提出的一種階段差異劃分的尋優方式,差異劃分每一階段的尋優方式,增強算法的尋優精度和迭代速度,數學式如下:

階段1:迭代初期

i=1,2,…,n

(17)

式中:λ1為常數,取值為3.2;RB_max為RB向量元素的最大值,其他元素含義同上。

階段2:迭代中期

i=1,2,…,n/2

(18)

i=n/2,…,n

(19)

式中:λ2、c1、c2均為常數,λ1取值為3.2,c1取值為0.9,c2取值為0.4。

階段3:迭代后期

i=1,2,…n

(20)

2.5 IMPA算法流程

依據2.1～2.4節的描述,改進海洋捕食者算法流程如下:

步驟1初始化最大迭代次數T、種群規模n,當前迭代次數t;局部極小值概率SFAD,精英矩陣(Elite)、獵物矩陣(Prey);

步驟2計算適應度,記錄捕食者最優位置;

步驟3第1階段更新;

步驟4第2階段更新;

步驟5第3階段更新;

步驟6中垂線算法的游離粒子位置更新方法更新捕食者位置;

步驟7解決渦流形成和SFAD效應;

步驟8更新適應度值和捕食者最優位置;

步驟9判斷算法結束條件,如果t

3 IMPA性能驗證

3.1 測試函數設定

為驗證改進算法收斂精度、收斂速度和穩定性等性能,采用6個常見基準函數進行仿真對比實驗,基準測試函數表達式見表1,其中F1—F3為單峰測試函數,有一個最優解用于驗證算法收斂速度;F4—F6為多峰測試函數,具有多個局部最優解,用于驗證算法收斂精度和全局搜索能力。選用海洋捕食者算法(MPA)、粒子群算法(PSO)、灰狼優化算法(GWO)、麻雀優化算法(SSA)與本文的改進海洋捕食者算法(IMPA)進行對比實驗,實驗平臺為:Matlab2019b(Intel(R)Core(TM)i5-8250UCPU@1.60 GHz)。

表1 基準測試函數表達式

3.1.1 改進算法參數選擇對IMPA性能的影響

在2.4節采用自適應移動步長動態調整策略通過動態地調整移動步長進一步來控制算法的勘探與開發,促進局部快速收斂,從而提高算法收斂精度,其中參數β的取值會直接影響改進算法的性能,為了確定最佳實驗參數,設計一組實驗分別對F1、F3、F4、F5測試函數進行優化。50次實驗結果的均值如表2所示。

表2 不同β的實驗結果

表2中,隨著β值的增大,算法收斂速度變快,跳出局部最優的能力增強,收斂精度有所提高,但隨著β值超過3之后,算法收斂精度隨之下降,實驗結果表明,當參數β的值為3時,算法整體性能最佳。

3.1.2 對比算法參數選擇確定及其影響

各對比算法的參數設置如表3所示,在設置參數時,為保證公平性,各算法的種群規模統一選取為50,其中MPA和IMPA的參數設置上面已進行實驗論證,這里不重復討論。PSO算法的參數為在各種應用中實驗論證出的較佳參數,GWO中的a參數為固定公式計算得出,這里不做討論。SSA算法中的安全閾值參數ST對算法的性能有較大影響,這里通過實驗論證對其討論并找出最佳參數,使算法性能最佳。

表3 各算法參數

表4為SSA算法對4個測試函數F1、F2、F4、F6進行優化時,不同ST值下50次獨立實驗的均值結果。ST的取值范圍在[0.51]之間,當預警值小于安全值時,表示安全,此時發現者搜索空間較大,當預警值大于等于安全值時,表示有了一定數量的捕食者,需要移動到安全區域。ST值的大小直接影響算法搜索空間的大小,進而影響算法收斂精度和收斂速度。從表4可以看出,隨著ST值從0.5逐漸增大的過程中,其均值在逐漸減小,算法收斂精度在逐漸提高,當ST值增大到0.8時,均值最小,之后隨著ST值增大,均值也隨之逐漸增大,收斂精度逐漸下降,實驗結果表明,當ST值為0.8時,算法性能最佳,所以,本文取值為0.8。

表4 不同ST值的實驗結果

3.2 對比實驗結果分析

本文計算的標準差和平均值分別用來評價算法穩定性和收斂精度;因數據矩陣隨機產生,每次獨立試驗結果不一定為最優值,故本文重復試驗50次,取其平均值,規定各測試函數維度為30維,因適應度數量級相差過大,F1—F6 收斂曲線的適應度均為 log10 處理后的結果。

3.3 IMPA收斂精度分析

實驗中測試函數維度為30維,各對比算法的標準差和均值如表5所示。

由表5可知,IMPA除測試函數為F1、F3時,其他測試函數的均值為零,而MPA只有當測試函數為F5時,均值才為0,表明IMPA無論是在處理單極值問題還是處理多極值問題收斂精度均比MPA高。MPA在處理單極值問題時表現良好,在處理多極值問題時,收斂精度明顯不如IMPA。與GWO、PSO和SSA相比較,IMPA均值最小,表明IMPA與其他算法相比收斂精度具有明顯優勢,其他算法無論是在處理單極值問題還是多極值問題上均表現不佳。

上述數據表明:IMPA無論是處理單極值問題還是多極值問題時,表現均為最佳,證明IMPA中,基于Logistic混沌映射增加種群多樣性和基于中垂線算法的游離粒子位置更新方法,能夠顯著提高算法收斂精度。

3.3.1 IMPA穩定性分析

如表5所示,除測試函數為F3外,MPA的標準差均大于IMPA,而IMPA的標準差除F3外全為0,說明無論在處理多極值問題還是處理單極值問題時,MPA穩定性都不如IMPA。與GWO、PSO和SSA相比較,IMPA的標準差均是最小的,表明無論是處理單極值問題還是處理多極值問題,IMPA算法的穩定性均明顯優于其他3種算法。

分析表明,MPA算法在融合了中垂線算法的游離粒子位置更新策略后,能夠更加高效快速地找到優質捕食者,增強算法全局搜索能力;另外,自適應移動步長動態調整策略,通過對移動步長控制參數的動態調整進一步調整移動步長,保證算法前期能夠進行開發,后期進行精細搜索找到優質潛藏獵物,提高算法的收斂精度。

3.3.2 IMPA收斂速度分析

圖3為各對比算法在求解不同基準測試函數時問題解的收斂過程。由圖3可以看出,在6個基準測試函數中,各算法求解基準測試函數適應度值達到最小值時,IMPA所需迭代次數均是5種對比算法中最小的,尤其求解多峰函數時,差距更明顯,證明本文提出的自適應移動步長動態調整策略和MPA階段轉換尋優過程,有效地提高了算法收斂速度,全局尋優能力更強。

圖3 不同算法在各基準測試函數上的收斂曲線

4 IMPA在機器人路徑規劃中的應用

路徑規劃在機器人組成部分中具有重要作用。路徑規劃技術就是在障礙物環境中規劃出一條從起始點到終點的最優或次優路徑,使機器人安全的到達預定地點。目的是使路徑長度最短、路徑拐點最少,要求不能碰到障礙物且與障礙物保持一定的安全距離。目前,海洋捕食者算法在機器人路徑規劃技術中應用較少,本文將IMPA應用于機器人路徑規劃,進一步驗證算法實際應用性能。

4.1 建立機器人路徑規劃數學模型

4.1.1 柵格地圖建模

通常情況下,移動機器人(AGV)的工作環境為二維有限空間,為了便于建模,對柵格地圖作如下假設:

1) AGV運行環境為二維矩形有限空間;

2) 運行過程中,將AGV看做一個質點,行駛速度為v,為了安全,機器人需與障礙物保持一定安全距離。

對二維矩形空間建立笛卡爾直角坐標系,x軸的柵格數為Nx=xmax/v,y軸的柵格數為Ny=ymax/v,每個柵格對應相應的序列號,且序列號與坐標之間關系滿足式(21)、式(22):

xp=[(p-1)modn]+1

(21)

(22)

式中:n為每一行柵格數;p為坐標序列號;mod為求余運算;INT為取整運算。柵格法建立的環境地圖中黑色區域代表障礙物,白色區域代表自由空間,如障礙物形狀為不規則屋,則通過補償方式將其補充填滿障礙物。

4.1.2 適應度函數設計

適應度函數是檢驗IMPA算法優化程度的重要函數。機器人路徑規劃的任務就是在最短時間內找到一條從起始點到終點的最短的、較平滑的路徑。路徑長度越短,到達目的地越快;路徑越平滑,可以避免轉彎降低速度,同時提高安全性。因此,本文綜合考慮路徑長度和光滑程度,設計適應度函數。

設機器人路徑為一條連接起點(x0,y0)和終點(xn,yn)的點序列p=(p1,p2,…pn)={(x0,y0),(x1,y1),…(xn,yn)},由一系列決策目標最優的點組成。其中p1=(x0,y0)表示路徑目標起點,pi=(xi,yi)表示路徑目標節點,pn=(xn,yn)表示表示路徑目標終點。機器人路徑長度計算公式如式(23)所示:

(23)

此外,路徑平滑度也是機器人安全、平穩運行的重要條件。機器人由于運動學和動力學約束,在運動時,拐彎角度不宜過大,假設路徑經過點pi和pi+2確定,兩點之間的點pi+1使3點之間的距離之和越小,相鄰3點形成的角度越大,路徑越平滑,路徑平滑度計算公式,如式(24)所示:

(24)

由于路徑中連續3點連線夾角情況分別為平角、鈍角、直角、銳角,其中,平角代表3點在同一直線上,平滑度最好,鈍角、直角次之,由于動力學和運動學約束,銳角不允許出現。綜合考慮路徑長度、平滑度和障礙物等因素,本文建立機器人適應度函數,如式(25)所示:

f=λ·G0+ηG1

(25)

式中:λ為路徑長度因子;η為路徑平滑度因子,可根據路徑長度和平滑度之間的權重,靈活選擇其大小,本文選擇λ=1,η=1。

4.2 實驗

為驗證本文改進算法(IMPA)在機器人路徑規劃中的性能,選擇灰狼算法(GWO)、粒子群算法(PSO),海洋捕食者算法(MPA)作為對比算法,和本文改進算法(IMPA)在相同的柵格地圖環境中進行路徑規劃對比實驗,設置粒子數量N=50,最大迭代次數T=500,設置GWO參數為:收斂因子a=2-2t/T(t為當前迭代次數);設置PSO參數為:慣性權重因子ω1=0.9,ω2=0.4,學習因子c1=2,c2=2。

分別在20×20柵格地圖和30×30柵格地圖中進行仿真實驗。圖4和圖5為各算法在20×20和30×30柵格地圖環境中的路徑規劃仿真圖,將各算法規劃路徑的性能指標放于表6中作為對比。

表6 各算法規劃路徑性能指標

圖4 20×20柵格地圖路徑規劃仿真圖

圖5 30×30柵格地圖路徑規劃仿真圖

由表6可知,在20×20柵格地圖中,IMPA最優路徑為28.856 9,在4種算法中是最短的,其次是MPA,IMPA路徑長度相較于MPA縮短了9.25%,相較于PSO縮短了16.13%,相較于GWO縮短了11.80%;IMPA的尋路時間同樣是4種算法中最短的,相較于MPA尋路效率提高了7.8%,相較于PSO提高了6.25%,相較于GWO提高了38.91%;同樣地,IMPA的路徑拐點個數是4種算法中最少的,相比其他3種算法具有明顯優勢。在30×30柵格地圖中,IMPA最優路徑為44.44,在4種算法中是最短的,其次是MPA,IMPA路徑長度相較于MPA縮短了15.35%,相較于PSO縮短了26.36%,相較于GWO縮短了36.64%;IMPA的尋路時間略長于MPA和PSO,但相差不大,比GWO縮短了30.22%。從圖4、圖5、表6可以看出,相較于傳統的MPA算法和其他2種對比算法,IMPA規劃的路徑長度更短,拐點更少,尋路時間也具有明顯優勢,取得了良好效果。

驗證改進算法在機器人路徑規劃中的收斂速度,各算法規劃路徑長度與迭代次數對應關系的仿真圖如圖6所示。在20×20柵格地圖中,在4種對比算法中,規劃路徑達到該算法所獲得最優路徑長度時,IMPA所需要迭代次數最少,證明其收斂速度最快,GWO所需迭代次數最多,說明其收斂速度最慢;在30×30柵格地圖中,IMPA規劃路徑達到該算法所獲得最優路徑長度時,IMPA所需要迭代次數略多于PSO,但明顯少于MPA和GWO,其收斂速度同樣優勢明顯,證明本文改進算法在機器人路徑規劃中收斂速度較快。

圖6 各算法路徑規劃仿真圖

5 結束語

針對海洋捕食者算法存在收斂速度慢,收斂精度低,易陷入局部最優的問題,提出一種改進海洋捕食者算法,引入Logistic混沌映射初始化種群,增加捕食者種群多樣性;基于當前迭代次數t的自適應移動步長動態調整策略,增強算法逃離局部最優能力;在IMPA迭代后期,加入中垂線算法(MA),基于中垂線策略的游離粒子位置更新方法,加快捕食者的位置更新,增強算法的尋優速度和尋優精度,避免算法陷入局部最優。最后通過改變IMPA階段轉換尋優過程,進一步平衡搜索過程,加強全局與局部適應性。選用6個基準測試函數對IMPA算法性能進行驗證,改進算法在求解單峰函數和多峰函數時,無論是在收斂速度、收斂精度,還是穩定性方面,均具有明顯優勢。將IMPA應用于移動機器人路徑規劃,分別在20×20和30×30柵格地圖中與其他算法進行對比實驗,實驗結果進一步證明了改進算法的有效性