董志民，喬 棟，朱守健，趙政宏

（1 山西大同大學(xué)煤炭工程學(xué)院 山西 大同 037009）

（2 山西大同大學(xué)建筑與測(cè)繪工程學(xué)院 山西 大同 037003）

0 引言

自20 世紀(jì)90 年代以來(lái)，我們的國(guó)家一直致力于探索和推廣移動(dòng)機(jī)器人的應(yīng)用和研究，許多科學(xué)院校和企業(yè)也積極投入到這項(xiàng)技術(shù)的研發(fā)中，他們不僅解決了定位、導(dǎo)航、硬件結(jié)構(gòu)的技術(shù)挑戰(zhàn)，而且還為這一領(lǐng)域的進(jìn)步提供了有力的支持。 隨著機(jī)器人領(lǐng)域的發(fā)展，路徑規(guī)劃已經(jīng)成為移動(dòng)機(jī)器人的關(guān)鍵部分［1］，它不僅僅涉及數(shù)學(xué)上的優(yōu)化，而且還涉及實(shí)際應(yīng)用，其復(fù)雜的結(jié)構(gòu)、嚴(yán)格的限制條件以及對(duì)環(huán)境的影響，使得它成為當(dāng)今科學(xué)家們關(guān)注的焦點(diǎn)。

傳統(tǒng)的搜索算法如D*算法［2］、A*算法［3］和Dijkstra算法［4］通過(guò)柵格網(wǎng)絡(luò)地圖可以搜索出一條最優(yōu)路徑，但是算法本身具有效率低、速度慢等特點(diǎn)，隨著問(wèn)題規(guī)模的擴(kuò)大，所花費(fèi)的時(shí)間和消耗的內(nèi)存也會(huì)成比例增加。 為了解決這一問(wèn)題，學(xué)者們結(jié)合已有的方法和各種策略來(lái)解決路徑規(guī)劃問(wèn)題，其中智能優(yōu)化算法在機(jī)器人路徑規(guī)劃中應(yīng)用越來(lái)越廣泛。

近些年來(lái)，隨著人工智能技術(shù)的提高，智能優(yōu)化算法已成為解決路徑規(guī)劃的主要方法，例如蟻群算法、粒子群優(yōu)化算法、遺傳算法，因?yàn)樵擃?lèi)算法在復(fù)雜情況下所消耗的計(jì)算代價(jià)和時(shí)間等都優(yōu)于傳統(tǒng)的路徑規(guī)劃方法［5-6］。

1 移動(dòng)機(jī)器人路徑規(guī)劃

路徑規(guī)劃是移動(dòng)機(jī)器人研究的重要領(lǐng)域，對(duì)機(jī)器人的日常工作和運(yùn)動(dòng)起著不可或缺的作用。 機(jī)器人的路徑規(guī)劃就是將各個(gè)傳感器的信息結(jié)合然后根據(jù)一定的約束條件情況下，從起點(diǎn)到終點(diǎn)規(guī)劃出一條適合機(jī)器人運(yùn)動(dòng)的路徑［7-8］。 例如不能碰撞到障礙物的硬性約束、要求能耗最低、耗時(shí)最短等，進(jìn)而達(dá)到一條最優(yōu)的適合機(jī)器人運(yùn)動(dòng)的軌跡。 為了達(dá)到這一目的，機(jī)器人的路徑規(guī)劃任務(wù)一般分為以下3 個(gè)步驟：①環(huán)境仿真；②通過(guò)算法可以構(gòu)建一條有效的路徑；③通過(guò)路徑平滑技術(shù)來(lái)提升機(jī)器人實(shí)際運(yùn)動(dòng)中的性能。

2 海洋捕食者算法

海洋捕食者算法由Afshin Faramarzi 等在2020 年提出，它基于元啟發(fā)式優(yōu)化算法。 海洋捕食者可以利用Lévy和布朗策略來(lái)規(guī)劃行進(jìn)步長(zhǎng)找到最合適的覓食方式，而這種新的捕食策略在尋優(yōu)能力上有更高的優(yōu)勢(shì)，一個(gè)頂級(jí)捕食者就是一個(gè)問(wèn)題的解，而這些頂級(jí)捕食者們可以構(gòu)成一個(gè)精英矩陣，通過(guò)算法的一系列優(yōu)化操作，最后計(jì)算該矩陣中適應(yīng)度值最小的一組即為最優(yōu)解［9-11］。

