分组教学蚁群算法改进及其在机器人路径规划中应用

蒲兴成，宋欣琳

（1.重庆邮电大学 计算机科学与技术学院，重庆 400065;2.重庆邮电大学 理学院，重庆 400065）

路径规划是机器人导航基础技术之一[1-4]。传统路径规划算法有Dijkstra 算法[5]，A*算法[6]等，这些算法是基于图搜索路径规划算法。随着算法理论发展，基于智能优化路径规划算法被广泛应用于移动机器人路径避障与导航。所谓智能优化算法就是通过模拟自然界中种群各种自发行为来获得优化问题最优解。蚁群算法作为经典智能优化算法，因其正反馈性和并行性等优势，被广泛应用于移动机器人路径规划问题中[7-9]。但同时，该算法也存在收敛速度慢和易陷入局部最优等缺陷。

针对上述蚁群算法存在的缺陷，许多学者基于标准蚁群算法做出了大量改进工作。蚁群算法改进大致分为两大类。一类是针对蚁群算法自身模型进行改进[10-14]。Gao 等[10]提出一种新的路径搜索策略。该策略将蚁群分为两部分，并将这两部分分别置于环境起点与终点。该算法通过双向搜索寻找最优路径，从而提高收敛速度和精度。在Lin 等[11]针对环境中U 型障碍死锁问题，设计一个自适应启发式函数，避免蚂蚁路径搜索的初始盲目性和后期单一性。Li 等[12]通过添加自适应函数改变蚁群状态转移概率，并结合精英蚂蚁和交叉选择路径节点，有效提高算法收敛速度。Pu 等[13]提出一种信息素增量计算方法，提高了算法收敛速度。梁凯等[14]为有效提高路径规划精度，提出一种基于中心节点替换平滑算法。另一类就是在蚁群算法的基础上，结合其他算法的优势弥补蚁群算法的不足[15-20]。Qin[15]提出一基于生物免疫系统行为自适应蚁群算法，这种混合算法能增加可行解的多样性。Yu[16]合粒子群与蚁群算法的特点，赋予蚁群一个“粒子”特性，通过粒子群算法改变蚁群位置，从而提高蚁群算法收敛速度。Dai 等[17]利用A*算法改善蚁群算法适应度函数，从而有效提高蚁群算法路径搜索能力。Zhu 等[18]利用人工势场算法改进蚁群算法适应度函数。这种改进算法能同时兼顾负反馈与自适应度函数的调节，因而该方法能大大加快算法收敛速度。Wu等[19]提出了一种混合蚁群算法，该算法通过对可行路径交叉变异，增加了解的多样性，为带时间窗车辆路由问题解决提供了新的思路。Tao 等[20]结合模糊控制，分阶段调整蒸发速率改进蚁群算法，以保证蚁群的全局搜索能力。

虽然上述各种改进策略能在一定程度上改善蚁群算法本身不足，但蚁群算法收敛速度慢和易陷入局部最优缺陷仍难以根本解决。此外，基于改进蚁群算法机器人路径规划过多依赖控制参数调整。针对上述问题，本文提出一种基于分组教学优化算法[21]（group teaching optimization algorithm,GTOA）的改进蚁群算法，并将改进算法应用于机器人路径规划。GTOA 是一种启发式随机群智能算法，该算法模拟课堂教学过程中教师与学生互动影响，从而提升种群整体优化能力，使所有进化个体更快收敛到全局最优解。该算法所需控制参数不涉及优化过程本身，能简化算法初始设置步骤。GTOA 这一特性可以很好弥补蚁群算法缺点。因此，将蚁群算法与分组教学优化算法相结合，通过改进信息素更新策略和死锁回退策略，并引入路径简化算子，可以有效解决蚁群算法收敛速度慢和易陷入局部最优自身缺陷。数值对比实验证明该改进算法能有效提高收敛速度以及移动机器人路径搜索能力。

1 基于分组教学优化蚁群算法改进

1.1 标准蚁群算法

蚁群算法作为群智能优化算法中经典算法之一，最早由意大利学者Dorigo 等[22-23]于20 世纪90年代提出。蚂蚁觅食主要依据寻路途中分泌的信息素浓度决定自己爬行方向。距离越短的路径，相同时间里蚂蚁经过的数量越多，路径信息素浓度就越高，蚁群就更有可能选择该路径。蚁群算法就是通过模拟蚂蚁觅食行为寻找最优路径。在标准蚁群算法中，蚂蚁根据随机状态转移概率[23]选择下一路径节点，随机状态转移概率公式为

