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

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

中圖分類號： TN820.4?34； TP242" " " " " " " " "文獻(xiàn)標(biāo)識碼： 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]是機(jī)器人行走的重要部分。路徑尋優(yōu)算法是路徑規(guī)劃的核心，其研究的主要目的是在環(huán)境地圖中搜索出一條從起點到終點距離最短的安全無碰撞路徑[3]。隨著群智能算法的不斷創(chuàng)新，已經(jīng)有越來越多的算法應(yīng)用于機(jī)器人最優(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ā)不平衡、易陷入局部極值等缺陷，影響機(jī)器人路徑尋優(yōu)時的運動效率。文獻(xiàn)[11]根據(jù)算法在不同更新階段存在的缺陷，分別提出差分演化、正余弦算法以及反向?qū)W習(xí)策略等手段進(jìn)行改進(jìn)，顯著提升了算法的尋優(yōu)精度與收斂效率。文獻(xiàn)[12]提出了一種結(jié)合Tent混沌序列的海洋捕食者改進(jìn)算法，增強(qiáng)了算法全局搜索能力。

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

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]處，主要進(jìn)行勘探行為。其位置更新如下：

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

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

第2階段：單位速度比階段（v=1），發(fā)生在迭代中期，在此階段，整個種群一分為二，其中一部分獵物負(fù)責(zé)勘探，另一部分捕食者負(fù)責(zé)開發(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ā)生在迭代后期，主要進(jìn)行開發(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)的隨機(jī)數(shù)；[Xmax]和[Xmin]是獵物位置的上限和下限；[U]是只包含0和1的二進(jìn)制向量，當(dāng)r大于0.2時，其數(shù)組設(shè)為0，反之則設(shè)為1；[Preyr1]和[Preyr2]是隨機(jī)選取兩個不同獵物的位置。

2" 改進(jìn)海洋捕食者算法（GMPA）

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

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

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

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

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

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

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

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

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

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

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

2.3" 隨機(jī)性學(xué)習(xí)策略

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

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

2.4" 改進(jìn)后算法流程

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

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

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

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

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

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

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

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

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

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

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

2） 目標(biāo)路徑最短。

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

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

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

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

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

4.1" 標(biāo)準(zhǔn)測試函數(shù)實驗

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

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

4.2" 機(jī)器人全局路徑仿真實驗

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

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

5" 結(jié)" 論

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

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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