改進人工大猩猩優化算法的機器人路徑規劃

賈鶴鳴，游進華，李永超，李政邦

（1.三明學院信息工程學院，福建 三明 365004；2.福建理工大學計算機科學與數學學院，福建 福州 350118）

移動機器人是具有環境感知能力、 自主規劃能力與自動執行任務能力的智能設備，其應用覆蓋了農業、醫療和快遞等行業及家庭等場合［1］。 制定路徑規劃就是根據機器人獲取的環境信息以及路徑長度、 搜索時間、平滑度和避障能力等性能指標，尋找一條從起點到終點的最近路徑。

近年來，國內外學者提出了多種路徑規劃算法，這些算法包括人工勢場法［2］、A*算法［3］和跳點搜索算法［4］等。人工勢場法的缺點是路徑規劃收斂過早，影響全局搜索，求出的解容易陷入局部最優而無法達到目標點；A* 算法的缺點是路徑規劃存在搜索效率低下和節點冗余等問題，機器人轉彎容易靠近障礙物；跳點搜索算法的缺點是識別關鍵跳點時要進行大量的迭代計算，搜索效率不高。傳統算法存在一定的局限性，不能很好地適應環境的變化，而粒子群算法［5］、遺傳算法［6］或模擬退火算法［7］等群智能優化算法就能克服這些缺點，但未經改進的智能算法存在早熟、 搜索時間較長和解為次優等問題。 因此，對原始算法進行改進，使之收斂速度更快、收斂精度更高是當前的研究熱點。

2021 年，B. Abdollahzadeh 等［8］提出一種新的啟發式智能優化算法，即人工大猩猩優化算法。在解決機器人路徑規劃問題時， 原始的人工大猩猩優化算法存在易陷入局部最優、 收斂精度不高、 收斂速度較慢等缺點。為了克服這些缺點，我們將人工大猩猩算法和三次樣條插值方法［9］結合起來來求解移動機器人路徑規劃問題，并完成了以下工作：在算法的全局搜索階段，引入自適應率較高的權重來擴大全局搜索范圍； 在算法的局部開發階段，引入自適應率較低的權重［10］和互利共生策略［11］來提高算法的收斂精度，并通過黃金正弦策略［12］進一步平衡算法的全局搜索和局部開發的能力。 將改進的人工大猩猩優化算法與三次樣條插值方法結合， 通過構造以最短路徑和避障為目標的適應度函數，實現了機器人路徑規劃問題的求解。通過簡單環境和復雜環境下的實驗測試證明了改進算法的有效性和實用性。

1 人工大猩猩優化算法

人工大猩猩優化算法是人們受大猩猩的群體社交生活行為啟發而提出的一種元啟發式算法， 其原理是通過銀背大猩猩位置的更新來改變其他大猩猩的位置，這一過程包括探索階段和開發階段。

1.1 探索階段

