Improvement of ant colony algorithm in group teaching and its application in robot path planning
-
摘要: 针对蚁群算法收敛速度慢、易陷入局部最优问题，提出一种基于分组教学优化改进蚁群算法。该算法从3个角度对蚁群算法进行改进。首先，利用分组教学优化算法改进蚁群算法适应度函数，提高算法全局求解能力。同时，引进一种新的回退策略，通过该策略处理U型障碍死锁问题，确保算法求解可行性。其次，采用一种新的动态信息素更新策略，滚动更新每轮迭代后路径信息素值，避免算法陷入局部最优。最后，引入路径简化算子，将冗余角简化为直线路径，缩短路径长度。仿真实验证明改进算法能有效提高移动机器人路径规划收敛速度和精度。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.
-
路径规划是机器人导航基础技术之一[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]选择下一路径节点，随机状态转移概率公式为
$$ {P}_{ij}^{k}=\left\{\begin{aligned} &\dfrac{{\tau }_{ij}^{\alpha }\left(t\right){\eta }_{ij}^{\beta }\left(t\right)}{{\displaystyle \sum _{s\in {\text{allowed}}_{k}}{\tau }_{is}^{\alpha }\left(t\right){\eta }_{is}^{\beta }\left(t\right)}},\quad j\in {\text{allowed}}_{k}\\ &0,\quad{其他}\end{aligned}\right. $$ $$ {\eta _{ij}}\left( t \right) = \frac{1}{{{d_{ij}}}} $$ 式中：
$ \alpha $ 是信息素启发因子，控制路径信息素的相对重要性；$ \beta $ 是期望启发式因子，控制路径节点距离的相对重要性；$ {\tau _{ij}}\left( t \right) $ 是$ t $ 时刻$ i $ 、$ j $ 两点间的信息素浓度；$ {d_{ij}} $ 是$ i $ 、$ j $ 两点间欧氏距离；$ {\eta _{ij}}\left( t \right) $ 是$ i $ 、$ j $ 两点间距离倒数。所有蚂蚁完成一次寻路后，需对蚂蚁经过的所有路径进行信息素更新[23]：$$ {\tau _{ij}}\left( {t + n} \right) = \rho \cdot {\tau _{ij}}\left( t \right) + \Delta {\tau _{ij}} $$ $$ \Delta {\tau }_{ij}=\left\{\begin{aligned} &Q/{L}_{k},\quad i,j\in {\text{Path}}_{k}\\ &0,\quad{其他}\end{aligned} \right.$$ 式中：
$ \rho $ 是信息素挥发系数；$ \Delta {\tau _{ij}} $ 是本次寻路后$ i $ 、$ j $ 两点间信息素更新的增量；$ Q $ 是常数，代表信息素强度；$ {L_k} $ 是第$ k $ 只蚂蚁在本次寻路中爬行过的路径长度；$ {\text{Pat}}{{\text{h}}_k} $ 是第$ k $ 只蚂蚁在本次迭代中搜索到的可行路径节点。1.2 蚁群算法的改进
传统蚁群算法在迭代前期，路径上信息素浓度差别不大，蚂蚁在选择下一爬行节点时概率几乎是随机的。在迭代后期，某些路径节点信息素浓度过高，蚂蚁大概率选择相同节点爬行。这直接导致了蚁群算法收敛速度慢和易陷入局部最优问题产生。针对这两个主要不足，本文结合分组教学优化算法优点改进标准蚁群算法，即赋予蚁群一个代表寻路能力参数，将该参数用于优化传统蚁群算法适应度函数，从而改善蚁群全局路径规划能力，避免算法陷入局部最优。另一方面，由于分组教学优化算法除了种群参数需要设置以外，算法中个体优化不依赖于其他参数调整，因此与分组教学优化算法结合的改进蚁群算法也能加快算法收敛速度。此外，改进死锁回退策略，既能够保证每一次迭代单个个体都能进行路径搜索操作，也能提高地图实时更新能力。同时，将U型死锁位置标记为障碍，能避免算法发生停滞。值得一提的是，为使算法性能更优，本文进一步改进了信息素更新策略，将标准蚁群算法固定参数调整为与蚁群搜索相关动态参数，有针对性地引导蚁群寻找最优路径；路径简化算子的引进，能有效将路径上的冗余转角简化为直线路径，实现提高路径优化精度的目标。下面将结合分组教学、蚁群回退机制、信息素更新策略和路径简化算子等方面具体介绍改进策略。
1.2.1 基于分组教学优化算法蚁群算法改进
GTOA[21]是一种启发式随机群智能算法，该算法具有较强自适应寻优能力。基于此，为提高蚁群算法全局优化能力和收敛速度，本文在蚁群算法的基础上引进GTOA。为避免蚁群适应度函数只单纯受到达目标点的距离控制，导致蚁群算法易陷入局部最优，先为蚁群添加一个代表寻路能力的自适应参数（以下将该参数简称为“寻路能力”）。此外，在教学阶段，通过比较GTOA评价函数，蚂蚁按照改进后的适应度函数与随机状态转移概率选择下一路径节点，最后完成种群整合等。下面将逐一给出具体操作。
1) 基于改进评价函数的分组教学优化算法
评价函数主要用于评估蚂蚁在路径搜索过程中表现，为使GTOA适用于蚁群算法，需将GTOA评价函数修改成蚁群个体与路径长度相关函数，修改后的评价函数为
$$ f\left( x \right) = \frac{{{x_k}\left( t \right)}}{{\min {L_k}}} $$ 式中：
$ {x_k}\left( t \right) $ 为蚂蚁$ k $ 在$ t $ 时刻寻路能力，$ \min {L_k} $ 为蚂蚁$ k $ 寻找到最短路径长度。由评价函数可知，蚂蚁个体搜索到的路径长度越短，个体评价就越高，因此，该个体通过学习获得寻路能力越强。2) 基于改进适应度函数的蚁群算法
为提升蚁群全局优化能力，本文结合GTOA教学阶段[13]来影响蚁群中蚂蚁个体寻路能力
$ {x_k}\left( t \right) $ 。首先，按照蚂蚁寻路能力高低，将蚁群划分为精英和普通子群，将寻路能力最高蚂蚁升级为教师蚂蚁。然后，基于GTOA模仿课堂教与学思想，在教师阶段，针对精英子群和普通子群采用不同学习方式，通过向教师蚂蚁学习以增强个体寻路能力。不仅如此，在学习阶段，每只蚂蚁在每一轮迭代中通过自学和随机向蚁群另一只蚂蚁学习，达到增强个体寻路能力目的，并通过比较评价函数确定蚂蚁在教学阶段后的最终寻路能力。结合蚂蚁到目标点距离$ {d_{ij}} $ 以及蚂蚁寻路能力$ {x_k}\left( t \right) $ ，蚁群算法适应度函数$ {\eta _{ij}}\left( t \right) $ 进一步改进为$$ {\eta _{ij}}\left( t \right) = \frac{1}{{{d_{ij}} \times {x_k}\left( t \right)}} $$ 改进适应度函数通过
$ {x_k}\left( t \right) $ 自适应调整蚁群路径选择概率。当蚁群距终点较远时，$ {d_{ij}} $ 较大，蚁群路径选择概率差异较大。$ {x_k}\left( t \right) $ 可以缩小各条路径被选择概率，避免算法陷入局部最优。当蚁群接近终点时，$ {d_{ij}} $ 较小，路径选择概率趋近相同。$ {x_k}\left( t \right) $ 可以扩大各条路径选择概率，加快蚁群算法收敛，同时也保证蚁群算法求解的多样性。3) 种群整合
经过GTOA教学阶段学习，蚂蚁个体间寻路能力在各个子群都具备一定差异。根据蚂蚁寻路能力降序排列将两个子群整合，并重新划分子群，用于下一轮迭代。以此保证在每次迭代中，同时提升精英子群和普通子群蚂蚁寻路能力，最终提升整个蚁群寻路能力。蚁群重新整合划分后，选择寻路能力最强蚂蚁作为下一轮迭代教师蚂蚁，其选择公式为
$$ T\left( {t + 1} \right) = \max \left( {{x_k}\left( t \right)} \right) $$ 此外，在分组教学过程中某些蚂蚁寻路能力过高或过低，或致使算法陷入局部最优。因此对蚂蚁寻路能力值设置一个阈值区间
$ \left[ {{\text{An}}{{\text{t}}_{\min }},{\text{An}}{{\text{t}}_{\max }}} \right] $ ，将超过此阈值区间蚂蚁个体寻路能力值设置为该区间边界值。1.2.2 蚁群回退机制
传统蚁群算法无法规避U型障碍，导致算法易陷入停滞状态，因此可在该类障碍处用回退机制避免此类问题。Lin等[11]过建立额外全局和局部禁忌表来标记可能产生死锁节点位置。任红格等[24]提出直接让陷入死锁蚂蚁“死亡”，即跳过此轮迭代搜索过程，直接返回起点。上述回退机制存在计算量大或者可行解减少等问题。为克服此缺陷，本文提出一种新回退机制，即当蚂蚁陷入U型障碍时，将该蚂蚁所处节点直接标记为地图上障碍节点并实时更新地图，然后将蚂蚁回退到路径上一节点重新进行路径选择，重复此操作直到另一可达节点出现时结束回退。通过回退机制将U型障碍填充为矩形障碍，从而避免后续蚂蚁再次陷入同一U型障碍，因此能提高算法收敛速度。
1.2.3 信息素更新改进策略
传统蚁群算法信息素更新策略中，蚂蚁经过的所有路径均采用相同的信息素更新强度。当蚁群完成一轮迭代后，所有可行路径
$ {L_k} $ 信息素更新增量相同，这就导致传统蚁群算法路径搜索的盲目性增大，蚂蚁无法快速锁定长度更短的路径。因此，在改进的信息素更新策略中，增加一个动态累加参数$ {c_{ij}} $ ，增强蚁群寻找最优路径的引导作用。$ {c_{ij}} $ 用于记录$ {L_k} $ 成为当前最短路径迭代轮数，即累加最优路径信息素浓度，当$ {L_k} $ 为当前最短路径时，$ {c_{ij}} $ 将加1。此外，将$ {L_k} $ 分别与当前局部最优路径$ {L_{{\text{local}}}} $ 和全局最优路径$ {L_{{\text{global}}}} $ 进行比较。根据比较结果，对可行路径信息素浓度采用分级更新强度$ {Q_1} $ 和$ {Q_2} $ 。一般来讲，$ {Q_2} $ >$ {Q_1} $ , 本文中，$ {Q_2} $ 数值为$ {Q_1} $ 数值的两倍。这样能使得$ {L_{{\text{global}}}} $ 路径节点信息素增量更大，进一步扩大全局最优路径在后续迭代中对蚁群路径搜索引导作用，同时也能避免由于$ {Q_1} $ 导致的蚁群陷入局部最优。改进信息素具体更新为$$ \Delta {\tau _{ij}} = \left\{ \begin{gathered} {{{c_{ij}}{Q_1}} \mathord{\left/ {\vphantom {{{c_{ij}}{Q_1}} {{L_k}}}} \right. } {{L_k}}},{\text{ }}{L_k} = {L_{{\text{local}}}} \\ {{{c_{ij}}{Q_2}} \mathord{\left/ {\vphantom {{{c_{ij}}{Q_2}} {{L_k}}}} \right. } {{L_k}}},{\text{ }}{L_k} = {L_{{\text{global}}}} \\ \end{gathered} \right. $$ $$ {c}_{ij}=\left\{\begin{aligned} &{c}_{ij}+1,\quad{L}_{k}={\rm{min}}{L}_{k}\\ &{c}_{ij},\quad{其他}\end{aligned} \right.$$ 改进信息素更新策略引导蚁群往最优路径方向搜索，可以进一步加快算法收敛速度，增强算法性能。
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次数 传统蚁群算法
路径长度/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 $ ，参数$ \alpha ,\beta $ 等，将蚁群划分为精英与普通两个子群；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参数名 符号 设定值 迭代次数 $ K $ 50 蚁群规模 $ M $ 50 信息素启发因子 $ \alpha $ 1.5 期望启发因子 $ \beta $ 7 信息素挥发系数 $ \rho $ 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 
图 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算法 最优路径/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 
图 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型障碍处陷入停滞，达到提高蚁群搜索可行解多样性。此外，新的信息素更新策略能强化蚁群更趋向更短路径，因此更能提高蚁群算法收敛速度。最后，路径简化算子能更进一步缩短蚁群路径，增大转弯角度，也更易于移动机器人平滑稳定运动。仿真对比实验证明移动机器人能通过改进算法有效规划可行路径，缩短算法运行时间，即提高求解路径精度和算法收敛速度。接下来，将进一步基于改进蚁群算法在障碍物不规则或受到随机干扰时研究机器人路径规划。
-
图 1 3种冗余转角
Fig. 1 Three redundant corners
下载:
全尺寸图片
图 2 3种冗余转角简化路段
Fig. 2 Three redundant corner simplified sections
下载:
全尺寸图片
图 3 基于分组教学的改进蚁群算法流程
Fig. 3 Flow of improved ant colony algorithm based on group teaching
下载:
全尺寸图片
图 4 4种算法迭代曲线对比图
Fig. 4 Comparison of iterative curves of four algorithms
下载:
全尺寸图片
图 5 GTACO最优路径图
Fig. 5 GTACO optimal path planning
下载:
全尺寸图片
图 6 4种算法迭代曲线对比图
Fig. 6 Comparison of iterative curves of four algorithms
下载:
全尺寸图片
图 7 GTACO最优路径图
Fig. 7 GTACO optimal path planning
下载:
全尺寸图片
表 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 表 2 对比实验参数设置
Table 2 Comparison experiment parameter settings
参数名 符号 设定值 迭代次数 $ K $ 50 蚁群规模 $ M $ 50 信息素启发因子 $ \alpha $ 1.5 期望启发因子 $ \beta $ 7 信息素挥发系数 $ \rho $ 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 表 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 -
[1] 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. doi: 10.3390/s18124504 [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. doi: 10.1109/TIE.2019.2893829 [3] 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. [4] 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. doi: 10.1109/TVT.2019.2893878 [5] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959, 1(1): 269–271. doi: 10.1007/BF01386390 [6] 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. [7] 楼传炜, 葛泉波, 刘华平, 等. 无人机群目标搜索的主动感知方法[J]. 智能系统学报, 2021, 16(3): 575–583. doi: 10.11992/tis.202009012 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. doi: 10.11992/tis.202009012 [8] 徐玉琼, 娄柯, 李志锟. 基于变步长蚁群算法的移动机器人路径规划[J]. 智能系统学报, 2021, 16(2): 330–337. doi: 10.11992/tis.202004011 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. doi: 10.11992/tis.202004011 [9] 夏小云, 周育人. 蚁群优化算法的理论研究进展[J]. 智能系统学报, 2016, 11(1): 27–36. doi: 10.11992/tis.201510002 XIA Xiaoyun, ZHOU Yuren. Advances in theoretical research of ant colony optimization[J]. CAAI transactions on intelligent systems, 2016, 11(1): 27–36. doi: 10.11992/tis.201510002 [10] 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. doi: 10.1007/s00500-020-05376-8 [11] LIN Wang. Path planning for unmanned wheeled robot based on improved ant colony optimization[J]. Measurement and control, 2020, 53(5/6): 1014–1021. [12] 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. doi: 10.3934/mbe.2020352 [13] PU Xingcheng, XIONG Chaowen, JI Lianghao, et al. 3D path planning for a robot based on improved ant colony algorithm[J]. Evolutionary intelligence, 2020: 1–11. [14] 梁凯, 毛剑琳. 基于改进蚁群算法的室内移动机器人路径规划[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. [15] 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. [16] 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. [17] 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. doi: 10.3389/fnbot.2019.00015 [18] 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. [19] 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. [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. doi: 10.3390/app11083605 [21] ZHANG Yiying, JIN Zhigang. Group teaching optimization algorithm: a novel metaheuristic method for solving global optimization problems[J]. Expert systems with applications, 2020, 148: 113246. doi: 10.1016/j.eswa.2020.113246 [22] DORIGO M, MANIEZZO V, COLORNI A. The ant system: an autocatalytic optimizing process[R]. Milan: Dipartimento di Elettronica, Politecnicl di Milano, 1991. [23] 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. [24] 任红格, 胡鸿长, 史涛. 基于改进蚁群算法的移动机器人全局路径规划[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. [25] 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.
