基于改进蚁群算法的路径规划算法研究

韦子文

（中铁第一勘察设计院集团有限公司，西安 710043）

铁路信号设备的检修场所主要包括继电器检修基地、转辙机修配基地和驼峰修配基地等，各检修基地分散配置于不同站段。信号设备的检修存在资源配置不均、耗费严重等问题。随着铁路现代化的发展，电务检修基地按照资源整合、集约化的管理思想将各检修基地进行整合，以实现生产集约化、规模化，管理智能化、规范化，作业专业化、现代化的目标，可较大幅度地提升劳效和产能［1］。

智能机器人能解决任务繁重、效率低下、资源耗费过大等诸多问题，可发挥举足轻重的作用。目前智能机器人在铁路电务检修基地应用较少，随着铁路现代化的不断发展，它的应用将越来越广泛。因此，对智能机器人移动路径规划的研究在车间调度、智能搬运等领域有着极大应用价值。

为进一步提升智能机器人的智能程度及利用率，国内、外学者从不同角度（包括传统算法和智能算法）对机器人路径规划进行了广泛研究。Fernandez J A 和Gonzalez J［2］采用图搜索法确定了移动机器人从起始点到目标点的最短路径；Qi N，Ma B 和Liu X［3］提出人工势场法搜索机器人最短行驶路径；Gu J 和Cao Q［4］采用栅格法规划路径。然而，上述传统算法得到的路径并不理想且搜索效率较低。智能算法如蚁群算法［5］、免疫算法［6］、神经网络［7］在移动机器人路径规划研究中的应用，虽然性能提升较明显，但是存在搜索空间大、搜索时间长等问题。

众多学者又对上述传统算法进行改进优化，路径寻优效果得到了提升。徐菱［8］等提出采用16 方向24 邻域的搜索方式，通过引入转移概率控制参数调节搜索范围，以提高蚁群算法在路径寻优过程中的搜索效率和效果；蒋强［9］等提出一种结合蚁群算法和Dijkstra 算法的多目标路径规划方法，同时对寻优路径进行了平滑处理；M Nazarahari［10］采用改进的遗传算法按照一定的指标遍历所有目标点，以寻找一条无碰撞路径；胡章芳［11］等综合考虑路径平滑度和困难度等因素，提出采用Surrounding Point Set 算法改进遗传算法初始化种群的能力，仿真结果表明该算法在路径规划研究中的收敛速度略有提高。

本文针对传统算法存在收敛速度慢、路径搜索效率低等问题，综合考虑智能机器人实际运行过程中多种限制条件，在传统蚁群算法中引入“分类学习”的思想（各蚁种分别更新其信息素），同时增加搜索范围。基于此，提出一种多蚁种多邻域搜索的蚁群算法，以用于各种复杂环境和未知环境下的路径规划。

1 建模

环境布局复杂、路径无碰撞等限制因素，构建以智能机器人行进路径最短、轨迹最平滑为目标的路径规划模型。

首先，建立智能机器人运动的路径网络。电务检修基地中智能机器人工作环境可视为二维静态环境，各检修台（障碍物）均静止，为此采用栅格法确定工作环境，其中黑色栅格表示由障碍物占据的禁止行进的位置坐标，白色栅格表示可以通行的位置坐标。为便于计算和蚁群算法寻找、存储路径，按照从左到右、从上到下的顺序对每一个栅格进行编号。栅格示例如图1所示。

图1 栅格示例图

其次，设定好路径的起点和终点。机器人行进时，每一步都会沿着搜索方向移动一步，并期望机器人能够以最短的距离从起点移动到终点。

1.1 模型假设及约束

为清晰地表达路径规划问题，根据电务检修基地智能机器人工作状况的特点做出如下假设和约束：

（1）电务检修基地路面平整，因此可忽略其行驶路径的坡度影响，路径网络可完全由二维栅格图体现。

（2）针对不同的工作计划，智能机器人可避免重复路径，即不会经过同一坐标点两次及以上。

