基于改进蚁群算法的城市交通路径规划研究.pdf
《基于改进蚁群算法的城市交通路径规划研究.pdf》由会员分享,可在线阅读,更多相关《基于改进蚁群算法的城市交通路径规划研究.pdf(4页珍藏版)》请在咨信网上搜索。
1、 2023 年第 7 期195智能技术信息技术与信息化基于改进蚁群算法的城市交通路径规划研究张 格1ZHANG Ge 摘要 针对传统蚁群算法应用于城市交通存在频繁死锁、未能迭代出最优解,收敛速度慢等缺陷,提出一种改进蚁群算法的城市交通路径规划方法。首先,通过道路权重信息和 A*算法的初始解设置信息素的初始浓度。其次,使用目标综合权重为启发因子改进启发函数,接力点最优和剪枝点隐藏的混合策略优化转移概率。最后,采用奖惩机制改进信息素的更新方式,引入停滞阶段使信息素的消失水平自适应调整,由此对信息素的变化范围动态限制。利用微观交通仿真软件(simulation of urban mobility,S
2、UMO)进行试验,结果表明所提出的方法可以适应城市交通变化规划出最优路径,蚁群收敛速度明显提升。关键词 蚁群算法;道路权重信息;动态适应;路径规划;SUMOdoi:10.3969/j.issn.1672-9528.2023.07.0491 湖北大学计算机与信息工程学院 湖北武汉 4300620 引言路径规划是无人驾驶技术中决策的重要组成部分,广泛应用于使用点线来描述问题的求解,其主要功能是在已知环境下,车辆规划出从起始位置到终点位置的完整路线。许多研究者针对路径规划问题对蚁群算法进行了改进:朱永强等人1使用双向 A*算法确定初始解,线性地改变信息素,而郑娟毅等人2结合模拟退火算法来确定蚁群算法
3、的初始解,Hou 等人3则提出一种蚁群沟通机制,同代和不同代的蚂蚁交流生成混合路径,根据不同路径分配不同信息素。Miao 等人4根据蚂蚁的综合权重表现转换为多目标优化问题进行求解。郑万群5基于工兵蚁策略来缓解蚂蚁易陷入 U 型陷阱造成解的质量过低的问题。Liang 等人6结合反馈机制,给特定人群制定不同的路线,实现动态调整路线。本文针对蚁群算法在复杂的城市路网中存在盲目搜索、频繁死锁、未能迭代出全局较优解、收敛速度慢等问题,在传统蚁群算法的基础上,通过设置初始信息素的浓度、优化状态转移概率规则、调整更新信息素的方式进行改进,仿真实验表明改进后的蚁群算法平均迭代次数有所减少,能够有效应用于城市交
4、通路径规划。1 传统蚁群算法传统蚁群算法是一种具有强大全局搜索能力的智能算法,广泛应用于解决旅行商、车辆调度等问题。初始每只蚂蚁所携带的信息素浓度一定,当其选择经过的路径越长,分布在路径上的信息素浓度就越低。蚂蚁通过其他蚂蚁在路径上留下信息素作为参考,容易更快找到食物。算法以栅格道路中的路径规划问题来描述,由于传统蚁群算法在解决旅行商问题时,每个城市之间是理想的相连状态,并计算城市之间的直线距离,而本文将其运用于实际路网中,每个结点并不是与每个路段的端点都保持相连,于是采用邻接表来存储每个结点的相邻结点,实现结点之间的有向连接,符合现实世界中车辆单、双向通行的交通情况。在 t0时刻,每条道路具
5、有相同初始信息素浓度,m 只蚂蚁放在起始结点,那么该结点作为蚂蚁 k(k=1,2,m)访问的第一个结点,并设置为已访问,然后根据启发信息计算从结点 i 转移至结点 j 的概率kijP,以及判断结点是否未访问且为相邻结点来选择移动到下一结点 j,直至下一结点为终点或者陷入死锁,蚂蚁 k 完成搜索。到达终点的蚂蚁更新路径结点上的信息素,直至 m 只蚂蚁全部迭代完成,达到最大迭代次数的限制后算法结束。状态转移概率公式为:(1)式中:adjcentk表示蚂蚁可选择的下一结点的结点集合;ij表示结点 i 与结点 j 路径的信息素浓度;ij表示启发函数,取值为结点 i 到结点 j 之间距离的倒数;,分别表
6、示信息素和启发信息的重要程度。信息素的更新公式为:(2)(3)2023 年第 7 期196智能技术信息技术与信息化式中:表示信息素的消失水平;ij表示更新的信息素浓度;Q 表示信息素分配总值。2 改进蚁群算法2.1 设置初始信息素的浓度在传统蚁群算法中,初始信息素为相同数值,而在求解问题规模较大时则会导致蚁群迷失方向。为使蚂蚁朝着目标结点搜索,采用 A*算法预先搜索出一条最短路径,并利用城市交通中道路权值7,不均匀地给每条道路分配相差不大的信息素,稍微加大 A*算法搜出的结点路径信息素浓度,引导蚁群做出决策,初始信息素浓度的设置公式为:(4)式中:,表示调整初始信息素的参数;priority
7、表示道路权值。道路权值是指车辆在道路行驶过程中的花费,评估指标一般有道路长度、车旅时间、拥堵程度、收费花销等。本文 priority 取值依据公开地图(open street map,OSM)导出的现实地图中若干种不同的道路类型:高速主干道路、高速次干道路、高速第三级道路、主支路、次支路、住宅道路等分别对应不同的权值,其中高速主干路的权值最高。那么道路上的信息素浓度越大,则越可能被蚂蚁选择。2.2 优化状态转移概率规则为了增大解的搜索空间,避免陷入局部最优,采用轮盘赌与随机概率相结合的办法优化8。当全局最优路径长度逐代减少,表明蚁群处于非停滞阶段;当全局最优路径长度逐代保持一固定值,表明蚁群处
8、于停滞阶段。在蚂蚁处于非停滞、轻微停滞阶段时,使用轮盘赌增强信息素的作用效果,在蚂蚁处于严重停滞阶段时,使用随机概率来扩大解的范围。改进后,得出选择下一结点的公式为:(5)式中:停滞次数ns表示迭代时重复出现上一代最优解的次数;N2表示调整停滞阶段范围的阈限值。由(1)式知,传统蚁群在选择下一结点时,启发函数仅仅只考虑了距离的因素,在现实生活的城市交通道路通行中,有许多影响出行的外界因素,经常拥堵的道路会让出行者感到厌烦,而车辆越少、顺畅的道路则会使旅行者感到愉快,故将车旅时间作为主要考虑因素,综合考虑各个因素的影响并分析它们在通行时的重要性,改进启发函数,将距离替换成目标综合权重:(6)(7
9、)式中:s 表示道路长度;v 表示道路设计速度;w1、w2、w3、w4表示各因素对目标综合权重的权重系数9;表示实时交通流量;f 表示道路等级;w 表示天气状况。传统蚁群算法应用于城市交通还存在频繁陷入死锁,导致无法迭代出最优解的问题10,本文提出一种接力点最优和剪枝点隐藏的改进算法,能够在死锁之前就避开选择陷阱结点,继续搜索最优解。算法步骤:(1)获取全局最优路径、A*算法得出的最短路径数组,避免剪去可能的最优结点。(2)建立死锁路径结点数组,即接力点到死锁点所经过的结点。接力点即全局最优路径与当前路径比较,完全相同的最后交集点。(3)保存当前死锁路径数组,为蚂蚁在接力搜索时是否存在陷入同一
10、死锁路径作判断。将本次死锁路径结点与上次死锁路径结点逐个比较,若完全相同,则表明蚂蚁陷入同一死锁路径,此时接力点为起点;若不相同,则表明蚂蚁产生新的死锁路径,此时接力点非起点。(4)重新生成一只蚂蚁至起点处,起点已访问。若接力点为起点,由公式(5)得出下一结点;若接力点并非起点,将起点至接力点的最优路径结点置为已访问,并置下一结点为接力点,蚂蚁从接力点继续搜索。(5)建立剪枝点数组。倒序判断当前死锁路径结点,若该结点没有出边即零分支结点,则收录该结点;若该结点仅有一条出边即单分支结点,则继续判断,直到找到一个不为单分支的结点或者比较完毕,将最后一个判断为单分支且不属于最短路径和全局最优路径的结
11、点收录。将剪枝点数组中的元素置为已访问,隐藏结点。(6)建立当前蚂蚁的全部死锁路径结点。在信息素更新时会对本次全部死锁路径惩罚,降低信息素浓度,在下一只蚂蚁搜索时清空重置。该算法可以使蚂蚁无论第几次陷入死锁点,都可以从接力点继续搜索,得到一条从起点至终点的完整搜索路径,促使蚂蚁找到最优解,从而提高解的质量。2.3 改进更新信息素的方式为了提高蚂蚁的收敛速度,本文对每只蚂蚁进行信息素的奖励与惩罚。用当代和全局最优蚂蚁的解进行信息素增加,用全局最差蚂蚁的解对死锁路径结点进行信息素减少,为避免惩罚与奖励效果的抵消,死锁路径不包括与最优路径的重叠部分。()bestiterbestijiterbestw
12、orstLLQt=LL (8)式中:Q 表示信息素分配总值;Lworst表示全局最差路径长度;Lbest表示全局最优路线长度;Literbest表示当前迭代的最优路线 2023 年第 7 期197智能技术信息技术与信息化长度,如果当代搜索到的路线越好,表明 Literbest值越小,那么奖励信息素就会越多。信息素的消失水平 的取值会影响算法的收敛速度和解的多样性,若 取值过小,表明信息素的消失较少,那么信息素会随时间持续积累,留存在路径上的信息素浓度越来越高,在一定程度上可以提高引导能力,但可能会使蚂蚁陷入到局部最优之中;若 取值过大,表明信息素的消失较多,那么信息素会随时间持续消失,留存在路
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 改进 算法 城市交通 路径 规划 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。