基于改进野马优化算法的AGV路径规划*

李一铭，王跟成

(西藏民族大学信息工程学院，咸阳 712082)

0 引言

自动导引运输车(automated guided vehicle，AGV)路径规划问题是搜索一条从起始位置到目标位置的最优路径问题。传统的AGV路径规划策略有A*算法[1]、人工视场算法[2]和dijkstra算法[3]等，随着智能仿生算法的发展和应用，国内外学者将蚁群算法(ACO)[4]、麻雀搜索算法(SSA)[5]等应用于AGV路径规划。郭鹏等[6]提出一种并行搜索的遗传算法，融合遗传算法和双向A*算法的基础上，使用自适应函数改进遗传算法的收敛性能，但算法的复杂度较高且运行速度较慢；屈新怀等[7]提出一种靠近目标粒子群算法，通过障碍物顶点划分坐标系，引入Metropolis准则，使算法具备跳出局部最优解的能力，通过自适应引力系数，使算法在靠近目标时搜索速度加快，进一步加快算法收敛速度；刘畅等[8]提出一种改进自适应遗传算法，通过引入逆转算子和插入算子控制算法的进化方向，算法的全局搜索能力有一定的提升，但算法后期收敛速度较慢。

本文提出一种基于改进野马优化算法的AGV路径规划方法。首先在二维空间上构建解空间，然后利用改进野马优化算法进行路径搜索。通过引入非线性自适应因子和黄金正弦分割系数提高算法路径规划能力，结合偏移进化策略和发现者位置更新方式对算法提高了算法放牧行为位置更新的多样性。由于优化算法生成路径拐点过多，使用3次B样条曲线平滑路径的同时减少路径长度。通过仿真实验对比不同的路径规划策略，结果表明本文算法提高了AGV路径规划的平滑性和性能，能够减少5.84%的AGV路径规划长度，具有较高的算法收敛精度和运行效率。

1 环境建模

出于模拟需要，通过栅格法[2]在二维平面上构建解空间，搭建20×20栅格地图环境，将障碍物定义为黑色不可行区域，白色栅格为可行区域作为路径的生成节点。搜索最优路径规划问题转化为在栅格地图的可视化基础上，寻找一条从起始位置出发到目标位置的最短路径问题。栅格二维空间环境模型如图1所示。

图1 栅格地图环境

2 野马优化算法

野马优化算法[9]模拟野马种群的生活行为和繁衍行为。该算法中野马群通常以一匹领导者、几匹母马和小马驹的群居活动方式。野马群的位置状态分为位于领土位置中和位于非领土位置。通常领导者会出现在靠近母马的地方以进行交流。为了防止近亲交配，小马驹在青春期前离开他们的父母群体，其中公马会加入到单一种群逐渐成熟到可以完成交配。野马种群中最重要的是领导者，其决定种群在自由放养的非领地区域的移动方向和速度。

小马驹通常大部分时间都在吃草，认为领导者的位置为放牧区的中心，种群成员在以领导者为圆心进行中心搜索，其表达式为：

(1)

式中，Stallion为领导者的位置；R为取值[-2,2]之间的随机数，主要用来控制个体与领导者的角度。自适应机制Z的计算表达式为：

P=R1

(2)

式中，P是由0和1组成的向量；R1和R3为[0,1]空间内均匀分布的随机向量；R2为取值[0,1]之间的随机数。满足条件(P==0)的随机向量R1返回IDX索引；TDR为自适应因子，从1线性递减为0，表达式如下：

TDR=1-t×(1/Tmax)

(3)

交配行为由分配入临时组且来自不同族群的青春期小马驹交配产生，假设离开i组的小马驹和离开j组的小马驹分别加入了一个临时组，这两只小马驹是雄性和雌性，由于这两只小马驹没有家庭关系，因此进入青春期后进行交配。表达式为：

(4)

式中，XP表示种群k中个体p离群后再次进入种群k的个体位置，其父母位置来自不同的种群。

领导者带领种群前往合适的栖息地，若一个种群对栖息地占主导位置，那么该种群必须离开此地。领导者相对于栖息地的下一位置计算公式为：

(5)

式中，WH为最优个体位置。野马算法种群初始化为随机初始化，在种群初始化阶段若其中一名组员的适应度值优于领导者，则两者根据式(6)进行身份互换：

(6)

3 改进策略

3.1 非线性自适应因子

为了更好平衡算法全局搜索和局部挖掘能力，防止算法在迭代中后期陷入搜索停滞的状态。大量文献记载了非线性自适应因子较线性自适应因子的优势，非线性适应因子可以保证算法在迭代前期下降速度加快，在算法迭代后期下降速度减缓，保证了算法全局搜索能力的同时确保了算法后期跳出搜索停滞状态的能力。改进算法线性迭代自适应因子为非线性，表达式为：

(7)

式中，t为当前迭代次数；T为最大迭代次数。

3.2 偏移进化策略

在标准野马优化算法中，小马驹的位置主要取决于其来自不同种群的父母位置。此阶段过程主要针对种群个体中适应度最差的个体进行操作，但小马驹的生成位置较为固定缺乏多样性，容易陷入搜索停滞状态，不利于种群进行全局搜索。本文在小马驹繁殖过程中加入随机偏移策略，通过随机位置对小马驹繁殖过程进行扰动，提高算法多样性。其随机点生成位置表达式为：

Q=rand(1,d)×(ub-lb)+lb

(8)

式中，ub、lb为空间上下界；rand为[0,1]之间的随机数，随机运动使得算法能够对搜索空间进行充分的探索，因此如果算法陷入局部最优，这种行为将帮助算法及时跳出。个体的新位置更新方式为：

(9)