2.1 構(gòu)建精英矩陣（Elite）和獵物矩陣（Prey）

獵物矩陣（Prey）每一個(gè)元素Xi，j的初始化方法如式（1）所示：

式（1）中，Xmin和Xmax分別表示種群變量的上下限，rand ∈（1，0） 為服從均勻分布的隨機(jī)向量。

精英捕食者矩陣Elite和獵物矩陣Prey分別如式（2）和式（3）所示：

式（2）、式（3）中，N 是種群的規(guī)模，D 是每個(gè)維度的位置（問(wèn)題的解的維度）。

2.1 海洋捕食者算法優(yōu)化階段

2.1.1 迭代初期

在迭代初期，獵物的速度明顯高于捕食者，它們遵循布朗運(yùn)動(dòng)，捕食者則主要進(jìn)行探索活動(dòng)。 此時(shí)迭代次數(shù)為總迭代次數(shù)的前三分之一，基于海洋捕食者算法優(yōu)化的勘探策略，可以通過(guò)數(shù)學(xué)公式描述來(lái)實(shí)現(xiàn)捕食者的優(yōu)化策略，如式（4）、式（5）所示：

式（4）、式（5）中，stepsizei為移動(dòng)步長(zhǎng)；RB為呈正態(tài)分布的布朗游走隨機(jī)變量；Elitei為由頂級(jí)捕食者構(gòu)造的精英矩陣；Preyi為與精英矩陣具有相同維數(shù)的獵物矩陣；?為逐項(xiàng)乘法運(yùn)算符；P為0.5；R 為［0，1］內(nèi)均勻分布的隨機(jī)變量；n為種群規(guī)模；Iter和Max_Iter分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

2.1.2 迭代中期

在迭代的中期，迭代次數(shù)占總迭代次數(shù)的三分之一到三分之二之間。 算法從原本的勘探策略開(kāi)始向更加靈活的開(kāi)發(fā)策略轉(zhuǎn)變。 此時(shí)捕食者與獵物速度相同，一半種群基于Lévy游走策略負(fù)責(zé)開(kāi)發(fā)，另一半基于布朗游走策略負(fù)責(zé)勘探，數(shù)學(xué)描述如式（6）～（10）所示：

其中，RL為呈Lévy 分布的隨機(jī)變量；CF 為控制捕食者步長(zhǎng)的自適應(yīng)時(shí)變參數(shù)。

2.1.3 迭代終期

在迭代終期又為開(kāi)發(fā)階段，此時(shí)為總迭代次數(shù)的后三分之一，獵物的行進(jìn)速度低于捕食者的行進(jìn)速度，它們會(huì)根據(jù)Lévy 策略來(lái)調(diào)整自身的行進(jìn)步長(zhǎng)。 其數(shù)學(xué)描述為式（11）、式（12）：

2.1.4 FADs 效應(yīng)或渦流

人工集魚(yú)裝置（fish aggregation devices，F(xiàn)ADs）或渦流效應(yīng)為外部的環(huán)境干擾，通?？梢愿淖兒Ｑ蟛妒痴咭捠承袨?，使用這一策略能使海洋捕食者算法在尋優(yōu)過(guò)程中解決收斂過(guò)早和陷入局部最優(yōu)等問(wèn)題。 如式（13）所示：

式（13）中FADs 為解決過(guò)早收斂和陷入局部最優(yōu)的影響因子，取值為0.2。Preyr1和Preyr2分別獵物矩陣的隨機(jī)值，即選取隨機(jī)兩個(gè)獵物；U 為二進(jìn)制向量；r 為［0，1］內(nèi)的隨機(jī)數(shù)。

2.2 算法流程

算法的實(shí)施過(guò)程包括5 個(gè)關(guān)鍵步驟。

