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

黄训爱,杨光永,樊康生,徐天奇

(1.云南民族大学 电气信息工程学院, 昆明 650500;2.云南省无人自主系统重点实验室, 昆明 650500)

0 引言

海洋捕食者算法(marine predators algorithm,MPA)是Faramarzi等于2020年提出的一种新型元启发式智能算法[1]。受到海洋中捕食者获得猎物方式的启发,通过对捕食者觅食行为的简化和模拟,在反演过程中结合Lévy飞行和布朗运动选择最佳觅食策略,具有寻优能力强、参数少、易于实现、计算精确等优点。被广泛应用于特征选择[2]、参数优化[3]、车间调度[4]、故障诊断[5]等领域。

王逸文等[6]提出了一种基于反向差分变异的种群变异机制和最优个体自适应扰动策略的改进海洋捕食者算法并将其应用于压力容器设计问题;Guo等[7]提出了一种改进海洋捕食者算法的原位标定方法,取得良好标定效果;于涵等[8]提出了一种改进混沌初始化,引入自适应步长和精英竞赛机制的改进海洋捕食者算法;周放歌等[9]采用改进二进制海洋捕食者算法搜索故障馈线,通过分组学习策略以及自适应t分布提高算法搜索能力;Durmus等[10]利用海洋捕食者算法对CEAA单元的电流幅值和角位置值进行优化,得到最优辐射方向图,并与其他元启发优化算法比较,取得良好效果;马驰等[11]将混沌映射与对立学习相结合,进一步提高种群质量和搜索精度,并将改进算法应用于无线传感器网络覆盖优化;李代华等[12]提出一种将海洋捕食者算法与自适应神经模糊推理系统相结合的径流预测方法;张贝等[13]提出一种融合趋向全局最优的反向学习策略,更新捕食者位置,采用三阶段最优引导最差策略,提高搜索能力,并应用于插值平滑的机器人路径规划。

随着人工智能技术的发展,机器人广泛应用在仓库货物搬运、救援、物流、智慧农业等领域[14]。而路径规划是移动机器人研究的重点,其目的是保证机器人不与障碍物碰撞的前提下规划出一条从起点到目的地的最优路径[15]。移动机器人路径规划方法可以分为传统路径规划算法和智能路径规划算法。传统路径规划方法有人工势场法[16]、模拟退火算法[17]、禁忌搜索算法等。此类方法存在搜索效率不高、路径冗余等问题。常用的智能路径规划方法有A*算法[18]、粒子群算法[19]、蚁群算法[20]、遗传算法[21]、灰狼优化算法[22]等,其搜索能力强,但极易陷入局部最优,计算比较复杂。

针对上述问题,本文提出一种多策略改进海洋捕食者算法(IMPA),引入Logistic混沌映射初始化种群,增加捕食者种群多样性;基于当前迭代次数t的自适应移动步长动态调整策略,增强算法逃离局部最优能力;在IMPA迭代后期,加入中垂线算法(MA),基于中垂线策略的游离粒子位置更新方法,能够加快捕食者的位置更新,增强算法的寻优速度和寻优精度,避免算法陷入局部最优。最后通过改变IMPA阶段转换寻优过程,进一步平衡搜索过程,加强全局与局部适应性。最后选用基准测试函数对改进算法性能进行测试,并应用于机器人路径规划,证明本文改进算法的有效性。

1 海洋捕食者算法

海洋捕食者算法(MPA)是一种新型元启发式优化算法,该算法主要灵感来自于海洋捕食者觅食策略,即海洋捕食者的莱维(Lévy )和布朗(Brownian)运动,以及捕食者和猎物之间的最佳相遇率策略,模拟了海洋中适者生存理论。

MPA优化过程主要分为3个阶段,考虑不同的速度比,同时模仿捕食者的整个生命过程:

1) 高速比阶段(t≤tmax/3),即猎物移动速度快于捕食者时;

2) 等速比阶段(tmax/3

3) 低速比阶段(t≥2tmax/3),即捕食者速度快于猎物时。

1.1 MPA初始化精英矩阵和猎物矩阵

