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

2023 年第 7 期195智能技术信息技术与信息化基于改进蚁群算法的城市交通路径规划研究张 格1ZHANG Ge 摘要 针对传统蚁群算法应用于城市交通存在频繁死锁、未能迭代出最优解，收敛速度慢等缺陷，提出一种改进蚁群算法的城市交通路径规划方法。首先，通过道路权重信息和 A*算法的初始解设置信息素的初始浓度。其次，使用目标综合权重为启发因子改进启发函数，接力点最优和剪枝点隐藏的混合策略优化转移概率。最后，采用奖惩机制改进信息素的更新方式，引入停滞阶段使信息素的消失水平自适应调整，由此对信息素的变化范围动态限制。利用微观交通仿真软件(simulation of urban mobility,SUMO)进行试验，结果表明所提出的方法可以适应城市交通变化规划出最优路径，蚁群收敛速度明显提升。关键词 蚁群算法；道路权重信息；动态适应；路径规划；SUMOdoi：10.3969/j.issn.1672-9528.2023.07.0491 湖北大学计算机与信息工程学院 湖北武汉 4300620 引言路径规划是无人驾驶技术中决策的重要组成部分，广泛应用于使用点线来描述问题的求解，其主要功能是在已知环境下，车辆规划出从起始位置到终点位置的完整路线。许多研究者针对路径规划问题对蚁群算法进行了改进：朱永强等人1使用双向 A*算法确定初始解，线性地改变信息素，而郑娟毅等人2结合模拟退火算法来确定蚁群算法的初始解，Hou 等人3则提出一种蚁群沟通机制，同代和不同代的蚂蚁交流生成混合路径，根据不同路径分配不同信息素。Miao 等人4根据蚂蚁的综合权重表现转换为多目标优化问题进行求解。郑万群5基于工兵蚁策略来缓解蚂蚁易陷入 U 型陷阱造成解的质量过低的问题。Liang 等人6结合反馈机制，给特定人群制定不同的路线，实现动态调整路线。本文针对蚁群算法在复杂的城市路网中存在盲目搜索、频繁死锁、未能迭代出全局较优解、收敛速度慢等问题，在传统蚁群算法的基础上，通过设置初始信息素的浓度、优化状态转移概率规则、调整更新信息素的方式进行改进，仿真实验表明改进后的蚁群算法平均迭代次数有所减少，能够有效应用于城市交通路径规划。1 传统蚁群算法传统蚁群算法是一种具有强大全局搜索能力的智能算法，广泛应用于解决旅行商、车辆调度等问题。初始每只蚂蚁所携带的信息素浓度一定，当其选择经过的路径越长，分布在路径上的信息素浓度就越低。蚂蚁通过其他蚂蚁在路径上留下信息素作为参考，容易更快找到食物。算法以栅格道路中的路径规划问题来描述，由于传统蚁群算法在解决旅行商问题时，每个城市之间是理想的相连状态，并计算城市之间的直线距离，而本文将其运用于实际路网中，每个结点并不是与每个路段的端点都保持相连，于是采用邻接表来存储每个结点的相邻结点，实现结点之间的有向连接，符合现实世界中车辆单、双向通行的交通情况。在 t0时刻，每条道路具有相同初始信息素浓度，m 只蚂蚁放在起始结点，那么该结点作为蚂蚁 k（k=1，2，m）访问的第一个结点，并设置为已访问，然后根据启发信息计算从结点 i 转移至结点 j 的概率kijP，以及判断结点是否未访问且为相邻结点来选择移动到下一结点 j，直至下一结点为终点或者陷入死锁，蚂蚁 k 完成搜索。到达终点的蚂蚁更新路径结点上的信息素，直至 m 只蚂蚁全部迭代完成，达到最大迭代次数的限制后算法结束。状态转移概率公式为：(1)式中：adjcentk表示蚂蚁可选择的下一结点的结点集合；ij表示结点 i 与结点 j 路径的信息素浓度；ij表示启发函数，取值为结点 i 到结点 j 之间距离的倒数；，分别表示信息素和启发信息的重要程度。信息素的更新公式为：(2)(3)2023 年第 7 期196智能技术信息技术与信息化式中：表示信息素的消失水平；ij表示更新的信息素浓度；Q 表示信息素分配总值。2 改进蚁群算法2.1 设置初始信息素的浓度在传统蚁群算法中，初始信息素为相同数值，而在求解问题规模较大时则会导致蚁群迷失方向。为使蚂蚁朝着目标结点搜索，采用 A*算法预先搜索出一条最短路径，并利用城市交通中道路权值7，不均匀地给每条道路分配相差不大的信息素，稍微加大 A*算法搜出的结点路径信息素浓度，引导蚁群做出决策，初始信息素浓度的设置公式为：(4)式中：，表示调整初始信息素的参数；priority 表示道路权值。道路权值是指车辆在道路行驶过程中的花费，评估指标一般有道路长度、车旅时间、拥堵程度、收费花销等。本文 priority 取值依据公开地图(open street map,OSM)导出的现实地图中若干种不同的道路类型：高速主干道路、高速次干道路、高速第三级道路、主支路、次支路、住宅道路等分别对应不同的权值，其中高速主干路的权值最高。那么道路上的信息素浓度越大，则越可能被蚂蚁选择。2.2 优化状态转移概率规则为了增大解的搜索空间，避免陷入局部最优，采用轮盘赌与随机概率相结合的办法优化8。当全局最优路径长度逐代减少，表明蚁群处于非停滞阶段；当全局最优路径长度逐代保持一固定值，表明蚁群处于停滞阶段。在蚂蚁处于非停滞、轻微停滞阶段时，使用轮盘赌增强信息素的作用效果，在蚂蚁处于严重停滞阶段时，使用随机概率来扩大解的范围。改进后，得出选择下一结点的公式为：(5)式中：停滞次数ns表示迭代时重复出现上一代最优解的次数；N2表示调整停滞阶段范围的阈限值。由(1)式知，传统蚁群在选择下一结点时，启发函数仅仅只考虑了距离的因素，在现实生活的城市交通道路通行中，有许多影响出行的外界因素，经常拥堵的道路会让出行者感到厌烦，而车辆越少、顺畅的道路则会使旅行者感到愉快，故将车旅时间作为主要考虑因素，综合考虑各个因素的影响并分析它们在通行时的重要性，改进启发函数，将距离替换成目标综合权重：(6)(7)式中：s 表示道路长度；v 表示道路设计速度；w1、w2、w3、w4表示各因素对目标综合权重的权重系数9；表示实时交通流量；f 表示道路等级；w 表示天气状况。传统蚁群算法应用于城市交通还存在频繁陷入死锁，导致无法迭代出最优解的问题10，本文提出一种接力点最优和剪枝点隐藏的改进算法，能够在死锁之前就避开选择陷阱结点，继续搜索最优解。算法步骤：(1)获取全局最优路径、A*算法得出的最短路径数组，避免剪去可能的最优结点。(2)建立死锁路径结点数组，即接力点到死锁点所经过的结点。接力点即全局最优路径与当前路径比较，完全相同的最后交集点。(3)保存当前死锁路径数组，为蚂蚁在接力搜索时是否存在陷入同一死锁路径作判断。将本次死锁路径结点与上次死锁路径结点逐个比较，若完全相同，则表明蚂蚁陷入同一死锁路径，此时接力点为起点；若不相同，则表明蚂蚁产生新的死锁路径，此时接力点非起点。(4)重新生成一只蚂蚁至起点处，起点已访问。若接力点为起点，由公式(5)得出下一结点；若接力点并非起点，将起点至接力点的最优路径结点置为已访问，并置下一结点为接力点，蚂蚁从接力点继续搜索。(5)建立剪枝点数组。倒序判断当前死锁路径结点，若该结点没有出边即零分支结点，则收录该结点；若该结点仅有一条出边即单分支结点，则继续判断，直到找到一个不为单分支的结点或者比较完毕，将最后一个判断为单分支且不属于最短路径和全局最优路径的结点收录。将剪枝点数组中的元素置为已访问，隐藏结点。(6)建立当前蚂蚁的全部死锁路径结点。在信息素更新时会对本次全部死锁路径惩罚，降低信息素浓度，在下一只蚂蚁搜索时清空重置。该算法可以使蚂蚁无论第几次陷入死锁点，都可以从接力点继续搜索，得到一条从起点至终点的完整搜索路径，促使蚂蚁找到最优解，从而提高解的质量。2.3 改进更新信息素的方式为了提高蚂蚁的收敛速度，本文对每只蚂蚁进行信息素的奖励与惩罚。用当代和全局最优蚂蚁的解进行信息素增加，用全局最差蚂蚁的解对死锁路径结点进行信息素减少，为避免惩罚与奖励效果的抵消，死锁路径不包括与最优路径的重叠部分。()bestiterbestijiterbestworstLLQt=LL (8)式中：Q 表示信息素分配总值；Lworst表示全局最差路径长度；Lbest表示全局最优路线长度；Literbest表示当前迭代的最优路线 2023 年第 7 期197智能技术信息技术与信息化长度，如果当代搜索到的路线越好，表明 Literbest值越小，那么奖励信息素就会越多。信息素的消失水平 的取值会影响算法的收敛速度和解的多样性，若 取值过小，表明信息素的消失较少，那么信息素会随时间持续积累，留存在路径上的信息素浓度越来越高，在一定程度上可以提高引导能力，但可能会使蚂蚁陷入到局部最优之中；若 取值过大，表明信息素的消失较多，那么信息素会随时间持续消失，留存在路径上的信息素浓度越来越低，在一定程度上可以提高全局搜索能力，但可能会使蚂蚁陷入到盲目搜索之中。根据自适应蚂蚁系统的思想，将传统蚁群算法中的信息素消失水平 由固定值修改为依据判断蚁群处于不同阶段来进行动态变化，加速蚁群的收敛。在蚁群处于非停滞阶段时，通过逐渐减少信息素的挥发来加强信息素的引导作用，当蚁群开始进入停滞阶段时，需要扩大解的范围，此时增加信息素的挥发来增强蚁群的全局搜索能力，并且随着迭代的进行，惩罚路径的信息素逐渐降低，此时蚂蚁更容易找到更好的解。最终能够加快蚂蚁的收敛并保证得出一定质量的解。信息素消失水平 动态取值：(9)式中：Nc表示当前迭代次数；Nmax表示最大迭代次数；N1、N2表示调整停滞阶段范围的阈限值。为了避免后期在最优路径上积累的信息素过多和惩罚路径导致信息素过少，从而导致算法陷入停滞状态，无法搜索出全局最优路径11，由此对信息素变化的范围进行动态限制：(10)(11)式中，d 表示调整()maxijtt取值范围的参数。3 SUMO 仿真实验3.1 仿真环境搭建本文基于 SUMO 进行仿真实验，通过 OSM 导出湖北大学武昌校区的街道地图，使用命令行将地图文件(*.osm)转换为路网文件(*.net.xml)，利用 SUMO 应用工具中的网络编辑器(netedit)来修缮路网，删除无关的结点和边。在 SUMO中的地图显示如图 1 所示。图 1 湖北大学地图为验证本文算法 的优势，将三种算法进行对比：传统蚁群算法(ant colony optimization,ACO)，本文提出的改进蚁群算法(improved ant colony algorithm,IACA)，以及本文提出的IACA 算法在蚂蚁死锁时采用接力点最优和剪枝点隐藏混合策略的算法(relay-improved ant colony algorithm,R-IACA)。所有算法均采用 Python 语言进行编程，在湖北大学地图上选择两条不同的线路(Route1、Route2)来进行测试。地图结点数为 157 个,道路数为 346 条。为验证各个算法的自适应能力，所有参数保持一致：m=10，Nmax=50，=0.1，=0.05，Q=100，=0.1，b=0.5，d=200，N1=3，N2=5。3.2 仿真测试结果在 Route1 中，起点设置为结点 155(777.84,880.0)，终点设置为结点 150(1 241.39,955.47)。在 50 次的试验结果中，ACO 算法出现次数最多的最优路径结点为 155,5,22,21,10,4,13,25,55,149,150，路径长度为 689.16 m。IACA算法和 R-IACA 算法出现次数最多的最优路径结点为 155,64,107,65,108,56,104,66,68,60,55,149,150，路径长度为648.59m。连接各结点后路径如图 2 所示。图 2 不同线路各算法的最优路径结果在 Route2 中，起点设置为结点 75(1 019.77,498.78)，终点设置为结点 49(1 416.23,1 247.58)。在 50 次的试验结果中，ACO 算法出现次数最多的最优路径结点为 75,146,78,74,80,76,18,73,106,71,56,108,65,107,64,155,5,22,145,29,1,0,15,50,87,23,95,47,96,46,48,53,54,49，路径长度为 1 531.54m。IACA 算法和 R-IACA 算法出现次数最多的最优路径结点为 75,146,78,74,80,76,18,77,19,61,17,7,103,2023 年第 7 期198智能技术信息技术与信息化44,88,6,47,96,46,48,53,54,49，路径长度为 1 006.62m。连接各结点后路径如图 2 所示。由图 2 可以得出，在复杂的城市交通路径中，由于 ACO算法在更新信息素时仅采用结点之间距离作为启发，并且信息素固定的消失水平较低，所以蚂蚁容易陷入局部最优，难以迭代出最优解。IACA 算法虽然能够在较为简单的 Route1中多次迭代出最优解，但由于各结点联系较少，可选择的结点有限，所以蚂蚁容易陷入死锁，并且在稍复杂的 Route2 中，需要更多次的进行结点选择，可达终点的路径选择更多，所以蚂蚁极易陷入局部最优，导致收敛速度较慢。而 R-IACA算法利用接力点继续搜索，并且隐藏剪枝点，降低死锁路径的信息素，在一定程度上避免选择死锁路径，能够适应较复杂环境迭代出最优路径，相比之下所求得解更优。三种算法分别在 Route1、Route2 上进行 50 次的实验中的仿真结果如表 1 所示。表 1 不同算法在 50 次试验下仿真结果线路类别算法平均路径长度/m平均收敛次数未达最优路径次数Route1ACO736.42 48IACA675.821.0824R-IACA649.44.671Route2ACO1 334.9949IACA1 124.4323.3341R-IACA1 006.622.720由表 1 可以得出，在 Route1 中，R-IACA 算法在收敛速度方面相比 IACA 算法提高了 77.85%，在解的质量方面相比 ACO 算法、IACA 算法分别提高了 11.82%、3.91%。在Route2 中，R-IACA 算法在收敛速度方面相比 IACA 算法提高了 88.34%，在解的质量方面相比 ACO 算法、IACA 算法分别提高了 24.60%、10.48%。实验表明本文提出的 R-IACA算法可以适应城市交通环境的变化，加快蚁群的收敛速度。各算法分别在 Route1、Route2 上试验 50 次，得出最优路径长度的取值如图 3 所示。图 3 不同路线各算法的性能表现由图 3 可以得出，在 Route1 和 Route2 上，ACO 算法所得解波动大且解质量较差，并在 Route2 这条较复杂的线路上表现得更为明显，IACA 算法次之，而 R-IACA 算法搜索所得解较稳定且解质量较好。4 结语 本文针对传统蚁群算法应用于城市交通路径规划中存在的问题对蚁群算法进行了改进。通过在SUMO中的仿真对比，本文所提出的改进蚁群算法更能适应相对复杂的环境，明显提升蚂蚁收敛速度和求解质量，能够有效为无人驾驶车辆进行城市交通路径规划。参考文献：1 朱永强,孙宗涛.改进蚁群算法在物流机器人路径规划中的应用 J.科学技术与工程,2020,20(30):12467-12471.2 郑娟毅,付姣姣,程秀琦.面向物流车辆路径规划的自适应蚁群算法 J.计算机仿真,2021,38(04):477-482.3 HOU W B,XIONG Z H,WANG C S,et al.Enhanced ant colony algorithm with communication mechanism for mobile robot path planningJ.Robotics and autonomous systems,2022(148):1-10.4 MIAO C W,CHEN G Z,YAN C L,et al.Path planning optimization of indoor mobile robot based on adaptive ant colony algorithmJ.Computers&industrial engineering,2021(156):1-10.5 郑万群.基于分类搜索蚁群算法的机器人路径规划研究D.石家庄:河北工程大学,2018.6 LIANG S,JIAO T,DU W,et al.An improved ant colony optimization algorithm based on context for tourism route planningJ.PLoS ONE,2021,16(9):1-16.7吴奇伦.一种基于权值累加的多车辆动态路径规划算法J.工业控制计算机,2019,32(8):147-148+151.8 徐英卓,李凯,周俊.基于改进蚁群算法的钻井救援车辆路径规划 J.计算机系统应用,2022,31(4):268272.9 尹枭.基于蚁群算法的冷链物流配送路径优化及系统实现D.黑龙江:哈尔滨工业大学,2017.10 魏立新，张钰锟，孙浩等.基于改进蚁群和 DWA 算法的机器人动态路径规划J.控制与决策,2022,37(09):2211-2216.11 雷金羡,孙宇,朱洪杰.改进蚁群算法在带时间窗车辆路径规划问题中的应用 J.计算机集成制造系统,2022,28(11):3535-3544.【作者简介】张格（1999），女，湖北武汉，硕士，研究方向：路径规划、智能算法。（收稿日期：2023-01-09 修回日期：2023-02-27）