步驟1：初始化算法參數(shù)，初始化種群。

步驟2：計(jì)算適應(yīng)度值，記錄最優(yōu)位置。

步驟3：在迭代過(guò)程中，捕食者可以通過(guò)式（4）到式（13）來(lái)調(diào)整自身的位置，以達(dá)到最佳的捕食效果。

步驟4：計(jì)算適應(yīng)度值，更新最優(yōu)位置。

步驟5：判斷是否滿(mǎn)足停止條件，如果不滿(mǎn)足則重復(fù)步驟3～5，否則輸出算法最優(yōu)結(jié)果。

依據(jù)海洋捕食者算法的基本思想，其流程可以按照?qǐng)D1 的描述。

圖1 海洋捕食者算法流程示意圖

3 仿真實(shí)驗(yàn)

為模擬移動(dòng)機(jī)器人的工作環(huán)境，本文使用柵格法描述工作環(huán)境信息，其目標(biāo)函數(shù)可表示為式（14）：

式（14）中，L表示適應(yīng)度值（路徑的長(zhǎng)度），n 表示路徑上的每一個(gè)點(diǎn)的坐標(biāo)。

使用MATLAB R2022a 仿真軟件進(jìn)行仿真。 兩種算法的初始種群數(shù)量都是30，它們的最高迭代次數(shù)被限定在500。 地圖中的起始點(diǎn)和終點(diǎn)分別位于（1，1）和（r，c）。 地圖中黑色的格子代表不可通行區(qū)域，白色格子代表可通行區(qū)域。 選用三種地圖測(cè)試該算法的性能。 為了驗(yàn)證算法結(jié)果不具有偶然性，每個(gè)算法在固定參數(shù)后都會(huì)運(yùn)行30次取平均值。 兩種算法在三種地圖的路徑規(guī)劃規(guī)劃結(jié)果及收斂如圖2 所示。

圖2 在3 種地圖上的仿真實(shí)驗(yàn)

在經(jīng)過(guò)30 次的仿真實(shí)驗(yàn)后，兩種算法在30×30 的柵格地圖下平均最短路徑，平均迭代次數(shù)如表1～3 所示。

表1 粒子群優(yōu)化算法和海洋捕食者算法在地圖1 中的性能比較

表2 粒子群優(yōu)化算法和海洋捕食者算法在地圖2 中的性能比較

表3 粒子群優(yōu)化算法和海洋捕食者算法在地圖3 中的性能比較

根據(jù)以上圖表和仿真信息可以得出，海洋捕食者算法的路徑規(guī)劃結(jié)果明顯優(yōu)于粒子群優(yōu)化算法。 不僅所得到的路徑長(zhǎng)度比較PSO 算法要短，迭代次數(shù)也大幅度下降。地圖1 中平均適應(yīng)度下降3.5%，平均迭代次數(shù)下降32.8%；地圖2 中平均適應(yīng)度下降3.7%，平均迭代次數(shù)下降33.7%；地圖3 中平均適應(yīng)度下降2.2%，平均迭代次數(shù)下降46.4%。 由以上可得，海洋捕食者算法在最短路徑和迭代次數(shù)上明顯優(yōu)于粒子群優(yōu)化算法。

4 結(jié)語(yǔ)

本文首先分析了海洋捕食者的算法原理和流程，利用MATLAB R2022a 仿真軟件進(jìn)行仿真，將海洋捕食者算法和粒子群優(yōu)化算法在3 種地圖上做仿真實(shí)驗(yàn)，在障礙物部分不同的情況下發(fā)現(xiàn)海洋捕食者算法在迭代次數(shù)和適應(yīng)度上都明顯優(yōu)于粒子群優(yōu)化算法。 適應(yīng)度平均下降3.06%，迭代次數(shù)平均下降了37.6%。 經(jīng)過(guò)實(shí)驗(yàn)證明，采用海洋捕食者算法得出的路徑精度極高，而且行進(jìn)速度極快，完全能夠滿(mǎn)足移動(dòng)機(jī)器人的路徑規(guī)劃需求。