随机在搜索空间范围内初始化猎物位置来启动优化过程。数学描述如下:

猎物矩阵(Prey)每一个元素Xij的初始化方法:

Xi, j=xmin+rand(Xmax-Xmin)

(1)

最终得到Prey矩阵如式(2)所示:

(2)

式中:n为种群规模;d为每个维度的位置。

对每一个Prey个体Xi=[Xi,1,Xi,2,…,Xi,d],计算其适应度,然后使用适应度最优个体XI,复制n份构成精英矩阵(Elite):

(3)

1.2 探索阶段

高速比阶段,当捕食者速度远小于猎物速度时,(t≤tmax/3),算法处于探索阶段,基于勘探策略的MPA优化过程数学描述如下:

i=1,2,…,n

(4)

式中:t为迭代次数;tmax为最大迭代次数;Elitei为由顶级捕食者构造的精英矩阵;Preyi为与精英矩阵具有相同维数的猎物矩阵;RB为呈正态分布的布朗游走随机向量,stepsizei为移动步长;⊗为逐项乘法运算符;P等于0.5;R为[0 1]内均匀随机向量;n为种群规模。

1.3 探索与开发之间的转换

等速比阶段,捕食者速度与猎物速度相同;(tmax/3

i=1,2,…,n/2

(5)

i=n/2,…,n

(6)

式中:RL为呈Lévy分布的随机向量;η=(1-t/tmax)(2t/tmax)为控制捕食者移动步长的自适应参数,其他参数意义同上。

1.4 开发阶段

低速比阶段,捕食者速度快于猎物速度时,(t≥2tmax/3),捕食者基于Lévy游走采用开发策略,其数学描述如下:

i=1,2,…,n

(7)

式中其他参数意义同上。

1.5 鱼类聚集装置或涡流效应作用

鱼类聚集装置(SFAD)等环境问题会对海洋捕食者造成影响,可看作局部最优,采用式(8)消除影响:

(8)

式中:SFAD表示海洋捕食者减小局部极值影响的概率,取值为0.2;U为二进制向量;r为[0 1]内随机数;Preyr1,Preyr2分别为从猎物矩阵中随机选取的2个猎物。

2 改进海洋捕食者算法

2.1 Logistic混沌映射初始化种群

传统的随机数生成器初始化MPA时存在遍历性不足,会影响后续搜索;而均匀分布的种群可以适度扩大算法的搜索范围,从而提高收敛速度和求解精度,Logistic混沌映射是混沌映射中的典型代表,可以用于增加种群多样性,比使用随机数生成器初始种群方式更加可靠、优越。本文将Logistic混沌映射应用于海洋捕食者算法的种群初始化阶段,其数学表达式如式(9)所示:

Xn+1=μXn(1-Xn)

(9)

式中:Xn为第n代混沌序列产生的值,Xn∈[0,1],参数μ一般取值是1≤μ≤4,当参数μ增大时,映射序列的取值范围也增大,映射分布变得更加均匀,当μ=4时,系统处于完全混沌状态下,此时映射分布均匀性达到巅峰,所以本文μ取值为4。

2.2 自适应移动步长动态调整策略

MPA的种群位置更新阶段中,猎物位置的变化决定算法能否快速收敛到更好的位置。本文通过动态调整移动步长,进一步控制算法的勘探与开发能力,促进局部快速收敛,从而提高算法收敛精度。传统MPA的移动步长主要是通过自适应参数η=(1-t/tmax)2t/tmax控制,算法前期更注重勘探,开发能力较弱,导致算法收敛速度较慢;因此,本文通过构造基于指数函数的自适应移动步长控制参数实现对移动步长的动态调整,如式(10)、式(11)所示:

τ=(1-(tmax+t)/(tmax-t))β

(10)

η1=eτ+c1

(11)

式中:c1取常数,为0.05;β=3。在算法迭代初期,η1数值较大且变化速率较快,能够增强其开发能力,加快算法收敛;在算法迭代中后期,η1平缓减小逐渐趋于稳定,算法能够进行局部精细搜索找寻到更优质潜藏猎物,提高算法的收敛精度。自适应移动步长控制参数变化曲线如图1所示。

图1 自适应移动步长控制参数收敛曲线

2.3 融合中垂线算法的捕食者位置更新策略

2.3.1 中垂线策略原理

为提高算法收敛速度,本文结合中垂线原理[23],提出中垂线算法(MA)收敛策略,一条线段的中垂线上任一点到这条线段两端的距离相等,粒子根据这一几何性质,不断缩小最优解的搜索范围,从而找到最优解。如图2(a)所示,假设在一个二维空间内,在矩形围成的范围内(如图中阴影区域所示)仅存在一个最优点P,存在随机的2个点A和B,将两点连接起来形成一条线段AB,作线段L为AB的中垂线,定义|PA|<|PB|,则P点必存在于线段L靠A侧区域。中垂线算法把最优点到P点的距离用其适应度值来代替,因AP的距离小于BP的距离,即A点适应度比B点更优。P点具有最佳适应度,如图2(a)所示,中垂线算法收敛过程如下:

图2 中垂线算法原理图

1) 判定|PA|是否小于|PB|,若是,则判定最优值位于中垂线靠A侧区域内(图1网格区域);

