一种改进的蚁群路径规划算法

王天生，张 峰

（1.上汽通用五菱汽车股份有限公司，广西 柳州 545000；2.武汉理工大学机电工程学院，湖北 武汉 430070）

0 引言

近年来随着移动机器人技术的大量应用，作为其重要分支的路径规划技术也受到了学者的广泛关注。所谓路径规划即是在充满障碍物的规划空间中找到一条从起点到终点的最优、最短路径，并且能够无碰撞地成功地绕开环境中所有的障碍物。目前，在路径规划领域中应用的比较多的算法主要分为两类，一类是可视图法[1]、自由空间法[2]、拓扑图法等传统的求解方法；另一类则是采用遗传算法、蚁群算法、神经网络法等智能算法。虽然上述的各种方法为路径规划问题提供了不同的解决方案，但是各种方法在执行上总是存在着不同的缺点与优点，并没有一种方法能够完全适应各种环境条件下的任何系统。

蚁群算法是一种模拟蚂蚁群体觅食行为的仿生优化算法，该算法具有较强的鲁棒性、优良的分布式计算机制、易于与其他算法相结合等优点[3]。因此，自意大利的Dorigo[4]学者提出蚁群算法以来，如今已经在各行各业得到了广泛的应用。但传统的蚁群算法由于其复杂性往往需要很长的搜索时间，而算法搜索初期的盲目性也容易造成算法收敛速度慢等缺点[5]。针对上述缺点，许多学者也提出了相应的改进方法，如Stutzle[6]为了避免蚁群算法趋于停滞、陷于局部最优，对信息素的更新范围进行了限定，从而提出了搜索效果更好的最大最小蚂蚁系统（MMAS）。黄震等[7-9]学者则是将蚁群算法与其他表现较好优化算法如遗传算法、A*算法等相结合，从而提出了收敛性较好的混合蚁群算法。大量的文献[10]也表明，多数学者对蚁群算法的改进主要聚焦于信息素的更新方式以及怎样提高种群的多样性，很少有学者关注蚂蚁的搜索方向以及启发函数信息的更新。因此，本文基于传统的蚁群算法加入了自适应调整启发函数，局部最优方向引导机制，并在此基础上提出了一种改进的蚁群路径规划算法，该算法具有较高的收敛速度。

1 传统的蚁群路径规划算法

虽然蚁群算法的提出是着眼于解决旅行商问题（TSP），但其基本思想却可以应用于许多其他问题的求解，路径规划问题便是其中之一。因此，基于蚁群算法的路径规划也得到了大量的发展，蚁群算法中最重要的是蚂蚁对下一步节点的概率的选择以及各节点之间的信息素的更新。

1.1路径选择概率

蚂蚁 k（k=1，2，…，m）在运动过程中，根据各路径上的信息素量来决定下一步的转移节点，其中用禁忌表tabuk表示蚂蚁k所走过的节点集合，禁忌表会在蚂蚁移动过程中做动态调整，在路径搜索过程中，蚂蚁根据各路径上的信息量以及路径的启发信息来计算状态转移概率。表示t时刻蚂蚁k由节点i转移到节点j的状态转移概率，其公式如式（1）所示。

否则式中，allowedk＝{C-tabuk}表示蚂蚁k下一步允许选择的节点，α为信息启发式因子，表示各节点间信息的相对重要性，反映了蚂蚁在运动过程中所累积的信息在蚂蚁运动时所起到的作用，其值越大，则蚂蚁越倾向于其他蚂蚁所走过的路径，蚂蚁之间的协作性也就越强，但过大的信息启发因子也会限制蚁群算法的全局搜索能力。β为期望式启发因子，反映了启发信息在蚂蚁选择路径中受重视的程度，其值越大，则蚁群算法越接近于贪心算法。ηij（t）为启发函数，在路径规划中，一般其表达式如式（2）：

式中，dij表示两节点之间的欧式距离。

1.2信息素的更新

