改進海洋捕食者算法的機器人路徑規(guī)劃

摘" 要： 為克服海洋捕食者算法存在的初始種群分布不均、收斂速度慢且易陷入局部最優(yōu)等問題，提出一種改進的海洋捕食者算法（GMPA）。首先，在初始化種群時采用Sobol序列和對立學(xué)習相結(jié)合的策略，得到更加均勻隨機的初始解；再引入慣性權(quán)重系數(shù)和柯西變異來更新種群，提高算法跳出局部最優(yōu)的能力；最后，針對更新后的種群，結(jié)合隨機性學(xué)習策略來增加迭代過程中種群的多樣性。為驗證所提算法的有效性，選用7個標準測試函數(shù)對其性能進行評估；并選用3組復(fù)雜度不同的柵格地圖，對改進后的算法與原始算法開展路徑規(guī)劃對比實驗。實驗結(jié)果表明：改進后的海洋捕食者算法在機器人路徑規(guī)劃問題中表現(xiàn)出良好的性能，顯著提高了收斂速度并增強了優(yōu)化能力。

關(guān)鍵詞： 路徑規(guī)劃； 海洋捕食者算法； Sobol序列； 對立學(xué)習策略； 種群分布； 隨機性學(xué)習策略； 路徑尋優(yōu)

中圖分類號： TN820.4?34； TP242" " " " " " " " "文獻標識碼： A" " " " " " " " " " " 文章編號： 1004?373X（2024）24?0153?07

Robot path planning based on improved MPA

QI Dezhong1， 2， TIAN Chen1， YUAN Lifeng1， WU Yunzhi1， ZHENG Tuo1

（1. School of Mechanical Engineering， Hubei University of Technology， Wuhan 430068， China;

2. School of Mechanical and Electronic Engineering， Shandong Agricultural University， Taian 271018， China）

Abstract： In allusion to the shortcomings of the marine predator algorithm （MPA）， such as uneven distribution of the initial population， slow convergence speed and easy to fall into local optimum， an improved MPA is proposed. A combination of Sobol sequence and contrastive learning strategy is used in initializing the population to obtain a more uniform and random initial solution. The inertia weight coefficient and Cauchy's variance are introduced to update the population， so as to improve the the algorithm's ability to escape from local optima. The stochastic learning strategy is combined with the updated population to increase the diversity of the population in the iterative process. In order to verify the effectiveness of the algorithm， 7 standard test functions are selected to evaluate the performance of the improved algorithm. The comparative experiments on path planning between the improved algorithm and the original algorithm are conducted by selecting 3 groups of raster maps with different complexities. The experimental results show that： the improved MPA has shown good performance in robot path planning problems， significantly improving convergence speed and enhancing optimization capabilities.

Keywords： path planning; marine predator algorithm; Sobol sequence; oppositional learning strategy; population distribution; random learning strategy; path optimization

0" 引" 言

路徑規(guī)劃[1?2]是機器人行走的重要部分。路徑尋優(yōu)算法是路徑規(guī)劃的核心，其研究的主要目的是在環(huán)境地圖中搜索出一條從起點到終點距離最短的安全無碰撞路徑[3]。隨著群智能算法的不斷創(chuàng)新，已經(jīng)有越來越多的算法應(yīng)用于機器人最優(yōu)路徑規(guī)劃，如A*算法[4?5]、人工勢場法[6?7]等傳統(tǒng)算法，還有粒子群算法[8]、麻雀搜索算法[9]、灰狼算法[10]等智能優(yōu)化算法。

近年來，海洋捕食者算法（Marine Predator Algori thm， MPA）作為一種新型的元啟發(fā)式優(yōu)化算法備受關(guān)注。該算法具有結(jié)構(gòu)簡單、參數(shù)設(shè)置少的優(yōu)勢，易于在實驗編碼中實現(xiàn)且處理速度快，為解決問題提供了一種高效的選擇；但還存在初始種群缺乏多樣性、全局搜索與局部開發(fā)不平衡、易陷入局部極值等缺陷，影響機器人路徑尋優(yōu)時的運動效率。文獻[11]根據(jù)算法在不同更新階段存在的缺陷，分別提出差分演化、正余弦算法以及反向?qū)W習策略等手段進行改進，顯著提升了算法的尋優(yōu)精度與收斂效率。文獻[12]提出了一種結(jié)合Tent混沌序列的海洋捕食者改進算法，增強了算法全局搜索能力。

