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

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

關鍵詞： 路徑規劃； 海洋捕食者算法； Sobol序列； 對立學習策略； 種群分布； 隨機性學習策略； 路徑尋優

中圖分類號： 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" 引" 言

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

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

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

1" 海洋捕食者算法

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

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

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

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]表示頂級捕食者向量，精英矩陣由該向量復制n次所組成。

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

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

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

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

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

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

對于后一半種群數量：

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

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

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

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

MPA中考慮到海洋環境變化對捕食者的影響，其數學模型如下：

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

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

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

2.1" Sobol序列和對立學習初始化種群

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

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

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

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

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

2.2" 慣性權重和柯西變異

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

[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）

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

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

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

2.3" 隨機性學習策略

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

[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）對種群進行初始化，然后設置好種群規模、最大迭代次數、FADs等相關參數值。

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

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

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

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

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

3" 環境模型及適應度函數

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

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

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

1） 移動的路徑必須在柵格區域內，且不與障礙物柵格發生碰撞；

2） 目標路徑最短。

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

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

式中：n表示節點數；xi表示第i個節點位置。

4" 仿真實驗結果

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

4.1" 標準測試函數實驗

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

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

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

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

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

5" 結" 論

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

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

參考文獻

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

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

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

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

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

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

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

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

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

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

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

[12] 陳龍，金可仲，蔡雪冰，等.基于改進MPA的分層無線傳感器網絡優化部署[J].傳感技術學報，2021，34（1）：109?117.

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

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

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

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

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

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