自适应萤火虫算法改进蚁群算法的移动机器人路径规划

杜力，徐光辉，汪繁荣

（1.湖北工业大学 电气与电子工程学院，湖北 武汉 430068；2.湖北工业大学 太阳能高效利用与储能系统运行控制湖北省重点实验室，湖北 武汉 430068）

0 引言

移动机器人路径规划问题一直是机器人研究领域的热点。简单而言，移动机器人路径规划是指移动机器人在存在障碍物的环境中运动时，无人为干预条件下，寻求一条从起始点到目标点的无碰撞路径［1］。根据机器人对作业环境的感知程度，路径规划问题大体上可以分为全局路径规划和局部路径规划两类［2］。其中，全局路径规划是指机器人在对作业环境全部已知情况下，利用算法得到一条优化的全局最优或次优路径，常用方法包括自由空间法［3］，栅格法［4］，A*算法（Astar algorithm）［5］等；局部路径规划是指机器人通过自身携带的传感器实时获取自身运动环境信息，然后选择一条从当前节点到某一子节点的最优子路径，通常采取的方法有人工势场法［6］，滚动窗口法［7］，Dijkstra算法［8］等。上述这些传统的路径规划方法虽然简单且易于实现，但适用范围较小，实时性较差。

近年来，随着群智能算法的发展和应用，移动机器人路径规划问题有了更多的解决方案［9-10］，如遗传算法（genetic algorithm，GA）［11］，蚁群算法（ant colony optimization，ACO）［12-13］，粒子群算法（particle swarm optimization，PSO）［14］等，都已在求解移动机器人路径规划问题中取得了比较理想的效果。其中，ACO因其鲁棒性强、易于实现和正反馈机制等优点得到了广泛应用。陈劲峰等［15］分析了父节点和子节点间的位置关系，缩小了蚁群的搜索范围，加快了蚁群的收敛速度；C.C.Hsu等［16］通过不断调整ACO参数，建立局部和反向信息素更新机制，提高了ACO路径规划效果；LIU JH等［17］通过自适应调整启发式信息和加入局部最优引导机制，提高了ACO的计算效率和在二维环境路径规划中的收敛速度。虽然上述改进的ACO在求解路径规划问题过程中都表现出了良好的性能，但是其求解质量与参数的选择密切相关，而参数的选择往往过于依赖个人经验，这种办法主观性强，智能性差，大大限制其优越性。为了更好地发挥ACO的优越性能，文献［13，18-19］将ACO与PSO融合，把ACO的关键参数赋给PSO的每个粒子，经过多次迭代自适应地寻找到ACO的最优参数组合。虽然PSO优化ACO的参数有着很好的效果，但PSO参数较多且设置较复杂。2008年，剑桥大学教授Yang提出了一种启发式萤火虫算法（firefly algorithm，FA）［20］，该算法通过对自然界中萤火虫会被比自身亮度高的萤火虫吸引而向其运动的行为进行模拟，建立数学模型解决优化问题。FA具有收敛速度快、操作方便、实现容易、参数选择相对简单等特点。

本文首先分析ACO和FA的基本原理，提出一种萤火虫算法改进蚁群算法的混合智能算法（firefly algorithm improved ant colony algorithm，FAACA），其核心思想是利用FA对ACO的核心参数进行优化，避免传统人工经验选取参数对ACO性能的影响。其次，为减少两种算法混合后的时间开销，采取精英策略和承接式结合的信息素更新方式提高ACO全局搜索速度，并对FA的步长因子进行自适应设计，防止萤火虫在最优值附近出现震荡，提高整个混合算法的求解精度，从而得到一种自适应萤火虫算法改进蚁群算法的混合智能算法（adaptive firefly algorithm improved ant colony algorithm，AFA-ACA）。最后，在不同栅格环境下进行路径规划仿真实验，仿真结果表明所提算法比传统的ACO规划得到的路径更短，得到最短路径所需迭代次数更少，运行更加平稳。

1 算法数学模型

1.1 ACO的数学模型

ACO是将自然界中蚁群觅食行为抽象化后得 到 的 一 种 启 发 式 搜 索 算 法［13，19，21］。蚂 蚁k（k=1，2，…，m）在t时刻运动方向的选择由各个路径上的信息素浓度决定。在t时刻蚂蚁从位置i选择下一个位置j的概率为

式中：τij（t）为t时刻位置i与位置j之间的路径上的信息素；ηij（t）为启发式函数，常取ηij（t）=1/dij，dij为位置i与位置j之间的欧式距离；α为信息启发式因子；β为期望启发式因子；下一个可移动栅格集合用Tallowed，k表示。每只蚂蚁在完成一次遍历后，对每条路径上所留的信息素按照式（2）处理：

式中：ρ为信息素挥发系数（0＜ρ＜1）；τij为位置i与位置j之间路径上的信息素量；为第k只蚂蚁在本次循环中残留在位置i与位置j之间的信息量。且有，

式中：Q为信息素强度；Lk为路径总长度。

1.2 ACO参数分析