2) 丢弃B点,在中垂线L靠A侧区域重新随机生成一点B′;

3)A点和B′点构成线段AB′,作其中垂线L′,此时B′点离P点更近,即B′点适应度更好,则MA判定最优值位于L′靠近B′点区域内(左图阴影区域);

4) 重复上述步骤不断生成新的A点,通过MA方法即可不段缩小最优点所处空间。

2.3.2 融合中垂线算法的捕食者位置更新策略

在图2(a)中加入一个随机粒子C(图中粒子即代表捕食者),并且C位于L靠A侧区域,如图2(b)所示,若采用传统的粒子位置更新策略更新B点和C点位置,要经过多次迭代才能到达中垂线靠A侧区域。

如图2(b)所示,将粒子B和C移动到B′点和C′点上,再采用MPA的位置更新策略,可以加快MPA的位置更新。上述策略实现方式为:首先判断粒子是否位于中垂线靠B侧区域,设

(12)

若粒子x在线段L靠B侧区域,则x的第j维变量满足式(13)、式(14):

(13)

其中

(14)

为了减小算法的时间复杂度和全局寻优能力,判定x仅需有两维变量不符合上述策略,则粒子位于A侧区域,粒子位置更新不采用上述策略。

若MA判定,若粒子位于中垂线靠B侧区域,则B点更新公式为:

(16)

2.4 改进MPA阶段转换寻优过程

传统MPA算法采用均分3阶段的寻优策略,优化过程中,三阶段分别占据总迭代次数的1/3,没有考虑阶段寻优速度的影响。随着总迭代次数的改变,每一阶段迭代次数也会改变。本文采用李帝铨等[24]提出的一种阶段差异划分的寻优方式,差异划分每一阶段的寻优方式,增强算法的寻优精度和迭代速度,数学式如下:

阶段1:迭代初期

i=1,2,…,n

(17)

式中:λ1为常数,取值为3.2;RB_max为RB向量元素的最大值,其他元素含义同上。

阶段2:迭代中期

i=1,2,…,n/2

(18)

i=n/2,…,n

(19)

式中:λ2、c1、c2均为常数,λ1取值为3.2,c1取值为0.9,c2取值为0.4。

阶段3:迭代后期

i=1,2,…n

(20)

2.5 IMPA算法流程

依据2.1～2.4节的描述,改进海洋捕食者算法流程如下:

步骤1初始化最大迭代次数T、种群规模n,当前迭代次数t;局部极小值概率SFAD,精英矩阵(Elite)、猎物矩阵(Prey);

步骤2计算适应度,记录捕食者最优位置;

步骤3第1阶段更新;

步骤4第2阶段更新;

步骤5第3阶段更新;

步骤6中垂线算法的游离粒子位置更新方法更新捕食者位置;

步骤7解决涡流形成和SFAD效应;

步骤8更新适应度值和捕食者最优位置;

步骤9判断算法结束条件,如果t

3 IMPA性能验证