式中：α是信息素启发因子，控制路径信息素的相对重要性；β是期望启发式因子，控制路径节点距离的相对重要性；τij(t)是t时刻i、j两点间的信息素浓度；dij是i、j两点间欧氏距离；ηij(t)是i、j两点间距离倒数。所有蚂蚁完成一次寻路后，需对蚂蚁经过的所有路径进行信息素更新[23]：

式中：ρ是信息素挥发系数；Δτij是本次寻路 后i、j两点间信息素更新的增量；Q是常数，代表信息素强度；Lk是第k只蚂蚁在本次寻路中爬行过的路径长度；Pathk是第k只蚂蚁在本次迭代中搜索到的可行路径节点。

1.2 蚁群算法的改进

传统蚁群算法在迭代前期，路径上信息素浓度差别不大，蚂蚁在选择下一爬行节点时概率几乎是随机的。在迭代后期，某些路径节点信息素浓度过高，蚂蚁大概率选择相同节点爬行。这直接导致了蚁群算法收敛速度慢和易陷入局部最优问题产生。针对这两个主要不足，本文结合分组教学优化算法优点改进标准蚁群算法，即赋予蚁群一个代表寻路能力参数，将该参数用于优化传统蚁群算法适应度函数，从而改善蚁群全局路径规划能力，避免算法陷入局部最优。另一方面，由于分组教学优化算法除了种群参数需要设置以外，算法中个体优化不依赖于其他参数调整，因此与分组教学优化算法结合的改进蚁群算法也能加快算法收敛速度。此外，改进死锁回退策略，既能够保证每一次迭代单个个体都能进行路径搜索操作，也能提高地图实时更新能力。同时，将U 型死锁位置标记为障碍，能避免算法发生停滞。值得一提的是，为使算法性能更优，本文进一步改进了信息素更新策略，将标准蚁群算法固定参数调整为与蚁群搜索相关动态参数，有针对性地引导蚁群寻找最优路径；路径简化算子的引进，能有效将路径上的冗余转角简化为直线路径，实现提高路径优化精度的目标。下面将结合分组教学、蚁群回退机制、信息素更新策略和路径简化算子等方面具体介绍改进策略。

1.2.1 基于分组教学优化算法蚁群算法改进

GTOA[21]是一种启发式随机群智能算法，该算法具有较强自适应寻优能力。基于此，为提高蚁群算法全局优化能力和收敛速度，本文在蚁群算法的基础上引进GTOA。为避免蚁群适应度函数只单纯受到达目标点的距离控制，导致蚁群算法易陷入局部最优，先为蚁群添加一个代表寻路能力的自适应参数（以下将该参数简称为“寻路能力”）。此外，在教学阶段，通过比较GTOA 评价函数，蚂蚁按照改进后的适应度函数与随机状态转移概率选择下一路径节点，最后完成种群整合等。下面将逐一给出具体操作。

1) 基于改进评价函数的分组教学优化算法

评价函数主要用于评估蚂蚁在路径搜索过程中表现，为使GTOA 适用于蚁群算法，需将GTOA评价函数修改成蚁群个体与路径长度相关函数，修改后的评价函数为

式中：xk(t) 为蚂蚁k在t时刻寻路能力，minLk为蚂蚁k寻找到最短路径长度。由评价函数可知，蚂蚁个体搜索到的路径长度越短，个体评价就越高，因此，该个体通过学习获得寻路能力越强。

2) 基于改进适应度函数的蚁群算法

为提升蚁群全局优化能力，本文结合GTOA 教学阶段[13]来影响蚁群中蚂蚁个体寻路能力xk(t)。首先，按照蚂蚁寻路能力高低，将蚁群划分为精英和普通子群，将寻路能力最高蚂蚁升级为教师蚂蚁。然后，基于GTOA 模仿课堂教与学思想，在教师阶段，针对精英子群和普通子群采用不同学习方式，通过向教师蚂蚁学习以增强个体寻路能力。不仅如此，在学习阶段，每只蚂蚁在每一轮迭代中通过自学和随机向蚁群另一只蚂蚁学习，达到增强个体寻路能力目的，并通过比较评价函数确定蚂蚁在教学阶段后的最终寻路能力。结合蚂蚁到目标点距离dij以及蚂蚁寻路能力xk(t)，蚁群算法适应度函数 ηij(t)进一步改进为

改进适应度函数通过xk(t)自适应调整蚁群路径选择概率。当蚁群距终点较远时，dij较大，蚁群路径选择概率差异较大。xk(t)可以缩小各条路径被选择概率，避免算法陷入局部最优。当蚁群接近终点时，dij较小，路径选择概率趋近相同。xk(t)可以扩大各条路径选择概率，加快蚁群算法收敛，同时也保证蚁群算法求解的多样性。

3) 种群整合