ACO路径规划中，初始化参数的选择对算法性能有着重要影响［21］。

（1）信息启发式因子α主要影响蚂蚁选择路径的随机性，该值越大时，表明启发式信息在蚁群搜索过程中占主导作用，蚁群搜索路径的随机性越低，算法容易陷入局部最优；该值越小时，搜索路径的随机性就会越高，蚁群收敛速度变慢。

（2）期望启发式因子β主要决定环境因素对蚂蚁路径选择概率的影响，该值过大时，环境因素占主导作用，蚁群更趋向于搜索较近的下一节点，随机性降低，算法容易陷入局部最优；该值过小时，则会导致随机性变大，路径寻优变得更加困难，蚁群收敛速度变慢。

（3）信息素挥发系数ρ主要影响算法的收敛速度和全局搜索能力，该值越大，路径上信息素浓度下降越快，算法全局搜索能力降低，收敛速度变快；该值越小，路径上信息素浓度下降越慢，算法全局搜索能力提高，收敛速度变慢。

1.3 FA的数学模型

FA与PSO原理类似，都是基于群体解的随机搜索算法［22］。群体中每个个体都代表一个候选解，用亮度代表解的适应性，适应性越好的个体亮度越高。群体中的萤火虫没有性别之分，若萤火虫在视野范围内发现亮度高的萤火虫即会向其移动，最终所有萤火虫都聚集于亮度最高的萤火虫，即最优解。

假设Xi=（xi1，xi2，…，xiD）是群体第i只萤火虫（解），其中i=1，2，…，N，N和D分别为群体大小和问题维数。对于任意两只萤火虫Xi和Xj（i≠j），它们之间的吸引可表示为

式中：β0为r=0时的吸引力；γ为光吸收系数；rij为Xi和Xj之间距离，定义为

对于Xi和Xj（i≠j），较差的萤火虫将向较好的萤火虫移动。假设Xi优于Xj，则Xj向Xi移动，其移动方式为

式中：d=1，2，…，D；ζ∈ 0，[ ]1为步长因子；ε为［-0.5，0.5］区内的随机数；t为迭代次数。

2 算法混合

ACO具有鲁棒性强、易于与其他启发式算法结合等优点，但是其求解性能过于依赖参数的选择，而FA在解决许多优化问题时表现出了搜索能力强、收敛速度快等良好性能。本文在ACO的基础上引入FA对ACO核心参数进行优化，设计一种萤火虫算法改进蚁群算法的混合智能算法（FA-ACA）。

FA-ACO核心思想是采用FA对ACO的关键参数进行优化，利用萤火虫算法中每只萤火虫的初始位置代表ACO的一组重要参数，通过萤火虫算法自适应地选取一组相对最佳参数，从而改变传统的经验选参方式，具体运行步骤如下。

步骤一初始化萤火虫算法各个参数：最大吸引力β0，步长因子ζ，最大迭代次数Tmax等。

步骤二设置每只萤火虫的位置对应一组蚁群算法的重要参数α，β，ρ，萤火虫在解空间中的位置即为其参数值。

步骤三利用萤火虫位置信息对应的参数运行蚁群算法，得到当前该萤火虫位置信息对应的适应度函数值。

步骤四利用步骤三中适应度函数值，更新对应萤火虫的亮度信息，萤火虫向亮度更高的个体聚集，并更新位置。

步骤五判断是否达到终止条件（萤火虫的亮度和位置不再更新或达到了最大迭代次数），若满足条件，则输出当前萤火虫对应的一组最优参数；否则，利用位置更新后萤火虫对应的参数信息返回继续执行步骤三。

步骤六利用步骤五得到的最优参数组合，代入蚁群算法并运行。

步骤七输出最优解。

3 自适应萤火虫算法改进的蚁群算法

由FA-ACA的执行步骤可知，萤火虫位置每改变一次，ACO都将被完整地调用一次，所以该算法虽求解质量较高，但时间成本极大。且传统的FA步长固定，搜索过程会出现个体移动步长大于个体与最优值之间距离的情况，导致个体在更新位置信息时，在最优值附近出现震荡，从而导致整个混合算法求解效率和求解精度降低。基于此，本文对FA-ACA中ACO的信息素采取精英策略与承接式相结合的更新方式，并对FA的步长因子进行重新设计，从而得到一种自适应萤火虫算法改进蚁群算法的混合算法（AFA-ACA）。

3.1 蚁群算法信息素更新方式

在执行步骤三时，采用精英策略对蚁群的信息素进行更新，即蚁群每进化一代，对最优路径上的信息素进行强化更新，其他情况下信息素不进行更新。参数切换时，采用承接式的信息素更新方式，即每次参数切换，信息素不重新初始化，下一代参数承接上一代参数留下的信息素继续进行迭代更新，避免参数切换时初期信息素的积累过程，极大提高混合算法的收敛速度。信息素更新公式为

