基于改进蚁群算法的路径规划算法研究.pdf

2023 年第 10 期83计算机应用信息技术与信息化基于改进蚁群算法的路径规划算法研究刘羽翀1 邓 平1 LIU Yuchong DENG Ping 摘要 针对利用蚁群算法（ant colony optimization，ACO）进行路径规划时，所搜寻的路径并非最优且收敛速度慢的情况，提出一种改进的蚁群算法。将蚁群下一步可选栅格与终点栅格的距离以一定权重加入到启发函数中，增强蚂蚁选择离终点较近栅格的期望程度，缩短收敛时间。在转移概率公式中加入调节因子，以增大距离较短的对角路径栅格的转移概率。改进信息素浓度更新公式，增大各路径信息素释放的差异化程度，保证路径长度的最优性。分别在 1010 和 2020 的栅格地图中对算法进行了仿真。结果表明，提出的改进蚁群算法具有路径搜索结果更优、收敛更快、效率更高的优点。相比于传统蚁群算法，性能得到了显著提升。关键词 蚁群算法；信息素；路径规划；栅格地图；转移概率 doi：10.3969/j.issn.1672-9528.2023.10.0181.西南交通大学信息编码与传输重点实验室 四川成都 6117560 引言随着室内定位技术的不断发展和应用，基于用户信息的位置服务(LBS)在大型室内环境中的需求不断增加。大型商场、超市、市政办公厅、医院、机场、地下矿井等区域对室内位置服务有着迫切的需求。其中，导航指示成为了室内导航定位服务中最普遍的应用，通过蓝牙、Wi-Fi、UWB 等无线设备帮助使用者获取当前位置，通过终端设备路径规划功能，寻找到当前位置与目标位置之间的优选路径。路径规划算法从起点开始规划出一条到终点的最佳移动路径，并且能够避开区域内的障碍物1。在二维尺度下，常用的路径规划算法包括 Dijkstra 算法2、遗传算法3、蚁群算法4、A*算法5、模拟退火算法6等。其中蚁群算法灵感来源于蚂蚁在寻找食物过程中发现路径的行为，采用正反馈机制，在每一次的迭代中，不断收敛，最终逼近路径选择的最优解。但在路径规划的过程当中，蚁群算法也容易陷入局部最优和收敛性差等问题7。文献 8将当前节点与终点夹角大小融入到距离启发函数当中，提高了蚁群算法搜索最优路径的效率。文献 9 提出了一种双种3 李伟刚,武君胜.专业学位研究生课程在线学习效果全过程监督 J.计算机教育,2022,331(7):91-95.4 蹇旭,陈婷.基于 K-means 算法的学生在线学习行为研究J.高师理科学刊,2022,42(12):39-43+50.5 裴浩.基于 Python+OpenCV 的课堂人脸签到微型系统 J.信息技术与信化,2023,274(1):181-184.6 陈宏松,安俊秀,陶全桧,等.基于 BERT-VGG16 的多模态情感分析模型 J.成都信息工程大学学报,2022,37(4):379-385.7 侯向宁,刘华春,侯宛贞.基于改进 VGG16 网络模型的花卉分类 J.计算机系统应用,2022,31(7):172-178.8 罗洁琳.基于视频的 K12 学生在线学习情感识别研究 D.武汉:华中师范大学,2021.9 陈小芹,谢志刚.基于归一化算法的教学质量评价研究 J.黑龙江生态工程职业学院学报,2023,36(1):91-95.10 赵卫东,施实伟,周婵.基于 ImageNet 预训练卷积神经网络的图像风格迁移 J.成都大学学报(自然科学版),2021,40(4):367-373.11 高慧.基于深度学习的视频目标检测算法研究 D.成都:电子科技大学,2021.12 唐康健,文展,李文藻.基于卷积神经网络的垃圾图像分类模型研究应用 J.成都信息工程大学学报,2021,36(4):374-379.【作者简介】李阳（1982），女，辽宁沈阳人，硕士研究生，讲师，研究方向：现代智能控制。（收稿日期：2023-05-12 修回日期：2023-05-28）2023 年第 10 期84计算机应用信息技术与信息化群蚁群算法，引入自适应步长搜索策略，通过具有差异化步长的两个种群相互协作提高算法寻优能力和搜索效率。文献10 结合蚁群算法和人工势场法，对蚁群的搜索过程进行引导，提高了算法的收敛性。文献 11 结合遗传算法，提出基于不同视野的异构蚁群算法，提高了蚁群算法的寻优能力。文献 12 增加了始末点路径上的信息素浓度，对启发因子进行改进，增大离终点更近的节点的权重，改进信息素浓度挥发公式，使其满足高斯分布，根据迭代次数进行动态改变。三部分算法的改进一定程度上减少了路径的长度，同时提高了算法收敛速度，使得算法具有更加稳定的收敛性。为了解决传统蚁群算法存在的不足，本文将从蚁群算法搜索过程中的启发函数、轮盘赌法转移概率、信息素浓度更新三个方面对算法进行改进，使得路径结果更优，算法收敛速度更快。1 栅格环境地图建模及运动规则描述1.1 栅格地图建模路径规划的前提是获取室内环境地图，后续根据所使用的地图特点，选择合适的路径规划算法计算出从地图中选定的起始点到终点的最优路径。常用的室内环境地图包括矢量地图、栅格地图等。矢量地图通过存储环境中的点、线、矩形、多边形、弧线等来构造地图。日常生活中常用的谷歌地图、百度地图就是采用的矢量地图。而栅格地图对实际地理位置的空间及亮度进行离散化操作，得到一系列的栅格表示的空间位置。相较于矢量地图，栅格地图容易创建、表示和保存，对于室内短距离路径规划来说效果较好。因此在实验过程当中，选用栅格地图构建出行人行走的地图。栅格地图的构建步骤主要分为以下几步。步骤一：栅格地图由矩阵来进行存储，常用 0 来表示栅格中可达区域，用 1 来表示障碍区域，由此构建出一个由“0”和“1”构成的二进制栅格矩阵。步骤二：从下到上，从左到右依次为每一个栅格标记序号 i(i=1,2,)，则二维平面中，栅格中心点处坐标(x,y)与栅格序号的映射关系为：(,)0.5),(,)!00.5,0.5(,)amod i Lmod i LxLa elseyLaceil i L=+（1）式中：a 表示每一个正方形栅格的边长，通常在实验中的取值为 1。L 表示整个栅格在轴的长度，当取 a=1 时，L 的取值则为栅格矩阵行向量的长度。mod 表示取余运算，ceil 表示向上取整运算。步骤三：在 MATLAB 中，根据栅格矩阵行列数，设置地图横纵坐标范围，并利用 fill 函数将可达区域填充为白色，将障碍区域绘制成黑色。一个简易的栅格地图示意图如图 1所示。图 1 栅格地图示意图1.2 运动规则描述在基于栅格地图下的行走过程当中，需要对行走方式进行规定。规定从一个栅格出发，仅能够向相邻的可达区域栅格运动，即上、下、左、右、对角相邻栅格中标记为“0”的都是可以到达的区域。从而可以达到避障的效果。图 2 运动规则示意图在绘制好栅格地图后，根据上述行人运动规则，将栅格矩阵转化为存储距离的邻接矩阵，表示栅格中每一个栅格中心点到其他栅格中心的距离。距离公式为：,(,)0(,)0,(,)1m nimjn G m nDi jG m n+=（2）式中：Dm,n(i,j)表示从点(i,j)到点(m,n)的邻接矩阵元素取值，其中点(m,n)为点(i,j)的上、下、左、右、对角这8个相邻的点。G 表示由“0”和“1”组成的栅格矩阵。2 传统蚁群算法蚁群算法的最初起源是自然界中蚂蚁群的觅食行为。蚁群在觅食的过程当中，会在其经过的路径上释放出一种叫做信息素的化学物质，蚂蚁通过信息素来进行信息的传递，其他蚂蚁则能够感知到信息素的存在，信息素浓度越高的路径越能吸引到蚂蚁爬行经过此路径。随着选择这条路径的蚂蚁越来越多，该条路径上的信息素浓度也会越来越高，之后的蚂蚁也会以更高的概率选择此条路径，从而表现出一种信息正反馈的现象。通过这样的正反馈机制，蚁群相互合作，协同搜索，就能够找到去往目的地的最优路径。如图 3 所示。2023 年第 10 期85计算机应用信息技术与信息化图 3 蚁群算法原理图2.1 下一步栅格选择当蚁群在栅格地图中寻找最优路径时，由于运动规则描述的规定，从一个栅格到下一个栅格时，在邻近栅格没有障碍栅格的情况下，最多有 8 条路径可以选择。因此需要通过栅格之间的信息素浓度及栅格之间距离等因素来进行最终确定。基于轮盘赌法的转移概率计算公式为：()(),()()()0 kijijkkijijijk AttjAttPtothers =（3）式中：Pijk(t)表示蚂蚁由栅格 i 到栅格 j 的概率。ij(t)表示从栅格 i 到栅格 j 的信息素浓度。ij(t)为距离启发函数，通常是栅格 i 到栅格 j 之间的距离的倒数。是表示信息素浓度重要程度的参数，通常常数。是表示启发式因子重要程度的参数，通常也是常数。Ak表示尚未访问的栅格节点，会随着蚁群的访问而动态更新。2.2 信息素更新信息素浓度的更新是蚁群算法中最为重要的一步，影响着后面蚁群对于路径的选择。初期，人为确定一个初始的信息素浓度，随着一次次的迭代，不同蚁群先后出发寻找最优路径，经过各个栅格，会在栅格中释放信息素，信息素浓度会随着蚁群的选择而增加，但也会随时间而挥发。在经过每一次迭代后都需要对信息素进行更新，最终，距离最近的路径上信息素浓度最高，近似得到最优解。信息浓度更新公式为：1()(1)mkijijijkt=+（4）/!00 kkkijQ LLothers=（5）式中：表示信息素的蒸发率，取值在 0 1 之间。Vij(t)为第 k 只蚂蚁从栅格 i 到栅格 j 所释放的信息素。Q 表示信息素增加强度系数。Lk表示第 k 只蚂蚁选取的路径长度，当蚂蚁没有走到从指定起点走到终点时，Lk的取值为 0。3 改进的蚁群算法3.1 改进的启发函数在初始化启发式信息矩阵的过程中，传统的蚁群算法采用栅格 i 到栅格 j 距离的倒数作为启发函数。用来表示蚁群从栅格 i 到栅格 j 的期望程度和两个栅格之间的距离相关。1ijijd=（6）然而，由于从某一栅格仅能到达相邻或对角栅格，假设栅格长度取 1，那么 dij的取值只会出现 1 和2两种情况，期望程度的取值也会仅限于 1 和12两种情况。蚁群转移概率相近，区分度不高。这样会导致算法收敛速度较慢、算法复杂度较高且耗时较多，当迭代次数较少的时候，蚁群不一定能够寻找到最优路径。基于此缺陷，本文对启发函数进行改进。在蚂蚁选择下一个栅格进行运动时，由于可向相邻和对角的可达栅格转移，在这最多 8 个可选栅格中，选择离终点更近的栅格，更有可能寻找到最优路径。因此，将从栅格 i 到目的地栅格 D 的距离也加入到启发函数当中。通过增加期望程度，将蚁群引导至较短较优的路径上。因此可提高蚂蚁寻找到最优路径的概率，降低算法的迭代次数，减少算法耗时。改进的启发函数公式为：ij31=()ijiDdd+（7）式中：dij表示栅格 i 到栅格 j 的距离，diD表示栅格 i 到目的地栅格 D 的距离。和 分别是 dij和 diD在启发函数中的权重值，为常数。3.2 改进的转移概率函数蚂蚁在选择下一个路径进行转移的时候，根据三角形两边之和大于第三边的原理，希望它能够尽可能选择对角的可达栅格进行转移，这样能够避免蚂蚁在寻找路径的过程当中走折线，而选择距离较短的直线路径。反映到栅格地图当中，即当蚂蚁选择下一栅格进行转移时，在上、下、左、右栅格和对角栅格都是可达栅格的情况下，尽可能地选择对角栅格，从而能够局部减少路径长度，使得路径选择达到更优，如图4 所示。图 4 下一栅格选择示意图2023 年第 10 期86计算机应用信息技术与信息化相邻栅格之间的距离为 1，对角栅格之间距离为2，因此根据栅格之间的距离 dij进行区分，在转移概率中加入调节因子来增加对角栅格的权重。ijdijre=（8）加入调节因子后的转移概率公式为：()()(),()()()()0 kijijijkkijijijijk Attr tjAttr tPtothers=（9）式中：和 以及 类似，是表征调节因子重要程度的参数，也为常数。3.3 改进的信息素浓度公式传统的蚁群算法中，蚁群会在运动过程中释放信息素，改变信息素浓度，影响后面蚂蚁的对于路径的选择。但传统的蚁群算法中，蚁群容易受到较差路径上信息素浓度的干扰，使得无法寻找到最优路径，并且计算量较大、算法收敛速度慢。基于此，对信息素浓度更新公式进行改进，对于较优路径上的信息素进行增强，使其得到更多的补偿，而对于较差路径上的信息素浓度进行降低，增大各路径信息素释放的差异化程度，从而使得蚁群能够选择更短路径，提高路径规划的最优性，同时提高算法的收敛速度。改进的信息素浓度公式为：1()(1)mkijijijkt=+（10）/!00 kkkijQ DDothers=（11）22log()1.5 1.5kkminkkminkminkkminLLkDLkLkLLk=（12）式中：kmin为第 k 次迭代蚁群寻找的最优路径。3.4 算法整体流程本文提出的算法是在传统的蚁群算法基础上进行的改进，总体遵循传统蚁群算法步骤，主要分为以下几步。步骤一：初始化栅格地图，将栅格地图存储为“0”“1”元素表示的矩阵，并通过算法，将栅格矩阵转换为邻接矩阵。设置路径搜索的起始点与终点。步骤二：初始化蚁群算法的各个参数，如蚁群迭代次数（即蚂蚁出动多少群）、每一群蚂蚁出动的数量、表征信息素重要程度的参数、表征启发因子重要程度的参数、信息素增强系数等。步骤三：蚂蚁分群出动，进行迭代。按照运动规则描述，以及转移概率，在栅格地图中进行路径选择。每迭代一次，进行信息素的增强释放及挥发，更新一次信息素浓度。步骤四：重复步骤三，当所有蚂蚁群都迭代完毕之后，获取最优路径，得到路径规划结果。算法流程图如图 5 所示。图 5 改进的蚁群算法流程图4 实验结果及分析为了验证改进的蚁群算法的有效性及性能，利用MATLAB2018b 进行实验仿真。设置蚁群迭代次数为 100，每个蚁群中蚂蚁的个数为 50 只。栅格的边长设为单位 1。信息素重要程度参数 设置为 1，启发因子重要程度参数 设置为 7，信息素增强系数 Q 设置为 1，信息素蒸发系数 设置为 0.5。分别对 10 阶栅格矩阵和 20 阶栅格矩阵，利用蚁群算法进行实验，以观察算法在处理不同复杂度情况下的性能。实验过程中，分别对传统蚁群算法、文献 12 提出的改进蚁群算法以及本文提出的改进蚁群算法进行 20 次仿真实验，记录各算法取得的最优路径长度以及算法收敛的迭代次数，并进行比较。4.1 十阶栅格地图对比实验创建一个十阶的栅格矩阵，随机设置障碍栅格点，得到一个 1010 的栅格地图，将序号为 1 的栅格作为起始点，坐标为（0.5，9.5），将序号为100的栅格作为终点，坐标为（9.5，0.5）。对传统蚁群算法、文献 12 提出的算法以及本文改进的蚁群算法进行仿真实验，得到的蚁群路径轨迹图及收敛曲线图如图 6 图 8 所示。图 6 传统蚁群算法收敛曲线及路径轨迹 2023 年第 10 期87计算机应用信息技术与信息化图 7 文献 12 算法收敛曲线及路径轨迹图 8 本文改进蚁群算法收敛曲线及路径轨迹由图 6 图 8 可知，在 1010 的栅格地图实验中，由传统的蚁群算法得到的路径轨迹图出现了较多的折线轨迹，蚁群更多地选择走折线路径而非对角路径，这样会导致最终的路径长度较长，同时收敛速度也会较慢。文献 12 提出的改进的蚁群算法实验结果相比于传统的蚁群算法，蚁群更多地选择对角路径，因此能够得到更优的、距离更短的路径，同时路径也更加平滑，收敛速度更快。本文提出的改进的蚁群算法，相比于传统蚁群算法，能够寻找到更短更平滑的路径，且收敛速度比前两者更快。为具体比较各个算法性能，在实验过程中，记录每个算法每次实验计算得出的最优路径长度、迭代次数及算法耗时，并取 20 次实验的平均值，记录如表 1 所示。表 1 十阶栅格地图算法性能比较算法平均路径长度平均迭代次数算法平均耗时传统蚁群算法18.32411.334 0文献 12 算法15.0840.924 0改进蚁群算法14.4920.892 2由表 1 可知，在 1010 栅格地图环境下的实验中，本文算法的平均路径长度比传统蚁群算法减少了 22.54%，比文献12 算法减少了 3.91%。在迭代次数方面，传统蚁群算法平均迭代次数高达 66，且实验中常出现局部最优的情况。文献12 提出的算法平均迭代次数为 6。而本文提出的改进蚁群算法平均迭代次数仅为 2，相较于前两种算法，分别减少了95.12%和 40%。在算法耗时方面，本文算法平均耗时比传统蚁群算法减少了 33.12%，比文献 12 算法减少了 3.44%。以上数据表明，本文提出的改进的蚁群算法在 1010 的简单栅格地图情况下，具有路径搜索结果更优、收敛更快、效率更高的优点。4.2 二十阶栅格地图对比实验为了进一步验证算法的有效性及性能，本文设置了边长为 1 的 2020 的栅格地图，且设置更多的障碍栅格以构成一个更加复杂的运动环境。将序号为 1 的栅格作为起始点，坐标为(0.5,19.5)，将序号为 400 的栅格作为终点，坐标为(19.5,0.5)。再次对传统蚁群算法、文献 12 提出的算法以及本文提出的改进的蚁群算法进行仿真实验，得到的路径轨迹以及收敛曲线如图 9 图 11 所示。图 9 传统蚁群算法收敛曲线及路径轨迹 图 10 文献 12 算法收敛曲线及路径轨迹 图 11 本文改进蚁群算法收敛曲线及路径轨迹由图 9 图 11 可以看出，在 2020 的复杂栅格地图环2023 年第 10 期88计算机应用信息技术与信息化境中，传统的蚁群算法依旧出现了蚁群选择折线路径而非对角路径的现象，导致路径长度无法达到更优，且收敛速度随着环境的复杂度增加而变得更慢。且在实验过程中多次出现局部最优的情况。文献 12 提出的算法得到的路径长度与本文提出算法得到的路径长度基本一致，都比传统蚁群算法更短更平滑，而本文提出的算法在收敛性上比文献 12 更优。2020 的复杂栅格环境下，三种算法的平均路径长度、平均迭代次数以及平均算法耗时如表 2 所示。表 2 二十阶栅格地图算法性能比较算法平均路径长度平均迭代次数平均算法耗时传统蚁群算法36.24889.325 4文献 12 算法29.80426.774 8改进蚁群算法29.21156.603 6由表 2 数据可知，在 2020 的复杂栅格环境中，本文算法得到的平均路径长度比传统蚁群算法减少了 19.40%，比文献 12 算法的平均路径长度减少了 1.98%。收敛性方面，本文算法平均在第 15 代时就可以达到收敛，比传统算法提高了82.95%，比文献 12 算法提高了 41.64%。在算法耗时上，本文算法平均耗时比传统蚁群算法降低了 29.19%，比文献 12算法降低了2.52%。由此可以得出，本文提出的改进蚁群算法，在简单栅格环境和复杂栅格环境中，具有搜索路径更优、收敛更快、效率更高的优越性。5 结语本文主要针对蚁群算法在运用到路径规划问题时，路径并非最优且收敛速度慢的情况，对传统蚁群算法进行了改进。首先将下一栅格点到终点距离添加到启发函数中，然后在转移概率公式中，添加调节因子，增大蚂蚁选择对角路线的概率，最后对信息素浓度更新公式进行改进，加大信息素在不同长度路径上释放信息素浓度的差异化，使得蚂蚁搜索的路径达到更优，同时提高了算法的收敛速度，减少了算法用时。仿真实验的结果表明，本文提出的改进的蚁群算法，能够使蚁群搜索路径更短、更优且更加平滑。算法也提升了蚁群寻路的收敛速度，使得蚁群较少的迭代次数就可以寻找到最优路径。同时，算法在耗时上也有了明显降低。实验表明，本文提出的算法有实际的优越性以及实用性。参考文献：1 王春颖,刘平,秦洪政.移动机器人的智能路径规划算法综述 J.传感器与微系统,2018,37(8):5-8.2 GU C L,FENG A S,WANG G Z,et al.Robot path planning of improved adaptive ant colony system algorithm based on dijkstraJ.Journal of robotics,2022,2022(2):1-111.3 王豪,赵学军,袁修久.基于改进自适应遗传算法的机器人路径规划 J.电光与控制,2022,29(5):72-76.4 FEI T,WU X X,ZHANG L Y,et al.Research on improved ant colony optimization for traveling salesman problemJ.Mathematical biosciences and engineering(MBE),2022,19(8):8152-8186.5 沈斯杰,田昕,袁千贺.融合改进 A*和时间弹性带的移动机器人路径规划算法 J.智能计算机与应用,2022,12(11):96-102.6 牛秦玉,李博.基于模拟退火遗传算法的全向 AGV 路径规划 J/OL.计算机集成制造系统:1-212023-02-22.https:/ 张松灿,普杰信,司彦娜,等.蚁群算法在移动机器人路径规划中的应用综述 J.计算机工程与应用,2020(4):1-14.8 刘加奇,王泰华,董征.基于改进蚁群算法的移动机器人路径规划 J.传感器与微系统,2022,41(5):140-143.9 刘睿,杨程伟,高长水,等.基于双种群蚁群算法的 AGV路径规划研究 J.计算机测量与控制,2023,31(5):193-199+206.10 LIU J,YANG J,LIU H,et al.An improved ant colony algorithm for robot path planningJ.Soft computing,2017,21(19):5829-5839.11 LEE J.Heterogeneous-ants-based path planner for global path planning of mobile robot applicationsJ.International journal of control automation and systems,2017,15(4):1754-1769.12 高茂源,王好臣.基于改进蚁群算法的移动机器人路径规划 J.传感器与微系统,2021,40(6):142-144+148.【作者简介】刘羽翀（1998），男，四川成都人，硕士研究生，研究方向：室内定位技术。邓平（1964），男，四川宜宾人，博士，教授，研究方向：无线网络定位技术、惯性导航技术、现代信号处理等。（收稿日期：2023-03-21 修回日期：2023-03-30）