多策略优化麻雀搜索算法及其路径规划的应用

梁景润,刘丽桑,陈炯晖,张友渊,陈家煜

(1. 福建理工大学 电子电气与物理学院,福建 福州 350118;2. 福建省工业集成自动化行业技术开发基地,福建 福州 350118)

在移动机器人领域,路径规划是指从起始点至目标点规划出一条安全、平滑和最短的路径[1]。路径规划在智能仓储、智能物流、柔性制造和自动驾驶等领域应用广泛,路径规划算法也一直是研究热点。传统的全局路径规划算法有Dijkstra、A*、PRM和RRT等。为了解决货运索道的路径规划问题,张飞凯等[2]对Dijkstra算法进行了优化,减少了路径搜索的计算量。谢春丽等[3]引入跳点搜索算法对A*算法进行改进,有效节省了算法的运行时间和内存开销。为了提高路径的安全性,程谦等[4]对PRM算法进行优化,使路径连接更多的采样点并增加了路径在弯道处与障碍物的距离。为了实现移动机器人在狭隘通道上的路径规划,陈法法等[5]对RRT算法进行了改进,在增加道路探索成功率的同时减少了路径成本。然而,这些传统的全局路径规划算法大多存在寻路时间长、内存开销大和复杂度较高等缺点。

近年来,一些智能优化算法如粒子群算法(PSO)、遗传算法(GA)、萤火虫优化算法(FA)、蚁群算法(ACO)、灰狼优化算法(GWO)和麻雀搜索算法(SSA)等也被引进移动机器人的路径规划领域。师玮等[6]提出一种改进的PSO方法来优化工业机械臂的运动轨迹,减少了必需的运动时间,提高运动轨迹优化的精度。陈高远等[7]提出了一种用于移动机器人路径规划的改进GA算法,并用PSO进行局部搜索,以加快GA算法的收敛速度,防止其陷入局部最优。针对移动机器人在运动过程中存在实际运动轨迹与预设轨迹偏差过大等问题,于飞等[8]通过对ACO进行改进,完成了移动机器人的按需规划,并最小化了移动机器人的运动轨迹与预设轨迹的偏差。虞馥泽等[9]提出了一种改进的FA并用于求解多机器人的路径规划问题,在提高路径安全性的同时减少路径长度。刘志强等[10]采用多种策略对传统的GWO进行了改进,解决了该算法收敛速度慢和容易陷入局部最优等问题,提高了算法的寻优精度,并减少了算法的规划路径的长度。

上述研究成果从多个角度为解决移动机器人的路径规划难题提供思路,但还有一些问题有待解决,如算法规划的路径过长、路径转弯次数过多和路径不够平滑等[11]。针对这些问题,本研究提出了一种基于Logistic混沌映射、自适应惯性因子和柯西变异等多种先进策略改进的麻雀搜索算法,以期改善麻雀初始种群的分布,提高算法初始解的质量,平衡算法的全局探索能力与局部勘探能力,增强算法跳出局部最优解的能力。

1 传统的麻雀搜索算法

麻雀搜索算法是一种元启发式群智能优化算法,来源于麻雀种群的捕食和反捕食行为特征具有结构简单、调优参数少和易于实现等优点[12]。然而,麻雀搜索算法与其他智能优化算法一样,也存在初始种群质量不高、搜索区域分布不均和易陷入局部最优等缺点[13]。

一般地,麻雀种群主要被划分为发现者和跟随者。其中,发现者主要帮助麻雀种群发现食物源,并引领麻雀种群向食物源靠近。除发现者外,大部分的麻雀为跟随者,主要跟随发现者来获取食物[14]。此外,麻雀种群在捕食过程中还会随机选择一小部分的麻雀个体作为侦查者,大约占整个种群的10%～20%。当发现天敌时,侦查者会向整个麻雀群体发出警告信号,整个麻雀群体必须尽快逃到其他安全的地方。

假设麻雀种群的集合矩阵表示为:

X=[x1,x2,x3,…,xp]T

(1)

其中,xi=[xi,1,xi,2,…,xi,d],i=(1,2,…,p),p代表麻雀种群的数量,d代表变量的维数,则麻雀种群的适应度函数用式(2)表示。

F(x)=[f(x1),f(x2),…,f(xn)]T

(2)

