第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 卷
第4期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·769· 动机器人抽象为一个点。将改进蚁群算法(group 20 teaching ant colony algorithm,GTACO)与传统蚁群 6 算法(ant colony algorithm,ACO)、改进蚁群算法 14 (improved ant colony algorithm,-ACO)、混合蚁群 12 (improved ant colony algorithm with shuffled frog leaping algorithm,IACO-SFLA)进行仿真模拟 实验对比，在求解精度（最优路径长度）、收敛速度 (迭代次数)和算法运行时间3个方面验证GTACO 2 68101214161820 的优越性能。 x/cm 在20×20栅格地图2中，将GTAC0与ACO 图5 GTACO最优路径图 L-ACO、IACO-SFLA进行比较。地图中黑色栅格 Fig.5 GTACO optimal path planning 代表障碍物，白色栅格代表可达节点。地图左上 表3和图4、图5中实验结果表明，AC0、-ACO 角为机器人起点，右下角为终点，寻找一条无碰 无法求解出最优路径，IACO-SFLA和GTACO均 撞的最优路径。为确保对比实验严谨，4种算法 能求解出从起，点到终点最优路径。其中GTACO 所包含共同参数设定为相同值，参数值设置如 能在较少的迭代次数中达到收敛状态，相较于 表2。实验数据统计如表3.4种算法迭代次数收 IACO-SFLA,GTACO能在更短时间完成规定迭 敛曲线趋势对比以及GTACO最优路径分别如图4、 代次数并求解出最优路径。 图5。 为进一步验证GTACO的优越性，采用更复 表2对比实验参数设置 杂40×40栅格地图。因实验地图规模变大，为使 Table 2 Comparison experiment parameter settings 算法实验效果达到最佳，扩大K和M的值为100。 参数名 符号 设定值 4种算法最优路径长度、迭代次数和运行时间对 迭代次数 比如表4.4种算法的迭代次数收敛曲线趋势对 K 50 蚁群规模 比如图6。图7为GTACO最优路径图。表4和 M 50 图6中实验结果表明，在对比实验使用的4种算 信息素启发因子 a 1.5 法中，L-ACO、IACO-SFLA与GTACO在规定迭代 期望启发因子 B 7 次数中达到收敛状态，且GTACO较IACO-SFLA 信息素挥发系数 0.1 计算出的路径精度更高，收敛速度更快，算法运 行时间也更短。 表34种算法数据对比 Table 3 Data comparison of four algorithms 表44种算法数据对比 Table 4 Data comparison of four algorithms 算法 最优路径cm 迭代次数 运行时间/s 算法 最优路径/cm 迭代次数 运行时间s ACO 29.21 37 3.02 ACO 73.25 未收敛 148.12 I-ACO 29.21 12 2.86 I-ACO 69.84 59 168.33 IACO-SFLA 28.63 5 5.24 IACO-SFLA 62.08 25 162.34 GTACO 28.63 4 3.08 GTACO 59.84 21 155.29 50 200 8 ACO IACO ACO-SFLA IACO-SFLA GTACO GTACO 40 150 盗30 姿100 20 10152025303540 0 10 2030405060708090100 迭代次数 迭代次数 图44种算法迭代曲线对比图 图64种算法迭代曲线对比图 Fig.4 Comparison of iterative curves of four algorithms Fig.6 Comparison of iterative curves of four algorithms
动机器人抽象为一个点。将改进蚁群算法（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 参数名 符号 设定值 迭代次数 K 50 蚁群规模 M 50 信息素启发因子 α 1.5 期望启发因子 β 7 信息素挥发系数 ρ 0.1 表 3 4 种算法数据对比 Table 3 Data comparison of four algorithms 算法 最优路径/cm 迭代次数 运行时间/s ACO 29.21 37 3.02 I-ACO 29.21 12 2.86 IACO-SFLA 28.63 5 5.24 GTACO 28.63 4 3.08 0 5 10 15 20 25 30 35 40 迭代次数 20 25 30 35 40 45 50 路径长度/cm ACO IACO IACO-SFLA GTACO 图 4 4 种算法迭代曲线对比图 Fig. 4 Comparison of iterative curves of four algorithms 0 2 4 6 8 10 12 14 16 18 20 x/cm 2 4 6 8 10 12 14 16 18 20 y/cm 图 5 GTACO 最优路径图 Fig. 5 GTACO optimal path planning 表 3 和图 4、图 5 中实验结果表明，ACO、I-ACO 无法求解出最优路径，IACO-SFLA 和 GTACO 均 能求解出从起点到终点最优路径。其中 GTACO 能在较少的迭代次数中达到收敛状态，相较于 IACO-SFLA，GTACO 能在更短时间完成规定迭 代次数并求解出最优路径。 K M 为进一步验证 GTACO 的优越性，采用更复 杂 40×40 栅格地图。因实验地图规模变大，为使 算法实验效果达到最佳，扩大 和 的值为 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 算法 最优路径/cm 迭代次数 运行时间/s ACO 73.25 未收敛 148.12 I-ACO 69.84 59 168.33 IACO-SFLA 62.08 25 162.34 GTACO 59.84 21 155.29 0 10 20 30 40 50 60 70 80 90 100 迭代次数 50 100 150 200 路径长度/cm ACO IACO IACO-SFLA GTACO 图 6 4 种算法迭代曲线对比图 Fig. 6 Comparison of iterative curves of four algorithms 第 4 期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·769·
·770· 智能系统学报 第17卷 40 target-following guider for mobile robot[J].IEEE transac- 35 tions on industrial electronics,2019,66(12):9360-9371. 30 [3]GAO Yingding,HU Tianyang,WANG Yinchu,et al.Re- 3 search on the path planning algorithm of mobile robot[Cl// 20 2021 13th International Conference on Measuring Tech- 15 nology and Mechatronics Automation.Beihai:IEEE. 10 2021:447-450. [4]ALI M A H,MAILAH M.Path planning and control of 0510152025303540 mobile robot in road environments using sensor fusion x/cm and active force control[J].IEEE transactions on vehicu- 图7 GTACO最优路径图 lar technology,2019,68(3):2176-2195. Fig.7 GTACO optimal path planning [5]DIJKSTRA E W.A note on two problems in connexion 表2~4和图47表明，基于分组教学改进蚁群 with graphs[J].Numerische mathematik,1959,1(1): 算法(GTACO)的移动机器人路径规划能力与基 269-271. 于ACO、I-ACO和IACO-SFLA移动机器人路径 [6]GOLDBERG A V.KAPLAN H,WERNECK R F.Reach 规划能力相比，无论在精确度还是在收敛速度方 for A*:efficient point-to-point shortest path algori- 面都有改善。通过仿真模拟实验验证，本文提出 thms[C]//Proceedings of the Eighth Workshop on Al- 的改进蚁群算法适用于移动机器人路径规划。 gorithm Engineering and Experiments.Florida:Society for Industrial and Applied Mathematics,2006,6(2): 3结束语 129-143. [7]楼传炜.葛泉波，刘华平，等.无人机群目标搜索的主动 针对蚁群算法在移动机器人路径规划中存在 感知方法).智能系统学报，2021,16(3：575-583 收敛速度慢和易陷入局部最优问题，提出了一种 LOU Chuanwei,GE Quanbo,LIU Huaping,et al.Active 基于分组教学优化改进蚁群算法。改进算法结合 perception method for UAV group target search[J].CAAl 分组教学优化与蚁群算法优点，即利用分组教学 transactions on intelligent systems,2021,16(3):575-583 优化算法的整体优化特性，通过蚁群中蚂蚁个体 [8]徐玉琼，娄柯，李志锟.基于变步长蚁群算法的移动机 之间相互影响，提高蚁群算法全局求解能力，避 器人路径规划).智能系统学报，2021,16(2：330-337. 免算法过早陷入局部最优。该改进算法充分利用 XU Yuqiong,LOU Ke,LI Zhikun.Mobile robot path 分组教学优化算法不依赖过多参数特性，避免路 planning based on variable-step ant colony algorithm[J]. 径搜索能力不过于依赖多个参数，从而加速算法 CAAI transactions on intelligent systems,2021,16(2): 收敛速度。回退机制的改进能进一步避免算法 330-337. 在U型障碍处陷入停滞，达到提高蚁群搜索可行 [9]夏小云，周育人.蚁群优化算法的理论研究进展J几.智 解多样性。此外，新的信息素更新策略能强化蚁 能系统学报，2016,11(1)少：27-36. 群更趋向更短路径，因此更能提高蚁群算法收敛 XIA Xiaoyun,ZHOU Yuren.Advances in theoretical re- 速度。最后，路径简化算子能更进一步缩短蚁群 search of ant colony optimization[J].CAAI transactions on intelligent systems,2016,11(1):27-36. 路径，增大转弯角度，也更易于移动机器人平滑 [10]GAO Wei.Modified ant colony optimization with im- 稳定运动。仿真对比实验证明移动机器人能通过 proved tour construction and pheromone updating 改进算法有效规划可行路径，缩短算法运行时 strategies for traveling salesman problem[J].Soft com- 间，即提高求解路径精度和算法收敛速度。接下 puting,2021,25(4):3263-3289. 来，将进一步基于改进蚁群算法在障碍物不规则 [11]LIN Wang.Path planning for unmanned wheeled robot 或受到随机干扰时研究机器人路径规划。 based on improved ant colony optimization[J].Measure- 参考文献： ment and control,2020,53(5/6):1014-1021 [12]LI Xue.WANG Lei.Application of improved ant colony [1]WANG Jiaying,LUO Bing,ZENG Ming,et al.A wind optimization in mobile robot trajectory planning[]. estimation method with an unmanned rotorcraft for envir- Mathematical biosciences and engineering:MBE,2020, onmental monitoring tasks[J].Sensors (Basel,Switzer- 17(6):6756-6774. land.2018.18(12):4504. [13]PU Xingcheng,XIONG Chaowen,JI Lianghao,et al.3D [2]ZHANG Mingyi,LIU Xilong,XU De,et al.Vision-based path planning for a robot based on improved ant colony
0 5 10 15 20 25 30 35 40 x/cm 5 10 15 20 25 30 35 40 y/cm 图 7 GTACO 最优路径图 Fig. 7 GTACO optimal path planning 表 2~4 和图 4~7 表明，基于分组教学改进蚁群 算法（GTACO）的移动机器人路径规划能力与基 于 ACO、I-ACO 和 IACO-SFLA 移动机器人路径 规划能力相比，无论在精确度还是在收敛速度方 面都有改善。通过仿真模拟实验验证，本文提出 的改进蚁群算法适用于移动机器人路径规划。 3 结 束 语 针对蚁群算法在移动机器人路径规划中存在 收敛速度慢和易陷入局部最优问题，提出了一种 基于分组教学优化改进蚁群算法。改进算法结合 分组教学优化与蚁群算法优点，即利用分组教学 优化算法的整体优化特性，通过蚁群中蚂蚁个体 之间相互影响，提高蚁群算法全局求解能力，避 免算法过早陷入局部最优。该改进算法充分利用 分组教学优化算法不依赖过多参数特性，避免路 径搜索能力不过于依赖多个参数，从而加速算法 收敛速度。回退机制的改进能进一步避免算法 在 U 型障碍处陷入停滞，达到提高蚁群搜索可行 解多样性。此外，新的信息素更新策略能强化蚁 群更趋向更短路径，因此更能提高蚁群算法收敛 速度。最后，路径简化算子能更进一步缩短蚁群 路径，增大转弯角度，也更易于移动机器人平滑 稳定运动。仿真对比实验证明移动机器人能通过 改进算法有效规划可行路径，缩短算法运行时 间，即提高求解路径精度和算法收敛速度。接下 来，将进一步基于改进蚁群算法在障碍物不规则 或受到随机干扰时研究机器人路径规划。 参考文献： WANG Jiaying, LUO Bing, ZENG Ming, et al. A wind estimation method with an unmanned rotorcraft for environmental monitoring tasks[J]. Sensors (Basel, Switzerland), 2018, 18(12): 4504. [1] [2] ZHANG Mingyi, LIU Xilong, XU De, et al. Vision-based target-following guider for mobile robot[J]. IEEE transactions on industrial electronics, 2019, 66(12): 9360–9371. GAO Yingding, HU Tianyang, WANG Yinchu, et al. Research on the path planning algorithm of mobile robot[C]// 2021 13th International Conference on Measuring Technology and Mechatronics Automation. Beihai: IEEE, 2021: 447−450. [3] ALI M A H, MAILAH M. Path planning and control of mobile robot in road environments using sensor fusion and active force control[J]. IEEE transactions on vehicular technology, 2019, 68(3): 2176–2195. [4] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959, 1(1): 269–271. [5] GOLDBERG A V, KAPLAN H, WERNECK R F. Reach for A*: efficient point-to-point shortest path algorithms[C]//Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments. Florida: Society for Industrial and Applied Mathematics, 2006, 6(2): 129−143. [6] 楼传炜, 葛泉波, 刘华平, 等. 无人机群目标搜索的主动 感知方法 [J]. 智能系统学报, 2021, 16(3): 575–583. LOU Chuanwei, GE Quanbo, LIU Huaping, et al. Active perception method for UAV group target search[J]. CAAI transactions on intelligent systems, 2021, 16(3): 575–583. [7] 徐玉琼, 娄柯, 李志锟. 基于变步长蚁群算法的移动机 器人路径规划 [J]. 智能系统学报, 2021, 16(2): 330–337. XU Yuqiong, LOU Ke, LI Zhikun. Mobile robot path planning based on variable-step ant colony algorithm[J]. CAAI transactions on intelligent systems, 2021, 16(2): 330–337. [8] 夏小云, 周育人. 蚁群优化算法的理论研究进展 [J]. 智 能系统学报, 2016, 11(1): 27–36. XIA Xiaoyun, ZHOU Yuren. Advances in theoretical research of ant colony optimization[J]. CAAI transactions on intelligent systems, 2016, 11(1): 27–36. [9] GAO Wei. Modified ant colony optimization with improved tour construction and pheromone updating strategies for traveling salesman problem[J]. Soft computing, 2021, 25(4): 3263–3289. [10] LIN Wang. Path planning for unmanned wheeled robot based on improved ant colony optimization[J]. Measurement and control, 2020, 53(5/6): 1014–1021. [11] LI Xue, WANG Lei. Application of improved ant colony optimization in mobile robot trajectory planning[J]. Mathematical biosciences and engineering:MBE, 2020, 17(6): 6756–6774. [12] PU Xingcheng, XIONG Chaowen, JI Lianghao, et al. 3D path planning for a robot based on improved ant colony [13] ·770· 智 能 系 统 学 报 第 17 卷
第4期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·771· algorithm[J].Evolutionary intelligence,2020:1-11. applications,2020,148:113246. [14]梁凯，毛剑琳.基于改进蚁群算法的室内移动机器人 [22]DORIGO M.MANIEZZO V,COLORNI A.The ant 路径规划.电子测量技术，2019,42(11：65-69. system:an autocatalytic optimizing process[R].Milan: LIANG Kai,MAO Jianlin.Path planning of indoor mo- Dipartimento di Elettronica,Politecnicl di Milano,1991 bile robot based on improved ant colony algorithm[J]. [23]DORIGO M.MANIEZZO V,COLORNI A.Ant sys- Electronic measurement technology,2019,42(11): tem:optimization by a colony of cooperating agents[]. 65-69. IEEE transactions on systems,man,and cybernetics,part [15]QIN Ling,PAN Yi,CHEN Ling,et al.An improved ant B.1996,26(1)29-41. colony algorithm with diversified solutions based on the [24]任红格，胡鸿长，史涛.基于改进蚁群算法的移动机器 immune strategy[J].BMC bioinformatics,2006,7(4): 人全局路径规划[).华北理工大学学报（自然科学版）， 1-8」 2021,43(2):102-109 [16]YU Miao.A solution of TSP based on the ant colony al- REN Hongge,HU Hongchang,SHI Tao.Global path gorithm improved by particle swarm optimization[J]. planning of mobile robots based on improved ant colony Discrete continuous dynamical systems-S,2019, algorithm[J].Journal of North China University of Sci- 12(4/5):979-987. ence and Technology (natural science edition),2021, [17]DAI Xiaolin,LONG Shuai,ZHANG Zhiwen,et al.Mo- 43(2):102-109. bile robot path planning based on ant colony algorithm [25]PU Xingcheng,XIONG Chaowen,ZHAO Longlong. with A*heuristic method[J].Frontiers in neurorobotics, Path planning for robot based on IACO-SFLA hybrid al- 2019.13:15 [18]ZHU Shinan,ZHU Weiyi,ZHANG Xueqin,et al.Path gorithm[C]//Proceedings of 2020 Chinese Control and Decision Conference.Hefei:IEEE,2020:652-629. planning of lunar robot based on dynamic adaptive ant colony algorithm and obstacle avoidance[J].Internation- 作者简介： al journal of advanced robotic systems,2020,17(3): 蒲兴成，教授.博士博士生导师 1-14. 主要研究方向为多智能体系统、群智 [19]WU Hongguang,GAO Yuelin,WANG Wanting,et al. 能算法和随机系统。主持和参与市级 A hybrid ant colony algorithm based on multiple 以上科研项目10余项。发表学术论 文50余篇，出版学术专著和教材各 strategies for the vehicle routing problem with time win- 2部。 dows[J].Complex intelligent systems,2021:1-18. [20]TAO Yong,GAO He,REN Fan,et al.A mobile service robot global path planning method based on ant colony 宋欣琳，硕士研究生，主要研究方 optimization and fuzzy control[J].Applied sciences, 向为群智能算法的改进及应用。 2021,11(8):3605. [21]ZHANG Yiying,JIN Zhigang.Group teaching optimiza- tion algorithm:a novel metaheuristic method for solving global optimization problems[J].Expert systems with
algorithm[J]. Evolutionary intelligence, 2020: 1–11. 梁凯, 毛剑琳. 基于改进蚁群算法的室内移动机器人 路径规划 [J]. 电子测量技术, 2019, 42(11): 65–69. LIANG Kai, MAO Jianlin. Path planning of indoor mobile robot based on improved ant colony algorithm[J]. Electronic measurement technology, 2019, 42(11): 65–69. [14] QIN Ling, PAN Yi, CHEN Ling, et al. An improved ant colony algorithm with diversified solutions based on the immune strategy[J]. BMC bioinformatics, 2006, 7(4): 1–8. [15] YU Miao. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization[J]. Discrete & continuous dynamical systems-S, 2019, 12(4/5): 979–987. [16] DAI Xiaolin, LONG Shuai, ZHANG Zhiwen, et al. Mobile robot path planning based on ant colony algorithm with A* heuristic method[J]. Frontiers in neurorobotics, 2019, 13: 15. [17] ZHU Shinan, ZHU Weiyi, ZHANG Xueqin, et al. Path planning of lunar robot based on dynamic adaptive ant colony algorithm and obstacle avoidance[J]. International journal of advanced robotic systems, 2020, 17(3): 1–14. [18] WU Hongguang, GAO Yuelin, WANG Wanting, et al. A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows[J]. Complex & intelligent systems, 2021: 1–18. [19] TAO Yong, GAO He, REN Fan, et al. A mobile service robot global path planning method based on ant colony optimization and fuzzy control[J]. Applied sciences, 2021, 11(8): 3605. [20] ZHANG Yiying, JIN Zhigang. Group teaching optimization algorithm: a novel metaheuristic method for solving global optimization problems[J]. Expert systems with [21] applications, 2020, 148: 113246. DORIGO M, MANIEZZO V, COLORNI A. The ant system: an autocatalytic optimizing process[R]. Milan: Dipartimento di Elettronica, Politecnicl di Milano, 1991. [22] DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE transactions on systems, man, and cybernetics, part B. 1996, 26(1): 29−41. [23] 任红格, 胡鸿长, 史涛. 基于改进蚁群算法的移动机器 人全局路径规划 [J]. 华北理工大学学报(自然科学版), 2021, 43(2): 102–109. REN Hongge, HU Hongchang, SHI Tao. Global path planning of mobile robots based on improved ant colony algorithm[J]. Journal of North China University of Science and Technology (natural science edition), 2021, 43(2): 102–109. [24] PU Xingcheng, XIONG Chaowen, ZHAO Longlong. Path planning for robot based on IACO-SFLA hybrid algorithm[C]//Proceedings of 2020 Chinese Control and Decision Conference. Hefei: IEEE, 2020: 652−629. [25] 作者简介： 蒲兴成，教授，博士，博士生导师， 主要研究方向为多智能体系统、群智 能算法和随机系统。主持和参与市级 以上科研项目 10 余项。发表学术论 文 50 余篇，出版学术专著和教材各 2 部。 宋欣琳，硕士研究生，主要研究方 向为群智能算法的改进及应用。 第 4 期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·771·