3.1 测试函数设定

为验证改进算法收敛精度、收敛速度和稳定性等性能,采用6个常见基准函数进行仿真对比实验,基准测试函数表达式见表1,其中F1—F3为单峰测试函数,有一个最优解用于验证算法收敛速度;F4—F6为多峰测试函数,具有多个局部最优解,用于验证算法收敛精度和全局搜索能力。选用海洋捕食者算法(MPA)、粒子群算法(PSO)、灰狼优化算法(GWO)、麻雀优化算法(SSA)与本文的改进海洋捕食者算法(IMPA)进行对比实验,实验平台为:Matlab2019b(Intel(R)Core(TM)i5-8250UCPU@1.60 GHz)。

表1 基准测试函数表达式

3.1.1 改进算法参数选择对IMPA性能的影响

在2.4节采用自适应移动步长动态调整策略通过动态地调整移动步长进一步来控制算法的勘探与开发,促进局部快速收敛,从而提高算法收敛精度,其中参数β的取值会直接影响改进算法的性能,为了确定最佳实验参数,设计一组实验分别对F1、F3、F4、F5测试函数进行优化。50次实验结果的均值如表2所示。

表2 不同β的实验结果

表2中,随着β值的增大,算法收敛速度变快,跳出局部最优的能力增强,收敛精度有所提高,但随着β值超过3之后,算法收敛精度随之下降,实验结果表明,当参数β的值为3时,算法整体性能最佳。

3.1.2 对比算法参数选择确定及其影响

各对比算法的参数设置如表3所示,在设置参数时,为保证公平性,各算法的种群规模统一选取为50,其中MPA和IMPA的参数设置上面已进行实验论证,这里不重复讨论。PSO算法的参数为在各种应用中实验论证出的较佳参数,GWO中的a参数为固定公式计算得出,这里不做讨论。SSA算法中的安全阈值参数ST对算法的性能有较大影响,这里通过实验论证对其讨论并找出最佳参数,使算法性能最佳。

表3 各算法参数

表4为SSA算法对4个测试函数F1、F2、F4、F6进行优化时,不同ST值下50次独立实验的均值结果。ST的取值范围在[0.51]之间,当预警值小于安全值时,表示安全,此时发现者搜索空间较大,当预警值大于等于安全值时,表示有了一定数量的捕食者,需要移动到安全区域。ST值的大小直接影响算法搜索空间的大小,进而影响算法收敛精度和收敛速度。从表4可以看出,随着ST值从0.5逐渐增大的过程中,其均值在逐渐减小,算法收敛精度在逐渐提高,当ST值增大到0.8时,均值最小,之后随着ST值增大,均值也随之逐渐增大,收敛精度逐渐下降,实验结果表明,当ST值为0.8时,算法性能最佳,所以,本文取值为0.8。

表4 不同ST值的实验结果

3.2 对比实验结果分析

本文计算的标准差和平均值分别用来评价算法稳定性和收敛精度;因数据矩阵随机产生,每次独立试验结果不一定为最优值,故本文重复试验50次,取其平均值,规定各测试函数维度为30维,因适应度数量级相差过大,F1—F6 收敛曲线的适应度均为 log10 处理后的结果。

3.3 IMPA收敛精度分析

实验中测试函数维度为30维,各对比算法的标准差和均值如表5所示。

由表5可知,IMPA除测试函数为F1、F3时,其他测试函数的均值为零,而MPA只有当测试函数为F5时,均值才为0,表明IMPA无论是在处理单极值问题还是处理多极值问题收敛精度均比MPA高。MPA在处理单极值问题时表现良好,在处理多极值问题时,收敛精度明显不如IMPA。与GWO、PSO和SSA相比较,IMPA均值最小,表明IMPA与其他算法相比收敛精度具有明显优势,其他算法无论是在处理单极值问题还是多极值问题上均表现不佳。

上述数据表明:IMPA无论是处理单极值问题还是多极值问题时,表现均为最佳,证明IMPA中,基于Logistic混沌映射增加种群多样性和基于中垂线算法的游离粒子位置更新方法,能够显著提高算法收敛精度。