其中,f(xi)=[f(xi,1),f(xi,2),…,f(xi,d)],表示第i个麻雀的适应度值。

一般地,优先获得食物的麻雀将成为发现者,其适应度值也会相应变好,从而帮助整个麻雀种群获得食物。发现者的位置更新方式[15]可用式(3)表示。

(3)

表1 4种算法的性能对比Tab.1 Comparison performance of four algorithms

除了发现者,大多数麻雀都是跟随者,跟从发现者获取食物。跟随者的位置更新方式[15]如式(4):

(4)

式中,Xworst代表麻雀种群中适应度最差的麻雀个体,Z为1×d的矩阵,且Z′=ZT(ZZT)-1。当i≤(n/2)时,表明第i个跟随者的适应度值较好,可以获得充足的食物;反之,则代表其适应度值较差,需要到其他地方去补充食物。

为了安全起见,麻雀种群中通常会被选择一小部分的麻雀个体作为警戒者。警戒者的位置更新方式[15]如式(5):

(5)

式中,Xbest表示全局最佳位置。λ是一个服从[0,1]正态分布的步长可控的随机数。k代表麻雀的行进方向,是[-1,1]范围的均匀随机数。fi和fg分别代表当前的全局最佳和最差的适应度值。ε为避免分母为0的最小常数。fi=fg表示麻雀处于种群的边缘,容易受到天敌的袭击。

综上,传统的麻雀搜索算法有以下缺点:

(1)麻雀种群在初始化时是随机创建的,导致种群分布不均,种群多样性较差,算法的初始解质量较低。

(2)发现者的位置更新方式具有一定的局限性,无法平衡全局搜索能力和局部挖掘能力。当预警值小于所设定的安全阈值时,发现者的搜索能力将会随着算法的迭代次数的增加而慢慢降低,导致算法的空间搜索区域不足,算法收敛效率较低。

(3)最差和最优麻雀个体缺乏交流反馈,面对复杂的工程优化问题时容易陷入局部最优解。

2 基于多策略优化的麻雀搜索算法

2.1 Logistic混沌映射

针对麻雀种群在后期迭代过程中存在种群多样性较差等问题,本研究采用Logistic混沌映射生成初始麻雀种群来丰富其多样性,提高算法初始解的质量。

混沌现象是一种可自主产生的特定非线性现象,具有确定规律的随机性和周期性等特点,可以不重复地搜索其整个工作空间范围。而Logistic混沌映射作为一种典型的混沌映射模型,与Tent混沌映射和Sine混沌映射等相比,具有更均匀的分布特征和可控的随机性。因此,本研究采用Logistic混沌映射初始化麻雀种群来丰富其多样性,从而提高算法初始解的质量。Logistic混沌映射的数学表达式[16]如式(6):

Xt+1=μ·Xt·(1-Xt)

(6)

其中,Xt+1为t+1代的麻雀个体,Xt为t代的麻雀个体。μ∈(0,4],且当μ=4时,Logistic混沌映射达到完全映射状态。经过Logistic混沌映射构建麻雀的初始种群,增加了麻雀初始种群的规模和多样性。相较于由随机策略产生的麻雀初始种群,使用Logistic混沌映射形成的麻雀种群的分布更加均匀,种群多样性更高。Logistic混沌映射方法不仅改善了麻雀种群的边缘聚集情况,而且使得麻雀种群在非边缘地区的分布更加均匀,扩大了算法的搜索范围,提高了算法的搜索效率。

2.2 自适应惯性因子

传统的麻雀搜索算法由于在算法迭代初期就开始逼近全局最优解,可能导致其在后期迭代过程中全局空间的搜索能力下降、探索范围变窄、容易落入局部最优值。针对这一问题,本研究采用了自适应惯性因子法更新麻雀种群的发现者的位置。通过引入自适应惯性因子,在算法迭代初期增大自适应惯性因子,集中探索全局空间区域;在算法迭代后期减小自适应惯性因子,专注于发现者的最佳位置的挖掘,使得算法能在全局搜索能力和局部勘探能力之间得到均衡,降低了算法陷入局部最优的风险。

利用自适应惯性因子改进发现者的位置更新方式如式(7):

(7)

其中,自适应惯性因子λ可表示如式(8):

(8)

式中相关变量已在公式(3)中阐明,不再赘述。

2.3 柯西变异算法

