基于改进粒子群的混合金豺优化算法的移动机器人路径规划

常新中,岳哲鹏,郜海超,娄泰山,关广胜

(1.河南应用技术职业学院 学院办公室,河南 郑州 450042; 2.郑州轻工业大学 电气信息工程学院,河南 郑州 450002)

随着智能控制设备制造技术的发展以及传感器技术的进步,移动机器人技术逐渐成为当前的研究热点,在航天领域[1]、农业[2-3]和工业[4]生产中发挥了重要的作用。移动机器人在工作时需要根据一定的规则,在工作区域沿着一条最优的路径行走。因此,路径规划是移动机器人导航的重要任务之一,也是目前研究的一个热点[5]。路径规划所用的算法大致分为传统算法和智能算法。传统算法有A*算法[6]、Dijkstra算法[7]和禁忌搜索算法[8]等,但是这些算法往往存在计算效率低、路径搜索能力差等缺点,无法满足技术发展的需求。智能算法具有算法简单、鲁棒性强等特点,在规划路径时不必依赖梯度信息[9]。于是,智能算法逐渐成为了当前的研究热点。智能算法被广泛应用于水下机器人、移动机器人和无人机等装备的路径规划中[10-12],但是其在寻优时会陷入局部最优而导致搜寻路径不是最短的问题。为此,国内外学者近年来一直在不断地探索新的智能算法,并对其进行了一定的研究与应用。宋阿妮等采用精英策略来改进蚁群的信息素浓度,提高蚁群算法跳出局部最优的能力,并引入信息素扩散策略来加强个体之间的交流,提高了算法在无人机三维路径规划中的适应性[13]。魏博等通过模拟粒子运动规律来更新蜂群位置,提高算法的种群开发能力,并利用反向轮盘赌的方法选择蜜源,解决了人工蜂群在路径规划中迭代速度慢、规划效率低的问题[14]。刘志强等通过Tent混沌映射来提升灰狼算法的种群丰富性,并融合动态权重因子和适应度系数更新灰狼的个体位置,提高灰狼算法的全局搜索能力,降低了搜索成本[15]。

随着智能算法的不断拓展,许多优秀算法被提出并得到了应用。其中,金豺优化(Golden Jackal Optimization,GJO)算法是由Chopra和Ansari在2022年提出的一种新型智能算法[16]。GJO算法模拟了金豺狼捕猎的过程,具有较强的寻优能力、较高的收敛速度,受到了众多学者的关注。谢豪等将GJO算法应用于PID的参数优化过程,利用GJO算法对PID的3个参数进行设置并使其向最优解迭代,提高了系统的调节能力[17]。Mahdy等将GJO算法应用到超级充电站的运行优化中,利用GJO算法对PI增益进行优化,提高了系统的稳定性[18]。Najjar等将GJO算法与长短期记忆神经网络模型相结合,预测了Cu-Al2O3的摩擦学性能[19]。从实验结果来看,该算法对复合材料的磨损率和摩擦系数变化具有出色的预测能力。

GJO算法虽然在众多领域都有较为出色的表现,但仍然存在会陷入局部最优、收敛速度慢以及未考虑金豺个体之间的经验交流等问题。因此,本文对粒子群优化(Particle Swarm Optimization,PSO)[20]算法进行改进并将其引入GJO算法,优化GJO算法的位置更新过程,提出一种改进粒子群的混合金豺优化(Hybrid Golden Jackal Optimization,HGJO)算法。同时,将该算法应用于移动机器人的路径规划,并通过路径规划问题的仿真实验验证该改进算法的有效性与可行性。

1 移动机器人的环境建模

利用智能算法对移动机器人进行的路径规划包括下列两个基本步骤:一是针对机器人所处环境进行建模;二是利用智能算法对路径进行反复迭代,以获取最短路径。只有在了解周围的环境信息后才能进行移动机器人的路径规划。合理构建环境地图是获取最优规划结果的前提。经典的环境地图表示方法有栅格法、可视图法、距离转换法、自由空间法等。与其他方法相比,栅格法具有实现简单、数据易于转换等优点,被广泛地应用于移动机器人的路径规划中。

图1 采用栅格法建立的移动机器人二维平面模型

2 金豺优化算法

金豺优化算法是根据金豺探索行为和狩猎行为进行建模的。它包括探索阶段和狩猎阶段。

(1) 探索阶段:金豺寻找并跟踪猎物。金豺天生就会发现并追逐猎物,且往往是雄豺狩猎而雌豺跟随的。猎物并不容易被捕获,有时会逃逸。雄豺与猎物相对位置的变化情况可表示为:

Y1(1)=YM(t)-E·|YM(t)-rl·Prey(t)|

(1)

式中:YM(t)为雄豺的位置;rl·Prey(t)为猎物的运动轨迹;t为当前迭代次数。

雌豺与猎物相对位置的变化情况可表示为:

Y2(1)=YFM(t)-E·|YFM(t)-rl·Prey(t)|

(2)

式中:YFM(t)为雌豺的位置。

(2) 狩猎阶段:当猎物受到金豺骚扰后,其逃逸能量就会开始减少。随后,金豺开始包围猎物。金豺在包围猎物后就会扑向猎物并吃掉猎物。猎物逃跑过程的能量E可表示为:

E=E1E0

(3)

猎物的初始能量为:

E0=2a-1

(4)

式中:a为0到1之间的随机值。

猎物逃逸时的能量为:

E1=C(1-t/T)

(5)

式中:C为恒定值,且C=1.5;T为最大迭代次数。在迭代时,E1是从1.5按线性减少到0的。

莱维分布函数为:

rl=0.05LF(y)

(6)

莱维飞行函数为:

LF(y)=0.01μσ/|ν1/β|

(7)

GJO算法的位置更新公式为:

(8)

针对金豺狩猎行为,可建立下列模型:

(9)

式中:Prey(t)为猎物在t时刻的位置。

金豺从探索阶段向狩猎阶段转换的条件是由E决定的。具体而言,当|E|>1时,金豺会进行探索并寻找猎物;当|E|<1时,金豺会扑向猎物。

3 改进粒子群的混合金豺优化算法

PSO算法是利用粒子自身最优位置和群体最优位置来获取最优解的。其基本表达式为:

(10)

PSO算法虽然可以快速收敛,但是容易陷入局部最优中。为了避免这一现象,本文将自适应动态权重因子w(t)和改进的学习因子引入PSO算法,对PSO算法进行改进,并将改进后PSO算法引入GJO算法中。改进粒子群的混合金豺优化算法表达式为:

(11)

(12)

式中:wmax为初始惯性权重;wmin为最终惯性权重。当迭代开始时,混合金豺优化算法以全局搜索最优为主,其权重因子取值较大;随着迭代次数的增加,其权重因子取值逐渐减小,局部搜索能力逐渐上升。

局部学习因子a1(t)和全局学习因子a2(t)分别表示个体经验与群体中其他粒子经验对整个粒子群运动模式的影响。当a1(t)取值较大时,个体对群体有较大的影响,导致算法收敛变慢;反之,当a2(t)取值较大时,群体会迅速丧失多样性,导致算法陷入局部最优。因此,需对学习因子进行改进。更为灵活的学习因子表达式为:

(13)

式中:a1e和a2e分别为局部学习因子和全局学习因子的终值;a1b和a2b分别为局部学习因子和全局学习因子的初值。

改进粒子群的HGJO算法的位置更新公式为:

(14)

式中,γ取值为0.4。

改进粒子群的HGJO算法流程如图2所示。该算法流程包括8个步骤。

图2 改进粒子群的HGJO算法流程

Step1:生成栅格地图并初始化位置坐标,设置起点和终点;设置初始种群数量N、最大迭代次数T、维数d和初始速度等参数。

Step2:种群初始化,并在之后计算种群中各金豺的适应度。

Step3:按照适应度从大到小排序,选取最优的金豺作为雄豺,次优的金豺作为雌豺;与之对应的位置信息分别为YM(t)和YFM(t)。

Step4:根据式(3)和式(7)计算猎物逃跑过程的能量E和莱维飞行函数。

Step5:按照式(12)和(13)计算自适应动态权重因子w(t)和学习因子a1(t)、a2(t)。

Step6:根据式(11)计算下一次迭代的速度Vi(t+1)。

Step7:由式(14)来更新种群的位置,并重新计算其适应度。

Step8:判断当前迭代次数是否达到最大迭代次数,若达到则输出最优解,反之循环Step2-Step7。

4 移动机器人路径规划的仿真实验

为验证所提出算法的有效性,本文将其应用在了移动机器人的路径规划仿真实验中。使用的仿真软件为Matlab 2021b,计算机配置为Intel(R)Xeon(R)CPU E3-1225 V2@3.20 GHz,内存为8.00 GB。实验中,通过构建30×30的栅格地图来模拟大范围随机分布障碍物的情况。针对HGJO算法、GJO算法和PSO算法分别进行了30次独立实验。这3种算法的种群数量N=50个,最大迭代次数T=500。3种算法的详细参数如表1所示。

表1 3种算法的详细参数

针对机器人路径规划的3种算法进行了仿真实验。其结果如表2所示。图3所示为3种算法针对30×30栅格地图的规划路径。图4所示为3种算法的仿真收敛曲线。

表2 针对机器人路径规划的3种算法的仿真实验结果

图3 3种算法针对30×30栅格地图的规划路径

图4 3种算法的仿真收敛曲线

从表2和图3可知:HGJO算法相比GJO算法在平均路径长度上缩短了1.920%,这是因为HGJO算法比GJO算法最长路径的长度小,能够获得较为优秀的平均路径长度;与PSO算法相比,HGJO算法更为稳定,在最长路径的长度上没有发生过大的情况;从运行时间上来说,HGJO算法所需运行时间最少,这从一个侧面说明所提出算法具有一定的竞争能力;从标准差来看,HGJO算法的标准差较小,这表明HGJO算法具有较好的稳定性。

从图4可以看出:HGJO算法能够多次跳出局部最优陷阱,比GJO算法有更强的全局搜索能力;HGJO算法能收敛到全局最优值,且具有较高的收敛精度。

5 结语

针对金豺优化算法在移动机器人路径规划应用过程存在的迭代效率低以及会陷入局部最优等问题,本文提出一种改进粒子群的混合金豺优化算法。利用自适应动态权重因子和改进的学习因子,对粒子群算法进行改进并将其引入GJO算法的位置更新中,能够改善算法跳出局部最优的性能。对移动机器人路径规划的仿真实验证明:本文提出的算法在运行时间上和收敛结果上都优于GJO算法;在平均路径长度方面,本文提出的HGJO算法比GJO算法缩短了1.920%。仿真实验结果表明,HGJO算法是可靠和实用的。