（3）机器人运行过程中受运动位姿及路径限界等因素的影响，目前蚁群算法在求解智能机器人路径规划问题时，求解得到的最优路径可能不符合实际运行路径。为此，本文对其工作环境中的各障碍物做了膨化处理，即：智能机器人在运行过程中将检测到障碍物的1.25 倍体积尺寸均视为障碍物进行避让。

1.2 目标函数

以智能机器人行进路径最短、转弯次数（智能机器人方向每转换一次即视为转弯一次）最少为目标，构建的目标函数为：

综合考虑智能机器人在实际运行过程中受到的

式中：dij——蚂蚁从i 移动到j 的距离；

N——路径上转弯的次数；

w1、w2——2 个子目标函数的权重系数；

Nmax——最大转弯次数约束；

Lgrid——智能机器人行进步长约束。

2 改进蚁群算法

2.1 传统蚁群算法

传统蚁群算法是在1991年由意大利学者Dorigo M等提出的模仿蚁群觅食行为的分布式计算优化算法。其基本原理是每只蚂蚁觅食过程中在经过的路径上释放“信息素”，并以“信息素”的浓度为指导选择运动方向，从而搜索最短的觅食路径。随着时间的推移，各路径上的“信息素”会挥发，但其中若干条较短路径上的“信息素”会逐渐增多，蚁群在此正反馈机制下最终寻找到一条最优路径。蚁群算法的核心思想包括状态转移［12］和信息素［13］更新。

2.1.1 状态转移

每只蚂蚁根据路径上的“信息素”浓度计算路径的选择概率，并基于这个概率选择运动方向。状态转移概率为：

式中：α——信息素权重；

β——启发式因子权重；

Jk（i）——第k 只蚂蚁下一步可被允许访问的点的集合；

τij（t）——信息素；

ηij（t）——表示期望程度的启发因子，表达为：

2.1.2 信息素更新

随着迭代次数的增加，蚂蚁行进的各路径上的“信息素”以式（7）、式（8）的规律进行更新。

式中：ρ——信息素挥发系数；

m——蚁群数量；

2.2 改进蚁群算法

针对传统蚁群算法存在收敛速度缓慢、前期信息素匮乏、易陷入早熟等问题，本文在此基础上对蚁群进行多分类，增加种群多样性，改进蚂蚁的状态转移概率公式，通过自适应调整信息素的挥发系数，并插入局部变邻域搜索操作，以解决其过早陷入局部最优的问题。

2.2.1 多蚁种

为了增加蚁群种群的多样性，本文引入“分类学习［14］”思想，将蚁群种群按照1：2 的比例分为精英蚁群和普通蚁群两类。精英蚁群的适应值较好，给予其较低的信息素挥发系数来增强其引导力；而普通蚁群的适应值相对较低，本文算法将普通蚁群平均分配给各精英蚂蚁，以扩大精英蚁群的搜索范围，避免其过早陷入局部最优。

2.2.2 改进状态转移规则

本文的算法对状态转移规则进行了优化，基于“节约里程法”这一核心思想在状态转移规则中引入距离节约因子。基本思想如图2所示。

图2 距离节约因子基本思想示意图

其主要出发点是，根据各蚂蚁起点到目标点之间的距离来寻找路径长度最短的行进方案。由图2可知，当前所在位置距下一步落脚点横向、纵向距离分别为doi和doj，至下一步落脚点的直线距离为dij。改进后的状态转移概率为：

式中：λ——距离节约值的权重；

μij（t）——距离节约值，表达为式（10）；ηij（t）表达为式（11）。

式中：dmax、dmin——所有下一步待选节点距终点的距离最大值和最小值；

dij——当前位置距终点的距离。

2.2.3 改进信息素更新策略

