基于离子运动-人工蜂群算法的移动机器人路径规划

魏 博，杨 茸，舒思豪，万 勇，苗建国

（1.重庆邮电大学先进制造工程学院，重庆 400064；2.四川大学空天科学与工程学院，成都 610065）

（*通信作者电子邮箱jianguomiao1992@163.com）

0 引言

路径规划是轮式移动机器人导航的核心技术之一，是指在具有障碍物环境下给定机器人起始点与目标点后，按照特定的评价标准为机器人提供一条安全、高效的运动路径，其评价标准通常有：最短行程、最短时间、最少能量等［1］，而传统的路径规划方法有人工势场法、图搜索法、栅格解耦法等［2-3］。近些年国内外学者对路径规划方法做了大量的研究，提出了众多优秀的群智能算法：如粒子群优化（Partical Swarm Optimization，PSO）算法、蚁群优化（Ant Colony Optimization，ACO）算法、烟花-蚁群融合算法（Fireworks-Ant Colony Algorithm，FA-ACA）等［4-7］，这些方法极大地提高了路径规划性能，但同时也有一定的局限性，比如易陷入局部最优、运算时间长、求解复杂等。

人工蜂群（Artificial Bee Colony，ABC）算法是Karaboga［8］受蜜蜂觅食启发提出的群体智能进化算法，该算法模拟了蜜蜂采蜜相互协作转换来指引搜索。标准的ABC 算法具有收敛速度快、寻优能力强、实现简单等优点，但同时也存在后期收敛速度过快导致局部最优、平衡能力差、精度相对较低等缺点。为了加快算法收敛，文献［9］中在ABC 算法初始化阶段引入了随机因子，并应用于多机器人路径规划；文献［10］中在机器人路径规划中应用了一种改进的ABC 算法，该改进算法在引领蜂搜索阶段引入了一组随机向量并添加了当前最优值，再进一步利用Bezier 曲线把路径规划问题转化成求极值点问题；文献［11］中对ABC 算法的侦察蜂搜索阶段进行改进，应用反向学习策略解决了种群多样性差和收敛速度慢等问题；文献［12］中将混沌优化方法引入ABC 算法，不仅缩小了算法的搜索空间，还提高了算法收敛速度和精度；文献［13］通过与PSO 算法结合来改进ABC 算法，在一定程度上平衡了ABC算法的开发能力和探索能力，避免了局部最优。

针对算法收敛速度慢和易陷入局部最优等问题，本文提出了一种基于离子运动的人工蜂群（Ion Motion-Artificial Bee Colony，IM-ABC）算法，为避免传统的ABC 算法平衡能力差、易陷入局部最优等缺点，该算法在搜索阶段的前后期采用不同策略。在算法前期提出了离子交叉搜索规则，以提升种群开发能力；后期采用反轮盘赌来扩大种群多样性，避免陷入局部最优。全局更新阶段则提出了自适应花香浓度规则，改善了抽样方式，引导种群更新的方向。与其他群智能算法相比，该算法在路径规划中能更有效地平衡算法的开发和探索能力，在能避免局部最优的前提下，极大地提升了算法的收敛速度与精度。

1 标准ABC算法

ABC 算法是一种新兴的群体启发智能进化算法，由于算法在寻优过程中设置参数较少、收敛速度快，在一定概率上能跳出局部最优获得较理想的全局最优解，因而受到了各国学者的重视［14］。

ABC 算法是模拟蜜蜂采蜜过程所提出的，其中蜂群主要分为三类：领蜂、跟随蜂和侦察蜂［15］。三种蜜蜂在采蜜过程中进行协作和信息共享，跟随蜂得到引领蜂信息后进行评价，根据优劣选择合适的花源进行采蜜；侦察蜂在蜜源枯竭时更新较差蜜源，每一个蜜源代表路径规划的一条可行解。ABC 算法寻优步骤如下：

1）初始化阶段。首先设定蜂群数量SUM、最大迭代次数N和控制参数Limit，在S维空间随机生成M个初始位置Xi=(xi1，xi2，…，xiS)，Xi按式（1）进行生成：

其中：Wi，j和Ui，j分别为S维空间取值的上下界，i=1，2，…，M，j=1，2，…，S；M代表解的个数，一般取值为SUM/2。

2）搜索阶段。种群中适应度值较小的一半为引领蜂，另一半为跟随蜂，跟随蜂随机选择个体q1∈(1，2，…，M/2)逐维进行搜索产生新个体V，如式（3）。

式中：φ为[1，-1]内的随机数。

跟随蜂按照轮盘赌在引领蜂群中选择概率pi较大的个体，然后在［0，1］内产生一个随机数，如果pi大于产生的随机数，则按照式（4）选择位置J：

