第17卷第4期 智能系统学报 Vol.17 No.4 2022年7月 CAAI Transactions on Intelligent Systems Jul.2022 D0:10.11992/tis.202108020 网络出版地址：https:/kns.cnki.net/kcms/detail/23.1538.TP.20220518.0930.002.html 分组教学蚁群算法改进及其在机器人路径规划中应用 蒲兴成2，宋欣琳 (1.重庆邮电大学计算机科学与技术学院，重庆400065,2.重庆邮电大学理学院，重庆400065) 摘要：针对蚁群算法收敛速度慢、易陷入局部最优问题，提出一种基于分组教学优化改进蚁群算法。该算法 从3个角度对蚁群算法进行改进。首先，利用分组教学优化算法改进蚁群算法适应度函数，提高算法全局求解 能力。同时，引进一种新的回退策略，通过该策略处理U型障碍死锁问题，确保算法求解可行性。其次，采用 一种新的动态信息素更新策略，滚动更新每轮迭代后路径信息素值，避免算法陷入局部最优。最后，引入路径 简化算子，将冗余角简化为直线路径，缩短路径长度。仿真实验证明改进算法能有效提高移动机器人路径规划 收敛速度和精度。 关键词：改进蚁群算法：分组教学优化：路径规划：移动机器人：信息素更新：启发式函数：路径简化：回退策略 中图分类号：TP273文献标志码：A文章编号：1673-4785(2022)04-0764-08 中文引用格式：蒲兴成，宋欣琳.分组教学蚊群算法改进及其在机器人路径规中应用八.智能系统学报，2022,17(4)： 764-771. 英文引用格式：PU Xingcheng,.SONG Xinlin.Improvement of ant colony algorithm in group teaching and its application in robot path planning[J].CAAI transactions on intelligent systems,2022,17(4):764-771. Improvement of ant colony algorithm in group teaching and its application in robot path planning PU Xingcheng2,SONG Xinlin' (1.School of Computer Science and Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065, China;2.School of Science,Chongging University of Posts and Telecommunications,Chongqing 400065,China) Abstract:To solve the problems of slow convergence speed and easily falling into local optimization,a novel improved ant colony algorithm is proposed based on a group teaching optimal algorithm(GTACO).The improved ant colony al- gorithm is optimized in three aspects.Firstly,the group teaching optimization algorithm is used to improve the fitness function of the ant colony algorithm to enhance the searching ability of global solutions.Simultaneously,a new fallback strategy is designed to deal with the U-shaped deadlock and ensure the feasibility of the solution.Secondly,a novel up- dating strategy for dynamic pheromones is adopted to avoid falling into local optimization of the algorithm by updating the path pheromone value after each iteration.Finally,the simplification operator of the path is applied to shorten the length of the path by simplifying the redundant corners into linear paths.Simulation experiments show that the im- proved algorithm can effectively increase the ability of path planning in convergence speed and accuracy for mobile ro- bots. Keywords:improved ant colony algorithm;group teaching optimization;path planning;mobile robot;pheromone up- date:heuristic function;path simplification;regression strategy 路径规划是机器人导航基础技术之一。传 收稿日期：2021-08-17.网络出版日期：2022-05-18. 基金项目：国家自然科学基金项目(61876200)：重庆市科委项 统路径规划算法有Dijkstra算法，A*算法等， 目(cstc2018 jeyjyAX0112):重庆市教委科研项目 (J2014032). 这些算法是基于图搜索路径规划算法。随着算法 通信作者：蒲兴成.E-mail:puxc@cqupt..edu.cnm 理论发展，基于智能优化路径规划算法被广泛应
DOI: 10.11992/tis.202108020 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20220518.0930.002.html 分组教学蚁群算法改进及其在机器人路径规划中应用 蒲兴成1,2，宋欣琳1 （1. 重庆邮电大学 计算机科学与技术学院，重庆 400065; 2. 重庆邮电大学 理学院，重庆 400065） 摘 要：针对蚁群算法收敛速度慢、易陷入局部最优问题，提出一种基于分组教学优化改进蚁群算法。该算法 从 3 个角度对蚁群算法进行改进。首先，利用分组教学优化算法改进蚁群算法适应度函数，提高算法全局求解 能力。同时，引进一种新的回退策略，通过该策略处理 U 型障碍死锁问题，确保算法求解可行性。其次，采用 一种新的动态信息素更新策略，滚动更新每轮迭代后路径信息素值，避免算法陷入局部最优。最后，引入路径 简化算子，将冗余角简化为直线路径，缩短路径长度。仿真实验证明改进算法能有效提高移动机器人路径规划 收敛速度和精度。 关键词：改进蚁群算法；分组教学优化；路径规划；移动机器人；信息素更新；启发式函数；路径简化；回退策略 中图分类号：TP273 文献标志码：A 文章编号：1673−4785(2022)04−0764−08 中文引用格式：蒲兴成, 宋欣琳. 分组教学蚁群算法改进及其在机器人路径规划中应用 [J]. 智能系统学报, 2022, 17(4): 764–771. 英文引用格式：PU Xingcheng, SONG Xinlin. Improvement of ant colony algorithm in group teaching and its application in robot path planning[J]. CAAI transactions on intelligent systems, 2022, 17(4): 764–771. Improvement of ant colony algorithm in group teaching and its application in robot path planning PU Xingcheng1,2 ，SONG Xinlin1 (1. School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China; 2. School of Science, Chongqing University of Posts and Telecommunications, Chongqing 400065, China) Abstract: To solve the problems of slow convergence speed and easily falling into local optimization, a novel improved ant colony algorithm is proposed based on a group teaching optimal algorithm (GTACO). The improved ant colony algorithm is optimized in three aspects. Firstly, the group teaching optimization algorithm is used to improve the fitness function of the ant colony algorithm to enhance the searching ability of global solutions. Simultaneously, a new fallback strategy is designed to deal with the U-shaped deadlock and ensure the feasibility of the solution. Secondly, a novel updating strategy for dynamic pheromones is adopted to avoid falling into local optimization of the algorithm by updating the path pheromone value after each iteration. Finally, the simplification operator of the path is applied to shorten the length of the path by simplifying the redundant corners into linear paths. Simulation experiments show that the improved algorithm can effectively increase the ability of path planning in convergence speed and accuracy for mobile robots. Keywords: improved ant colony algorithm; group teaching optimization; path planning; mobile robot; pheromone update; heuristic function; path simplification; regression strategy 路径规划是机器人导航基础技术之一[1-4]。传 统路径规划算法有 Dijkstra 算法[5] ，A*算法[6] 等， 这些算法是基于图搜索路径规划算法。随着算法 理论发展，基于智能优化路径规划算法被广泛应 收稿日期：2021−08−17. 网络出版日期：2022−05−18. 基金项目：国家自然科学基金项目（61876200）；重庆市科委项 目 （cstc2018jcyjyAX0112）；重庆市教委科研项目 （J2014032）. 通信作者：蒲兴成. E-mail: puxc@cqupt.edu.cn. 第 17 卷第 4 期 智 能 系 统 学 报 Vol.17 No.4 2022 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2022
第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 algorithm, 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·
·766· 智能系统学报 第17卷 浓度过高，蚂蚁大概率选择相同节点爬行。这直 2)基于改进适应度函数的蚁群算法 接导致了蚁群算法收敛速度慢和易陷入局部最优 为提升蚁群全局优化能力，本文结合GTOA教 问题产生。针对这两个主要不足，本文结合分组 学阶段]来影响蚁群中蚂蚁个体寻路能力x()。 教学优化算法优点改进标准蚁群算法，即赋予蚁 首先，按照蚂蚁寻路能力高低，将蚁群划分为精 群一个代表寻路能力参数，将该参数用于优化传 英和普通子群，将寻路能力最高蚂蚁升级为教师 统蚁群算法适应度函数，从而改善蚁群全局路径 蚂蚁。然后，基于GTOA模仿课堂教与学思想，在 规划能力，避免算法陷入局部最优。另一方面， 教师阶段，针对精英子群和普通子群采用不同学 由于分组教学优化算法除了种群参数需要设置以 习方式，通过向教师蚂蚁学习以增强个体寻路能 外，算法中个体优化不依赖于其他参数调整，因 力。不仅如此，在学习阶段，每只蚂蚁在每一轮 此与分组教学优化算法结合的改进蚁群算法也能 迭代中通过自学和随机向蚁群另一只蚂蚁学习， 加快算法收敛速度。此外，改进死锁回退策略， 达到增强个体寻路能力目的，并通过比较评价函 既能够保证每一次迭代单个个体都能进行路径搜 数确定蚂蚁在教学阶段后的最终寻路能力。结合 索操作，也能提高地图实时更新能力。同时，将 蚂蚁到目标点距离d以及蚂蚁寻路能力x(①，蚁 U型死锁位置标记为障碍，能避免算法发生停滞。 群算法适应度函数()进一步改进为 值得一提的是，为使算法性能更优，本文进一步 1 改进了信息素更新策略，将标准蚁群算法固定参 0=d×回 数调整为与蚁群搜索相关动态参数，有针对性地 改进适应度函数通过()自适应调整蚁群路 引导蚁群寻找最优路径；路径简化算子的引进， 径选择概率。当蚁群距终点较远时，d较大，蚁群 能有效将路径上的冗余转角简化为直线路径，实 路径选择概率差异较大。x()可以缩小各条路径 现提高路径优化精度的目标。下面将结合分组教 被选择概率，避免算法陷入局部最优。当蚁群接 学、蚁群回退机制、信息素更新策略和路径简化 近终点时，d较小，路径选择概率趋近相同。x() 算子等方面具体介绍改进策略。 可以扩大各条路径选择概率，加快蚁群算法收 1.2.1基于分组教学优化算法蚁群算法改进 敛，同时也保证蚁群算法求解的多样性。 GTOA2是一种启发式随机群智能算法，该 3)种群整合 经过GTOA教学阶段学习，蚂蚁个体间寻路 算法具有较强自适应寻优能力。基于此，为提高 能力在各个子群都具备一定差异。根据蚂蚁寻路 蚁群算法全局优化能力和收敛速度，本文在蚁群 算法的基础上引进GTOA。为避免蚁群适应度函 能力降序排列将两个子群整合，并重新划分子 数只单纯受到达目标点的距离控制，导致蚁群算 群，用于下一轮迭代。以此保证在每次迭代中， 同时提升精英子群和普通子群蚂蚁寻路能力，最 法易陷入局部最优，先为蚁群添加一个代表寻路 能力的自适应参数（以下将该参数简称为“寻路能 终提升整个蚁群寻路能力。蚁群重新整合划分 后，选择寻路能力最强蚂蚁作为下一轮迭代教师 力”)。此外，在教学阶段，通过比较GTOA评价 蚂蚁，其选择公式为 函数，蚂蚁按照改进后的适应度函数与随机状态 T(t+1)=max(x(t)) 转移概率选择下一路径节点，最后完成种群整合 此外，在分组教学过程中某些蚂蚁寻路能力 等。下面将逐一给出具体操作。 过高或过低，或致使算法陷入局部最优。因此对 1)基于改进评价函数的分组教学优化算法 蚂蚁寻路能力值设置一个阈值区间[Antmin,Antmax], 评价函数主要用于评估蚂蚁在路径搜索过程 将超过此阈值区间蚂蚁个体寻路能力值设置为该 中表现，为使GTOA适用于蚁群算法，需将GTOA 区间边界值。 评价函数修改成蚁群个体与路径长度相关函数， 1.2.2蚁群回退机制 修改后的评价函数为 传统蚁群算法无法规避U型障碍，导致算法 f()=0 易陷入停滞状态，因此可在该类障碍处用回退机 min L 制避免此类问题。Lin等u过建立额外全局和局 式中：(t)为蚂蚁k在t时刻寻路能力，minL为蚂蚁 部禁忌表来标记可能产生死锁节点位置。任红格 k寻找到最短路径长度。由评价函数可知，蚂蚁个 等2提出直接让陷入死锁蚂蚁“死亡”，即跳过此 体搜索到的路径长度越短，个体评价就越高，因 轮迭代搜索过程，直接返回起点。上述回退机制 此，该个体通过学习获得寻路能力越强。 存在计算量大或者可行解减少等问题。为克服此
浓度过高，蚂蚁大概率选择相同节点爬行。这直 接导致了蚁群算法收敛速度慢和易陷入局部最优 问题产生。针对这两个主要不足，本文结合分组 教学优化算法优点改进标准蚁群算法，即赋予蚁 群一个代表寻路能力参数，将该参数用于优化传 统蚁群算法适应度函数，从而改善蚁群全局路径 规划能力，避免算法陷入局部最优。另一方面， 由于分组教学优化算法除了种群参数需要设置以 外，算法中个体优化不依赖于其他参数调整，因 此与分组教学优化算法结合的改进蚁群算法也能 加快算法收敛速度。此外，改进死锁回退策略， 既能够保证每一次迭代单个个体都能进行路径搜 索操作，也能提高地图实时更新能力。同时，将 U 型死锁位置标记为障碍，能避免算法发生停滞。 值得一提的是，为使算法性能更优，本文进一步 改进了信息素更新策略，将标准蚁群算法固定参 数调整为与蚁群搜索相关动态参数，有针对性地 引导蚁群寻找最优路径；路径简化算子的引进， 能有效将路径上的冗余转角简化为直线路径，实 现提高路径优化精度的目标。下面将结合分组教 学、蚁群回退机制、信息素更新策略和路径简化 算子等方面具体介绍改进策略。 1.2.1 基于分组教学优化算法蚁群算法改进 GTOA[21] 是一种启发式随机群智能算法，该 算法具有较强自适应寻优能力。基于此，为提高 蚁群算法全局优化能力和收敛速度，本文在蚁群 算法的基础上引进 GTOA。为避免蚁群适应度函 数只单纯受到达目标点的距离控制，导致蚁群算 法易陷入局部最优，先为蚁群添加一个代表寻路 能力的自适应参数（以下将该参数简称为“寻路能 力”）。此外，在教学阶段，通过比较 GTOA 评价 函数，蚂蚁按照改进后的适应度函数与随机状态 转移概率选择下一路径节点，最后完成种群整合 等。下面将逐一给出具体操作。 1) 基于改进评价函数的分组教学优化算法 评价函数主要用于评估蚂蚁在路径搜索过程 中表现，为使 GTOA 适用于蚁群算法，需将 GTOA 评价函数修改成蚁群个体与路径长度相关函数， 修改后的评价函数为 f (x) = xk (t) minLk xk (t) k t minLk k 式中： 为蚂蚁 在 时刻寻路能力， 为蚂蚁 寻找到最短路径长度。由评价函数可知，蚂蚁个 体搜索到的路径长度越短，个体评价就越高，因 此，该个体通过学习获得寻路能力越强。 2) 基于改进适应度函数的蚁群算法 xk (t) di j xk (t) ηi j(t) 为提升蚁群全局优化能力，本文结合 GTOA 教 学阶段[13] 来影响蚁群中蚂蚁个体寻路能力 。 首先，按照蚂蚁寻路能力高低，将蚁群划分为精 英和普通子群，将寻路能力最高蚂蚁升级为教师 蚂蚁。然后，基于 GTOA 模仿课堂教与学思想，在 教师阶段，针对精英子群和普通子群采用不同学 习方式，通过向教师蚂蚁学习以增强个体寻路能 力。不仅如此，在学习阶段，每只蚂蚁在每一轮 迭代中通过自学和随机向蚁群另一只蚂蚁学习， 达到增强个体寻路能力目的，并通过比较评价函 数确定蚂蚁在教学阶段后的最终寻路能力。结合 蚂蚁到目标点距离 以及蚂蚁寻路能力 ，蚁 群算法适应度函数 进一步改进为 ηi j(t) = 1 di j × xk (t) xk (t) di j xk (t) di j xk (t) 改进适应度函数通过 自适应调整蚁群路 径选择概率。当蚁群距终点较远时， 较大，蚁群 路径选择概率差异较大。 可以缩小各条路径 被选择概率，避免算法陷入局部最优。当蚁群接 近终点时， 较小，路径选择概率趋近相同。 可以扩大各条路径选择概率，加快蚁群算法收 敛，同时也保证蚁群算法求解的多样性。 3) 种群整合 经过 GTOA 教学阶段学习，蚂蚁个体间寻路 能力在各个子群都具备一定差异。根据蚂蚁寻路 能力降序排列将两个子群整合，并重新划分子 群，用于下一轮迭代。以此保证在每次迭代中， 同时提升精英子群和普通子群蚂蚁寻路能力，最 终提升整个蚁群寻路能力。蚁群重新整合划分 后，选择寻路能力最强蚂蚁作为下一轮迭代教师 蚂蚁，其选择公式为 T (t+1) = max(xk (t)) [Antmin,Antmax] 此外，在分组教学过程中某些蚂蚁寻路能力 过高或过低，或致使算法陷入局部最优。因此对 蚂蚁寻路能力值设置一个阈值区间 ， 将超过此阈值区间蚂蚁个体寻路能力值设置为该 区间边界值。 1.2.2 蚁群回退机制 传统蚁群算法无法规避 U 型障碍，导致算法 易陷入停滞状态，因此可在该类障碍处用回退机 制避免此类问题。Lin 等 [11] 过建立额外全局和局 部禁忌表来标记可能产生死锁节点位置。任红格 等 [24] 提出直接让陷入死锁蚂蚁“死亡”，即跳过此 轮迭代搜索过程，直接返回起点。上述回退机制 存在计算量大或者可行解减少等问题。为克服此 ·766· 智 能 系 统 学 报 第 17 卷
第4期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·767· 缺陷，本文提出一种新回退机制，即当蚂蚁陷入U 转角。通过简化算子分别简化为图2(a)、图2(b) 型障碍时，将该蚂蚁所处节点直接标记为地图上 和图2(c)中的路径。 障碍节点并实时更新地图，然后将蚂蚁回退到路径 上一节点重新进行路径选择，重复此操作直到另 30 一可达节点出现时结束回退。通过回退机制将U 2.5 型障碍填充为矩形障碍，从而避免后续蚂蚁再次 2.0 陷入同一U型障碍，因此能提高算法收敛速度。 1.2.3信息素更新改进策略 1.0 传统蚁群算法信息素更新策略中，蚂蚁经过 的所有路径均采用相同的信息素更新强度。当蚁 0.5 群完成一轮迭代后，所有可行路径L信息素更新 0 0.5 1.0 1.5 2.0 2.5 3.0 增量相同，这就导致传统蚁群算法路径搜索的盲 x/m 目性增大，蚂蚁无法快速锁定长度更短的路径。 (a)90°转角 因此，在改进的信息素更新策略中，增加一个动态 30 累加参数c,增强蚁群寻找最优路径的引导作用。 25 c用于记录L成为当前最短路径迭代轮数，即累 2.0 加最优路径信息素浓度，当L为当前最短路径时， c将加1。此外，将L分别与当前局部最优路径 1.0 Loe和全局最优路径Lelob进行比较。根据比较结 果，对可行路径信息素浓度采用分级更新强度 0.5 Q和Q2。一般来讲，Q2>Q,本文中，Q2数值为Q数 0 0.51.01.52.02.53.0 值的两倍。这样能使得Lg路径节点信息素增量 x/cm (b)90°转角 更大，进一步扩大全局最优路径在后续迭代中对 蚁群路径搜索引导作用，同时也能避免由于Q导 3.0 致的蚁群陷人局部最优。改进信息素具体更新为 2.5 AT=CuQ.=Lca 2.0 CijQ2/Lk:Lt=Lgobal ∫c+l,Lk=minLe 夏15 c=c,其他 1.0 改进信息素更新策略引导蚁群往最优路径方 0.5 向搜索，可以进一步加快算法收敛速度，增强算 法性能。 0.51.01.52.02.53.0 x/cm 1.2.4路径简化算子 (c)45°转角 若路径存在过多角度较小转角，则机器人在 图13种冗余转角 移动过程中可能会出现失去平衡现象。此外，通 Fig.1 Three redundant corners 过蚁群算法迭代规划出的路径如果存在大量转 角，该路径就不一定是最优路径。因此，如何消 3.0 除冗余转角是路径规划时必须考虑的一个问题。 2.5 路径简化算子”根据三角形两边之和大于第三 2.0 边原理消除冗余转角。改进路径简化算子根据路 径中相邻3个节点构成的夹角角度进行路径简 复15 化。若夹角内节点为可达节点，则将该转角简化 1.0 为直线路径。因此，路径简化算子不仅可以缩短 0.5 路径长度，而且可以增大转角角度，让机器人运 0 0.5 1.0 1.52.02.53.0 动更加平滑。如图1(a)与图1(b)中分别为存在 x/cm 90°冗余转角的两种情况，图1(c)中存在45冗余 (a)90°简化路段
缺陷，本文提出一种新回退机制，即当蚂蚁陷入 U 型障碍时，将该蚂蚁所处节点直接标记为地图上 障碍节点并实时更新地图，然后将蚂蚁回退到路径 上一节点重新进行路径选择，重复此操作直到另 一可达节点出现时结束回退。通过回退机制将 U 型障碍填充为矩形障碍，从而避免后续蚂蚁再次 陷入同一 U 型障碍，因此能提高算法收敛速度。 1.2.3 信息素更新改进策略 Lk ci j ci j Lk Lk ci j Lk Llocal Lglobal Q1 Q2 Q2 Q1 Q2 Q1 Lglobal Q1 传统蚁群算法信息素更新策略中，蚂蚁经过 的所有路径均采用相同的信息素更新强度。当蚁 群完成一轮迭代后，所有可行路径 信息素更新 增量相同，这就导致传统蚁群算法路径搜索的盲 目性增大，蚂蚁无法快速锁定长度更短的路径。 因此，在改进的信息素更新策略中，增加一个动态 累加参数 ，增强蚁群寻找最优路径的引导作用。 用于记录 成为当前最短路径迭代轮数，即累 加最优路径信息素浓度，当 为当前最短路径时， 将加 1。此外，将 分别与当前局部最优路径 和全局最优路径 进行比较。根据比较结 果，对可行路径信息素浓度采用分级更新强度 和 。一般来讲， > , 本文中， 数值为 数 值的两倍。这样能使得 路径节点信息素增量 更大，进一步扩大全局最优路径在后续迭代中对 蚁群路径搜索引导作用，同时也能避免由于 导 致的蚁群陷入局部最优。改进信息素具体更新为 ∆τi j = { ci jQ1 / Lk , Lk = Llocal ci jQ2 / Lk , Lk = Lglobal ci j = { ci j +1, Lk = minLk ci j, 其他 改进信息素更新策略引导蚁群往最优路径方 向搜索，可以进一步加快算法收敛速度，增强算 法性能。 1.2.4 路径简化算子 若路径存在过多角度较小转角，则机器人在 移动过程中可能会出现失去平衡现象。此外，通 过蚁群算法迭代规划出的路径如果存在大量转 角，该路径就不一定是最优路径。因此，如何消 除冗余转角是路径规划时必须考虑的一个问题。 路径简化算子[17] 根据三角形两边之和大于第三 边原理消除冗余转角。改进路径简化算子根据路 径中相邻 3 个节点构成的夹角角度进行路径简 化。若夹角内节点为可达节点，则将该转角简化 为直线路径。因此，路径简化算子不仅可以缩短 路径长度，而且可以增大转角角度，让机器人运 动更加平滑。如图 1（a）与图 1（b）中分别为存在 90°冗余转角的两种情况，图 1（c）中存在 45°冗余 转角。通过简化算子分别简化为图 2（a）、图 2（b） 和图 2（c）中的路径。 0.5 1.0 1.5 x/cm 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 0.5 1.0 1.5 x/cm 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 0.5 1.0 1.5 x/cm 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 (b) 90° 转角 (c) 45° 转角 (a) 90° 转角 y/cm y/cm y/cm 图 1 3 种冗余转角 Fig. 1 Three redundant corners 0.5 1.0 1.5 x/cm 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 x/cm x/cm (c) 45° 简化路段 y/cm y/cm y/cm (a) 90° 简化路段 (b) 90° 简化路段 第 4 期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·767·
·768· 智能系统学报 第17卷 3.0 数，选择下一路径节点，并判断是否需要启动回 2.5 退机制； 2.0 4)蚁群通过自学和随机向一只蚂蚁学习，通 过评价函数确定学习阶段最终寻路能力： 复15 5)更新蚂蚁经过路径的信息素； 1.0 6)将两个子群整合为一个种群，按照能力大 05 小再次划分为精英与普通两个子群，选择寻路能 力最强蚂蚁作为下一次迭代教师蚂蚁： 0 0.5 1.0 1.5 2.0 2.53.0 x/cm 7判断是否达到迭代终止条件：若达到迭代 (b)90°简化路段 终止条件，则采用路径简化算子输出最佳路径； 30 反之则跳转至步骤2)继续求解。 2.5 基于分组教学的改进蚁群算法流程如图3。 2.0 开始 1.0 初始化参数及种群 0.5 向教师蚂蚊学习阶段 0 0.51.01.52.02.53.0 x/cm (c)45°简化路段 根据状态转移概率选择下一节点 图23种冗余转角简化路段 Fig.2 Three redundant corner simplified sections 为说明路径简化算子有效性，表1给出了 回退机制 遇到U型障碍 10次对比实验。根据表1实验数据可知，路径简 化算子可以大幅度提高求解最优路径精度。 N 表1路径简化算子实验数据 信息素更新策略 Table 1 Experimental data of path simplification operator 传统蚁群算法 使用简化算子 随机学习阶段 次数 路径长度cm 后路径长度/cm 简化率% 38.04 30.38 20.14 重组种群，选择教师蚂蚁 35.21 30.56 13.21 3 33.21 30.38 8.52 4 39.46 29.21 26.00 达到迭代 N 5 34.62 30.38 12.25 停止条件 6 36.28 34.04 6.17 7 36.87 32.38 12.18 Y 8 35.21 30.97 12.04 路径简化算子 9 33.21 30.38 8.52 10 36.04 29.80 17.31 输出 1.3基于GTOA改进蚊群算法步骤与流程 图3基于分组教学的改进蚊群算法流程 基于GTOA改进蚁群算法主要有如下7步。 Fig.3 Flow of improved ant colony algorithm based on 1)初始蚁群规模M,迭代次数K,参数α，B等， group teaching 将蚁群划分为精英与普通两个子群： 2数值对比实验 2)蚂蚁个体向教师蚂蚁学习，通过评价函数 评估教师阶段最终寻路能力； 在数值对比实验中，使用栅格法进行环境建 3)根据随机状态转移概率与改进后适应度函 模，将地图中不规则障碍扩充为矩形障碍，将移
x/cm 0.5 1.0 1.5 x/cm 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 0.5 1.0 1.5 x/cm (c) 45° 简化路段 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 y/cm y/cm y/cm (a) 90° 简化路段 (b) 90° 简化路段 图 2 3 种冗余转角简化路段 Fig. 2 Three redundant corner simplified sections 为说明路径简化算子有效性，表 1 给出了 10 次对比实验。根据表 1 实验数据可知，路径简 化算子可以大幅度提高求解最优路径精度。 表 1 路径简化算子实验数据 Table 1 Experimental data of path simplification operator 次数 传统蚁群算法 路径长度/cm 使用简化算子 后路径长度/cm 简化率/% 1 38.04 30.38 20.14 2 35.21 30.56 13.21 3 33.21 30.38 8.52 4 39.46 29.21 26.00 5 34.62 30.38 12.25 6 36.28 34.04 6.17 7 36.87 32.38 12.18 8 35.21 30.97 12.04 9 33.21 30.38 8.52 10 36.04 29.80 17.31 1.3 基于 GTOA 改进蚁群算法步骤与流程 基于 GTOA 改进蚁群算法主要有如下 7 步。 1) 初始蚁群规模 M ，迭代次数 K ，参数 α, β 等， 将蚁群划分为精英与普通两个子群； 2) 蚂蚁个体向教师蚂蚁学习，通过评价函数 评估教师阶段最终寻路能力； 3) 根据随机状态转移概率与改进后适应度函 数，选择下一路径节点，并判断是否需要启动回 退机制； 4) 蚁群通过自学和随机向一只蚂蚁学习，通 过评价函数确定学习阶段最终寻路能力； 5) 更新蚂蚁经过路径的信息素； 6) 将两个子群整合为一个种群，按照能力大 小再次划分为精英与普通两个子群，选择寻路能 力最强蚂蚁作为下一次迭代教师蚂蚁； 7) 判断是否达到迭代终止条件：若达到迭代 终止条件，则采用路径简化算子输出最佳路径； 反之则跳转至步骤 2) 继续求解。 基于分组教学的改进 蚁群算法流程如图 3。 开始 初始化参数及种群 向教师蚂蚁学习阶段 根据状态转移概率选择下一节点 随机学习阶段 达到迭代 停止条件 路径简化算子 输出 信息素更新策略 重组种群, 选择教师蚂蚁 Y N 遇到 U 型障碍 N 回退机制 Y 图 3 基于分组教学的改进蚁群算法流程 Fig. 3 Flow of improved ant colony algorithm based on group teaching 2 数值对比实验 在数值对比实验中，使用栅格法进行环境建 模，将地图中不规则障碍扩充为矩形障碍，将移 ·768· 智 能 系 统 学 报 第 17 卷