改进人工大猩猩优化算法的机器人路径规划

贾鹤鸣，游进华，李永超，李政邦

（1.三明学院信息工程学院，福建 三明 365004；2.福建理工大学计算机科学与数学学院，福建 福州 350118）

移动机器人是具有环境感知能力、 自主规划能力与自动执行任务能力的智能设备，其应用覆盖了农业、医疗和快递等行业及家庭等场合［1］。 制定路径规划就是根据机器人获取的环境信息以及路径长度、 搜索时间、平滑度和避障能力等性能指标，寻找一条从起点到终点的最近路径。

近年来，国内外学者提出了多种路径规划算法，这些算法包括人工势场法［2］、A*算法［3］和跳点搜索算法［4］等。人工势场法的缺点是路径规划收敛过早，影响全局搜索，求出的解容易陷入局部最优而无法达到目标点；A* 算法的缺点是路径规划存在搜索效率低下和节点冗余等问题，机器人转弯容易靠近障碍物；跳点搜索算法的缺点是识别关键跳点时要进行大量的迭代计算，搜索效率不高。传统算法存在一定的局限性，不能很好地适应环境的变化，而粒子群算法［5］、遗传算法［6］或模拟退火算法［7］等群智能优化算法就能克服这些缺点，但未经改进的智能算法存在早熟、 搜索时间较长和解为次优等问题。 因此，对原始算法进行改进，使之收敛速度更快、收敛精度更高是当前的研究热点。

2021 年，B. Abdollahzadeh 等［8］提出一种新的启发式智能优化算法，即人工大猩猩优化算法。在解决机器人路径规划问题时， 原始的人工大猩猩优化算法存在易陷入局部最优、 收敛精度不高、 收敛速度较慢等缺点。为了克服这些缺点，我们将人工大猩猩算法和三次样条插值方法［9］结合起来来求解移动机器人路径规划问题，并完成了以下工作：在算法的全局搜索阶段，引入自适应率较高的权重来扩大全局搜索范围； 在算法的局部开发阶段，引入自适应率较低的权重［10］和互利共生策略［11］来提高算法的收敛精度，并通过黄金正弦策略［12］进一步平衡算法的全局搜索和局部开发的能力。 将改进的人工大猩猩优化算法与三次样条插值方法结合， 通过构造以最短路径和避障为目标的适应度函数，实现了机器人路径规划问题的求解。通过简单环境和复杂环境下的实验测试证明了改进算法的有效性和实用性。

1 人工大猩猩优化算法

人工大猩猩优化算法是人们受大猩猩的群体社交生活行为启发而提出的一种元启发式算法， 其原理是通过银背大猩猩位置的更新来改变其他大猩猩的位置，这一过程包括探索阶段和开发阶段。

1.1 探索阶段