以上學(xué)者在海洋捕食者算法理論方面做了大量研究并對其優(yōu)化，優(yōu)化后的算法具有一定的適用性，但這些算法在機器人路徑規(guī)劃領(lǐng)域上的研究較少，依然需要對其進行優(yōu)化，提高海洋捕食者算法的實用性。本文提出一種改進海洋捕食者算法。首先將Sobol序列和對立學(xué)習策略引入種群并初始化，使初始解分布更均勻；然后加入慣性權(quán)重系數(shù)和柯西變異對種群進行更新，避免陷入局部最優(yōu)；最后結(jié)合隨機性學(xué)習策略來增加迭代過程中種群的多樣性。將所提算法應(yīng)用于路徑規(guī)劃中進行實驗，仿真結(jié)果表明該算法在路徑長度、轉(zhuǎn)折點數(shù)等方面的性能優(yōu)于原始算法。

1" 海洋捕食者算法

海洋捕食者算法作為一種群智能優(yōu)化算法，借鑒了海洋中生物適者生存的理論，其靈感源于海洋捕食者在尋找食物時選擇的最佳策略，包括Levy游走策略和布朗游走策略。若種群數(shù)量為n且個體維度為d，則通過式（1）初始化種群。

[X0=Xmin+rand（Xmax-Xmin）]" " " "（1）

式中：[Xmax]和[Xmin]分別表示搜索空間的上限和下限；rand是0～1范圍內(nèi)的均勻隨機向量。

MPA中的精英矩陣和獵物矩陣分別用式（2）、式（3）表示：

[Elite=XI1，1XI1，2…XI1，dXI1，2XI2，2…XI2，d????XIn，1XIn，2…XIn，dn×d]" " " （2）

[Prey=X1，1X1，2…X1，dX1，2X2，2…X2，d????Xn，1Xn，2…Xn，dn×d]" " " （3）

式中：[XI]表示頂級捕食者向量，精英矩陣由該向量復(fù)制n次所組成。

MPA使用3個階段來描述海洋捕食者的捕食過程。

第1階段：高速比階段（v≥10），發(fā)生在迭代總數(shù)的前[13]處，主要進行勘探行為。其位置更新如下：

[stepsizei=RB?（Elitei-RB?Preyi）Preyi=Preyi+P?R?stepsizeii=1，2，…，n] （4）

式中：[RB]表示布朗運動的隨機數(shù)向量；[R]為[0，1]中的均分隨機數(shù)向量；P=0.5。

第2階段：單位速度比階段（v=1），發(fā)生在迭代中期，在此階段，整個種群一分為二，其中一部分獵物負責勘探，另一部分捕食者負責開發(fā)。其更新如下：

[stepsizei=RL?（Elitei-RL?Preyi）Preyi=Preyi+P?R?stepsizeii=1，2，…，12n] （5）

對于后一半種群數(shù)量：

[stepsizei=RB?（RB?Elitei-Preyi）Preyi=Elitei+P?CF?stepsizeiCF=1-IterMax_Iter2IterMax_Iteri=12n，12n+1，12n+2，…，n] （6）

式中：[RL]是代表Lévy運動的參數(shù)向量；CF表示捕食者運動步長的自適應(yīng)參數(shù)。

第3階段：低速比階段（v=0.1），發(fā)生在迭代后期，主要進行開發(fā)。其更新如下：

[stepsizei=RL?（RL?Elitei-Preyi）Preyi=Elitei+P?CF?stepsizei]" " " "（7）

MPA中考慮到海洋環(huán)境變化對捕食者的影響，其數(shù)學(xué)模型如下：

[Preyi=Preyi+CFXmin+R?Xmax-Xmin?U， r≤FADsPreyi+FADs1-r+rPreyr1-Preyr2， rgt;FADs] （8）