式（4）中fit为蜜源适应度值，按式（5）进行更新。引领蜂和跟随蜂产生新解后按照式（6）进行贪婪选择并保留新解。

3）全局更新阶段。经过引领蜂和跟随蜂种群的搜索完成后，为了避免种群多样性丧失，若i位置连续Limit代不变，那么就根据式（1）随机生成一个替代解，接下来返回雇佣蜂和跟随蜂搜索过程，重复地循环直至找到最优解。

2 IM-ABC算法

2.1 算法原理

在标准的ABC 算法中，引领蜂搜索实际可以理解成自身向其他个体学习的过程，在算法中引领蜂的更新是在自身位置周围随机选择个体进行交叉更新，这样选择的个体优秀和较差的几率对等。虽然这种方式在一定程度上扩大了种群多样性，但大大地降低了算法的收敛速度，也就是说这种方式探索能力强但开发能力差［16］。为了平衡算法的开发能力和探索能力，可以根据周围个体适应度值的优劣调整进化方向，这样有利于提高种群总体的进化速度和效果。

考虑到跟随蜂依据轮盘赌选择策略来更新种群是一种相对贪婪的方式，在算法的整个过程中会快速地降低种群多样性，容易导致过早收敛和局部最优，为了在保证收敛速度的前提下，避免局部最优，需要引入一个自适应因子进行调节。为了使算法得到更好的效果，把算法搜索阶段分为前后两期。

2.1.1 离子概念模型

在自然界中，具有相似电荷的离子往往会排斥，而具有相反电荷的离子相互吸引。吸引力和排斥力与阴离子和阳离子之间的关系如图1 所示，实线箭头代表引力，虚线箭头代表离子在吸引力/排斥力作用下阴离子向最好的阳离子靠拢，而阳离子向最好的阴离子移动。

图1 阴阳离子运动模型图Fig.1 Anion and cation motion model

2.1.2 离子交叉搜索规则

为了平衡算法的开发和探索能力，把算法搜索阶段分为前后两期，并引入离子交叉搜索规则：

1）搜索阶段前期，在ABC 算法中引入离子运动交叉搜索方程，假设引领蜂为阳离子，跟随蜂为阴离子，蜜蜂之间传递的信息比作离子间引力，则引领蜂和跟随蜂交叉更新如式（7）、（8）所示。引领蜂和跟随蜂选择适应度值最优的个体交叉学习，并引入引力因子AFi，j、BFi，j自适应调节增大搜索步长，这种方法可以自适应提高算法进化速度、促进种群快速收敛。

式中：Ai，j、Bi，j分别是引领蜂和跟随蜂产生的新生个体；Abestj、Bbestj代表种群中最优引领蜂与跟随蜂。

2）搜索阶段后期，种群个体大都处于较优状态，优秀个体的进化信息不再起主导作用，这时需要平衡前期的开发能力，增大蜂群的局部探索能力，使蜂群能够在自身邻域附近进行精细化搜索，不需要如前期那样较大的搜索步长，避免因搜索步长较大导致局部最优，降低寻找到全局最优解的概率。

在后期中引领蜂按照式（3）进行搜索，产生的新解按照式（6）进行选择替换；跟随蜂则引入反向轮盘赌选择机制如式（11），适应度值倒数较大的个体被选中的可能性变大，能有效地跳出局部最优。

2.1.3 自适应花香浓度规则

在全局更新阶段，由于侦察蜂位置更新方式随机性较大，属于放回型采样，会对较差的蜜源做多次无用更新计算，和实际意义不贴切，可以加入自适应花香浓度信息策略，根据加入自适应因子的花香浓度进行更新。自适应因子可以调节每次循环中的花香浓度，当侦察蜂发现某个方向蜜源较差时，就不会第二次更新该方向，侦察蜂根据式（12）计算位置更新概率。

式中：KTi为每维度的花香浓度，∂(t)是自适应参数，Max_Cycle是算法的最大迭代次数。初始时每个维度花香浓度都相等，当排除后的维度花香浓度KTi设为零，这样就避免了同一个方向二次更新，同时自适应地为侦察蜂更新提供方向性，一定程度上加速了算法收敛，且不会导致局部最优。

2.2 算法流程

IM-ABC算法流程如图2所示。具体步骤如下：

步骤1 设置初始化相关参数：种群数量SUM，最大迭代次数N，控制参数Limit。

步骤2 在可行空间内产生初始种群，并设置迭代次数iter=0。

步骤3 利用离子运动规律产生新解，引领蜂和跟随蜂按式（7）、（8）产生新解Ai，j、Bi，j。

步骤4 对产生的新解Ai，j、Bi，j按式（6）保留较优的解。

