改进蚁群算法在机器人中的应用概述

廖 铮，杨奇燊，林生杰，郑晓云，王治坤

（北京理工大学珠海学院，广东 珠海519000）

蚁群算法是一种元启发式的智能搜索算法，与另外的一些模拟式的进化型算法一样，具有智能的特性。蚁群算法自被意大利学者DORⅠGO[1]于1996年提出，引起了许多研究者的关注。蚁群算法最初是被应用于商旅行问题，取得的效果尚好，但是因为其具有易收敛的缺点，仍需改进。随着蚁群算法的发展和改进，因蚁群算法具有易与其他优化算法结合的优点，蚁群算法逐渐被应用于多个领域。本文首先从蚁群算法原理出发，再从蚁群算法在机器人中的应用及其发展趋势进行描述。

1 原始蚁群算法的基本原理

算法最初期的应用在TSP类型的问题时，主要由初始、信息素更新2部分组成。以简单的两点间的距离问题为例，分别取A、B两点。蚁群路径图如图1所示。

图1 蚁群路径图

第一步，在初始时，从A点到B点的3条路径上并没有任何信息素物质影响蚂蚁的路径方向，所以初始时蚂蚁路过3条路径的概率是相同的，3条路径路过的蚂蚁初始时是一样的。第二步，蚂蚁在不断经过3条道路的过程中，会散发出一种能够吸引其他蚂蚁的物质——信息素，可以吸引其他蚂蚁过来，不断集中走这一条路。第三步，在初始时，假设蚂蚁每分钟经过的路程相同。由于2是3条道路上路程最短的，则在相同的时间内，蚂蚁路过2路上的数量是最多的，并且因为数量最多，所以可以散发更多的信息素，可以吸引更多的蚂蚁走2路上，因此，2路上的信息素变得越来越浓密。第四步，经过一段时间的循环，蚂蚁在选择1、2、3路上的时候会更多地选择第2路，因为2路上的信息素含量远大于1、3路的信息素含量，所以推断出：经过时间的推移，1、3路上基本没有蚂蚁经过，2路上的蚂蚁是最多的。

基本的蚁群算法原理核心由下列3条公式组成[2]：

经典的蚁群规划模型有3种经典模型，王颖等[3]详细说明了蚁群算法的3种模型，3种模型分别为cycle system、quantity system、dentisy system。以下是3种模型：

对上述3种经典模型进行了仿真实验，可得在求解商旅行的问题中，ant cycle system性能是最佳的。

2 蚁群算法的改进与发展

蚁群算法到现阶段位置有2个比较需要改进的缺点，分别为算法的收敛度太短和局部空间寻优快。针对这2个缺陷，大部分学者利用蚁群算法的信息素传播原理，对信息素规则进行修改。因为信息素的调整策略对算法的收敛性和求解效率具有很大影响的。

有很多国内外的学者利用多种方式对信息素的传播和挥发进行修正。如柳长安等[4]利用栅格法并对栅格进行编号，再通过引入自适应的函数对信息素的含量进行修正，最后再通过研究狼群分配原则再次对信息素进行修正。在蚂蚁的前进路上，把路上蚂蚁留下的信息含量较低的路线去掉，使得蚂蚁在每次迭代中都能找到最多信息素含量的路线，得到最优解。针对正反馈过程易陷入局部最优解的情况，对蚁群算法进行改进，覃刚力等[5]提出针对信息素矩阵在每一次蚁群迭代中的改变，提出了一种动态自适应调整信息素的方法改进蚁群算法求解商旅行问题，通过信息素矩阵的改变，达到对蚁群算法的监控，实时判断算法的搜索状态，采用强制机制，减小必要的信息素，达到更好的效果。针对蚂蚁的易出现停滞现象，郑松等[6]提出了一种针对全局动态调整选择策略的改进蚁群算法，能够有效抑制蚁群算法的停滞现象，更容易得到局部最优解。

3 蚁群算法在机器人上的应用

因为蚁群的数量庞大、基数足的特点，可以通过传播信息素的方法来改变蚁群的路径规划趋势和移动方向的规划。国内外许多学者对此进行进一步的改进和运用。

3.1 蚁群算法在TSP问题上的应用

因为蚁群的数量庞大、基数足的特点，可以通过传播信息素的方法来分配整个蚁群中的任务和对路线进行规划。蚁群在寻找食物的过程中，每只蚂蚁都会在途径的路上释放一种具有信息的因子——信息素，每个蚂蚁都能感知到这种物质的存在，并根据信息浓度的强度指导自己的移动方向。传统的机器人路径规划一般是在自然环境中，机器人按照给定的参数指标和一定的规则在给定的全局空间中不断探索一条从开始位置到目标位置的无碰撞路径。