精英蚁群和普通蚁群的信息素更新方式也不同。若精英蚁群行进路径上信息素浓度过高，大于一定阈值Mmax，极易陷入局部最优，因此对其信息素更新策略进行改进，表达为式（12）；若普通蚁群行进路径上信息素浓度过低且低于Mmin，则对其信息素进行补偿，补偿数量为M2，具体更新策略表达为式（13）。

2.2.4 多邻域搜索

传统蚁群算法中，蚂蚁搜索方向仅为“前、后、左、右”4 个方向，其有效搜索方向有限。为了提高蚂蚁的搜索精度，同时考虑路径曲线的平滑性，本文算法将其搜索方向扩展到8 个方向，蚂蚁视野得到扩展，从而扩大了其搜索范围，搜索方向如图3所示。

图3 蚁群八方向搜索示意图

2.3 改进蚁群算法流程

本文改进蚁群算法具体流程如下：

步骤1：初始化多蚁种多邻域搜索蚁群算法的参数。

步骤2：初始化智能机器人所处的栅格环境和行进路径禁忌表，并确定其行进路径的起始点和终点。

步骤3：精英蚁群和普通蚁群按式（9）～式（11）计算其状态转移概率，以在多个搜索方向中选择智能机器人下一步行进的点。

步骤4：当智能机器人到达下一行进点时，同步更新禁忌表；检查是否到达终点，若是则跳转到步骤5，若不是则跳转至步骤3。

步骤5：蚂蚁个数i=i+1，检查整个蚁群是否完成路径搜索任务，若是则跳转到步骤6，若不是则跳转至步骤3。

步骤6：记录当前迭代次数的最佳路径，并让精英蚁群和普通蚁群按式（12）、式（13）更新信息素。

步骤7：迭代次数iter=iter+1，检查迭代次数是否达到最大值N，若是则输出最佳路径，若不是则返回步骤3。

算法流程如图4所示。

图4 改进蚁群算法流程图

3 案例仿真实验

3.1 案例背景

选取某电务检修基地室内布置搭建环境栅格模型，膨胀化后的障碍物位置如图5所示。综合考虑转弯次数、路径可行性、路径少重复性等多种因素，以式（1）为目标函数进行案例仿真分析。

图5 案例栅格环境图

算法初、中期主要考虑路径最短这一目标，算法后期主要考虑路径的平滑性。因此，随着迭代次数的增加，w1由大至小自适应递减，w2由小至大自适应递增。

本文采用的改进蚁群算法的具体参数设置如表1所示。

表1 参数设置表

3.2 仿真与对比

本文分别采用多蚁种多邻域搜索的改进蚁群算法（ACO）和排序蚁群算法（RAS）、精英蚁群算法（EAS）仿真10 次，取寻优路径和仿真结果进行对比，寻优路径分别如图6、图7所示，仿真结果如表2所示。

表2 三种算法仿真结果对照表

图6 本文算法最优路径图

图7 三种算法对比图

由图6、图7 可知，本文算法（ACO）的路径寻优效果更理想。虽然本文算法收敛代数略迟于其他两种算法，但其搜索路径更平滑（转弯次数更少）、距离更短。

4 结论

本文以电务检修基地中智能机器人的工作场景为背景，综合考虑其实际运行中的各种限制因素，构建路径最短、最平滑的函数模型。得出主要结论如下：

（1）针对多约束条件下传统算法在智能机器人路径寻优过程中存在的“早熟”现象、寻优效果不理想等不足，本文提出了一种基于蚁群算法的多约束条件下多蚁种多邻域搜索的改进蚁群算法，增加蚂蚁种群的种类，并在此基础上在状态转移概率中引入距离节约值、分不同种群改进了信息素更新策略。

（2）在相同环境下，与排序蚁群算法和精英蚁群算法相比较，本文提出的算法有效克服了“早熟”问题，得到的优化路径更平滑且距离更短，表明了本文提出的算法具有一定的优越性和实用性。

（3）本文未考虑动态障碍物和多智能机器人协同路径寻优的情况，这是本文的不足，也是未来研究的重点方向。