针对传统的麻雀搜索算法在面对复杂的工程优化问题时易陷入局部最优解等缺点,本研究采用柯西变异算法进一步增强最差麻雀个体与最优麻雀个体的交流反馈,提高了算法的收敛效率和跃出局部最优解的能力。

传统的算法在更新跟随者的位置后,适应度值最差的麻雀个体一般很难定位到猎物的位置。若在实际的捕食过程中有目的地增强最差个体与最优个体的交流反馈,既能进一步降低最差麻雀个体的适应度值,又能对最优麻雀个体的位置起扰动作用,有助于算法跃出局部最优解。因此,在传统算法的基础上,通过融合柯西变异算法的交流反馈阶段可以提高算法的寻优精度以及收敛速度,用公式表达[17]如式(9):

(9)

通过融合柯西变异算法增强了麻雀种群中最差麻雀个体与最优麻雀个体的交流反馈,使得最差麻雀个体能快速飞往猎物的位置,进一步降低了最差麻雀个体的适应度值,提高了算法的收敛效率。

此外,通过柯西变异算法的随机小步长对当前的局部最优麻雀个体的位置进行扰动,实现全局最优解附近的不断搜索,持续更新当前最优麻雀个体的位置和适应度值,扩大了算法的搜索区域,增强了算法的全局搜索能力和规避局部最优的能力。

3 基于LAFSSA的全局最优路径规划

3.1 LAFSSA流程

将基于多策略改进的麻雀搜索算法(LAFSSA)应用于移动机器人的全局路径规划,基本流程如图 1所示。

图1 LAFSSA路径规划流程图Fig.1 Flow chart of LAFSSA for path planning

3.2 LAFSSA的适应度函数

对于移动机器人的全局路径规划寻优问题,适应度函数的构造通常需要考虑路径规划的两个特性:一是移动机器人不能与障碍物发生碰撞;二是移动机器人在当前环境模型中规划的全局路径是最短的。因此,本研究从路径长度和避障函数两个方面构造LAFSSA的适应度函数。

假设Pi(xi,yi)和Pi+1(xi+1,yi+1)分别是算法规划的路径点序列P′={P0,P1,…,Pi,Pi+1,…,Pm-1}中相邻的两个路径点,则算法规划的全局最短路径可由路径点序列P′中相邻的路径点的欧式距离求得,表示如式(10):

(10)

式中,(xi,yi)和(xi+1,yi+1)分别为路径点Pi和Pi+1对应环境模型中的横坐标和纵坐标。m代表路径点序列P′对应环境模型中的路径点个数。

除了需要考虑移动机器人的全局最优路径长度最短,还需要避免移动机器人的路径穿过障碍物。因此,本研究提出一个惩罚函数F2,当移动机器人的路径将与障碍物发生碰撞时,对其进行惩罚,从而避免了移动机器人的路径穿过障碍物,与障碍物保持一定的距离,用公式(11)表示:

F2=φ·Q

(11)

式中,φ为惩罚因子,Q为障碍物在环境模型中的位置。

综上可知,LAFSSA的移动机器人全局路径规划的总的适应度函数公式为:

(12)

4 仿真实验与分析比较

4.1 实验环境

为方便模拟出移动机器人周围的真实环境,构建了两个地图环境模型如图2所示。其中,x,y分别表示地图环境模型的长和宽。环境模型1的地图大小为20×20,上三角形表示移动机器人的起点位置,其坐标为(1,1);五角星表示移动机器人的终点位置,其坐标为(20,20)。环境模型2的地图大小为40×40,上三角形表示移动机器人的起点位置,其坐标为(1,1);五角星表示移动机器人的终点位置,其坐标为(40,40)。通过比较可知,图 2(b)的环境模型比图 2(a)的更加复杂,这对移动机器人的路径规划将是一个挑战。

图2 地图环境模型Fig.2 Environmental model mapping

实验的仿真环境为处理器Intel(R) Core(TM) i7-5500 @ 2.40 GHz、内存8 GB和装有MATLAB R2017b软件的Windows7 64位系统的笔记本电脑。

4.2 实验结果

为验证所提的LAFSSA的有效性,分别使用蚁群优化算法(ACO)、鲸鱼优化算法(WOA)、麻雀搜索算法(SSA)和所提的改进麻雀搜索算法(LAFSSA)在环境模型1、2中进行移动机器人的全局路径规划。仿真实验中,ACO、WOA和SSA的种群规模设置为50,最大迭代次数设置为200。

