改进海洋捕食者算法的机器人路径规划

摘" 要： 为克服海洋捕食者算法存在的初始种群分布不均、收敛速度慢且易陷入局部最优等问题，提出一种改进的海洋捕食者算法（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—），男，湖北荆州人，博士研究生，讲师，主要研究方向为机电一体化。