近年来，国内外的学者都对蚁群算法在路径规划问题上的研究提出了不同的创新点。任红格等[7]提出的采用修改的算法路径搜索策略以及创新的启发函数进行规划。结合信息素挥发系数，解决了平时有时无法搜索到最优路径等问题，提高了搜索算法的的效率，也得到了较为优良的路径规划路线。刘辉等[8]基于改进的蚁群算法对无人矿车路径进行规划研究，将速度-坡度作为一个影响因子，结合蚁群算法的状态转移概率建立相关的影响公式。在实际的场景中，具体是在路径较短的条件下选择坡度较小的节点。将每代蚂蚁中的优良的蚂蚁进行局部路径优化，提高搜索路径的能力。与传统的蚁群算法进行比较该种算法在实际的采矿类环境下，改进过后的蚁群算法在采矿的情况下全局寻优的能力更为良好，算法的实际收敛速度更快，实际用时较短。邓向阳等[9]在基本的蚁群算法基础上提出先验优势方位角的概念，建立了主优势网格和次优网格的模型，在全局的解空间中构建了起始点与目标点互换的交替双向引导策略，应用在具有复杂障碍物分布的大规模地图，改变了传统蚁群算法信息素结构。由仿真实验可得出，该算法大大提升了构建初始解及收敛的速度，针对于大规模场景下的路径规划，改良的蚁群算法在处理大规模的地图环境中可以具有优良的适应性，求解的过程也得到了很大的提升，能够很好地求解在复杂的路况下的复杂路障环境的问题。李文振等[10]针对在蚁群算法在移动机器人路径规划中存在的一些稳定性不足、收敛速度慢、易陷入局部最优等问题，优化改进了传统的蚁群算法。主要是通过改进转移概率来改变转移规则，让蚂蚁可以准确预测搜索到下一个最佳栅格位置，同时采用了新的信息素更新规则可以加快收敛速度，扩大搜索空间。仿真结果表明，该改进算法在路径搜索效率和收敛速度方面明显优于传统蚁群算法。蓝丹等[11]结合智能车辆的具体动力学方程约束，对规划路径进行平滑和优化处理，对智能车在车道障碍物的具体建模场景中，均成功规划出一条更为便捷且更为平滑的全局安全路径。实验结果表明该方法能够较好地克服传统蚁群算法存在的缺陷，能提高算法效率同时优化车辆的具体行驶路径，实现了动态避障的目标。何雅颖等[12]提出的由起点到终点距离以及地图参数来构建全局优先区域，避免算法在庞大的全局空间中进行盲目的搜索；在信息素的更新公式中引入信息素增强因子，再提高相应的路径信息素含量。采用反向学习来优化路径上的信息素含量，能够很好地解决传统蚁群算法存在陷入局部最优、收敛速度慢等一些问题。

3.2 蚁群算法的其他应用

自蚁群算法被其他的研究者开发以来，已经被运用于很多其他的方面，如基于生产的多目标分配问题、集装箱经典分配问题、无人机的远距离调度问题、甚至还可以用于电力的用户规划，运用十分广泛。

孙新宇等[13]基于经典蚁群算法的基本特性和固有特点，对比了最优解算法、试探算法和循环改进算法对解决装配线问题，不能取得良好的结果之后，便对原有的蚁群算法进行改进和尝试，在原有的蚁群算法加入局部搜索的机制，利用了比较新颖的蚁群算法解决了混流装配线的调度问题。四川大学徐刚等[14]基于原有的算法模型对基本特征进行改进，引入了具有变异特征的蚁群算法，利用蚁群中的相互帮助、相互传递信息的机制寻找水库中的水分配的最优解，并且本方法较好地解决了动态规划中的水库群问题优化调度中的所特有的“维数”问题。除此之外，蚁群算法的运用对无人机的位置功能的规划也有帮助，柳长安[15]在文中利用蚁群算法不受搜索空间的限制约束和不必要求连续性和导数存在的假设的特点，在对无人机的动态航路的规划中有良好的路径规划特性，并提出了改进的蚁群算法，解决了多架无人机的路径规划问题。在配电网的调度规划问题中，王志刚等[16]以配电网中的综合使用费用和过负荷惩罚费最小为目的，提出了一种网架规划的数学模型，把每只蚂蚁作为一个线路集合，最后形成一个规划方案，有效说明了蚁群算法在配电网的调度规划问题中的可行性。同时，东南大学的陈歆技等[17]将线路中的故障定位问题转化为一种新型的TSP问题，并且采用电力系统中的分级保护的原理对整个配电网进行区分，最后借助蚁群算法进行局部优化，最后较好地解决了配电的故障问题。

4 改进蚁群算法在机器人应用中的未来展望

随着蚁群算法的不断改进与发展，蚁群算法已经能在很多领域进行应用。在未来，蚁群算法与其他各种智能算法结合的改进型蚁群算法将被多次利用并且运用于解决实际问题。但是与其他智能算法相比，蚁群算法还不成熟，蚁群算法的运用还有很长一段时间，仍需要更多的研究者去发掘和运用。同时，蚁群算法的收敛性问题虽然被众多学者解决，但是如何权衡收敛速度和收敛次数的矛盾是最主要的问题。