式中：[FADs]表示受環(huán)境影響的概率，F(xiàn)ADs=0.2；r是[0，1]區(qū)間內(nèi)的隨機數(shù)；[Xmax]和[Xmin]是獵物位置的上限和下限；[U]是只包含0和1的二進制向量，當r大于0.2時，其數(shù)組設(shè)為0，反之則設(shè)為1；[Preyr1]和[Preyr2]是隨機選取兩個不同獵物的位置。

2" 改進海洋捕食者算法（GMPA）

2.1" Sobol序列和對立學(xué)習初始化種群

Sobol序列是一種低差異序列，使用確定性擬隨機數(shù)序列代替?zhèn)坞S機數(shù)序列，同時，在種群中引入對立解，將產(chǎn)生的所有解的種群合并在一起，隨后根據(jù)適應(yīng)值的大小從高到低排序，依次選取與種群數(shù)量相等的個體作為新的初始種群。

[X=Kn?Xmax-Xmin+Xmin]" " （9）

[X=Xmax+Xmin-X]" " " " "（10）

式中：[Kn∈0，1]為Sobol序列產(chǎn)生的隨機數(shù)；[Xmax]的[Xmin]分別表示解空間的上限和下限。

隨機生成與Sobol序列生成個體散點圖如圖1所示。

2.2" 慣性權(quán)重和柯西變異

引入?yún)?shù)w來平衡MPA的全局搜索和局部開發(fā)階段。當慣性權(quán)重比較大時，有利于算法的全局搜索，種群移動速度較快，從而可以探索更廣泛的區(qū)域；而當慣性權(quán)重比較小時，有利于算法的局部搜索，能夠在最優(yōu)解附近進行精細搜索，從而加快算法整體的收斂速度。該參數(shù)定義如下：

[w=0.2cosπ21-IterMax_iter]" " " "（11）

因此，位置更新如下：[stepsizei=RL?（Elitei-RL?Preyi）Preyi=w·Preyi+P?R?stepsizeii=1，2，…，12n] （12）

[stepsizei=RL?（Elitei-RL?Preyi）Preyi=w·Preyi+P?R?stepsizeii=12n，12n+1，12n+2，…，n] （13）

在對獵物進行更新迭代過程中，為避免算法陷入局部最優(yōu)而停止，引入Cauchy變異算子對當前最優(yōu)個體進行變異擾動，以逃離局部最優(yōu)，繼續(xù)搜索新區(qū)域。

[Elitenew=Elite+Cauchy·Elite]" " " " （14）

式中：Cauchy為柯西分布的隨機變量；Elite為當前局部最優(yōu)解。

2.3" 隨機性學(xué)習策略

隨機性學(xué)習策略的理念主要借鑒了教與學(xué)優(yōu)化算法，它在該算法中模擬捕食者之間討論交流的學(xué)習模式，通過向具有卓越表現(xiàn)的個體學(xué)習，以優(yōu)化自身位置。對于個體X，再從種群選取與之不同的Xk，通過比較兩者的適應(yīng)度值，篩選出表現(xiàn)卓越的對象，然后向優(yōu)秀的個體學(xué)習，調(diào)整當前位置以提升個體性能。

[X_new=X+rand（X-Xk），" f（Xk）lt;f（X）X+rand（Xk-X），" f（Xk）gt;f（X）]" "（15）

2.4" 改進后算法流程

Step1：由式（9）、式（10）對種群進行初始化，然后設(shè)置好種群規(guī)模、最大迭代次數(shù)、FADs等相關(guān)參數(shù)值。

Step2：計算初始種群中每個個體的適應(yīng)度值，然后選取適應(yīng)度值最優(yōu)的個體構(gòu)成精英矩陣，并將其進行海洋記憶存儲。

Step3：根據(jù)式（4）、式（7）、式（12）、式（13）對獵物位置和步長進行更新。

Step4：計算出每個獵物的適應(yīng)度值并進行比較，選取最優(yōu)適應(yīng)度值的獵物個體構(gòu)成精英矩陣，然后由式（14）、式（15）進行更新，并進行海洋記憶存儲。

