基于多策略改进海鸥算法求解机器人路径规划*

李 婕,尚文祥,胡永涛

(河南工学院a.电气工程与自动化学院;b.新乡市机械设备运行状态智能监测工程技术研究中心,新乡 453003)

0 引言

随着智能技术的飞速发展,机器人是被广泛应用于各行各业如农业[1]、娱乐、工业等领域。如何高效地规划移动机器人的移动路径已成为目前主要的研究热点问题之一,此问题是一个受复杂约束的条件下,复杂环境中的非线性最优规划问题[2]。近年来,研究学者着重于基于智能优化算法的机器人路径规划方法研究。这些基于智能算法的机器人路径规划方法均能够提高路径规划的求解精度,比如有:GA算法[3]、PSO算法[4]、ABC算法[5]、改进PSO优化器[6]、改进GWO优化器[7]、改进ACO优化器[8,13]、动态分组ACO算法[9]、FWA-ACO混合算法[10]、PSO-ACO算法[11]、量子WDO算法[12]等。这些方法在求解高维复杂环境中机器人路径规划问题时仍会过早地陷入局部最优,造成求解速度和精度较低等问题。

海鸥优化(seagull optimization algorithm,SOA)被广泛应用于求解各类约束规划问题,如结构优化[14]、光伏MPPT问题[15]、矿震定位问题[16]、参数辨识问题[17]、PID控制器参数优化[18]、电-气互联系统优化调度[19]等。这些文献中的与SOA相关算法处理复杂约束问题能获取较好的求解质量,但是,对于高维的复杂非线性规划问题(如复杂环境中机器人路径规划问题),SOA算法依旧容易陷入局部最优,求解质量较低。

为此,为改善SOA算法的寻优能力,通过融合了混沌策略,多方向翻筋斗迁徙策略,翻筋斗式螺旋跳跃捕食策略及混合波动非线性自适应碰撞因子,提出了一种融合多策略改进的SOA(multi-strategy improved seagull optimization algorithm,MSOA)算法。将MSOA算法应用求解测试函数和复杂环境中机器人路径规划问题上,通过仿真实验验证了所提出算法的适用性,求解稳定性和精度等方面的优势。

1 海鸥优化(SOA)算法

SOA算法主要通过迁徙策略和捕食策略来改变海鸥个体的觅食位置,以实现寻觅丰富食物的目的。算法主要数学寻优过程可简化为:

(1)迁徙策略。为更好地获得食物,海鸥个体会频繁迁徙,通过扩大觅食范围,寻求更加丰富的食物。海鸥个体迁徙位置的更新包括未发生碰撞的位置更新如式(1)和式(2)所示,沿最优迁徙方向位置的更新如式(3)所示,向最优海鸥靠近时位置的更新如式(5)所示。

C(k)=λ×X(k)

(1)

式中:C(k)为海鸥个体的未碰撞迁徙位置,X(k)为海鸥个体当前迁徙位置,λ为避免海鸥个体之间发生碰撞控制参数。

λ=φ(1-k/kmaxiteration)

(2)

式中:φ为常数,取值为2。

M(k)=η×(Xb(k)-X(k))

(3)

η=2×λ2×rand

(4)

式中:M(k)为海鸥个体的当前迁徙位置,Xb(k)为海鸥个体当前最优迁徙位置,η为算法的控制因子,rand为[0,1]内的任意随机数。

D(k)=|C(k)+M(k)|

(5)

式中:D(k)为海鸥个体的最后迁徙位置。

(2)捕食策略。海鸥个体捕食过程中,对猎物的攻击方式以螺旋运动为主,海鸥个体的螺旋攻击运动行为如式(6)所示,其捕食位置的更新如式(7)所示。

(6)

式中:r为海鸥个体螺旋飞行的运动半径大小,α为在[0,2π]范围内服从均匀分布的任意攻击角度,u和v为控制螺旋飞行轨迹的参数。

X(k)=(D×(X×Y×Z))×Xb(k)

(7)

2 多策略改进海鸥算法(MSOA)

2.1 MSOA算法

本部分重点从分析算法的迁徙策略和捕食策略不足之处,对算法进行多策略改进提出MSTOA算法,具体内容为:

(1)初始种群混沌初始化策略。原始SOA算法初始种群生成方式单一,随机性较强,不利于初始种群的均匀分布,会降低SOA算法初始搜索速度和精度。为此,文中采用Circle混沌映射初始化种群如下:

(8)

(2)多方向翻筋斗迁徙策略。在SOA算法中,由图1可知,原始迁徙策略是在迁徙区域A内,海鸥个体沿固定方向D不断地向最佳海鸥个体靠近的过程,整个迁徙过程受参数λ的影响较重,然而参数λ是一个线性递减的变化因子,这就会导致随着迁徙的不断进行,海鸥个体之间的距离会不断地减小,聚集程度就会由稀疏向密集发展。当海鸥个体聚集程度严重时候,不利于海鸥个体向最佳位置移动,也就会降低算法寻优能力。为克服这种缺点,文中提出了多方向翻筋斗迁徙策略,由图1可知,在迁徙过程中,若是海鸥个体以最佳海鸥个体为中心,沿多个迁徙方向(A,B,C)进行翻筋斗动作,翻筋斗至原有海鸥位置的对称处。这样可以明显看出,海鸥个体的迁徙区域A会扩大至迁徙区域B,同时,海鸥个体会分散至最优海鸥个体周围,聚集程度明显降低。算法的迁徙区域扩大和聚集程度的降低有利于提高算法的局部开发和全局搜索能力。这种多方向翻筋斗迁徙策略定义为:

图1 多方向翻筋斗迁徙策略

MF(k)=X(k)+β×η×(r1×Xb(k)-r2×X(k))

(9)

式中:MF(k)为海鸥个体翻筋斗后的迁徙位置,β为翻筋斗因子,r1和r2为[0,1]区间内的随机数。

D(k)=(-1)ksin(γ)|C(k)+MF(k)|

(10)

式中:γ为海鸥个体翻筋斗的方向控制角度因子。

(3)翻筋斗式螺旋跳跃捕食策略。在SOA算法中,海鸥个体的螺旋式捕食策略存在对猎物攻击过程中,无法保证螺旋飞行过程中海鸥个体之间不发生聚集与碰撞,若出现聚集与碰撞现象就会导致算法种群的多样性降低,不利于算法局部寻优和搜索速度。为此,文中提出了翻筋斗式螺旋跳跃捕食策略,分为两步先对海鸥个体螺旋攻击位置进行跳跃操作(即螺旋跳跃攻击策略如图2所示),其次,以猎物为中心,对海鸥个体的螺旋跳跃攻击位置进行翻筋斗变异,如图3所示(翻筋斗式螺旋跳跃捕食策略)。

图2 螺旋跳跃攻击策略

图3 翻筋斗式螺旋跳跃捕食策略

由图2可知,原始的螺旋攻击策略存在攻击范围窄的不足,攻击方向单一,这不利于算法的局部寻优。为此,文中提出了螺旋跳跃攻击策略。这种策略首先采用螺旋方式更新海鸥个体的攻击位置,其次,以猎物位置为中心,对海鸥个体进行跳跃运动。可以明显看出,通过改变跳跃角度θ和初始速度v0,采用这种攻击策略,增加了攻击方向,扩大了螺旋式攻击策略的攻击范围,也可改善海鸥个体的聚集现象,丰富海鸥个体的多样性,这有利于提高算法的局部寻优能力。

这种螺旋跳跃攻击策略主要由螺旋运动和抛物线运动构成,故其数学模型可描述为:

(11)

式中:g为重力加速值,取值9.8;XG(k)为海鸥个体螺旋攻击位置由式(6)计算,XR(k+1)为海鸥个体螺旋跳跃后的攻击位置。

由于翻筋斗策略可以增加种群的多样性,提高算法的寻优能力,为此,文中结合翻筋斗策略和螺旋跳跃攻击策略提出了翻筋斗式螺旋跳跃捕食策略,如图3所示。当海鸥个体在攻击区域A内进行螺旋跳跃攻击猎物,虽然可以丰富种群的多样性,增强算法跳出局部最优的能力,但是当海鸥个体进入到较小的攻击区域B内,依然会存在聚集现象,导致算法的寻优能力下降。为此,采用翻筋斗策略对螺旋跳跃后的海鸥个体进行翻筋斗操作,这样就沿着不同的翻筋斗方向,可实现丰富海鸥个体的多样性,增强算法的局部寻优能力。这种策略的数学模型描述为:

X(k)=XR(k)+β×(r3×Xb(k)-r4×XR(k))

(12)

式中:β为翻筋斗因子与式(8)中相同,r3和r4为[0,1]区间内的随机数,XR(k)为海鸥个体螺旋跳跃后的攻击位置,X(k)为海鸥个体翻筋斗螺旋跳跃后的攻击位置。

(4)混合波动碰撞控制因子。由多方向翻筋斗迁徙策略分析中发现,参数λ对算法的寻优性能影响程度较高。整个迁徙过程中,原有的线性递减碰撞因子λ缺乏自我调节的能力,不利于算法的全局搜索和局部开发。为此,文中采用一种混合波动碰撞控制因子为:

(13)

由图4可知,参数λ的动态波动性明显增强,迭代前期,表现为先快速非线性下降又转入非线性上升,接着又非线性下降;迭代中期,参数λ抖降,迭代中后期,由较短的缓慢上升阶段随即转入快速下降阶段。这种混合式的忽升忽降的非线性变化,使得参数λ能够实现自适应的平衡算法的全局搜索和局部开发,提高算法的收敛精度。

图4 混合波动非线性碰撞控制因子

2.2 MSOA算法步骤

基于2.1节提出的改进MSOA算法,MSOA算法具体步骤为:

步骤1:设定海鸥种群N,最大寻优次数kmaxiteration,维数D及搜索空间大小;

步骤2:按照式(8)初始化海鸥种群位置,并计算海鸥种群的适应度值;

步骤3:更新混合波动碰撞控制因子λ参照式(13);

步骤4:海鸥个体多方向翻筋斗迁徙位置更新参照式(1)、式(4)、式(9)和式(10);

步骤5:海鸥个体翻筋斗式螺旋跳跃捕食位置更新参照式(6)、式(7)、式(11)和式(12);

步骤6:重新计算适应度值并更新海鸥位置;

步骤7:判断算法是否满足最大迭代次数,若达到最大迭代次数,输出最优解,反之,返回步骤3继续迭代计算;

步骤8:算法寻优结束,输出最优解。

2.3 MSOA算法时间复杂度

假设MSOA算法的海鸥种群N,最大寻优次数kmaxiteration和维数D。海鸥种群初始化时间复杂度为O(2N×D),更新过程中的时间复杂度为O(kmaxiteration×N×D)+O(kmaxiteration×N)。因此,MSOA算法的时间复杂度为O(N(kmaxiteration+2)×D+kmaxiteration)。

3 MSOA算法性能评估实验与结果分析

3.1 实验环境和基准函数设置

为评估MSOA算法的寻优性能,选用单模态函数测试算法的收敛精度和鲁棒性,多模态函数测试算法的跳出局部最优的能力,进一步利用平均绝对误差(MAE)统计方法[29]来验证算法的优越性。基准测试函数如表1所示。选用5种算法即CS[20]、ALO[21]、MFO[22]、SOA[14]、GWO[25]和MSOA进行对比分析。5种对比算法的参数均采用文献中推荐的值。所有算法在MATLAB2019软件上,Win10系统,32 G内存,Intel i7处理器上运行计算,选用30次的均值(Mean)、标准差(SD)和耗时(Time)作为实验评价指标。

表1 基准测试函数

3.2 实验结果分析

表2给出了不同算法在基准测试函数上的实验结果。由表2实验结果可知,对单模态函数F1～F6,MSOA算法Mean和SD值优于SOA、CS、GWO、ALO和MFO算法,特别在函数F1、F2、F3和F4上均能够稳定的提供全局最优解。在函数F6上,MSOA算法结果劣于MFO,但优于其他4种算法。同时,由图5可知,与其他5种算法相比,在混沌初始化策略,多方向翻筋斗迁徙策略,翻筋斗式螺旋跳跃捕食策略作用下,MSOA算法可快速的收敛至最优解,收敛曲线下降速率明显快于其他算法,具有较快的收敛速度。

