超强启发异类蚁群算法的机器人导航路径规划

刘 钦

（郑州财税金融职业学院，河南 郑州450048）

1 引言

在物流仓储中，自动导引小车（Automatic Guided Vehicle，AGV）代替人工进行物料运输与分拣成为发展趋势，而AGV运输路径长度、平滑性与小车工作效率紧密相连［1］，因此研究AGV导航路径规划问题对提高小车工作效率具有重要意义。

根据对工作环境的掌握程度，机器人导航路径规划分为全局路径规划和局部路径规划，研究的是静态环境下全局路径规划问题。从研究时间上讲，前期出现的路径规划方法有栅格法［2］、可视图法［3］、人工势场法［4］等，当前研究热点为智能算法应用于路径规划，方法有人工鱼群算法［5］、粒子群算法［6］、遗传算法［7］等。以上方法针对不同环境下路径规划问题具有较好效果，但都存在各自缺陷，比如栅格法和自由空间法环境实行性差，环境改变时需重新建模；人工势场法存在局部极值和目标不可达问题；智能算法普遍问题是算法自身寻优深度与寻优广度之间的矛盾，因此机器人路径规划仍需进行深入研究。

以栅格环境下机器人路径规划为研究课题，提出了开创型蚂蚁主导的超强启发式异类蚁群算法。在传统蚁群算法基础上，提出了由开创型蚂蚁、传统型蚂蚁、守旧型蚂蚁组成的异类蚁群算法；在信息素更新方面，提出了超强启发式信息素更新方法，实现了规划路径短且耗时少的目的。

2 栅格建模与蚁群算法

2.1 栅格环境模型

栅格环境建模法原理简单，易于实现。使用一定大小的栅格将工作区域进行划分，当栅格中存在障碍物时将栅格属性赋值为1，当栅格中不存在障碍物时将栅格属性赋值为0，这样就将抽象的工作环境建模为机器可识别的0-1矩阵［8］。

如图1所示的，真实工作环境，使用栅格法建立的0-1矩阵为：

图1 真实工作环境Fig.1 Real Working Environment

2.2 蚁群算法

蚁群算法是模拟蚁群觅食行为而提出的算法，最初被应用于解决旅行商问题［9］。记蚁群规模为m，t时刻蚂蚁k从城市i向城市j转移的概率为：

蚁群算法在运行过程中，信息素的更新包括两个方面：一是蚂蚁在行走过程中会留下信息素，二是信息素随着时间推移不断挥发，路径上信息素全局更新方法为［10］：

式中：ρ∈(0,1)-信息素挥发因子所有蚂蚁在城市ij间遗留的信息素蚂蚁k在城市ij间遗留的信息素；Q-常数，代表信息素总量；Lk-蚂蚁k的路径长度。

3 超强启发式异类蚁群算法

3.1 异类蚁群

由基本蚁群算法可知，所有蚂蚁均按照式（1）选择下一节点，即蚁群中所有蚂蚁为同一类蚂蚁，但是按照达尔文生物进化理论，种群中个体越多样则种群的生存、进化和寻优能力越强，基于这一思想，提出了由异类蚂蚁组成的异类蚁群算法，共由以下三类蚂蚁组成。

（1）开创型蚂蚁。此类蚂蚁进行路径规划时具有开创性，完全不参考其他蚂蚁在路径上遗留的信息素，只根据下一节点与目标点距离进行概率选择，即：

（2）守旧型蚂蚁。此类蚂蚁路径规划时比较保守，遵照“前人”传统进行路径规划，即完全按照信息素的引导进行节点选择，方法为：

（3）传统型蚂蚁。此类蚂蚁按照传统的节点选择方式进行路径规划，节点转移概率如式（5）所示。

蚁群中的三类蚂蚁，守旧型蚂蚁完全按照“前人”传统进行路径规划，不具有创新性，路径的创新和路径多样性主要依靠开创型蚂蚁和传统型蚂蚁，因此异类蚁群算法寻优性能与各类蚂蚁数量比例相关性极大，后文将对各类蚂蚁数量比例设置进行实验。

3.2 超强启发式信息素更新方法

信息素的全局更新方法有两种：（1）当所有蚂蚁完成路径规划后，对所有蚂蚁经过的所有路径进行信息素更新；（2）当所有蚂蚁完成路径规划后，对最优路径上的信息素进行更新。第一种信息素更新方法问题在于，对所有蚂蚁走过的路径均进行信息素更新，不仅浪费了算法时间，而且很多路径不具备参考价值。第二种信息素更新方法问题在于，只对最优路径信息素进行更新，当算法陷入局部最优时，这种信息素更新方式会将算法牢牢地困在局部最优；其次，这种信息素更新方法只起到了“奖励先进”的作用，却未对“后进”路径进行惩罚。