式中：τij1（t）为按照全局同步信息素更新方式（即在蚁群算法被调用的过程中，蚁群每进化一代，信息素随之更新，切换参数时，信息素不重新初始化，继续进行更新，更新公式见式（2）～（3））进行信息素更新时，持续到当前代次环境中的信息量；Δτij（t）′为本次循环中，最优蚂蚁在路径［i，j］上释放的信息量，

式中：ω为常数；Gk为最短路径长度。

3.2 萤火虫算法步长因子的自适应设计

在标准的萤火虫算法中，亮度低的萤火虫会被亮度高的萤火虫吸引并向其移动，群体中的个体会逐渐聚集，最后收敛于亮度最高的一点。因此，对群体中任意两个个体Xi和Xj，都有

式中，i，j=1，2，3，…，N。

由式（9）～（10）可以看出，所有的个体（解）都收敛于一点，且收敛后的解不再发生变化。根据式（6）、（9）和（10）可得

由式（11）可以看出，当萤火虫算法收敛时，步长因子ζ趋近于0。

基于以上分析，本文对FA的参数ζ进行自适应设计，更新公式为

式中，Tmax为萤火虫的最大迭代次数，随着迭代次数增加，步长因子逐渐减小至0。

4 仿真实验与结果分析

为了验证本文所提算法的有效性和求解质量，选择两种不同栅格环境下的移动机器人路径规划问题，并利用本文所提算法和传统蚁群算法进行仿真对比实验。实验平台选择MATLAB 2018a，计算机CPU型号为intel i78th，运行内存为8 GB。

4.1 环境建模

利用栅格法建立机器人运动的环境模型［13］。为了减少数据计算量，忽略机器人的大小体积等，将移动机器人作质点化处理。如图1所示，假设每个栅格对应二维空间中的坐标为（xi，yi），以（0.5，9.5）为中心的网格数为1，以（1.5，9.5）为中心的网格数为2，以此类推，每个栅格从左到右，从上到下编号，各栅格坐标与序号的关系为

图1 栅格环境Fig.1 Grid environment

式中：i为栅格号；N为栅格地图的行数和列数。假设每个栅格边长均为1 cm。

4.2 算法的参数设置

萤火虫算法参数取值见表1，设其适应度函数为Fitk（s）=1/Lk（s）。蚁群算法的参数α，β和ρ由萤火虫空间位置给出。文献［21］经过多次仿真实验，得到了ACO各个参数最佳取值范围，以此作为参考，确定ACO参数的搜索范围，具体见表2。

表1 萤火虫算法初始化参数Tab.1 FA initialization parameters

表2 ACO初始化参数值范围Tab.2 ACO initialization parameter value range

4.3 路径规划结果及比较

文献［23］在解决移动机器人路径规划问题时，基于经验选取参数α=1，β=0.7和ρ=0.3。现选取2种不同的栅格环境，运用上述参数运行传统的ACO，并与本文所提算法进行仿真对比实验。两种算法最大迭代次数为100次，蚁群数量为50，每种算法运行20次。

本文选取其中一组实验结果进行对比分析，在栅格环境1和2下，ACO和AFA-ACA规划后的最优路径和路径长度收敛曲线如图2～3所示。

图2 栅格环境1下ACO和AFA-ACA最优路径和收敛曲线Fig.2 Optimal path and convergence curves of ACO and AFA-ACA in grid environment 1

图3 栅格环境2中ACO和AFA-ACA的最优路径和收敛曲线Fig.3 Optimal path and convergence curves of ACO and AFA-ACA in grid environment 2

现将两种不同栅格环境下的AFA-ACA和ACO路径规划结果记录在表3和表4中。

表3 栅格环境1中数据比较Tab.3 Data comparison in grid environment 1

表4 栅格环境2中数据比较Tab.4 Data comparison in grid environment 2

仿真结果表明，两种算法都找到了一条从起点到终点的无碰撞路径，验证了AFA-ACA的可行性。由图2～3可知，随着迭代次数增加，AFAACA路径规划得到的路径长度不断变短，说明其优化能力在不断增强，与ACO相比，AFA-ACA有着更好的智能性和稳定性。栅格环境1下，AFAACA与ACO得到的最短路径长度都为29.21 cm，但ACO的迭代次数为76次，AFA-ACA的迭代次数为18次。栅格环境2下，AFA-ACA与ACO得到的最短路径长度分别为30.97 cm和32.73 cm，前者得到的路径长度更短，且AFAACA的迭代次数为5次，ACO的迭代次数为78次。两种栅格环境下的路径规划仿真结果都表明，与传统ACO相比，本文所提算法在迭代次数和算法的平稳性上都有明显提升，满足移动机器人的路径规划要求。

5 结 语

AFA-ACA能很好解决ACO求解多变的路径规划问题时过于依赖参数的选择等问题。将AFA-ACA用于移动机器人路径规划中，与传统的ACO相比，前者找到最优路径所需迭代次数更少，且算法收敛性和稳定性都有很大提升。同时，本文的研究工作还有许多需要改进的地方，比如如何减少算法复杂度，如何将该算法用于局部路径规划问题中，如何提高该算法的其他性能等。