3.3.1 IMPA稳定性分析

如表5所示,除测试函数为F3外,MPA的标准差均大于IMPA,而IMPA的标准差除F3外全为0,说明无论在处理多极值问题还是处理单极值问题时,MPA稳定性都不如IMPA。与GWO、PSO和SSA相比较,IMPA的标准差均是最小的,表明无论是处理单极值问题还是处理多极值问题,IMPA算法的稳定性均明显优于其他3种算法。

分析表明,MPA算法在融合了中垂线算法的游离粒子位置更新策略后,能够更加高效快速地找到优质捕食者,增强算法全局搜索能力;另外,自适应移动步长动态调整策略,通过对移动步长控制参数的动态调整进一步调整移动步长,保证算法前期能够进行开发,后期进行精细搜索找到优质潜藏猎物,提高算法的收敛精度。

3.3.2 IMPA收敛速度分析

图3为各对比算法在求解不同基准测试函数时问题解的收敛过程。由图3可以看出,在6个基准测试函数中,各算法求解基准测试函数适应度值达到最小值时,IMPA所需迭代次数均是5种对比算法中最小的,尤其求解多峰函数时,差距更明显,证明本文提出的自适应移动步长动态调整策略和MPA阶段转换寻优过程,有效地提高了算法收敛速度,全局寻优能力更强。

图3 不同算法在各基准测试函数上的收敛曲线

4 IMPA在机器人路径规划中的应用

路径规划在机器人组成部分中具有重要作用。路径规划技术就是在障碍物环境中规划出一条从起始点到终点的最优或次优路径,使机器人安全的到达预定地点。目的是使路径长度最短、路径拐点最少,要求不能碰到障碍物且与障碍物保持一定的安全距离。目前,海洋捕食者算法在机器人路径规划技术中应用较少,本文将IMPA应用于机器人路径规划,进一步验证算法实际应用性能。

4.1 建立机器人路径规划数学模型

4.1.1 栅格地图建模

通常情况下,移动机器人(AGV)的工作环境为二维有限空间,为了便于建模,对栅格地图作如下假设:

1) AGV运行环境为二维矩形有限空间;

2) 运行过程中,将AGV看做一个质点,行驶速度为v,为了安全,机器人需与障碍物保持一定安全距离。

对二维矩形空间建立笛卡尔直角坐标系,x轴的栅格数为Nx=xmax/v,y轴的栅格数为Ny=ymax/v,每个栅格对应相应的序列号,且序列号与坐标之间关系满足式(21)、式(22):

xp=[(p-1)modn]+1

(21)

(22)

式中:n为每一行栅格数;p为坐标序列号;mod为求余运算;INT为取整运算。栅格法建立的环境地图中黑色区域代表障碍物,白色区域代表自由空间,如障碍物形状为不规则屋,则通过补偿方式将其补充填满障碍物。

4.1.2 适应度函数设计

适应度函数是检验IMPA算法优化程度的重要函数。机器人路径规划的任务就是在最短时间内找到一条从起始点到终点的最短的、较平滑的路径。路径长度越短,到达目的地越快;路径越平滑,可以避免转弯降低速度,同时提高安全性。因此,本文综合考虑路径长度和光滑程度,设计适应度函数。

设机器人路径为一条连接起点(x0,y0)和终点(xn,yn)的点序列p=(p1,p2,…pn)={(x0,y0),(x1,y1),…(xn,yn)},由一系列决策目标最优的点组成。其中p1=(x0,y0)表示路径目标起点,pi=(xi,yi)表示路径目标节点,pn=(xn,yn)表示表示路径目标终点。机器人路径长度计算公式如式(23)所示:

(23)

此外,路径平滑度也是机器人安全、平稳运行的重要条件。机器人由于运动学和动力学约束,在运动时,拐弯角度不宜过大,假设路径经过点pi和pi+2确定,两点之间的点pi+1使3点之间的距离之和越小,相邻3点形成的角度越大,路径越平滑,路径平滑度计算公式,如式(24)所示:

(24)