基于以上两种信息素全局更新方法存在的问题，这里提出了超强启发式信息素更新方法，思路为：按照适应度值对路径进行排序，将排名靠前的1/3路径作为“先进”进行奖励，将排名靠后的1/10路径作为“后进”进行惩罚。这种信息素更新方法既起到了“奖励先进、惩罚后进”的作用，同时选出了具有参考价值的前1/3路径进行信息素更新，达到对蚂蚁进行路径规划具有超强启发作用。路径上信息素的奖惩力度随路径优劣程度自适应变化，奖励路径的信息素增量为：

惩罚路径上的信息素惩罚量为：

式中：Δχij(t)-所有蚂蚁在路径ij上的信息素惩罚量蚂蚁k在路径ij上的信息素惩罚量。

综合式（6）（7），得到超强启发式信息素更新方法为：

3.3 超强启发式异类蚁群算法流程

根据蚁群中三类蚂蚁的节点选择方法和超强启发式信息素更新原理，制定超强启发式异类蚁群算法流程，如图2所示。

图2 增强启发式异类蚁群算法Fig.2 Hyper-Heuristic Heterogeneous Ant Colony Algorithm

4 实验分析与验证

4.1 三类蚁群规模确定

超强启发式异类蚁群算法中包含三类蚂蚁，各类蚂蚁数量的比例对算法性能影响较大。这里使用Matlab中的两个基准测试函数确定三类蚂蚁数量比例，包括Sphere函数和Griewank函数。其中Sphere函数维度为30，搜索空间为[-100,100]，Griewank函数维度为30，搜索空间为[-600,600]。

超强启发式异类蚁群算法参数设置为：种群规模m=100，信息素启发因子α=1，启发信息启发因子β=1，挥发系数ρ=0.3，信息素总量Q=1，最大迭代次数Nmax=100。

为了分析三类蚂蚁数量比例对异类蚁群算法寻优性能的影响，设置了四种数量分配方法：（1）三类蚂蚁等量分配，各占比1/3；（2）以开创型蚂蚁为主导的异类蚁群算法，将开创型蚂蚁设置为1/2，守旧型和传统型各占比1/4；（3）以守旧型蚂蚁为主导的异类蚁群算法，将守旧型蚂蚁设置为1/2，开创型和传统型各占比1/4；（4）以传统型蚂蚁为主导的异类蚁群算法，将传统型蚂蚁设置为1/2，开创型和守旧型各占比1/4。算法最大迭代次数设置为500次，每种算法对两个测试函数独立寻优20次。函数平均值随迭代次数变化曲线，如图3所示。

图3 不同数量比例的寻优结果Fig.3 Optimizing Result of Different Quantity Proportion

由图3可以看出，对于Sphere函数和Griewank函数两种基准测试函数，开创型蚂蚁主导的异类蚁群算法具有最快的收敛速度和最高的寻优精度，传统型和守旧型主导的异类蚁群算法寻优能力相对较差。这是因为开创型蚂蚁仅以路径最小为路径规划的唯一标准，不受种群内传统的影响，带动整个种群具有较强的创新能力。而传统型和守旧型的创新能力较差，导致以此两类蚂蚁为主导的蚁群算法寻优能力相对较弱。因此将开创型蚂蚁为主导的异类蚁群算法应用于机器人路径规划。

4.2 机器人路径规划

图4 不同环境下的最优路径Fig.4 Optimal Path under Different Environment

统计两种算法在简单和复杂环境下20次路径规划的最优路径长度、平均路径长度、路径长度方差、最优路径耗时等参数，结果，如表1所示。

表1 路径规划结果Tab.1 Path Planning Result

由图4可知，在简单和复杂环境下，异类蚁群算法规划的最优路径均优于传统蚁群算法，由表1中数据可知，在简单和复杂环境下，异类蚁群算法规划的路径平均长度远远短于传统蚁群算法，且路径长度方差也远远小于传统蚁群算法，说明异类蚁群算法不仅规划的路径优于传统蚁群算法，而且算法性能稳定，路径质量整体好于传统蚁群算法。另外，异类蚁群算法寻到最优路径耗时不足传统蚁群算法耗时的1/3，说明异类蚁群算法寻优速度远远高于传统蚁群算法。这是因为异类蚁群算法中包含三类蚂蚁，种群多样性有利于种群的进化、寻优；其次，以开创型蚂蚁为主导，可以抛开蚁群“传统”对蚂蚁个体的桎梏，增强整个种群的寻优能力；再者，对较优路径奖惩、对较差路径惩罚的信息素超强启发式更新方法，使传统蚂蚁和守旧蚂蚁快速向开创型蚂蚁搜索的较优路径靠拢，极大地提高了算法收敛速度。

5 结论

提出了基于超强启发式异类蚁群算法的栅格环境下机器人路径规划方法，通过分析与实验，可以得出结论：（1）由不同类蚂蚁组成的异类蚁群算法具有更高的寻优精度和寻优稳定性；（2）超强启发式信息素更新方法使传统型蚂蚁和守旧型蚂蚁迅速向开创型蚂蚁搜索的较优路径靠近，极大地提高了算法收敛速度。