步骤5 跳转回步骤2 和步骤3 进行反复迭代，若迭代次数iter＞N/2，则跳转到步骤6。

步骤6 引领蜂按式（3）随机产生新解vi，j，并按式（6）保留较优的解。

步骤7 跟随蜂按照式（11）的反轮盘赌的机制选择个体，并按式（3）产生新个体vi，j，并按式（6）保留较优的解。

步骤8 跳转回步骤2 和步骤3 进行反复迭代，若位置i连续Limit代未更新，则放弃该位置，侦察蜂根据式（12）的花香因子选择个体，并更新种群。

步骤9 判断是否达到最大迭代次数或目标精度，若满足，则输出最优解，否则跳转至步骤5。

图2 IM-ABC算法流程Fig.2 Flowchart of IM-ABC algorithm

3 性能测试及路径规划仿真实验

3.1 算法性能测试

为了验证IM-ABC 算法的有效性，本文选择研究人员普遍使用的四个标准测试函数：Sphere、Rosenbrock、Rastrigin 和Griwank，对传统的ABC算法和目前性能较为优秀的快速搜索人工蜂群（Fast Search Artificial Bee Colony，FSABC）算法、局部路径人工蜂群算法（Local Route Artificial Bee Colony，LRABC）算法进行测试比较。FSABC 算法采用局部搜索算子在求解精度上有显著提升［17］，LRABC 算法在收敛速度上有较大提升［18］，但两个算法在开发能力上仍具有一定的缺陷。

在实验中对四种算法的参数进行设置，算法中总群数量SUM设为100，引领蜂和跟随蜂的数量分别设为50，Limit值设置为750，测试函数的维度均为30，且最大迭代次数N设置为2 000，通过对实验数据的最优值、最差值、平均值和方差来衡量算法性能。测试函数信息见表1，测试结果数据见表2，实验结果显示本文所提的IM-ABC 算法的精度要优于传统的ABC算法和其余两个ABC改进算法，具有良好的搜索能力。

表1 标准测试函数Tab.1 Benchmark functions

表2 算法仿真结果比较Tab.2 Comparison of algorithm simulation results

3.2 路径规划实验

本文算法主要用于求解机器人路径规划问题，为了验证算法的实际应用效果，通过建立栅格模型来模拟现实中复杂多变的仓储环境。如图3 所示，以20 m×20 m 的栅格环境为例，在栅格地图中，工作环境被划分成两种栅格，黑色栅格表示障碍物，白色栅格表示无障碍物，在系统仿真程序中分别用1和0表示，栅格图的尺寸和大小可根据实际环境进行调整。

图3 栅格模型工作环境Fig.3 Grid model working environment

实验利用Matlab 2016a 软件进行仿真，通过测试ABC 算法、FSABC 算法、LRABC、IM-ABC 算法在栅格地图上寻找由起始点到目标点中心连线的最短路径来模拟实际环境中的最短路径。在20 m×20 m 大小的栅格地图环境中，将蜂群规模SUM设置为100，最大迭代次数N为200，Limit值设置为10。实验结果如图4、5和表3所示。

表3 路径规划仿真实验结果对比Tab.3 Comparison of path planning simulation experimental results

由图4及表3可知，IM-ABC算法收敛速度较快，相较传统ABC算法而言，改进后的算法寻优性能上提升了12.6%，迭代次数减少了58.3%，主要原因是传统的ABC 算法在搜索阶段盲目性较大，导致整个搜索过程步长较短，收敛速度慢，同时在全局更新阶段由于随机更新，进一步降低了收敛速度；而改进算法在避免局部最优的前提下，提出离子搜索方式和花香浓度策略，提高了算法的收敛速度。因此本文所提算法具有更短最优路径和更快的收敛速度。

图4 四种算法搜索的最优路径Fig.4 Optimal paths searched by four algorithms

图5 四种算法的收敛图Fig.5 Convergence graphs of four algorithms

4 结语

本文提出了一种基于离子运动的人工蜂群（IM-ABC）算法，主要用于解决仓储环境下路径规划问题。针对传统ABC算法存在的不足与缺陷，引入自然界离子间相互作用力来改善蜂群算法搜索阶段，并把搜索阶段分成前、后期来平衡算法的开发和探索能力，在保证不陷入局部最优的前提下，加大搜索步长，并在全局更新阶段加入自适应性花香浓度，根据花香浓度指引变异自适应性更新，提升算法的效率。该算法在不同的标准测试函数下验证极值求解能力并表现出较大的优势，通过求解机器人路径规划问题验证了算法的实际应用效果。下一步的工作是探究算法参数对算法的影响，更进一步研究多机器人蜂群算法模型及性能。