由于路径中连续3点连线夹角情况分别为平角、钝角、直角、锐角,其中,平角代表3点在同一直线上,平滑度最好,钝角、直角次之,由于动力学和运动学约束,锐角不允许出现。综合考虑路径长度、平滑度和障碍物等因素,本文建立机器人适应度函数,如式(25)所示:

f=λ·G0+ηG1

(25)

式中:λ为路径长度因子;η为路径平滑度因子,可根据路径长度和平滑度之间的权重,灵活选择其大小,本文选择λ=1,η=1。

4.2 实验

为验证本文改进算法(IMPA)在机器人路径规划中的性能,选择灰狼算法(GWO)、粒子群算法(PSO),海洋捕食者算法(MPA)作为对比算法,和本文改进算法(IMPA)在相同的栅格地图环境中进行路径规划对比实验,设置粒子数量N=50,最大迭代次数T=500,设置GWO参数为:收敛因子a=2-2t/T(t为当前迭代次数);设置PSO参数为:惯性权重因子ω1=0.9,ω2=0.4,学习因子c1=2,c2=2。

分别在20×20栅格地图和30×30栅格地图中进行仿真实验。图4和图5为各算法在20×20和30×30栅格地图环境中的路径规划仿真图,将各算法规划路径的性能指标放于表6中作为对比。

表6 各算法规划路径性能指标

图4 20×20栅格地图路径规划仿真图

图5 30×30栅格地图路径规划仿真图

由表6可知,在20×20栅格地图中,IMPA最优路径为28.856 9,在4种算法中是最短的,其次是MPA,IMPA路径长度相较于MPA缩短了9.25%,相较于PSO缩短了16.13%,相较于GWO缩短了11.80%;IMPA的寻路时间同样是4种算法中最短的,相较于MPA寻路效率提高了7.8%,相较于PSO提高了6.25%,相较于GWO提高了38.91%;同样地,IMPA的路径拐点个数是4种算法中最少的,相比其他3种算法具有明显优势。在30×30栅格地图中,IMPA最优路径为44.44,在4种算法中是最短的,其次是MPA,IMPA路径长度相较于MPA缩短了15.35%,相较于PSO缩短了26.36%,相较于GWO缩短了36.64%;IMPA的寻路时间略长于MPA和PSO,但相差不大,比GWO缩短了30.22%。从图4、图5、表6可以看出,相较于传统的MPA算法和其他2种对比算法,IMPA规划的路径长度更短,拐点更少,寻路时间也具有明显优势,取得了良好效果。

验证改进算法在机器人路径规划中的收敛速度,各算法规划路径长度与迭代次数对应关系的仿真图如图6所示。在20×20栅格地图中,在4种对比算法中,规划路径达到该算法所获得最优路径长度时,IMPA所需要迭代次数最少,证明其收敛速度最快,GWO所需迭代次数最多,说明其收敛速度最慢;在30×30栅格地图中,IMPA规划路径达到该算法所获得最优路径长度时,IMPA所需要迭代次数略多于PSO,但明显少于MPA和GWO,其收敛速度同样优势明显,证明本文改进算法在机器人路径规划中收敛速度较快。

图6 各算法路径规划仿真图

5 结束语

针对海洋捕食者算法存在收敛速度慢,收敛精度低,易陷入局部最优的问题,提出一种改进海洋捕食者算法,引入Logistic混沌映射初始化种群,增加捕食者种群多样性;基于当前迭代次数t的自适应移动步长动态调整策略,增强算法逃离局部最优能力;在IMPA迭代后期,加入中垂线算法(MA),基于中垂线策略的游离粒子位置更新方法,加快捕食者的位置更新,增强算法的寻优速度和寻优精度,避免算法陷入局部最优。最后通过改变IMPA阶段转换寻优过程,进一步平衡搜索过程,加强全局与局部适应性。选用6个基准测试函数对IMPA算法性能进行验证,改进算法在求解单峰函数和多峰函数时,无论是在收敛速度、收敛精度,还是稳定性方面,均具有明显优势。将IMPA应用于移动机器人路径规划,分别在20×20和30×30栅格地图中与其他算法进行对比实验,实验结果进一步证明了改进算法的有效性