对于环境模型1,使用ACO、WOA、SSA和LAFSSA规划出移动机器人的全局路径如图3所示。

图3 4种算法在环境模型1中的规划路径Fig.3 Path planned by four algorithms in environmental model 1

由图3可知,在环境模型1中,算法规划的路径长度从短到长依次为:LAFSSA、ACO、WOA、SSA。算法规划的路径转向次数从少到多依次为:LAFSSA、SSA、WOA、ACO。因此,综合考虑路径长度和路径转折次数作为算法的衡量标准时,所提的LAFSSA均是最优的。

从图4可以更加直观地看到ACO、WOA、SSA和LAFSSA在环境模型1中移动机器人全局路径的寻优效果表现。算法的收敛精度从高到低依次为LAFSSA、ACO、WOA和SSA。算法的收敛速度从快到慢依次为LAFSSA、SSA、ACO和WOA。因此,综合考虑算法的收敛精度和收敛速度,LAFSSA在环境模型1中的路径寻优效果比ACO、WOA和SSA等算法更好。

图4 4种算法在环境模型1中的收敛曲线图Fig.4 Convergence curve of four algorithms in environmental model 1

为进一步验证LAFSSA的可靠性,使用ACO、WOA、SSA和LAFSSA等算法在环境模型2中规划出移动机器人的全局路径,如图 5所示。

由图5可知,在环境模型2中,算法规划的路径长度从短到长依次为:LAFSSA、WOA、SSA、ACO。算法规划的路径转向次数从少到多依次为:LAFSSA、WOA、SSA、ACO。因此,对于更加复杂的环境模型2,LAFSSA在路径长度和路径转折次数等方面的性能均优于ACO、WOA和SSA等算法。

图5 4种算法在环境模型2中的规划路径Fig.5 Path planned by four algorithms in environmental model 2

ACO、WOA、SSA和LAFSSA等4种算法在环境模型2中的收敛曲线如图6所示。

图6 4种算法在环境模型2中的收敛曲线图Fig.6 Convergence curve of four algorithms in environmental model 2

由图6可得知,所提4种算法的收敛精度从高到低依次为LAFSSA、WOA、SSA和ACO,收敛速度从快到慢依次为LAFSSA、ACO、SSA和WOA。因此,从算法的收敛精度和收敛速度等方面综合考虑,与ACO、WOA和SSA等算法相比,LAFSSA在环境模型2中的全局路径规划效果更好。此外,地图环境越复杂,LAFSSA的竞争力越显著。

综上,与ACO、WOA和SSA等算法相比,LAFSSA在路径长度和路径转折次数等方面均表现出较好的性能。为更突出LAFSSA的优越性,综合考虑路径长度、路径转折次数和算法耗时等3个指标,总结了ACO、SSA、WOA和LAFSSA等算法的性能如表1所示。

由表1的结果可知,在环境模型1和环境模型2中,与ACO、WOA和SSA等算法相比,本研究所提LAFSSA规划的移动机器人的路径长度更短,路径转折次数更少,算法耗时更低,移动机器人的路径寻优时间更少,规划路径的平滑性也被有效提升。

5 结论

针对传统的SSA在求解移动机器人的路径规划问题时存在路径长度长、路径转折次数多和路径搜索耗时等问题,本研究提出了一种基于多种先进策略改进的SSA,称为LAFSSA。该算法引入Logistic混沌映射策略生成麻雀初始种群,增加麻雀种群的多样性,提高算法初始解的质量。此外,本研究提出一种自适应惯性因子法用于改进SSA中发现者的位置更新策略,进一步平衡算法的全局搜索能力和局部勘探能力。为防止陷入局部最优,该算法融合柯西变异算法增强最差麻雀个体与最优麻雀个体的交流反馈。在环境模型1和环境模型2中进行的移动机器人的路径规划仿真实验,验证了所提LAFSSA的有效性。与SSA相比,LAFSSA规划的路径长度平均缩短了45.49%,路径转折次数平均减少了36.11%,算法耗时平均减少了29.04%,具有较高的寻优精度和较好的路径平滑效果,在解决移动机器人的路径规划问题时具有更加显著的优势。