蚁群算法中蚂蚁群体的协作离不开信息素，但无限量的累加各节点上的信息素量不仅不符合蚂蚁群体的自然规律，也会造成信息素过多而淹没启发信息，因此，当所有蚂蚁到达终点后就要对全局信息素进行更新。其更新不仅包含信息素的累加，也包含信息素的挥发。各节点之间的信息素可按如公式（4）（5）执行：

式中，ρ表示信息素挥发系数，用于衡量信息素的衰减程度，其取值范围一般为ρ∩（0，1）表示本次循环中路径（i，j）上的信息素增量表示蚂蚁群体中第k只蚂蚁在本次循环中留在路径（i，j）上的信息量，如式（6）所示：

否则式中，Q表示信息素强度，其值大于0，Lk表示第k只蚂蚁在本次循环中所走路径的总长度。

2 改进的蚁群路径规划算法

2.1自适应调整启发函数

在传统的蚁群算法中，由于启发函数ηis（t）对终点的指向性较差，从而导致算法搜索时间长，收敛速度慢，因此，考虑在算法搜索初期以待选节点与终点之间欧式距离的倒数作为新的启发函数，如式（7）所示。

式中，djd表示节点j与终点d的欧式距离。

在实际的路径规划中，由于搜索空间中各种障碍物的影响，以欧式距离作为待选节点与终点之间的最短可行路径并不利于散发后期的快速收敛，故将式（7）中的启发函数应用于算法搜索于初期阶段，随着算法迭代次数的增加，各代中的最优路径也就更加接近实际的最短路径，此时，启动启发函数更新机制，以算法每代的最优线路为基础对启发函数进行更新。启发函数的更新公式如（8）（9）（10）所示。

当 i=start时，则公式（9）变为如下公式（10）所示。

式中，NC表示算法迭代次数；djd（t，NC）表示在算法迭代NC次时，节点j与终点d之间的最短可行路径；η″ij（t，NC）表示更新后的启发函数，R_best（NC）表示在NC中的最优线路；i，j分别表示R_best（NC）中相邻的两节点，其中i节点在前，j节点在后；start表示起始点；dsj表示起始点与节点j之间的欧式距离；dij表示相邻节点i，j之间的欧式距离。在动态调整启发函数后，蚂蚁搜索过程中的状态转移概率如公式（11）所示。

否则式中，const为一常数，其值大于0；NC为算法迭代次数。

2.2局部方向引导机制

在传统的蚁群算法中，蚂蚁的状态转移概率的主要影响因素是信息素与启发函数，但路径规划问题最大的不同是在路径规划前有事先可知的起始点与终点。因此，处在当前节点i的蚂蚁在搜索转移节点时，则可认为当前节点i与目标点d的连线方向为最优的搜索方向。转移节点j的优劣以当前节点i分别与转移节点j和目标点d连线向量的夹角θijd来衡量。θijd越小，则转移节点越靠近最优的搜索方向。在综合考虑信息素，自适应的启发函数以及局部最优的搜索方向后，改进的路径选择概率如公式（12）所示。

否则式中，λ表示局部方向因素强度系数，其值大于0.γ表示局部方向因素衰减系数，其值大于1.θijd表示i与终点d的连线向量与i到j连线向量的夹角。从公式（12）可知，γ值的大小影响着局部方向因素的衰减程度。由于在蚁群算法的初级阶段，各节点之间信息素差异较小，转移概率随机性较大，算法收敛速度较低，这时可通过加大局部方向因素的影响，使蚂蚁更多的向最优路线聚集，算法的后期，则应逐渐降低局部方向因素的影响，从而让信息素和启发函数成为转移概率选择的主导因素，因此，合理的选择参数λ，γ的值非常的重要。

3 仿真测试

