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

田涌君，张金炜，戎 辉，王文扬，郭 蓬，3，高 嵩，3

（1.中国汽车技术研究中心有限公司，天津 300300；2.河北工业大学，天津 300222；3.天津大学，天津 300072）

进入21世纪以来，众多技术迅速发展，无人驾驶技术也是其中之一。路径规划作为无人驾驶的重要组成部分，研究人员对路径规划提出了很多算法，如传统算法（模拟退火法、人工势场法、模糊逻辑法），智能仿生算法（蚁群算法、粒子群算法、遗传算法），启发式搜索算法（A*算法、D*算法）等算法。

本文主要介绍蚁群算法及其改进方法。蚁群算法是一种经典的智能仿生算法又称蚂蚁算法，是一种在图中搜索最优或者次优路线的智能算法。在1992年，Marcc Dorigo博士提出了蚁群算法，它的主要思想是蚂蚁在搜索食物过程中会形成一定的规则，在这种规则下每只蚂蚁都能沿着相同路径找到食物。

蚁群算法也存在着缺陷，最主要的、关键性的缺点就是搜索时间长、较容易陷入局部最优解。有关蚁群算法的改进，提出了很多解决方法，大致可以分为两大类，一类是基于经典蚁群算法的改进，一类与其它智能算法融合的改进。

1 经典蚁群算法

蚂蚁通过群体性的方式寻找路径，它们会在所走过的路上留下信息素，此信息素就是蚂蚁之间沟通的媒介，当下一只蚂蚁路过该路径时就会利用信息素做出下一步的判断，并且会释放出自己的信息素，这样就形成了信息素的积累，使得后续蚂蚁可以选择信息素强的路径，随着大量蚂蚁在信息素的作用下不断搜索路径，最终会得到一条最优或者次优路径。

1.1 蚁群算法流程图

图1为经典蚁群算法流程图。

1）构造解空间 解空间的构造通过搭建栅格地图来完成，用白色栅格表示可行驶区域，黑色栅格表示障碍物区域，从中设置出发点和目标点。

2）节点选择 蚂蚁从当前节点选择下一个节点的方法如公式（1）所示。

图1 经典蚁群算法流程图

式中：i——当前节点的周围8个节点集合；——信息素；——启发值。

首先计算当前节点j与四周节点i之间的选择概率，然后利用选择概率采用轮转赌法选择下一节点。公式（2）为的计算方法。

3）信息素更新 在路径搜索中，蚂蚁每过一个节点就会对该节点进行信息素更新。公式（3）为信息素更新公式。

2 基于经典蚁群算法改进

2.1 改进启发函数

经典蚁群算法中的启发函数是通过相邻栅格距离构造的，所得的数值差别很小，算法的搜索效率很低。针对这个问题，仿照A*算法的估价函数对蚁群算法的启发函数进行改进，增加目标点对启发函数的影响，加快算法的收敛速度。A*算法是一种有序的启发式搜索算法，其基本原理是利用当前节点、可选节点和目标节点的位置关系构造估价函数，估价函数值最小的路径即为下一步选择的路径。估价函数为当前节点S到可选节点n的代价与从可选节点n到目标节点E代价之和。表示为公式（4）。

式中：g（n）——节点S到可选节点n的代价；h（n）——可选节点n到目标节点S代价。则蚁群算法的启发函数可改进为公式（5）。

式中：——栅格i与栅格j的距离；——栅格j与目标点E的距离。

2.2 改进状态选择策略

经典蚁群算法在初始阶段搜索路径时，由于蚂蚁会在走过的路径上留下信息素，这样就造成路径积累信息素过多，从而使得蚂蚁很大概率选择信息素多的路径，因此蚁群算法在初始阶段就失去了选择路径的多样性，陷入局部最优解。针对此问题，对状态选择策略做了如公式（6）的改进。）

式中：；q0——（0，1）的常量；q——（0，1）的取值符合均匀分布的随机数。当时，按的最大值确定性搜索，否则，依据按轮盘赌法选择法随机性搜索。两种选择策略混合使用，增加解的多样性。

2.3 改进信息素分配规则

经典蚁群算法的信息素分配规则是当所有蚂蚁走完路程之后才更新全局信息素，在这种信息素更新机制中，把蚂蚁所走过的全部路径都参与到信息素的更新中，这样容易降低算法的收敛速度。

改进的信息素分配规则如下。

1）在全部蚂蚁搜索完路径之后，把蚂蚁搜索的路径长度按照从小到大的顺序进行排序，保留前1/w的蚂蚁路径，并将其信息素更新如公式（7）所示。

2）每次迭代的最优解和记录下来的全局最优解路径上的信息素进行更新可以使算法的收敛速度加快。信息素增量如公式（8）所示。

式中：——记录下来的全局最优解；——本次迭代最优解。

3 蚁群算法与其他智能算法结合

3.1 融合人工势场的改进

蚁群算法与人工势场算法的融合，是全局路径规划和局部路径规划的有效结合。人工势场算法，采用引力与斥力的思想，引导无人车向终点运动，利用这种方法构建蚁群算法的启发信息素，如公式（9）所示。

式中：dij——节点i到节点j的欧氏距离；Lig——采用人工势场法求到的节点j到目标节点g的距离；Ncmax——最大迭代次数；Nc——当前迭代次数；ξ——启发信息递减系数，且ξ＞1。

3.2 融合粒子群算法的改进

融合粒子群的改进，其思想是应用粒子群建模的方法，能够快速规划出从出发点到目的点的路径。这些规划出来的路径并不是最优路径，再结合蚁群算法，在快速搜索出来的路径上添加信息素，那么就会对蚂蚁搜索具有引导作用，将会提高蚁群算法全局搜索效率。

4 总结

蚁群算法在1992年被提出来之后，国内外的众多学者对其做了大量的研究和改进，总的来说改进方法分为两大类：一是基于经典蚁群算法的改进，二是与其它智能算法融合的改进。

［1］ 杨帆.无人驾驶汽车的发展现状和展望［J］.上海汽车，2014（3）：35-40.

［2］ 孙梅.移动机器人路径规划技术综述［J］.山东工业技术，2016（21）：164.

［3］ 霍凤财，任伟建，刘东辉.基于改进的人工势场法的路径规划方法研究［J］.自动化技术与应用，2016，35（3）：63-67.

［4］ 陈刚，沈林成. 复杂环境下路径规划问题的遗传路径规划方法［J］.机器人，2001，23（1）：40-44.

［5］ 李士勇，陈永强，李研.蚁群算法及应用［M］.哈尔滨：哈尔滨工业大学出版社，2004.

［6］ 史恩秀，陈敏敏，李俊，等.基于蚁群算法的移动机器人全局路径规划方法研究 ［J］.农业机械学报，2014，45（6）：53-57.

［7］ 王宪，王伟，宋书林，等.基于蚁群粒子群融合的机器人路径规划算法 ［J］.计算机系统应用，2011，20（9）：98-102.