基于梯度统计变异量子遗传算法的车辆路径规划.pdf
《基于梯度统计变异量子遗传算法的车辆路径规划.pdf》由会员分享,可在线阅读,更多相关《基于梯度统计变异量子遗传算法的车辆路径规划.pdf(10页珍藏版)》请在咨信网上搜索。
1、基于梯度统计变异量子遗传算法的车辆路径规划李晖,秦慧萍,卢凯,韩子傲(哈尔滨商业大学计算机与信息工程学院,哈尔滨150028)通信作者:秦慧萍,E-mail:q_摘要:针对传统路径规划算法收敛速度慢、稳定性差、易陷入局部极值的问题,提出一种基于梯度统计变异量子遗传算法的车辆路径规划方法.首先在依据染色体适应度值动态调整旋转角步长的基础上,引入梯度下降思想对量子旋转门调整策略进行改进;根据染色体变化趋势的统计特性,设计基于梯度统计的变异算子实现变异操作,提出基于量子位概率密度的自适应变异策略;以路径最短为指标建立车辆路径规划模型,通过仿真实验验证改进算法在车辆路径规划中的有效性,与其他优化算法相
2、比,本文改进算法所规划路径长度更短,搜索稳定性更好,能有效控制算法陷入局部最优.关键词:量子遗传算法;路径规划;梯度下降;自适应变异算子;量子旋转门;变异策略引用格式:李晖,秦慧萍,卢凯,韩子傲.基于梯度统计变异量子遗传算法的车辆路径规划.计算机系统应用,2023,32(12):161170.http:/www.c-s- Path Planning Based on Gradient Statistical Mutation Quantum Genetic AlgorithmLIHui,QINHui-Ping,LUKai,HANZi-Ao(SchoolofComputerandInformat
3、ionEngineering,HarbinUniversityofCommerce,Harbin150028,China)Abstract:Tosolvetheslowconvergence,poorstability,andpronenesstofallintolocalextremesoftraditionalpathplanningalgorithms,thisstudyproposesavehiclepathplanningmethodbasedonagradientstatisticalmutationquantumgeneticalgorithm.Firstly,basedonth
4、edynamicadjustmentoftherotationanglestepbythechromosomefitnessvalue,theideaofgradientdescentisintroducedtoimprovetheadjustmentstrategyofthequantumrotationgate.Accordingtothestatisticalcharacteristicsofchromosomevariationtrend,amutationoperatorbasedongradientstatisticsisdesignedtorealizemutationopera
5、tion,andanadaptivemutationstrategybasedonQubitprobabilitydensityisputforward.Thenthevehiclepathplanningmodelisbuiltwiththeshortestpathastheindex.Finally,theeffectivenessoftheimprovedalgorithminvehiclepathplanningisverifiedbysimulationexperiments.Comparedwithotheroptimizationalgorithms,theproposedalg
6、orithmhasashorterpathandbettersearchstabilitytoavoidthealgorithmfromfallingintothelocaloptimum.Key words:quantumgeneticalgorithm(QGA);pathplanning;gradientdescent;adaptivemutationoperator;quantumrotationgate;mutationstrategy自动驾驶汽车将成为未来车辆领域的发展方向,其核心是自动驾驶技术.路径规划17作为自动驾驶技术的关键环节之一,已成为自动驾驶领域的研究热点.Hou 等8提
7、出一种具有通信机制的增强蚁群算法进行路径规划,通过个体之间的直接通信,加速历史路径的整合,同时对路径选择规则和启发式函数进行改进,提计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(12):161170doi:10.15888/ki.csa.009313http:/www.c-s-中国科学院软件研究所版权所有.Tel:+86-10-62661041基金项目:黑龙江省自然科学基金优秀青年项目(YQ2020G002);黑龙江省普通本科高等学校青年创新人才培养计划(UNPYSCT-2020212)收
8、稿时间:2023-05-24;修改时间:2023-06-26;采用时间:2023-07-03;csa 在线出版时间:2023-09-21CNKI 网络首发时间:2023-09-23SoftwareTechniqueAlgorithm软件技术算法161高算法收敛速度和搜索效率;Liu 等9提出一种基于改进灰狼算法的路径规划方法,引入基于狮子优化算法的干扰因子和动态权值,避免多样性的丧失,但是跳出局部最优的能力有待加强;Kumar 等10提出一种人工蜂群和进化规划算法结合的路径规划方法,采用人工蜂群算法根据改进策略进行初步搜索,之后采用进化算法对得到的可行路径进行细化,降低搜索成本;徐兴等11将灾
9、变策略和内嵌 A*算法的动态变异算子引入遗传算法中,降低早熟现象并且提高算法后期的局部搜索能力,同时具有多约束条件的适应度函数提高了所规划路径的平滑度,但是每次灾变初始化种群,降低了计算效率.遗传算法(geneticalgorithm,GA)虽然全局搜索能力强,具有易于扩展其他算法的特性;但是后期染色体相似度高,存在早熟收敛问题1214.量子遗传算法(quantumgeneticalgorithm,QGA)15是遗传算法结合量子计算产生的一种新兴智能优化算法.根据量子态的叠加、纠缠等特性,引入量子编码和量子旋转门更新操作,相较于遗传算法,量子遗传算法具有更好的种群多样性和收敛速度.然而,基本量
10、子遗传算法主要依靠量子旋转门进行种群更新,在组合优化问题1619求解时,仍存在稳定性低、收敛性差,陷入局部最优不易跳出的问题.本文提出一种基于梯度统计变异量子遗传算法的车辆路径规划方法,采用动态调整量子旋转门策略,在根据染色体适应度值动态调整旋转角步长的基础上,引入梯度下降思想,提高算法的收敛能力和全局搜索的稳定性;根据染色体变化趋势的统计特性,设计变异算子代替量子非门实现变异操作,提出基于量子位概率密度的自适应变异策略,以提高算法跳出局部最优的能力.通过路径规划仿真实验分析,验证算法有效性.1基本量子遗传算法量子位(quantumbit,Qubit)是量子计算机的最小信息单元,在一个双态量子
11、系统中,一个量子位状态可描述为20:|=|0+|1(1)|0|1|0|1其中,量子态处于态和态之间的叠加态,分别表示量子态和的概率幅,并且满足归一化条件20:|2+|2=1(2)采用量子位编码初始化种群,能够以小规模的种Q(0)=qi(0),(i=1,2,m)mqi(0)群包含复杂的种群信息.一个初始化量子种群为,为种群规模,每个个体用一条染色体表示,一条染色体代表一个可行解,其编码形式如式(3)所示:qi(0)=?1i1(0)2i1(0)ki1(0)1in(0)2in(0)kin(0)1i1(0)2i1(0)ki1(0)1in(0)2in(0)kin(0)?(3)qi(0)inkjir(0)
12、=jir(0)=1/2i=1,2,m r=1,2,nj=1,2,k其中,表示初始化种群中第 个染色体;为一个可行解中包含的基因位个数,为每个基因位编码中包含的量子位个数.种群初始化时,为了确保种群分布的均衡性,染色体中每个量子位的概率幅:,其中,;.量子遗传算法利用量子旋转门更新量子位的概率幅实现对问题的搜索寻优.通常采用的量子旋转门如式(4)所示21:U()=cossinsincos(4)其中,为旋转角度.|更新后的量子态为:?=U()|=cossinsincos(5)|0|1其中,分别表示更新后量子态和的概率幅.在双态量子系统中,量子位概率幅的更新如图 1所示.量子位概率幅的取值具有连续性
13、,因此量子遗传算法具备连续空间搜索能力.|0|1o图 1量子位概率幅更新2梯度统计变异量子遗传算法 2.1 自适应量子旋转门染色体更新过程中,量子旋转门的旋转角度 起到计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第12期162软件技术算法SoftwareTechniqueAlgorithm关键作用,其大小和符号决定染色体进化的速度和方向.在基本量子遗传算法中,量子旋转门的旋转角度通过查表获得,实现方式繁琐,并没有根据所需解决的具体问题给出旋转角度选择的依据.另外,通过查表获得的旋转角度 不仅没有考虑种群中染色体的差异性,而且也未充分利用搜索点的变化趋势.(0,0)T
14、(1,1)T量子门的旋转角度 的大小和符号会直接影响算法的收敛速度,因此,通过最优染色体与当前染色体对应量子位的概率幅计算量子门旋转方向22.可以保证当前染色体朝最优染色体方向进化.令为当前最优染色体中某量子位的概率幅,是当前染色体中相应量子位的概率幅,记:A=?0101?(6)A,0sgn(A)A=0旋转角 的方向选取原则为:当时,方向为;当时,方向随机选择.考虑到同一代种群中不同染色体之间的差异,以及不同代种群之间染色体基因位的变化趋势对群体进化的影响,将旋转角度的大小和染色体适用度值联系起来,同时引入梯度下降思想研究染色体基因位的变化趋势,提出一种旋转角步长自适应调整的方法:jir=sg
15、n(A)0exp(a|fitbest fiti|fitbest+(a1)|f(Xir)frmin|frmaxfrmin)(7)frmax=max?f(Xi)Xir?(i=1,2,m)(8)frmin=min?f(Xi)Xir?(i=1,2,m)(9)jirij0a (0,1)fitiifitbestf(Xir)ifrminfrmax其中,表示第 个染色体第 r 个基因位中第 个量子位的旋转角度;表示初始旋转角步长;权值用以体现适应度函数值和基因位梯度对染色体进化程度的影响;为第 个染色体的适应度值;为当前最优染色体的适应度值;为第 个染色体第r 个基因位的梯度;和分别为当前种群中第 r 个基因
16、位的梯度最小值和最大值.动态调整量子旋转门策略既考虑染色体适应度值又兼顾染色体基因位变化趋势,当染色体适应度值距离最优染色体较远且量子位梯度变化较小时,增大旋转角度,加快收敛,反之则需要减小旋转角度,避免错过最优染色体,以此提高算法的收敛速度和全局搜索的稳定性.2.2 量子变异量子遗传算法虽然具有较强的全局搜索能力,但仅通过量子旋转门进行种群更新,易陷入局部最优.因此,需要对种群进行一定的扰动操作,减少“早熟”现象的发生.传统方法通常采用量子非门对种群中个体量子位的概率幅进行变异操作,虽然一定程度上能够避免陷入局部最优,但是当执行变异操作的染色体非常接近最优染色体时,量子非门变异会造成量子位更
17、新方向的反转,可能造成种群动荡,优秀染色体信息丢失.另外,该变异算子没有考虑种群中所包含的生物体信息及外部环境等干扰因素对染色体基因变异的影响,缺乏群体观念.Zir从全局上,根据过往染色体信息对当前染色体基因位的影响考虑量子位变异问题,使量子变异操作能够在种群进化过程中施加合理的扰动,避免种群过早收敛.由于基因遗传信息随遗传代数的增加而递减,当前染色体基因位受父代染色体的影响最大,因此,仅考虑父代染色体对当前染色体基因位的影响,统计过往染色体基因位适应度值的梯度:Zir=f(Xir)+o(f(Xir)(10)o(f(Xir)f(Xir)其中,表示子代和父代梯度的高阶无穷小量.根据染色体基因位的
18、变化趋势设计概率密度函数:f(Zir)=5lbl1exp(Zirbl2)/bl3)2)(11)bl1bl2bl3(l=1,2,5)其中,和为高斯混合分布参数.将式(11)转化为概率分布函数:F(Zir)=5lbl1Zirexp(Zirbl2)/bl3)2)(12)采用量子位梯度的概率分布作为变异算子对量子位概率幅进行变异操作,如式(13)所示:jir(t)=1F(Zir)jir(t)=1jir(t)2(13)jir(t)tirj|0jir(t)tirj|1其中,表示第 代第 个染色体第 个基因位的第个量子位态的概率幅;表示第 代第 个染色体中第 个基因位的第 个量子位态的概率幅.另外,在种群进
19、化过程中,合理的变异概率有利于2023年第32卷第12期http:/www.c-s-计 算 机 系 统 应 用SoftwareTechniqueAlgorithm软件技术算法163提高种群进化的多样性和稳定性.根据种群中染色体的进化趋势,提出基于量子位概率密度的自适应变异机制:依据染色体基因位适应度值的梯度确定当前量子位的变异概率,在染色体进化过程比较“平坦”时,给予一个大的扰动概率,使染色体跳出局部最优,增加种群多样性;在染色体进化过程比较“陡峭”时,给予一个小的扰动概率,避免破坏拥有优良基因的个体,提高种群的稳定性.依据自适应变异概率随机选择个体中的量子位,施加变异操作,自适应变异概率如式
20、(14)所示:pm=P(Z Zir)=1F(Zir)=15lbl1Zirexp(Zlrbl2)/bl3)2)(14)梯度统计变异量子遗传算法的流程如图 2 所示.开始是否设置初始参数及初始化种群初始量子位坍缩初始染色体适应度评价是否满足终止条件量子位坍缩染色体适应度评价,计算基因梯度 f(Xir)量子旋转门依据 ir 自适应更新染色体自适应量子变异输出最佳染色体及其适应度值结束jt=t+1图 2梯度统计变异量子遗传算法流程图3基于梯度统计变异量子遗传算法的车辆路径规划针对车辆路径规划问题,本文的主要目标:在规避静态障碍物的基础上,得到一条长度最短的可行路径.做出如下假设:1)车辆在有限平面空间
21、中由起始点到目标点匀速移动,2)在车辆行驶过程中,障碍物的形状大小、地理位置均不发生改变;3)车辆相对地图中的静态障碍物可看作一个质点.3.1 构建环境地图以某工业园区建筑布局为例,采用栅格地图23进行车辆路径规划研究,如图 3 所示,其中白色栅格表示可行驶区域,黑色栅格表示障碍物.车辆的起始点和目标点在图中用五角星符号标记.201918171615141312109876543201 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 201图 32020 的栅格地图 3.2 车辆路径规划实现20202020利用梯度统计变异量子遗传算法规划车辆行驶路径
22、,首先需要进行路径编码,通常采用空间位置点(规划空间中的路径点作为染色体的基因位)序列表示车辆行驶路径.这种表示形式只需要考虑每个空间位置点的可行性问题,有利于路径规划的计算.假设规划空间为图 3 所示的栅格地图,在规划空间内有个路径点,条路径点组合,在栅格地图中,对同一条平行线上的路径点进行量子位编码,然后将量子编码的路径点排列,构成一条可行路径,即构成一条染色体.染色体编码形式如图 4 所示.第 i 条染色体量子位基因位Xi11Xi21Xi22Xir1Xir2XirjXirkXin1Xin2XinjXinkXi12Xi1jXi2jXi1kXi2k图 4染色体编码计 算 机 系 统 应 用h
23、ttp:/www.c-s-2023年第32卷第12期164软件技术算法SoftwareTechniqueAlgorithmpoint_fitway_fit路径规划主要考虑安全性及路径代价,本文以路径最短作为车辆路径规划的路径代价.采用路径点评价函数确定路径点量子态更新,根据路径评价函数确定对路径的选择.采用欧氏距离构造路径点评价函数,如式(15)所示,计算路径点到起始点和目标点的距离之和,距离越小,所需代价越小.minpoint_fit=(xirxs)2+(yirys)2+(xirxg)2+(yiryg)2(15)(xir,yir)ir(xs,ys)(xg,yg)其中,表示第 条染色体中第 个
24、路径点坐标;表示起始点坐标;表示目标点坐标.路径评价函数计算所有路径点依次连接的路径总长度,如式(16)所示:minway_fit=M1r=1(xirxir+1)2+(yryir+1)2(16)M其中,为一条路径中所有路径点的个数.在车辆路径规划中,根据式(6)式(9)对染色体中路径点的每个量子位编码进行量子旋转门自适应更新.由于路径点的适应度值是离散的,染色体中路径点的梯度利用相邻两代的一阶差分表示:frmax=max|f Xir(t1)f Xir(t)|(17)frmin=min|f Xir(t1)f Xir(t)|(18)i=1,2,m其中,.通过统计过往染色体中路径点的梯度信息,得到式
25、(11)中参数的具体数值:(b1b2b3)T=0.7521 0.1421 0.1519 0.6852 0.043520.5204 2.0720.19080.42045.7430.9951 2.1260.6099 1.012.565基于梯度统计变异量子遗传算法的车辆路径规划的总体流程如下.1)构建环境地图.根据已知的规划空间构建栅格地图.mt0Q(0)jir(0)=jir(0)=1/22)初始参数设置及种群初始化.设置种群规模popsize 为,进化代数 以及旋转角初始值,确定车辆行驶的起始点和目标点位置,对路径点进行量子编码,初始化种群,初代染色体中每个路径点量子位的概率幅.Q(0)3)初始量
- 配套讲稿:
如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。