第4期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·765· 用于移动机器人路径避障与导航。所谓智能优化 机群智能算法，该算法模拟课堂教学过程中教师 算法就是通过模拟自然界中种群各种自发行为来 与学生互动影响，从而提升种群整体优化能力， 获得优化问题最优解。蚁群算法作为经典智能优 使所有进化个体更快收敛到全局最优解。该算法 化算法，因其正反馈性和并行性等优势，被广泛 所需控制参数不涉及优化过程本身，能简化算法 应用于移动机器人路径规划问题中。但同时， 初始设置步骤。GTOA这一特性可以很好弥补蚁 该算法也存在收敛速度慢和易陷入局部最优等 群算法缺点。因此，将蚁群算法与分组教学优化 缺陷。 算法相结合，通过改进信息素更新策略和死锁回 针对上述蚁群算法存在的缺陷，许多学者基 退策略，并引入路径简化算子，可以有效解决蚁 于标准蚁群算法做出了大量改进工作。蚁群算法 群算法收敛速度慢和易陷人局部最优自身缺陷。 改进大致分为两大类。一类是针对蚁群算法自身 数值对比实验证明该改进算法能有效提高收敛速 模型进行改进o.1。Gao等o提出一种新的路径 度以及移动机器人路径搜索能力。 搜索策略。该策略将蚁群分为两部分，并将这两 部分分别置于环境起点与终点。该算法通过双向 1基于分组教学优化蚁群算法改进 搜索寻找最优路径，从而提高收敛速度和精度。 1.1 标准蚁群算法 在Lin等)针对环境中U型障碍死锁问题，设计 蚁群算法作为群智能优化算法中经典算法之 一个自适应启发式函数，避免蚂蚁路径搜索的初始 一，最早由意大利学者Dorig0等m-2]于20世纪90 盲目性和后期单一性。Li等通过添加自适应函 年代提出。蚂蚁觅食主要依据寻路途中分泌的信 数改变蚁群状态转移概率，并结合精英蚂蚁和交 息素浓度决定自己爬行方向。距离越短的路径， 叉选择路径节点，有效提高算法收敛速度。P等町 相同时间里蚂蚁经过的数量越多，路径信息素浓 提出一种信息素增量计算方法，提高了算法收敛 度就越高，蚁群就更有可能选择该路径。蚁群算 速度。梁凯等为有效提高路径规划精度，提出 法就是通过模拟蚂蚁觅食行为寻找最优路径。在 一种基于中心节点替换平滑算法。另一类就是在 标准蚁群算法中，蚂蚁根据随机状态转移概率2 蚁群算法的基础上，结合其他算法的优势弥补蚁 选择下一路径节点，随机状态转移概率公式为 群算法的不足1s-20。Qin提出一基于生物免疫 号(0)() je allowed 系统行为自适应蚁群算法，这种混合算法能增加 (0() 可行解的多样性。Yu16合粒子群与蚁群算法的 特点，赋予蚁群一个“粒子”特性，通过粒子群算 其他 1 法改变蚁群位置，从而提高蚁群算法收敛速度。 (0= d Dai等利用A*算法改善蚁群算法适应度函数， 式中：α是信息素启发因子，控制路径信息素的相 从而有效提高蚁群算法路径搜索能力。Zhu等l) 对重要性；B是期望启发式因子，控制路径节点距 利用人工势场算法改进蚁群算法适应度函数。这 离的相对重要性；t)是时刻i、j两点间的信息素 种改进算法能同时兼顾负反馈与自适应度函数的 浓度；d是i、两点间欧氏距离；()是i、两点间 调节，因而该方法能大大加快算法收敛速度。Wu 距离倒数。所有蚂蚁完成一次寻路后，需对蚂蚁 等提出了一种混合蚁群算法，该算法通过对可 经过的所有路径进行信息素更新： 行路径交叉变异，增加了解的多样性，为带时间 T(t+m）=pT(0)+△t 窗车辆路由问题解决提供了新的思路。Tao等o1 _∫Q/Lk,i.je Pathe 结合模糊控制，分阶段调整蒸发速率改进蚁群算 △=0，其他 法，以保证蚁群的全局搜索能力。 式中：P是信息素挥发系数；△t是本次寻路后i 虽然上述各种改进策略能在一定程度上改善 两点间信息素更新的增量；Q是常数，代表信息 蚁群算法本身不足，但蚁群算法收敛速度慢和易 素强度；L是第k只蚂蚁在本次寻路中爬行过的路 陷入局部最优缺陷仍难以根本解决。此外，基于 径长度；Path是第k只蚂蚁在本次迭代中搜索到的 改进蚁群算法机器人路径规划过多依赖控制参数 可行路径节点。 调整。针对上述问题，本文提出一种基于分组教 1.2蚁群算法的改进 学优化算法2(group teaching optimization al- 传统蚁群算法在迭代前期，路径上信息素浓 gorithm,GTOA)的改进蚁群算法，并将改进算法 度差别不大，蚂蚁在选择下一爬行节点时概率几 应用于机器人路径规划。GTOA是一种启发式随 乎是随机的。在迭代后期，某些路径节点信息素用于移动机器人路径避障与导航。所谓智能优化 算法就是通过模拟自然界中种群各种自发行为来 获得优化问题最优解。蚁群算法作为经典智能优 化算法，因其正反馈性和并行性等优势，被广泛 应用于移动机器人路径规划问题中[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 al￾gorithm, GTOA）的改进蚁群算法，并将改进算法 应用于机器人路径规划。GTOA 是一种启发式随 机群智能算法，该算法模拟课堂教学过程中教师 与学生互动影响，从而提升种群整体优化能力， 使所有进化个体更快收敛到全局最优解。该算法 所需控制参数不涉及优化过程本身，能简化算法 初始设置步骤。GTOA 这一特性可以很好弥补蚁 群算法缺点。因此，将蚁群算法与分组教学优化 算法相结合，通过改进信息素更新策略和死锁回 退策略，并引入路径简化算子，可以有效解决蚁 群算法收敛速度慢和易陷入局部最优自身缺陷。 数值对比实验证明该改进算法能有效提高收敛速 度以及移动机器人路径搜索能力。 1 基于分组教学优化蚁群算法改进 1.1 标准蚁群算法 蚁群算法作为群智能优化算法中经典算法之 一，最早由意大利学者 Dorigo 等 [22-23] 于 20 世纪 90 年代提出。蚂蚁觅食主要依据寻路途中分泌的信 息素浓度决定自己爬行方向。距离越短的路径， 相同时间里蚂蚁经过的数量越多，路径信息素浓 度就越高，蚁群就更有可能选择该路径。蚁群算 法就是通过模拟蚂蚁觅食行为寻找最优路径。在 标准蚁群算法中，蚂蚁根据随机状态转移概率[23] 选择下一路径节点，随机状态转移概率公式为 P k i j =    τ α i j(t)η β i j(t) ∑ s∈allowedk τ α is (t)η β is (t) , j ∈ allowedk 0, 其他ηi j(t) = 1 di j α β τi j(t) t i j di j i j ηi j(t) i j 式中： 是信息素启发因子，控制路径信息素的相 对重要性； 是期望启发式因子，控制路径节点距 离的相对重要性； 是 时刻 、 两点间的信息素 浓度； 是 、 两点间欧氏距离； 是 、 两点间 距离倒数。所有蚂蚁完成一次寻路后，需对蚂蚁 经过的所有路径进行信息素更新[23] ： τi j(t+n) = ρ · τi j(t)+ ∆τi j ∆τi j = { Q/Lk , i, j ∈ Pathk 0, 其他 ρ ∆τi j i j Q Lk k Pathk k 式中： 是信息素挥发系数； 是本次寻路后 、 两点间信息素更新的增量； 是常数，代表信息 素强度； 是第 只蚂蚁在本次寻路中爬行过的路 径长度； 是第 只蚂蚁在本次迭代中搜索到的 可行路径节点。 1.2 蚁群算法的改进 传统蚁群算法在迭代前期，路径上信息素浓 度差别不大，蚂蚁在选择下一爬行节点时概率几 乎是随机的。在迭代后期，某些路径节点信息素 第 4 期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·765·