基于改进蚁群算法的全局路径规划研究与仿真

燕紫君，吴明芬*



基于改进蚁群算法的全局路径规划研究与仿真

燕紫君，吴明芬*

(五邑大学计算机学院 江门 529020）

路径规划是指在有障碍物的工作环境中，寻找一条从给定起点到终点的适当路径，使运动过程中能安全、无碰的绕过所有障碍物。目前针对路径规划的算法较多，本文主要针对传统蚁群算法在二维路径规划中易陷于局部最优解，最终导致搜索过早停滞等问题，提出了一种改进的蚁群算法。该改进的算法主要以全局最优为出发点，通过引入终点对启发因子的影响，在邻接点和终点的共同作用下对启发因子函数的重新构建，有效地解决了传统蚁群算法在处理全局路径规划中带来的问题。采用MAKLINK图论理论建立二维空间模型，应用MATLAB作为编码的软件工具来对传统的蚁群算法和改进的蚁群算法在路径规划中进行仿真验证，实验结果表明改进的蚁群算法有更好的性能。

全局路径规划；蚁群算法；启发因子；MAKLINK图论理论

引言

路径规划是指在有障碍物的工作环境中，寻找一条从给定起点到终点的适当运动路径，使在运动过程中的物体能安全、无碰的绕过所有障碍物。考虑到实际环境复杂多变,如何迅速的策划一个有效的最优的路径变得异常显著。目前国内外研究者们针对该问题已经提出了多种解决方法，比如神经网络算法[1]、人工势场法[2]等，神经网络算法具有较强的学习能力，但是当路径中的障碍物变多，且为动态时，就要不断的调整阈值；人工势场法的优势在于实时控制，但容易陷入局部最优解而停止运动。蚁群算法的提出为解决这一问题提供了新的思路。从金纯等人的《矿井中多机器人搜救系统路径规划》[3]、Rong Wang等人的《Two-Dimension Path Planning Method Based on Improved Ant Colony Algorithm》[4]、张琦等的《基于改进蚁群算法的移动机器人路径规划》[5]等文献中可知，蚁群算法在解决这一问题中有着较强的优越性，但还是存在收敛于局部次优解的问题，为了克服这些的问题，本文提出了一种改进的蚁群算法，该算法主要是通过引入终点对启发因子的影响，在邻接点和终点的共同作用下对启发因子函数的重新构建，有效地解决了传统蚁群算法在处理全局路径规划中带来的问题。

1 传统的蚁群算法

蚁群算法是一种模拟蚂蚁搜索食物的算法，它于90年代由M.Dorigo[6]等人提出，该算法一经提出便成为了智能领域一种主要的算法。该算法在解决优化问题的基本步骤是：蚂蚁行走路径被看作问题的可行优化路径，整个蚂蚁所在的路径构成了解空间的优化问题。释放的信息素在短路径会超过其它路径，随着时间的推移，更多的蚂蚁会选择这些较短的路径。最终蚂蚁在积极的反馈作用下将专注于最好的路径。

在t时刻，蚂蚁k从节点i选择下一个要走的节点j必须要依据概率转换公式，如公式（1）、公式（2）和公式（3）所示

（2）

（3）

信息素初始化时通常将每条路径上的值都设置为一固定的常数。在对于信息素的更新策略方面有局部信息素更新方式和全局信息素更新方式，局部信息素更新方式指蚂蚁选完下一路径后立即更新该路径上的信息素；全局信息素更新方式是所有蚂蚁选择完下一个节点后，对信息素进行更新。为了更好的得到全局最优路径，本文选择全局信息素更新方式。其公式如公式（4）所示。

2 改进的蚁群算法

由于在解决机器人全局路径规划时传统的蚁群算法存在收敛于局部次优解而导致搜索的过早停滞问题，为了克服在全局路径规划中蚁群算法中存在的这些的问题，下面提出了一种改进的蚁群算法。

2.1 环境建模

本文利用MAKLINK图论理论[7]建立一个二维空间模型， MAKLINK线定义为两个障碍物之间不与障碍物相交的顶点之间的连线,以及障碍物顶点与边界相交的连线[8]。典型的MAKLINK图如图1所示。在MAKLINK图上存在一条自由连接线，连接线中的点依次为,连接部分MAKLINK线中的点加上起点和终点就构成了规划路径。

Fig. 1 The two-dimension MIKLINK model

在MAKLINK模型中规划最短路径的主要思路是：首先利用MAKLINK图建立路径规划二维空间模型，然后根据dijkstra算法[6]（单源最短路径算法）来对最短路径初始化，初始化各参数，采用蚁群算法搜索路径，更新路径上的信息素。假设得到的路径为，其中表示第条连接线上的第个等分点。

2.2 蚁群算法的改进

下面使用全局式启发因子示意图来更详细的对此改进的公式进行描述，如图2所示，在最短路径规划中已经得知了起点和终点，所以目标就是在起点和终点之间找一条最短路径。所以当蚂蚁选择下一个城市时，如果是基于传统蚁群算法，会倾向于选择节点，但改进的蚁群算法会从全局考虑，更倾向于选择节点。由两点之间线段最短可知改进的启发因子函数中引入了可以得到更短的规划路径。由于两边之和大于第三边，所以改进以后的启发因子函数，更加考虑全局，可以从一定程度上避免局部最优解。

Fig. 2 The stimulating factor function .

为了说明该改进的有效性，举个简单的例子来说明。如图3表示一个普通路网图，要分别用传统蚁群算法和改进蚁群算法在起点S到终点T之间规划出一条合理的路径。

Fig. 3 Ordinary road network diagram

Fig. 4 Traditional ant colony algorithm in network planning

Fig. 5 Improved ant colony algorithm in network planning

在图4和图5红色加粗路径代表规划的路径，由于边(2,3)+边（2,6）>边(3,6),所以两种方法中改进的蚁群算法具有更加优越的性质。

3 实验仿真及结果分析

由于不同的参数设置会对实验结果产生较大的影响，所以本文在经过对多个参数值进行实验仿真后选取出比较好的一组参数，对于公式（4）中的参数进行初始化即信息素重要度，启发式因子重要度，信息素挥发因子，蚂蚁的数量，迭代次数c=500。。

步骤一：描绘二维路径中的障碍物，描述起点和终点，初始化链路的端点。从而构建一个MAKLINK图。

步骤三：使用dijkstra算法产生一条初始化的最优路径，将其经过的连接线存储在列表中，并使用公式（6）和（7）来将链路分离出多个等分点。

根据上诉步骤编写了相应的MATLAB程序进行仿真，改进的蚁群算法和原始的蚁群算法得到的路径如图6所示，其中红色的线代表的是传统蚁群算法规划的路径，蓝色的线代表了改进的蚁群算法。传统的蚁群算法得到的路径长度为212km，改进的蚁群算法得到的规划路径长度为109km，反映了改进的蚁群算法能够找到更优的路径。图7为两种蚁群算法的迭代次数和路径总长度的示意图，从该图中可以看出改进的蚁群算法能够更加快速的找到一条更优的全局规划路径而且在迭代中更加稳定。以上证明了改进的蚁群算法的有效性。

Fig. 6 Two kinds of ant colony algorithm contrast figure on planning path

Fig. 7 Two kinds of ant colony algorithm contrast figure on total length of path and iteration

图7 两种蚁群算法的迭代次数和路径总长度

4 结论

本文通过应用改进的启发因子提出了一种改进的蚁群算法，更好的解决了传统蚁群算法在解决最短路径规划中改进的蚁群算法收敛速度慢、易限于局部最优解等问题。通过MAKLINK图论建模和MATLAB仿真可知较传统的蚁群算法该方法能够更好的解决全局路径规划问题。

虽然该算法在此环境下有较好的应用，但本文的建模环境比较单一，只有障碍物的阻碍，在实际应用中会有各种因素来影响路径的规划，这时要考虑到多种因素，这也是作者以后要研究要考虑的问题。

[1] 黄磊. 基于神经网络的移动机器人路径规划研究[D]. 武汉理工大学, 2008

[2] 于振中, 闫继宏, 赵杰. 改进人工势场法的移动机器人路径规划[J]. 哈尔滨工业大学学报, 2010(01): 50-55.

[3] 金纯, 王升刚, 尹远阳. 矿井中多机器人搜救系统路径规划[J]. 机床与液压, 2014, 42(15): 10-14.

[4] Rong Wang, Hong Jiang. Two-Dimension Path Planning Method Based on Improved Ant Colony Algorithm [J]. Advances in Pure Mathematics, 2015(5): 571-578.

[5] 张琦, 马家辰, 谢玮. 基于改进蚁群算法的移动机器人路径规划[J].东北大学学报( 自然科学版), 2013, 34(11): 1521-1524.

[6] Dorigo, M. and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem”, IEEE Transaction on Evolutionary Computation, Vol.1, No1. pp 53-66, 1997.

[7] 史峰, 王辉, 郁磊等.MATLAB智能算法30个案例分析[M].北京：北京航天航空大学出版社, 2011, 7.

[8] 王云飞. 基于蚁群算法的武警巡逻路径优化问题研究[D]. 国防科学技术大学, 2014.

Research and Simulate of Global Path Planning Based on Improved Ant Colony Algorithm

YAN Zijun, WU Mingfen*

(College of Computer Science , Wuyi University, Jiangmen，529020)

Path planning is to find a proper path from a given starting point to the end point in a work environment with obstacles, and it makes the object in motion process safety without touching obstacles. At present, there are many kinds of algorithm to solve the issue of path planning. In this paper, we focus on the shortage of traditional Ant Colony algorithm, causing issues of premature and search stalled. When it is applied to solve the problem of robot path planning, an improved Ant Colony algorithm has been put forward, and the improved algorithm set global optimization as original intention. By introducing the end point effect on the stimulating factor, we rebuild the stimulating factor function under the joint of adjacent point and end point, and through this method we can deal with the matters that traditional algorithm brings effectively. As the result, we use MAKLINK to build a two-dimensional space model, and use the MATLAB as a coding tool to simulate the traditional ant colony algorithm and the improved ant colony algorithm in path planning. The result shows that the improved Ant Colony algorithm has better performance.

global path planning; Ant Colony algorithm; stimulating factor function; MAKLINK graph theory

10.19551/j.cnki.issn1672-9129.2017.01.02

TP391.9

A

1672-9129(2017)01-0006-04

2017-02-01；

2017-02-10。

国家自然科学基金(11271040，11361027)；广东省教育厅重大项目(2014KZDXM055)；广东省科技厅项目(2016A070708002，2015A070706001，2014A070708005)资助。

吴明芬，广东省江门市五邑大学计算机学院(529020)，E-mail：mfwu@sina.com