在探索阶段，主要是对空间进行全局探索。 假设大猩猩个体位置为X(t)(t为当前迭代次数），GX(t+1)是下次迭代时的大猩猩个体位置。 通过计算个体的适应度值，并对所有个体的适应度值进行比较，选取最优个体进行位置更新。 对应的更新模型为如下形式：

其中：p(p∈(0,1))是给定的参数， 用来模拟银背大猩猩个体对未知位置的探索的影响因素；UB和LB分别是变量的上界和下界；r1、r2、r3、r4和rand是（0,1）之间的随机数，Xr和GXr分别是从整个种群中随机选择的大猩猩位置；MaxIt表示最大迭代次数；在初始阶段，C的变化会较大， 在后期变化值的变化会逐渐减少；l是0 到1 之间的随机数；Z是区间内的随机数。

1.2 开发阶段

在开发阶段，存在两个机制，一是跟随银背大猩猩机制，另一种是大猩猩竞争成年雌性机制。

当C≥W时，选择跟随银背大猩猩机制，位置更新公式为

当C

在以上式子中，Xsilverback为银背大猩猩的位置，N1表示正态分布和问题维度中的随机数，N2表示正态分布中的随机数，β和W是给定参数，r5是（0,1）之间的随机数。

2 改进的人工大猩猩优化算法

与其他群智能算法一样，在算法优化过程中，人工大猩猩优化算法的全局探索和局部开发间始终存在矛盾。为了防止算法在快速收敛中出现早熟，我们通过增加自适应权重来扩大全局搜索范围和提高局部开发能力， 并通过互利共生策略和黄金正弦算法来提高种群多样性和收敛速度。

2.1 自适应权重

在本文中， 我们引入两个不同的惯性加权因子分别进行全局探索和局部开发， 对个体位置的邻域进行更新。当惯性加权因子较大时进行全局搜索，当惯性加权因子较小时进行局部开发， 这样可以精准找出最佳解决方案。自适应权重和位置更新公式如下：进行全局探索时，将自适应权重和位置更新公式分别确定为

进行局部开发时， 将自适应权重和位置更新公式分别确定为

在以上式子中，Xi为当前第i 个大猩猩个体位置，表示更新后第i 个大猩猩个体位置。

2.2 互利共生策略

在局部开发阶段， 人工大猩猩优化算法的随机性较强，易陷入局部最优，因此我们借助互利共生策略来增强个体与最优个体间的联系， 降低局部最优解的影响。 经过改进，可得位置更新公式

其中：Xbest表示当前个体的历史最优位置；Xrand表示随机个体位置；表示更新后的个体位置；bf是利益因子，随机选择1 或2，分别表示部分收益或全部收益；RMV表示随机个体和最优个体的交互作用。

2.3 黄金正弦策略

在进行局部开发过程中， 传统的人工大猩猩优化算法的随机性较大，开发得不够严密，这将导致部分较优解遗漏，进而导致算法的收敛精度降低。为了解决这个问题，我们加入了黄金正弦策略，利用该策略可构造正弦函数模型，以遍历单位圆上正弦函数的所有点，这样才能保证局部开发区域的完整性， 并能充分开发优质解的区域，以提高算法的收敛速度。加入黄金正弦策略的位置更新公式为

在以上式子中：R1是[0,2]内的随机数；R2是[0,]内的随机数；τ是黄金分割数，且；Xbest表示当前个体的历史最优位置；表示更新后的个体位置。

3 基于三次样条插值的机器人路径规划

三次样条插值方法是一种常用的分段式插值方法， 其特点就是利用一系列三次多项式的插值点区间形成一条光滑的曲线。 三次样条插值拟合出的机器人移动路径具有更好的动力学特性，因此，我们通过三次样条插值方法和改进人工大猩猩算法（MGTO）的结合来求解机器人路径规划问题。

3.1 三次样条插值方法

在[a,b]内插入n−1个样本点xi(i=1,2,…,n−1),把区间[a,b]分成n个小区间[x0,x1],[x1,x2], …,[x n−1,xn]，区间[a,b]上就有了n+1个节点，且有x0=a,xn=b。 给定这些节点的函数值f(xi)=f i(i=0,1,2,…,n),则每个小区间上的曲线是一个三次函数S i(x)(i=0,1,2, …,n−1)。

三次样条函数满足以下条件：

（1）满足插值条件，即S(xi)=y i(i=0,1, …,n)。

（2）曲线要光滑，这就要求一阶导数、二阶导数均连续，即S(x)∈C2[a,b]。

由条件（3）中4 个条件可以得到4n个方程，组成方程组后就可以求解了。

3.2 编码

每个方程的区间交接处称为路径节点。 在所有的样本点处是一阶连续的和二阶连续的， 故分段样条之间的方向可能是不同的， 即每个三次方程可能是不同的，而路径的节点就代表了整个路径的最大转向次数。一般来说，不论是简单环境还是复杂环境，经过3~5 次转向就能够避开所有的障碍物。因此，我们将大猩猩个体的位置作为节点的编码， 即大猩猩个体位置拥有的维数代表节点的个数， 大猩猩个体的横坐标代表节点的横坐标集合，纵坐标代表着节点的纵坐标集合。

设定起点坐标(xs,ys)和终点坐标(xt,yt)以后，先依据大猩猩的个体位置确定路径节点的坐标(xm1,ym1),(xm2,ym2),… ,(xmm,ymm)，再利用三次样条插值法插入n个点，由这些点拟合的连线L就是移动路径。

3.3 适应度函数的构建

为使路径长度尽可能短， 我们采取欧式距离计算路径长度，计算公式为

假设适应度函数为

其中：L是路径长度；beta是一个较大的数，在本文中取beta=100；Violation是一个标志变量，其初始值为0。 为了符合实际场景，我们将障碍物设置为正十二边形，求Violation值的程序表示如下：

在以上式子中，nobs 表示障碍物个数，（xobs,yobs）表示障碍物的中心点位置，xx 和yy 分别表示插值点横坐标集合和纵坐标集合。

先利用式（20） 计算插值点到障碍物中心点的距离，再利用式（21）判断是否经过障碍物，若其中有数值大于0，则表示经过障碍物，相应的Violation是一个大于0 的数，反之，有Violation =0。

3.4 算法步骤

步骤1：根据具体障碍环境选择路径的节点数m、插值点数n、 起点坐标(xs,ys)和终点坐标(xt,yt)、种群个数nPop、最大迭代次数MaxIt。

步骤2：先初始化种群位置，再利用三次样条插值方法计算插值点的坐标。

步骤3：利用式（18）计算n个插值点之间的距离，即路径长度。

步骤4：利用式（20）、式（21）和式（22）计算标志变量Violation，再利用式（19）计算适应度值z。

步骤5：用式（1）~式（6）进行全局搜索的位置更新，并用式（9）~式（10）进行进一步的更新，比较两者的适应度值，选取适应度值小的位置替代原来的位置。

步骤6：用式（7）~式（8）进行局部开发的位置更新，并分别用式（11）~式（12），式（13）~式（14）和式（15）~式（17）进行位置更新，比较更新后的适应度值与更新前的适应度值，选取适应度值小的位置替换最优位置。

步骤7：重复步骤4~步骤6，直到达到最大迭代次数。

步骤8：得到并输出最优路线值。

4 仿真实验及其分析

为验证本算法在求解机器人路径规划问题上的有效性和实用性，在保证客观、公正的前提下，利用改进的人工大猩猩算法（MGTO）与标准的人工大猩猩算法（GTO）、教与学优化算法（TLBO）［13］、多元宇宙优化算法（MVO）［14］、龙格-库塔优化算法（RUN）［15］、算数优化算法（AOA）［16］做仿真实验，以检验MGTO 算法的寻优性能。

4.1 实验参数的设定

为了确保算法结果的公正和客观， 我们将MGTO算法、GTO 算法、TLBO 算法、MVO 算法、RUN 算法、AOA 算法都置于相同的软硬环境下。 运行环境是windows11，编程环境为MATLABR2019a。 在仿真实验中，6 种算法的种群规模为20、最大迭代次数为500，其他参数的设定如下： 在MVO 算法中， 取WEP=0.5；在RUN 算法中， 取w=1，wdamp=0.98，a=1，alpha=0.1；在AOA 算法中， 取C1=2，C2=6，C3=2，C4=0.5，u=0.1，l=0.1；在GTO 和MGTO 算法中，取P=0.03，w=0.8，β=3。

4.2 简单障碍环境下的路径规划

在简单的障碍环境中， 设置9 个障碍物，6 个路径节点，将起点的坐标定为（-25, 28），终点为（30, -30），将各算法的实验次数定为30，可得如图1、图2 和表1所示的实验结果。

表1 简单环境下用6 种算法求得的路径长度

表3 复杂环境下由6 种算法求得的路径长度

图1 简单环境下6 种算法的路径规划

图2 简单环境下6 种算法的迭代曲线

从图1 和图2 可以看出，在简单环境中，GTO 算法与AOA 算法的结果几乎一致，而MGTO 算法的寻优性能明显好于其他算法。 从表1 可看出，不论是最差解、最优解还是平均解，MGTO 算法都是最优的。 这说明三种策略的加入能有效提高算法的收敛速度和寻优能力。

4.3 复杂障碍环境下的路径规划

在复杂的障碍环境下，设置12 个障碍物，将起始点的坐标定为（-30, -30），终点为（30, 30），将各算法的实验次数定为30，可得如图3、图4 和表2 所示的实验结果。

图3 复杂环境下6 种算法的路径规划

图4 复杂环境下6 种算法的迭代曲线

从图3 和图4 可以看出，在复杂的避障环境中，原GTO 算法与RUN 算法相比， 没有太多的优越性，但MGTO 算法的寻优性能远超GTO 算法和其他算法。

从仿真结果可以看出，在两种实验环境中，无论是最差解、最优解，还是平均解，MGTO 算法都优于其他算法。因此，MGTO 算法在解决机器人路径规划问题上具有良好的工程适用性。

5 结束语

本文将人工大猩猩算法与三次样条插值法结合，用于求解机器人路径规划问题。首先，改进了人工大猩猩优化算法， 在全局探索和局部开发阶段分别引入不同非线性惯性因子， 同时在局部开发阶段融入互利共生和黄金正弦策略。 通过仿真实验证明了MGTO 算法的求解性能优于其他对比算法， 验证了该算法在路径规划问题方面的优越性和有效性。