Step5：種群個體同時受海洋環(huán)境FADs影響，由公式（8）進行位置更新并保留最佳位置。

Step6：判斷算法是否達到停止迭代的條件，若滿足則算法結(jié)束；否則轉(zhuǎn)至Step2進行更新。

3" 環(huán)境模型及適應(yīng)度函數(shù)

為了簡化問題，機器人可以被視作質(zhì)點，目標是在已知環(huán)境中找到最佳路徑。首先進行場景網(wǎng)格化，本文采用柵格法模擬機器人的工作環(huán)境并搭建模型，在該模型中，每個柵格的邊長設(shè)定為1。三種不同復(fù)雜程度的環(huán)境柵格圖如圖2所示。

圖中：黑色柵格用以表示障礙物所占據(jù)的區(qū)域；白色柵格則表示移動機器人允許越過的區(qū)域。

此時，MPA中的適應(yīng)度函數(shù)是評價路徑好壞的一個重要指標。設(shè)定每個獵物更新的位置坐標集合代表機器人的一條路徑，通過算法的迭代找出一條符合約束條件的最優(yōu)路徑。約束條件有：

1） 移動的路徑必須在柵格區(qū)域內(nèi)，且不與障礙物柵格發(fā)生碰撞；

2） 目標路徑最短。

在滿足上述條件的諸多柵格位置中，第j行柵格應(yīng)選橫坐標最小值i作為最終路徑節(jié)點（xi，yi），即目標函數(shù)（路徑長度）可表示為：

[L（path）=i=1n（xi+1-xi）2+1]" "（16）

式中：n表示節(jié)點數(shù)；xi表示第i個節(jié)點位置。

4" 仿真實驗結(jié)果

GMPA算法性能驗證實驗分為標準函數(shù)測試實驗和機器人全局路徑規(guī)劃仿真實驗兩部分。實驗環(huán)境為Intel? CoreTM i5?7300HQ CPU，2.5 GHz主頻，8 GB內(nèi)存以及Windows 10（64位）的操作系統(tǒng)，在軟件Matlab 2020a上進行仿真驗證。

4.1" 標準測試函數(shù)實驗

實驗選取7組標準測試函數(shù)進行仿真對比測試，分別與MPA、PSO、BOA、GWO、WOA等算法進行比較。在本文實驗中，將算法的種群規(guī)模設(shè)置為30，最大迭代次數(shù)設(shè)定為500。每個算法獨立運行30次，將最優(yōu)仿真結(jié)果的平均值（Ave）與標準差（Std）作為算法性能的評價指標。5種對比算法具體參數(shù)設(shè)置如表1所示，標準測試函數(shù)及相關(guān)屬性如表2所示，6種算法基于測試函數(shù)的收斂曲線如圖3所示?；跇藴蕼y試函數(shù)的6種算法測試結(jié)果如表3所示。

由圖3和表3可知，GMPA算法在7個測試函數(shù)上的尋優(yōu)精度明顯是最好的。這表明所提出的策略對MPA的優(yōu)化能力有所提高，與其他算法相比，GMPA是更好的算法。

4.2" 機器人全局路徑仿真實驗

為進一步驗證改進算法在移動機器人基于障礙物分布密集程度不同的靜態(tài)環(huán)境的全局路徑規(guī)劃問題求解中的尋優(yōu)性能，在3種不同柵格地圖環(huán)境中，默認起點為地圖左上角，終點為地圖右下角。將改進的海洋捕食者算法與原始算法進行對比，程序仿真參數(shù)設(shè)置與4.1節(jié)中測試實驗一致。3種環(huán)境柵格圖的指標統(tǒng)計結(jié)果如表4所示。2種算法尋優(yōu)結(jié)果如圖4～圖6所示。

從上述結(jié)果可以看出，在3種地圖的基礎(chǔ)上，改進海洋捕食者算法相較于原始算法，最優(yōu)路徑分別縮短了19.5%、3.3%、16.1%，說明改進后的算法收斂精度更高。同時，改進后的路徑轉(zhuǎn)折點數(shù)量減少，說明改進后的算法較原始算法有較好的局部搜索能力，減少了冗余路徑的出現(xiàn)。改進后的算法隨著地圖復(fù)雜程度的增加，其優(yōu)勢也越來越明顯，說明改進后的海洋捕食者算法有著更好的全局搜索能力。