式中，R4为随机数，当rand>0.5时，小马驹通过标准算法的繁殖过程产生，当rand≤0.5时，算法通过随机偏移策略产生小马驹。

受麻雀优化算法发现者位置更新的启发，在野马优化算法位置更新方式中加入发现者位置更新方式，提高算法放牧行为位置更新多样性，其位置更新表达式为：

(10)

式中，q为正态分布的随机数；L为长度为d的全1矩阵；R为预警值；ST为安全值，若R

3.3 黄金正弦分割因子

黄金正弦算法(Golden-SA)[10]是一种元启发式算法，该算法受到黄金分割搜索的启发可以遍历正弦函数上的所有值即遍历整个单位圆上的所有的点，通过引入黄金分割率，使算法在迭代过程中不断收缩搜索范围并且不断逼近最优解，既保证了算法的寻优速度又确保了算法的收敛精度。Golden-SA算法与WHO算法的初始化方式相同，通过随机在搜索空间的边界内生成随机种群个体，表达式为：

(11)

式中，Xi为个体i的位置；ub为上界；lb为下界；c为取值空间[0,1]的随机数。Golden-SA算法的核心是其参数c1、c2，表示黄金正弦分割系数，使搜索空间缩小并且在算法迭代过程中起到指引个体逐渐向全局最优位置方向移动，表达式为：

c1=a(1-h)+bh

(12)

c2=ah+b(1-h)

(13)

式中，a=π；b=-π；h为黄金分割比率，通常取h=(5-1)/2=0.618 33。本文将黄金正弦分割系数引入野马优化算法的种群位置更新和领导者位置更新表达式中，引入后的位置更新表达式为：

(14)

(15)

3.4 B样条曲线路径平滑策略

改进野马优化算法的部分路径中还存在尖锐拐点。本文引入3次均匀B样条曲线来平滑处理算法生成的路径，在减少路径尖锐拐点的同时减少路径长度。当k=3时的B样条曲线数学表达式为：

(16)

(17)

(18)

(19)

3次均匀B样条曲线的各节点矢量间插值为常数，第i段3次均匀B样条曲线的数学表达式为：

(20)

由式(20)可得3次均匀B样条曲线的基函数数学表达式为：

(21)

将式(20)带入式(21)中，用矩阵形式表达为：

(22)

3.5 算法流程描述

步骤1：初始化野马算法参数。种群规模N、最大迭代次数T、领导者比例PS、交配概率PC等；

步骤2：计算野马种群个体的适应度，创建野马种群和领导者；

步骤3：根据式(9)和式(14)对野马种群进行位置更新；

步骤4：根据式(15)对领导者位置进行更新；

步骤5：更新野马种群适应度值，若野马种群中存在适应度优于领导者的适应度个体，则按照式(6)更换领导者；

步骤6：判断当前是否达到最大迭代次数，若是，终止循环，否则跳转步骤2；

步骤7：B样条曲线对路径进行平滑处理后输出最优路径。

算法流程图如图2所示。

图2 算法流程图

4 仿真验证

为了验证算法对AGV路径规划的有效性，本实验选取20×20的二维栅格图环境，AGV所处的起始位置为(0,0)，终点位置为(20,20)。实验设置种群规模为50，最大迭代次数为200次。分别采用ACO算法、标准WHO算法、改进野马优化算法(WHO-BC)进行对比试验。其中ACO算法的信息素重要程度因子a=1、b=5、q=2000、信息素的挥发因子p=0.7；WHO算法的设置为：PS=0.2、PC=0.13。算法对比结果如表1所示，生成的最优路径对比结果如图3所示。

表1 3种算法数据结果

(a) ACO算法 (b) WHO算法

(c) WHO-BC算法图3 路径搜索结果对比图

从图3和表1中可以看出，WHO算法的最优路径长度为30.23，经过改进后WHO-BC算法的路径长度为28.56，相较于标准WHO算法生成的路径减少了5.84%，表明了本文所提出的改进方法对于路径长度缩短的有效性和可行性，能够有效地平衡算法的全局搜索能力和局部勘探能力，加快算法收敛速度和精度。ACO算法生成的路径长度31.86，存在过多拐点和无效路径，相较于标准WHO和WHO-BC算法路径长度全局搜索能力较差；ACO和WHO算法的迭代运行时间分别为6.03 s和3.45 s，迭代次数为72和32次，而本文改进的WHO-BC算法的运行时间为2.57 s，迭代次数为27次，表明本文改进方法通过引入偏移进化策略增强了算法种群的多样性，黄金正选分割因子在迭代过程总缩小搜索空间，引领算法个体逐渐向全局最优位置方向移动，进一步表明本文算法改进的有效性和可行性。从整体上来看路径寻优能力上WHO-BC算法>标准WHO算法>ACO算法。

通过图4的算法迭代对比试验可以看出，本文改进的WHO-BC算法位置总体靠下，相较于标准WHO算法具有跳出局部最优解的能力。综上所述，表明本文算法性能优于对比算法，总体能够减少5.84%的AGV路径规划长度。

图4 算法迭代对比图

5 结论

本文提出一种基于改进野马优化算法的AGV路径规划方法。在标准野马优化算法的基础上，通过引入非线性自适应因子、偏移进化策略、黄金正弦分割因子和发现者位置更新方式改进算法的收敛速度和寻优精度，并且通过B样条曲线对算法生成的路径进行平滑处理，进一步提高AGV路径规划的性能。经过仿真对比试验可知，改进野马优化算法相较于ACO算法和标准WHO算法生成的路径更加平滑并且路径长度更短；通过迭代曲线和运行时间对比试验，表明改进野马优化算法具有较高的效率和较好的收敛速度。