改進人工大猩猩優(yōu)化算法的機器人路徑規(guī)劃

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

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

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

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

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

1 人工大猩猩優(yōu)化算法

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

1.1 探索階段

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

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

1.2 開發(fā)階段

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

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

當(dāng)C

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

2 改進的人工大猩猩優(yōu)化算法

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

2.1 自適應(yīng)權(quán)重

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

進行局部開發(fā)時， 將自適應(yīng)權(quán)重和位置更新公式分別確定為

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

2.2 互利共生策略

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

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

2.3 黃金正弦策略

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

在以上式子中：R1是[0,2]內(nèi)的隨機數(shù)；R2是[0,]內(nèi)的隨機數(shù)；τ是黃金分割數(shù)，且；Xbest表示當(dāng)前個體的歷史最優(yōu)位置；表示更新后的個體位置。

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

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

3.1 三次樣條插值方法

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

三次樣條函數(shù)滿足以下條件：

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

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

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

3.2 編碼

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

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

3.3 適應(yīng)度函數(shù)的構(gòu)建

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

假設(shè)適應(yīng)度函數(shù)為

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

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

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

3.4 算法步驟

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

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

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

步驟4：利用式（20）、式（21）和式（22）計算標(biāo)志變量Violation，再利用式（19）計算適應(yīng)度值z。

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

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

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

步驟8：得到并輸出最優(yōu)路線值。

4 仿真實驗及其分析

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

4.1 實驗參數(shù)的設(shè)定

為了確保算法結(jié)果的公正和客觀， 我們將MGTO算法、GTO 算法、TLBO 算法、MVO 算法、RUN 算法、AOA 算法都置于相同的軟硬環(huán)境下。 運行環(huán)境是windows11，編程環(huán)境為MATLABR2019a。 在仿真實驗中，6 種算法的種群規(guī)模為20、最大迭代次數(shù)為500，其他參數(shù)的設(shè)定如下： 在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 簡單障礙環(huán)境下的路徑規(guī)劃

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

表1 簡單環(huán)境下用6 種算法求得的路徑長度

表3 復(fù)雜環(huán)境下由6 種算法求得的路徑長度

圖1 簡單環(huán)境下6 種算法的路徑規(guī)劃

圖2 簡單環(huán)境下6 種算法的迭代曲線

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

4.3 復(fù)雜障礙環(huán)境下的路徑規(guī)劃

在復(fù)雜的障礙環(huán)境下，設(shè)置12 個障礙物，將起始點的坐標(biāo)定為（-30, -30），終點為（30, 30），將各算法的實驗次數(shù)定為30，可得如圖3、圖4 和表2 所示的實驗結(jié)果。

圖3 復(fù)雜環(huán)境下6 種算法的路徑規(guī)劃

圖4 復(fù)雜環(huán)境下6 種算法的迭代曲線

從圖3 和圖4 可以看出，在復(fù)雜的避障環(huán)境中，原GTO 算法與RUN 算法相比， 沒有太多的優(yōu)越性，但MGTO 算法的尋優(yōu)性能遠(yuǎn)超GTO 算法和其他算法。

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

5 結(jié)束語

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