经过GTOA 教学阶段学习，蚂蚁个体间寻路能力在各个子群都具备一定差异。根据蚂蚁寻路能力降序排列将两个子群整合，并重新划分子群，用于下一轮迭代。以此保证在每次迭代中，同时提升精英子群和普通子群蚂蚁寻路能力，最终提升整个蚁群寻路能力。蚁群重新整合划分后，选择寻路能力最强蚂蚁作为下一轮迭代教师蚂蚁，其选择公式为

此外，在分组教学过程中某些蚂蚁寻路能力过高或过低，或致使算法陷入局部最优。因此对蚂蚁寻路能力值设置一个阈值区间 [Antmin,Antmax]，将超过此阈值区间蚂蚁个体寻路能力值设置为该区间边界值。

1.2.2 蚁群回退机制

传统蚁群算法无法规避U 型障碍，导致算法易陷入停滞状态，因此可在该类障碍处用回退机制避免此类问题。Lin 等[11]过建立额外全局和局部禁忌表来标记可能产生死锁节点位置。任红格等[24]提出直接让陷入死锁蚂蚁“死亡”，即跳过此轮迭代搜索过程，直接返回起点。上述回退机制存在计算量大或者可行解减少等问题。为克服此缺陷，本文提出一种新回退机制，即当蚂蚁陷入U型障碍时，将该蚂蚁所处节点直接标记为地图上障碍节点并实时更新地图，然后将蚂蚁回退到路径上一节点重新进行路径选择，重复此操作直到另一可达节点出现时结束回退。通过回退机制将U型障碍填充为矩形障碍，从而避免后续蚂蚁再次陷入同一U 型障碍，因此能提高算法收敛速度。

1.2.3 信息素更新改进策略

传统蚁群算法信息素更新策略中，蚂蚁经过的所有路径均采用相同的信息素更新强度。当蚁群完成一轮迭代后，所有可行路径Lk信息素更新增量相同，这就导致传统蚁群算法路径搜索的盲目性增大，蚂蚁无法快速锁定长度更短的路径。因此，在改进的信息素更新策略中，增加一个动态累加参数cij，增强蚁群寻找最优路径的引导作用。cij用于记录Lk成为当前最短路径迭代轮数，即累加最优路径信息素浓度，当Lk为当前最短路径时，cij将加1。此外，将Lk分别与当前局部最优路径Llocal和全局最优路径Lglobal进行比较。根据比较结果，对可行路径信息素浓度采用分级更新强度Q1和Q2。一般来讲，Q2>Q1,本文中，Q2数值为Q1数值的两倍。这样能使得Lglobal路径节点信息素增量更大，进一步扩大全局最优路径在后续迭代中对蚁群路径搜索引导作用，同时也能避免由于Q1导致的蚁群陷入局部最优。改进信息素具体更新为

改进信息素更新策略引导蚁群往最优路径方向搜索，可以进一步加快算法收敛速度，增强算法性能。

1.2.4 路径简化算子

若路径存在过多角度较小转角，则机器人在移动过程中可能会出现失去平衡现象。此外，通过蚁群算法迭代规划出的路径如果存在大量转角，该路径就不一定是最优路径。因此，如何消除冗余转角是路径规划时必须考虑的一个问题。路径简化算子[17]根据三角形两边之和大于第三边原理消除冗余转角。改进路径简化算子根据路径中相邻3 个节点构成的夹角角度进行路径简化。若夹角内节点为可达节点，则将该转角简化为直线路径。因此，路径简化算子不仅可以缩短路径长度，而且可以增大转角角度，让机器人运动更加平滑。如图1（a）与图1（b）中分别为存在90°冗余转角的两种情况，图1（c）中存在45°冗余转角。通过简化算子分别简化为图2（a）、图2（b）和图2（c）中的路径。

图1 3 种冗余转角Fig.1 Three redundant corners

图2 3 种冗余转角简化路段Fig.2 Three redundant corner simplified sections

为说明路径简化算子有效性，表1 给出了10 次对比实验。根据表1 实验数据可知，路径简化算子可以大幅度提高求解最优路径精度。

表1 路径简化算子实验数据Table 1 Experimental data of path simplification operator

1.3 基于GTOA 改进蚁群算法步骤与流程

基于GTOA 改进蚁群算法主要有如下7 步。

1)初始蚁群规模M，迭代次数K，参数 α,β等，将蚁群划分为精英与普通两个子群；

2)蚂蚁个体向教师蚂蚁学习，通过评价函数评估教师阶段最终寻路能力；

3)根据随机状态转移概率与改进后适应度函数，选择下一路径节点，并判断是否需要启动回退机制；

4)蚁群通过自学和随机向一只蚂蚁学习，通过评价函数确定学习阶段最终寻路能力；

5)更新蚂蚁经过路径的信息素；