在探索階段，主要是對空間進行全局探索。 假設大猩猩個體位置為X(t)(t為當前迭代次數），GX(t+1)是下次迭代時的大猩猩個體位置。 通過計算個體的適應度值，并對所有個體的適應度值進行比較，選取最優個體進行位置更新。 對應的更新模型為如下形式：

其中：p(p∈(0,1))是給定的參數， 用來模擬銀背大猩猩個體對未知位置的探索的影響因素；UB和LB分別是變量的上界和下界；r1、r2、r3、r4和rand是（0,1）之間的隨機數，Xr和GXr分別是從整個種群中隨機選擇的大猩猩位置；MaxIt表示最大迭代次數；在初始階段，C的變化會較大， 在后期變化值的變化會逐漸減少；l是0 到1 之間的隨機數；Z是區間內的隨機數。

1.2 開發階段

在開發階段，存在兩個機制，一是跟隨銀背大猩猩機制，另一種是大猩猩競爭成年雌性機制。

當C≥W時，選擇跟隨銀背大猩猩機制，位置更新公式為

當C

在以上式子中，Xsilverback為銀背大猩猩的位置，N1表示正態分布和問題維度中的隨機數，N2表示正態分布中的隨機數，β和W是給定參數，r5是（0,1）之間的隨機數。

2 改進的人工大猩猩優化算法

與其他群智能算法一樣，在算法優化過程中，人工大猩猩優化算法的全局探索和局部開發間始終存在矛盾。為了防止算法在快速收斂中出現早熟，我們通過增加自適應權重來擴大全局搜索范圍和提高局部開發能力， 并通過互利共生策略和黃金正弦算法來提高種群多樣性和收斂速度。

2.1 自適應權重

在本文中， 我們引入兩個不同的慣性加權因子分別進行全局探索和局部開發， 對個體位置的鄰域進行更新。當慣性加權因子較大時進行全局搜索，當慣性加權因子較小時進行局部開發， 這樣可以精準找出最佳解決方案。自適應權重和位置更新公式如下：進行全局探索時，將自適應權重和位置更新公式分別確定為

進行局部開發時， 將自適應權重和位置更新公式分別確定為

在以上式子中，Xi為當前第i 個大猩猩個體位置，表示更新后第i 個大猩猩個體位置。

2.2 互利共生策略

在局部開發階段， 人工大猩猩優化算法的隨機性較強，易陷入局部最優，因此我們借助互利共生策略來增強個體與最優個體間的聯系， 降低局部最優解的影響。 經過改進，可得位置更新公式

其中：Xbest表示當前個體的歷史最優位置；Xrand表示隨機個體位置；表示更新后的個體位置；bf是利益因子，隨機選擇1 或2，分別表示部分收益或全部收益；RMV表示隨機個體和最優個體的交互作用。

2.3 黃金正弦策略

在進行局部開發過程中， 傳統的人工大猩猩優化算法的隨機性較大，開發得不夠嚴密，這將導致部分較優解遺漏，進而導致算法的收斂精度降低。為了解決這個問題，我們加入了黃金正弦策略，利用該策略可構造正弦函數模型，以遍歷單位圓上正弦函數的所有點，這樣才能保證局部開發區域的完整性， 并能充分開發優質解的區域，以提高算法的收斂速度。加入黃金正弦策略的位置更新公式為

在以上式子中：R1是[0,2]內的隨機數；R2是[0,]內的隨機數；τ是黃金分割數，且；Xbest表示當前個體的歷史最優位置；表示更新后的個體位置。

3 基于三次樣條插值的機器人路徑規劃

三次樣條插值方法是一種常用的分段式插值方法， 其特點就是利用一系列三次多項式的插值點區間形成一條光滑的曲線。 三次樣條插值擬合出的機器人移動路徑具有更好的動力學特性，因此，我們通過三次樣條插值方法和改進人工大猩猩算法（MGTO）的結合來求解機器人路徑規劃問題。

3.1 三次樣條插值方法

在[a,b]內插入n?1個樣本點xi(i=1,2,…,n?1),把區間[a,b]分成n個小區間[x0,x1],[x1,x2], …,[x n?1,xn]，區間[a,b]上就有了n+1個節點，且有x0=a,xn=b。 給定這些節點的函數值f(xi)=f i(i=0,1,2,…,n),則每個小區間上的曲線是一個三次函數S i(x)(i=0,1,2, …,n?1)。

三次樣條函數滿足以下條件：

（1）滿足插值條件，即S(xi)=y i(i=0,1, …,n)。

（2）曲線要光滑，這就要求一階導數、二階導數均連續，即S(x)∈C2[a,b]。

由條件（3）中4 個條件可以得到4n個方程，組成方程組后就可以求解了。

3.2 編碼

每個方程的區間交接處稱為路徑節點。 在所有的樣本點處是一階連續的和二階連續的， 故分段樣條之間的方向可能是不同的， 即每個三次方程可能是不同的，而路徑的節點就代表了整個路徑的最大轉向次數。一般來說，不論是簡單環境還是復雜環境，經過3~5 次轉向就能夠避開所有的障礙物。因此，我們將大猩猩個體的位置作為節點的編碼， 即大猩猩個體位置擁有的維數代表節點的個數， 大猩猩個體的橫坐標代表節點的橫坐標集合，縱坐標代表著節點的縱坐標集合。

設定起點坐標(xs,ys)和終點坐標(xt,yt)以后，先依據大猩猩的個體位置確定路徑節點的坐標(xm1,ym1),(xm2,ym2),… ,(xmm,ymm)，再利用三次樣條插值法插入n個點，由這些點擬合的連線L就是移動路徑。

3.3 適應度函數的構建

為使路徑長度盡可能短， 我們采取歐式距離計算路徑長度，計算公式為

假設適應度函數為

其中：L是路徑長度；beta是一個較大的數，在本文中取beta=100；Violation是一個標志變量，其初始值為0。 為了符合實際場景，我們將障礙物設置為正十二邊形，求Violation值的程序表示如下：

在以上式子中，nobs 表示障礙物個數，（xobs,yobs）表示障礙物的中心點位置，xx 和yy 分別表示插值點橫坐標集合和縱坐標集合。

先利用式（20） 計算插值點到障礙物中心點的距離，再利用式（21）判斷是否經過障礙物，若其中有數值大于0，則表示經過障礙物，相應的Violation是一個大于0 的數，反之，有Violation =0。

3.4 算法步驟

步驟1：根據具體障礙環境選擇路徑的節點數m、插值點數n、 起點坐標(xs,ys)和終點坐標(xt,yt)、種群個數nPop、最大迭代次數MaxIt。

步驟2：先初始化種群位置，再利用三次樣條插值方法計算插值點的坐標。

步驟3：利用式（18）計算n個插值點之間的距離，即路徑長度。

步驟4：利用式（20）、式（21）和式（22）計算標志變量Violation，再利用式（19）計算適應度值z。

步驟5：用式（1）~式（6）進行全局搜索的位置更新，并用式（9）~式（10）進行進一步的更新，比較兩者的適應度值，選取適應度值小的位置替代原來的位置。

步驟6：用式（7）~式（8）進行局部開發的位置更新，并分別用式（11）~式（12），式（13）~式（14）和式（15）~式（17）進行位置更新，比較更新后的適應度值與更新前的適應度值，選取適應度值小的位置替換最優位置。

步驟7：重復步驟4~步驟6，直到達到最大迭代次數。

步驟8：得到并輸出最優路線值。

4 仿真實驗及其分析

為驗證本算法在求解機器人路徑規劃問題上的有效性和實用性，在保證客觀、公正的前提下，利用改進的人工大猩猩算法（MGTO）與標準的人工大猩猩算法（GTO）、教與學優化算法（TLBO）［13］、多元宇宙優化算法（MVO）［14］、龍格-庫塔優化算法（RUN）［15］、算數優化算法（AOA）［16］做仿真實驗，以檢驗MGTO 算法的尋優性能。

4.1 實驗參數的設定

為了確保算法結果的公正和客觀， 我們將MGTO算法、GTO 算法、TLBO 算法、MVO 算法、RUN 算法、AOA 算法都置于相同的軟硬環境下。 運行環境是windows11，編程環境為MATLABR2019a。 在仿真實驗中，6 種算法的種群規模為20、最大迭代次數為500，其他參數的設定如下： 在MVO 算法中， 取WEP=0.5；在RUN 算法中， 取w=1，wdamp=0.98，a=1，alpha=0.1；在AOA 算法中， 取C1=2，C2=6，C3=2，C4=0.5，u=0.1，l=0.1；在GTO 和MGTO 算法中，取P=0.03，w=0.8，β=3。

4.2 簡單障礙環境下的路徑規劃

在簡單的障礙環境中， 設置9 個障礙物，6 個路徑節點，將起點的坐標定為（-25, 28），終點為（30, -30），將各算法的實驗次數定為30，可得如圖1、圖2 和表1所示的實驗結果。

表1 簡單環境下用6 種算法求得的路徑長度

表3 復雜環境下由6 種算法求得的路徑長度

圖1 簡單環境下6 種算法的路徑規劃

圖2 簡單環境下6 種算法的迭代曲線

從圖1 和圖2 可以看出，在簡單環境中，GTO 算法與AOA 算法的結果幾乎一致，而MGTO 算法的尋優性能明顯好于其他算法。 從表1 可看出，不論是最差解、最優解還是平均解，MGTO 算法都是最優的。 這說明三種策略的加入能有效提高算法的收斂速度和尋優能力。

4.3 復雜障礙環境下的路徑規劃

在復雜的障礙環境下，設置12 個障礙物，將起始點的坐標定為（-30, -30），終點為（30, 30），將各算法的實驗次數定為30，可得如圖3、圖4 和表2 所示的實驗結果。

圖3 復雜環境下6 種算法的路徑規劃

圖4 復雜環境下6 種算法的迭代曲線

從圖3 和圖4 可以看出，在復雜的避障環境中，原GTO 算法與RUN 算法相比， 沒有太多的優越性，但MGTO 算法的尋優性能遠超GTO 算法和其他算法。

從仿真結果可以看出，在兩種實驗環境中，無論是最差解、最優解，還是平均解，MGTO 算法都優于其他算法。因此，MGTO 算法在解決機器人路徑規劃問題上具有良好的工程適用性。

5 結束語

本文將人工大猩猩算法與三次樣條插值法結合，用于求解機器人路徑規劃問題。首先，改進了人工大猩猩優化算法， 在全局探索和局部開發階段分別引入不同非線性慣性因子， 同時在局部開發階段融入互利共生和黃金正弦策略。 通過仿真實驗證明了MGTO 算法的求解性能優于其他對比算法， 驗證了該算法在路徑規劃問題方面的優越性和有效性。