表2 基准测试函数实验结果

(a) F1 (b) F2

对于多模函数F7～F11,在函数F8上,MSOA算法可提供的Mean值为全局最优解。在函数F9～F11上,MSOA算法的Mean和SD值均小于SOA、CS、GWO、ALO和MFO算法。同时,由图6可知,在混合波动非线性自适应碰撞因子作用下,增强了MSOA算法种群个体间学习能力,使其可快速的跳出局部最优解,跳出局部最优解的能力明显优于其他5种算法。

(a) F8 (b) F12

由表2中的Time值可知,对所有的测试函数,MFO算法的耗时最长,MSOA算法的耗时略高于SOA、CS、GWO和MFO算法。MSOA算法比SOA算法的耗时增加幅度较小,这是融入多种变异策略导致MSOA算法种群个体搜索时间增加,但算法的收敛精度和收敛效率均大幅提升。因此,这种耗时的延长是在合理接受范围内。

表3给出了不同算法之间的MAE统计结果。由表3可知,MSOA算法获得了较小的MAE值为0.000 529。在所有算法中排名第一。因此,与其他5种算法相比,MSOA算法具有较强的优越性。

表3 不同算法的MAE结果比较

以上结果表明,MSOA算法在基准测试函数上表现优异,能够较好地处理单模态和多模态问题,这是采用混沌初始化策略,多方向翻筋斗迁徙策略,翻筋斗式螺旋跳跃捕食策略增强MSOA算法局部和全局搜索能力,同时采用混合波动非线性自适应碰撞因子,平衡了MSOA算法的全局搜索能力与局部开发能力,提高了MSOA算法的整体寻优能力。

4 基于MSOA算法的移动机器人路径规划

4.1 环境建模与适应度函数

在构建环境模型中,假设移动机器人为一个无质量和大小的质点;移动环境中包含了障碍物,在二维移动空间内,障碍物分布随机且数量若干;移动机器人需在移动二维空间内进行移动。文中采用栅格法构建移动机器人的环境,白色区域为可移动区域,黑色为障碍物。假设移动机器人移动坐标为(x,y);构建移动机器人移动的路径长度作为适应度函数,如式(14)所示。

(14)

4.2 基于MSOA算法的移动机器人路径规划

根据第2节提出的改进MSOA算法,文中提出基于MSOA的机器人路径规划算法流程如图7所示及具体步骤为:

图7 基于MSOA算法的机器人路径规划方法

步骤1:栅格地图路径规划环境及MSOA算法的初始参数信息设置。如机器人移动始末位置,地图大小,种群数量大小及最大寻优迭代次数等;

步骤2:初始化每只海鸥的坐标位置,参照式(8),并获取最短初始路径长度和规划信息;

步骤3:根据MSOA算法和适应度函数更新每只海鸥的坐标位置,计算海鸥的适应度函数值;

步骤4:重新计算路径长度函数适应度值并更新最短路径长度和规划信息;

步骤5:判断算法是否满足最大迭代次数,假如是,就输出最短路径长度及最佳路径规划信息,反之,返回步骤3继续计算;

步骤6:算法迭代计算结束。

4.3 机器人路径规划实验与结果分析

4.3.1 实验设置

为进一步验证MSOA算法的优势,将其应用于求解在移动机器人路径规划问题,通过选取7种算法与MSOA算法作对比分析。实验中采用常规的栅格法方法来创建3种路径规划地图环境MapⅠ、MapⅡ、MapⅢ,其大小分别为32 m×32 m、42 m×42 m、52 m×52 m,如图8～图10所示。地图中白色方块是可通过区域,黑色方块是障碍物不可通过区域。3种地图的机器人起始点均设置为最左上角,终止点均设置为最右下角。实验中共选取7种流行的算法:SOA[14]、STOA[23]、SSA[24]、GWO[25]、TSO[26]、SCA[27]、RSO[28]以及MSOA算法。所有算法种群大小为300,迭代次数为500,寻优次数为30次。各算法的路径规划寻优性能评价指标选取路径长度的最短值(Min),均值(Mean),标准差值(SD),寻优成功率(S)及平均寻优时间(Time)。