6)将两个子群整合为一个种群，按照能力大小再次划分为精英与普通两个子群，选择寻路能力最强蚂蚁作为下一次迭代教师蚂蚁；

7)判断是否达到迭代终止条件：若达到迭代终止条件，则采用路径简化算子输出最佳路径；反之则跳转至步骤2)继续求解。

基于分组教学的改进 蚁群算法流程如图3。

图3 基于分组教学的改进蚁群算法流程Fig.3 Flow of improved ant colony algorithm based on group teaching

2 数值对比实验

在数值对比实验中，使用栅格法进行环境建模，将地图中不规则障碍扩充为矩形障碍，将移动机器人抽象为一个点。将改进蚁群算法（group teaching ant colony algorithm,GTACO）与传统蚁群算法（ant colony algorithm,ACO）、改进蚁群算法[24]（improved ant colony algorithm,I-ACO）、混合蚁群算法[25]（improved ant colony algorithm with shuffled frog leaping algorithm,IACO-SFLA）进行仿真模拟实验对比，在求解精度（最优路径长度）、收敛速度（迭代次数）和算法运行时间3 个方面验证GTACO的优越性能。

在20×20 栅格地图[24]中，将GTACO 与ACO、I-ACO、IACO-SFLA 进行比较。地图中黑色栅格代表障碍物，白色栅格代表可达节点。地图左上角为机器人起点，右下角为终点，寻找一条无碰撞的最优路径。为确保对比实验严谨，4 种算法所包含共同参数设定为相同值[24]，参数值设置如表2。实验数据统计如表3。4 种算法迭代次数收敛曲线趋势对比以及GTACO 最优路径分别如图4、图5。

表2 对比实验参数设置Table 2 Comparison experiment parameter settings

表3 4 种算法数据对比Table 3 Data comparison of four algorithms

图4 4 种算法迭代曲线对比图Fig.4 Comparison of iterative curves of four algorithms

图5 GTACO 最优路径图Fig.5 GTACO optimal path planning

表3 和图4、图5 中实验结果表明，ACO、I-ACO无法求解出最优路径，IACO-SFLA 和GTACO 均能求解出从起点到终点最优路径。其中GTACO能在较少的迭代次数中达到收敛状态，相较于IACO-SFLA，GTACO 能在更短时间完成规定迭代次数并求解出最优路径。

为进一步验证GTACO 的优越性，采用更复杂40×40 栅格地图。因实验地图规模变大，为使算法实验效果达到最佳，扩大K和M的值为100。4 种算法最优路径长度、迭代次数和运行时间对比如表4。4 种算法的迭代次数收敛曲线趋势对比如图6。图7 为GTACO 最优路径图。表4 和图6 中实验结果表明，在对比实验使用的4 种算法中，I-ACO、IACO-SFLA 与GTACO 在规定迭代次数中达到收敛状态，且GTACO 较IACO-SFLA计算出的路径精度更高，收敛速度更快，算法运行时间也更短。

表4 4 种算法数据对比Table 4 Data comparison of four algorithms

图6 4 种算法迭代曲线对比图Fig.6 Comparison of iterative curves of four algorithms

图7 GTACO 最优路径图Fig.7 GTACO optimal path planning

表2～4 和图4～7 表明，基于分组教学改进蚁群算法（GTACO）的移动机器人路径规划能力与基于ACO、I-ACO 和IACO-SFLA 移动机器人路径规划能力相比，无论在精确度还是在收敛速度方面都有改善。通过仿真模拟实验验证，本文提出的改进蚁群算法适用于移动机器人路径规划。

3 结束语

针对蚁群算法在移动机器人路径规划中存在收敛速度慢和易陷入局部最优问题，提出了一种基于分组教学优化改进蚁群算法。改进算法结合分组教学优化与蚁群算法优点，即利用分组教学优化算法的整体优化特性，通过蚁群中蚂蚁个体之间相互影响，提高蚁群算法全局求解能力，避免算法过早陷入局部最优。该改进算法充分利用分组教学优化算法不依赖过多参数特性，避免路径搜索能力不过于依赖多个参数，从而加速算法收敛速度。回退机制的改进能进一步避免算法在U 型障碍处陷入停滞，达到提高蚁群搜索可行解多样性。此外，新的信息素更新策略能强化蚁群更趋向更短路径，因此更能提高蚁群算法收敛速度。最后，路径简化算子能更进一步缩短蚁群路径，增大转弯角度，也更易于移动机器人平滑稳定运动。仿真对比实验证明移动机器人能通过改进算法有效规划可行路径，缩短算法运行时间，即提高求解路径精度和算法收敛速度。接下来，将进一步基于改进蚁群算法在障碍物不规则或受到随机干扰时研究机器人路径规划。