5" 結(jié)" 論

本文提出一種改進的海洋捕食者算法（GMPA），以求解移動機器人全局路徑規(guī)劃問題。針對傳統(tǒng)MPA初始種群分布不均、收斂速度慢且不易跳出局部最優(yōu)等問題，引入Sobol序列和對立學(xué)習對種群初始化，并結(jié)合慣性權(quán)重和柯西變異擾動來平衡全局搜索和局部開發(fā)的能力，最后通過引入隨機性學(xué)習策略增加迭代過程中種群的多樣性。將改進后的算法應(yīng)用于機器人路徑尋優(yōu)問題中進行測試，結(jié)果表明：在3種不同的環(huán)境下對比原算法，改進后的算法在尋優(yōu)結(jié)果上有一定的提升。

注：本文通訊作者為鄭拓。

參考文獻

[1] 李磊，葉濤，譚民，等.移動機器人技術(shù)研究現(xiàn)狀與未來[J].機器人，2002（5）：475?480.

[2] 柴紅杰，李建軍，姚明.改進的A*算法移動機器人路徑規(guī)劃[J].電子器件，2021，44（2）：362?367.

[3] 柯永斌，謝田，姜程文，等.基于改進袋獾優(yōu)化算法的無人機路徑規(guī)劃[J].電子器件，2023，46（2）：397?403.

[4] 王殿君.基于改進A*算法的室內(nèi)移動機器人路徑規(guī)劃[J].清華大學(xué)學(xué)報（自然科學(xué)版），2012，52（8）：1085?1089.

[5] 王一凡，湯建華，付華良，等.基于改進雙向A*勢場混合算法的滅火機器人路徑規(guī)劃方法研究[J].電子器件，2022，45（5）：1139?1144.

[6] 于振中，閆繼宏，趙杰，等.改進人工勢場法的移動機器人路徑規(guī)劃[J].哈爾濱工業(yè)大學(xué)學(xué)報，2011，43（1）：50?55.

[7] 周克帥，范平清.改進A*算法與人工勢場算法移動機器人路徑規(guī)劃[J].電子器件，2021，44（2）：368?374.

[8] 王慧，王光宇，潘德文.基于改進粒子群算法的移動機器人路徑規(guī)劃[J].傳感器與微系統(tǒng)，2017，36（5）：77?79.

[9] 宋立業(yè)，胡朋舉.改進SSA在三維路徑規(guī)劃中的應(yīng)用[J].傳感器與微系統(tǒng)，2022，41（3）：158?160.

[10] 劉志強，何麗，袁亮，等.采用改進灰狼算法的移動機器人路徑規(guī)劃[J].西安交通大學(xué)學(xué)報，2022，56（10）：49?60.

[11] 付華，劉尚霖，管智峰，等.階段化改進的海洋捕食者算法及其應(yīng)用[J].控制與決策，2023，38（4）：902?910.

[12] 陳龍，金可仲，蔡雪冰，等.基于改進MPA的分層無線傳感器網(wǎng)絡(luò)優(yōu)化部署[J].傳感技術(shù)學(xué)報，2021，34（1）：109?117.

[13] 郭志軍，尹亞昆，李亦軒，等.融合改進A*和TEB算法的移動機器人路徑規(guī)劃[J].河南科技大學(xué)學(xué)報（自然科學(xué)版），2023，44（4）：57?65.

作者簡介：戚得眾（1984—），男，山東日照人，博士研究生，副教授，研究方向為機電一體化。

田" 晨（1998—），男，湖北黃石人，碩士研究生，研究方向為機器人動力學(xué)分析。

袁麗峰（1998—），男，江西九江人，碩士研究生，研究方向為機器人路徑規(guī)劃。

吳云志（1997—），男，湖北鄂州人，碩士研究生，研究方向為智能算法優(yōu)化。

鄭" 拓（1985—），男，湖北荊州人，博士研究生，講師，主要研究方向為機電一體化。