(a) 最短路径规划 (b) 寻优曲线

(a) 最短路径规划 (b) 寻优曲线

(a) 最短路径规划 (b) 寻优曲线

4.3.2 路径规划结果分析

不同地图路径规划对比实验结果在表4～表6给出,各算法之间的移动机器人最优路径移动路径及寻优收敛曲线对比如图8～图10所示。由表中结果可知,对于MapⅠ、MapⅡ和MapⅢ,就路径长度平均Mean值而言,MSOA算法分别为46.72 m、64.65 m和77.83 m。与SSA、SOA、STOA、GWO、RSO、TSO和SCA算法相比,MSOA算法路径长度均值最小。同时,就路径长度的最短Min值而言,MSOA算法分别为46.65 m、62.42 m和75.75 m。对于MapⅠ,MSOA、SOA、STOA、TSO和SCA算法具有一样的路径长度的平均值,其优于SSA、GWO和RSO算法。就路径长度的标准差SD值来看,对于3种地图,MSOA算法的SD值全部小于SSA、SOA、STOA、GWO、RSO、TSO和SCA算法,且SD值精度可达到了1E-01。就寻优成功指数S来看,对于MapⅠ、MapⅡ和MapⅢ,MSOA算法的寻优成功指数S均为1.00,其结果等于或者大于其他7种算法。就平均寻优时间Time值来看,对3种地图,MSOA算法可提供有竞争性的平均寻优时间。对于MapⅠ,MSOA算法的Time值短于SOA、STOA、GWO、RSO和SCA算法。对于MapⅡ,MSOA算法的Time值短于GWO算法,对于MapⅢ,MSOA算法的Time值长于SSA、TSO和RSO算法,短于其他算法。

表4 MapⅠ路径规划实验结果

表5 MapⅡ路径规划实验结果

表6 MapⅢ路径规划实验结果

由图8～图10可以看出,对于MapⅠ、MapⅡ和MapⅢ,就最短路径规划线路来看,与其他7种算法相比,MSOA算法的最短路径规划线较为平直,转弯次数较少,最短路径规划的合理性较高。就寻优曲线来看,MSOA算法的寻优曲线下降较快,位于其他7种算法的下方,这说明了MSOA算法的收敛效率和寻优精度明显优于其他算法。SOA算法的寻优曲线下降缓慢,存在严重的局部最优解,这是因为SOA算法寻优过程中种群的多样性丧失严重,导致了SOA算法难以跳出局部最优,造成SOA算法的寻优速度降低和精度较低。因此,与SOA算法相比,MSOA算法弥补了SOA算法的不足,提高了算法的路径寻优效率和精度。

以上结果可以看出,MSOA算法总能够以较快的速度获得较短的机器人路径规划线路,路径寻优能力优于其他7种算法,表现很好的稳定性和鲁棒性。这是由于MSOA算法融合了混沌初始化策略,多方向翻筋斗迁徙策略,翻筋斗式螺旋跳跃捕食策略及混合波动非线性自适应碰撞因子,平衡了MSOA算法的全局搜索能力与局部开发能力,提高了MSOA算法的寻优能力。

5 结论

为更好地求解机器人路径规划问题及改进SOA算法的性能,针对SOA算法收敛精度弱、易陷入局部最优解等不足进行了相应改进,提出了多策略改进海鸥(MSOA)算法。得出主要结论如下:

(1)提出了多策略改进海鸥算法。在MSOA算法中,设计了全新的多方向翻筋斗迁徙觅食策略和筋斗式螺旋跳跃捕食策略,并结合Circle混沌序列和混合搏斗非线性自适应碰撞因子,提高了算法的整体寻优能力。

(2)提出了基于多策略改进海鸥(MSOA)算法的机器人路径规划方法用于求解机器人路径规划问题。

(3)测试函数和机器人路径规划实验结果表明,MSOA算法的寻优能力优于SOA、CS、GWO、ALO和MFO算法。同时,对于不同的地图,MSOA算法能够快速准确地避开障碍物,获得最短的路径长度。MSOA算法的路径规划寻优能力优于SSA、SOA、STOA、GWO、RSO、TSO和SCA算法,表现出较好的稳定性、适用性和鲁棒性。