为了验证改进的蚁群算法在机器人路径规划中的有效性，本文利用Matlab2010仿真软件在如图1所示的两种复杂度不同的栅格环境下进行了路径规划的仿真（栅格中黑色代表障碍物），并记录了对应的最优路径迭代收敛曲线。从图中可以看出，环境1为的栅格环境，环境中的障碍物也较少，环境2则为的栅格环境，规划空间也更为复杂。在记录各算法在各环境下的最优路径迭代曲线时，考虑到蚁群算法的随机性，选取了各算法的20次试验的平均值作为参考数据。算法中各参数的取值分别为蚂蚁数m=30，α ＝ 1，β ＝ 6，ρ＝ 0.1，Q ＝ 14，λ ＝ 3，γ ＝ 4，const=10，栅格环境1中算法的最大循环次数NCmax1=50，栅格环境2中算法的最大循环次数NCmax1=100.

图1 不同的仿真测试栅格环境

图2为两种算法在环境1下的最优规划路径，图3分别为传统算法与改进算法在环境1下的最优路径迭代收敛曲线。从图中可以看出，两种算法虽然都环境1下找到了最优的规划路径，但改进算法在迭代9次时收敛，而传统算法则是23次。因此改进的蚁群算法较传统的算法在收敛速度上具有不小的优势，收敛速度更快。

图2 环境1下的最优规划路径

图3 环境1下两算法的最优路径迭代收敛曲线

图4为两种算法在环境2下的最优规划路径，图5则分别为传统算法与改进算法在环境2下的最优路径迭代收敛曲线。从图中可以看出改进的算法在迭代38次时收敛，传统算法则要迭代75次才收敛。因此，改进算法较传统算法收敛更快。从上述的仿真测试可以看出，改进的蚁群路径规划算法不仅适应简单的规划环境，在复杂的环境中较传统算法也有较快的收敛速度。

图4 环境2下的最优规划路径

（续下图）

（接上图）

图5 环境2下两算法的最优路径迭代收敛曲线

4 结束语

针对将传统的蚁群算法应用到机器人路径规划中易出现搜索时间长，收敛速度慢等问题，本文提出了一种改进的蚁群路径规划算法。改进的蚁群算法能自适应的调整启发函数，并加入了动态衰减的局部方向引导机制。在算法搜索初期，以搜索节点与终点的欧式距离的倒数表示取法函数，在算法迭代到一定阶段后，以各代的最优路径信息动态地更新启发函数信息。以搜索节点与终点连线的方向为最优的搜索方向，并引入了局部方向因素强度系数、局部方向因素衰减系数，并借此构建了新的路径选择概率表达式。仿真测试表明，改进的蚁群路径规划算法在各种不同的规划环境中都有较快的收敛速度。

参考文献：

[1]李善寿，方潜生，肖本贤，等.全局路径规划中基于改进可视图法的环境建模[J].华东交通大学学报，2008，25（06）：73-77.

[2]熊 菡.移动机器人全局路径规划及轨迹跟踪研究[D].武汉：武汉科技大学，2014.

[3]金 弟，杨 博，刘 杰，等.复杂网络簇结构探测——基于随机游走的蚁群算法[J].软件学报，2012（03）：451-464.

[4]Dorigo M，Gambardella L M.Ant colony system：A coopera tive learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1（1）：53-66.

[5]马金财.基于蚁群算法的机器人路径规划问题研究[D].昆明：昆明理工大学，2014.

[6]Thomas Stutzle T，Holger H Hoos.Max-min ant system[J].Future Generation Computer Systems， 2000，16（8）：889-914.

[7]苏海锋，许道林，李汶江，等.基于改进蚁群A～*算法的输电线路路径搜索[J].河北大学学报（自然科学版），2017，37（01）：92-100.

[8]黄 震，罗中良，黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J].中山大学学报（自然科学版），2015，54（01）：41-46.

[9]薛冰冰.基于改进型遗传算法的足球机器人路径规划研究[D].长春：长春工业大学，2012.

[10]朱颢东，孙 振，吴 迪.基于改进蚁群算法的移动机器人三维路径规划[J].华中师范大学学报（自然科学版），2016，50（06）：812-817.