融合粒子群算法与改进灰狼算法的机器人路径规划.pdf
《融合粒子群算法与改进灰狼算法的机器人路径规划.pdf》由会员分享,可在线阅读,更多相关《融合粒子群算法与改进灰狼算法的机器人路径规划.pdf(8页珍藏版)》请在咨信网上搜索。
1、系统仿真学报系统仿真学报Journal of System Simulation第 35 卷第 8 期2023 年 8 月Vol.35 No.8Aug.2023融合粒子群算法与改进灰狼算法的机器人路径规划融合粒子群算法与改进灰狼算法的机器人路径规划曹梦龙,赵文彬*,陈志强(青岛科技大学 自动化与电子工程学院,山东 青岛 266061)摘要摘要:针对灰狼算法在处理机器人路径规划问题时存在路径较长、收敛速度较慢等问题,提出一种基于PSO与改进GWO的粒子群-灰狼混合算法(PSO-GWO)。通过多次运行PSO算法来确定初始狼群规模及初始适应度值;引入非线性收敛因子平衡GWO算法的探索和开发能力,提出
2、动态惯性权重因子来保证头狼领导制度及促进种群交流;运用莱维飞行和贪婪策略使算法有效避免局部最优,获得最优解。仿真结果表明:该算法相较于GWO算法在3种地图下平均路径长度缩短17%、16%、16.2%;平均运行时间缩短13%、8%、16%。关键词关键词:GWO;PSO;机器人路径规划;莱维飞行;非线性收敛因子中图分类号:TP391.9 文献标志码:A 文章编号:1004-731X(2023)08-1768-08DOI:10.16182/j.issn1004731x.joss.22-0407引用格式引用格式:曹梦龙,赵文彬,陈志强.融合粒子群算法与改进灰狼算法的机器人路径规划J.系统仿真学报,20
3、23,35(8):1768-1775.Reference format:Cao Menglong,Zhao Wenbin,Chen Zhiqiang.Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf AlgorithmJ.Journal of System Simulation,2023,35(8):1768-1775.Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf Algorith
4、mCao Menglong,Zhao Wenbin*,Chen Zhiqiang(College of Automation and Electronic Enginnering,Qingdao University of Science and Technology,Qingdao 266061,China)Abstract:Aiming at the long paths and slow convergence speed of GWO algorithm in robot path planning,a hybrid PSO-GWO algorithm based on PSO alg
5、orithm and the improved GWO algorithm is proposed.By running PSO algorithm for many times,the initial wolf group size and initial fitness value are determined.A nonlinear convergence factor is introduced to balance the exploration and development capabilities of GWO algorithm,and a dynamic inertia w
6、eight factor is proposed to ensure the leadership system of alpha wolf and to promote the population communication.Levy flight and greedy strategy are used to effectively avoid the local optima and obtain the optimal solution.Simulation experiments show that the average path length of the proposed a
7、lgorithm is reduced by 17%,16%and 16.2%compared with the GWO algorithm under three maps.The average running time is reduced by 13%,8%,16%.Keywords:GWO;PSO;robot path planning;Lvy flight;nonlinear convergence factor收稿日期:2022-04-25 修回日期:2022-07-15基金项目:山东省自然科学基金(ZR2020MF087)第一作者:曹梦龙(1971-),男,教授,博士,研究方向
8、为自主导航与智能控制。E-mail:cml_通讯作者:赵文彬(1997-),男,硕士生,研究方向为机器人导航、路径规划。E-mail:第 35 卷第 8 期2023 年 8 月Vol.35 No.8Aug.2023曹梦龙,等:融合粒子群算法与改进灰狼算法的机器人路径规划http:/www.china-0引言引言机器人提供搬运行李、指引地点等工作的主要步骤为识别环境、目标设定、导航1。其中,导航解决的主要问题之一是机器人路径规划(RPP)1。传统的路径规划算法2包括遗传算法(GA)、人工势场算法(APF)、随机路线图算法(RA)、A*算法3,其中,GA算法处理路径规划问题具有随机性、过早收敛等问
9、题;APF算法具有易陷入局部最优、无法处理斥力与引力函数等问题;RA算法存在路径过长、急转弯等问题2;A*算法存在实时性差、节点增多搜索效率差等问题3;群体智能优化算法通过对自然界生物习性的观察,模拟群体成员之间的信息共享和相互学习,不断改变探索方向,最终实现搜索路径的优化1-2。目前,许多群体智能算法被应用于RPP问题,其效果优于传统算法2。群体智能算法2包括蝙蝠优化算法4、人工鱼群优化算法5、灰狼优化算法(GWO)5,以及哈里斯、霍克斯优化等2。其中,GWO算法具有导航的实时性、在机器人和障碍物之间保持安全间隙的优点,但其作为智能优化算法,具有容易陷入局部最优的缺点,因此,研究人员在GWO
10、算法的基础上进行了改进。文献6在更新、狼初始位置时添加了干扰因子,以增强其主动搜索能力,通过动态权重防止灰狼陷入局部最优,有效提高了GWO算法的精度和收敛速度;文献7将GWO算法全局路径规划的节点作为APF算法的临时目标点,进行二次路径规划,该算法在全局静态环境和局部动态环境可取得较好效果;文献8为提升GWO算法处理复杂多目标路径规划的能力,引入非线性收敛因子平衡全局探索与局部开发能力,再利用布谷鸟算法进行二次种群位置更新,该算法提高了所得路径的精度;混合灰狼算法(HGWO)9利用反向学习产生初始种群,保证初始解精度,利用历史信息与精英反向学习确保算法的精度。由以上分析可知,这些文献提出的改进
11、策略对GWO算法的收敛性和精度都有一定提升,但很少有人关注初始解对GWO算法性能10的影响以及算法陷入局部最优如何解决的问题,或仅从数学角度改进初始种群产生方式9。针对上述问题,本文提出一种融合PSO算法与改进 GWO 算法的新算法PSO-GWO。先由PSO算法针对地图生成解,作为GWO算法中、狼的初始解,以提升GWO算法初始解的质量;通过非线性收敛因子平衡GWO算法对搜索空间的全局开发和局部勘探能力;通过采用动态惯性权重保证狼的领导作用,防止陷入局部最优;若GWO算法陷入局部最优,则运用基于莱维飞行的最优扰动策略,对结果进行扰动,同时运用贪婪策略保证结果最优。1算法简介算法简介1.1 粒子群
12、算法粒子群算法PSO算法主要通过更新粒子的速度、位置等信息寻找最优解,该算法具有原理简单、易于实现,有利于全局寻优的优点11-12。假设种群有N个粒子在D维空间搜索,初始粒子群算法更新表示为vt+1ij=vtij+c1r1(ptij-xtij)+c2r2(ptg j-xtij)(1)xt+1ij=xtij+vt+1ij(2)式中:t为迭代次数;vij为第i个粒子j维的速度;xij为第i个粒子j维的位置;为惯性权重;c1、c2为学习因子;r1、r2为随机数。1.2 灰狼算法灰狼算法GWO算法灵感来自于灰狼的狩猎行为和社会阶层13-14。灰狼被认为是顶级捕食者,处于食物链的顶端。其团队组成一般有5
13、12头,且具备严格的社会阶层14,狼群阶层如图1所示。狼作为领导阶层决定整个团队的狩猎、作息等生活习惯,其他阶层的狼遵从狼的决定;狼作为狼的从属者,对下级狼群进行协调,并协助狼做出决策;狼保证群体的安全;狼负责执行狼的决策。1769第 35 卷第 8 期2023 年 8 月Vol.35 No.8Aug.2023系统仿真学报Journal of System Simulationhttp:/www.china-GWO算法基于社会等级和狩猎策略进行优化,狼在不断追踪识别目标的位置,、狼提供关于目标位置的最佳信息,在搜索空间中随机生成一组优化问题的候选解14:d=|CWP(t)-W(t)|(3)W(
14、t+1)=WP(t)-Ad(4)式中:d为目标和狼之间的距离;W和WP(t)为灰狼位置和目标位置向量;t为当前迭代次数;A和C为狼的系数向量。A=2ar1-a(5)C=2r2(6)式中:收敛因子a在迭代过程中从2线性减少到0;r1、r2为0,1中的随机向量。因此,A的取值范围为-2,2,C的取值范围为0,2。灰狼有能力识别猎物的位置并包围他们,在优化过程中,狼群更新、狼的位置,每只狼都按照式(7)(13)重新排列和重新定位自己的位置。d=|C1W-W|(7)d=|C2W-W|(8)d=|C3W-W|(9)W=W-A1(d)(10)W=W-A2(d)(11)W=W-A3(d)(12)W(t+1)
15、=(W+W+W)3(13)式中:W、W、W分别为更新后、的位置;C1、C2、C3由式(6)决定;W(t+1)为寻优后的位置。2融合改进算法描述融合改进算法描述对GWO算法来说,初始种群选取不当会导致其无法收敛至最优解或收敛速度减慢13-14。本文采用PSO算法,通过运行3次产生的合法路径对结果进行排序,将路径长度与路径节点分别赋值给、狼。2.1 非线性收敛因子非线性收敛因子GWO算法具有自适应调整的线性收敛因子a和控制参数机制13-14。式(5)中,a线性减小使得位置调节系数A在-a,a区间内变化。当|A|1时,狼群全局搜索能力增强,有助于对全局搜索;当|A|1时,狼群集中靠近最优解。参数a在
16、此过程中线性减少,不能平衡该算法的全局搜索和局部开发能力,GWO算法有较大可能性陷入局部最优,并不利于处理RPP问题7。因此,本文引入非线性收敛因子a,其公式为a=am1-(et/tmax-1e-1)k(14)式中:t为当前迭代次数;tmax为最大迭代次数;am为收敛因子的初始值;k110为控制因子,k值越大,a衰减越慢,反之衰减越快。如图2所示,非线性收敛因子a衰减缓慢,因此,位置调节系数A在较大范围内变化,GWO算法具备较强探索全局空间能力,可以保证GWO算法在算法前期充分探索搜索空间;当算法运行到后期,种群收敛。a快速衰减有利于算法对局部的开发能力,有利于算法根据已有信息寻找最优解。2.
17、2 动态加权规则动态加权规则通过式(7)(13)可以看出,GWO算法通过、狼的位置更新灰狼位置,并没有考虑灰狼个体信息交流。这一缺点提高了GWO算法陷入局部最优的可能性。针对此问题,同时为了保持狼的领导作用,引入动态加权规则。图1 狼群阶层Fig.1 Wolf pack class 1770第 35 卷第 8 期2023 年 8 月Vol.35 No.8Aug.2023曹梦龙,等:融合粒子群算法与改进灰狼算法的机器人路径规划http:/www.china-C1=random(0 1)2(15)C2=1-random(0 1)2(16)C3=0.5(17)W(t+1)=C3W1+C2W2+C1W
18、3(18)动态加权规则通过保持头狼所占比重不变,对狼与狼引入随机惯性权重,促进狼与狼的交流。由于狼作为头狼一直发挥作用,结果可逐渐取最优值,狼与狼作为仅次于狼的狼群,通过对其采取不同的系数,有助于增加种群多样性,降低算法陷入局部最优的可能性。2.3 停滞扰动策略与贪心机制停滞扰动策略与贪心机制GWO算法由于其特殊的搜索机制易于陷入局部最优5。为防止GWO算法陷入局部最优,引入基于莱维飞行的停滞扰动策略10。莱维飞行概念由法国科学家Paul levy提出,其具有长时间以较小步长随机游走,偶尔以较大步长进行方向突变跳跃的特点15-16。本文利用其特性对GWO算法陷入局部最优进行干扰,由于莱维分布难
19、以使用MATLAB实现,本文采用Mantegna所提出的莱维飞行随机生成搜索路径的方法15。u=(1+)sin()2()1+22-12u=1(19)s=u/|v|1(20)式中:s为随机步长;u和v均为服从正态分布的参数,即uN(0 2n),vN(0 2v);为伽马函数;在每次迭代过程中,在(0 2)区间内选择一个随机值。通过这个策略,莱维飞行可以产生许多小的、偶尔长距离的跳跃,有助于开发和探索过程的平衡。若最优值保持多次迭代不变,且这段迭代次数与总迭代次数比值为1:20,则认为算法陷入局部最优,此时采用莱维飞行的特性更新种群搜索个体的位置,提高种群多样性,使算法跳出局部最优。扰动策略为Wt+
20、1i=W*+randnLevy(Wi)+randn|W*-Wt i|(21)Levy(Wi)=s(W*-Wti)(22)式中:randn为服从正态分布的随机量;-1 1为比例因子;W*为目前全局最优值,随着迭代较大概率更新;Wi为第i次迭代值。莱维飞行可以实现位置的随机更新,但是无法保证得到的新解的适应度优于原解。因此,将贪心策略与莱维飞行相关联,贪心策略使用适者生存的概念,每一次新的迭代就会产生更优位置的狼群。Wti=Wi(t)f(xi(t)f(xi(t)(23)2.4 适应度函数适应度函数RPP问题一般要求路径长度最短且时间最短。本文考虑到实际的可行性,将无碰撞约束条件与路径长度相结合,保
21、证路径的可行性。f=f=in(xi+1-xi)0(24)式中:xi为路径节点,i1 n;n为节点总数。若最终路径与障碍物无法产生碰撞,则其适应度值为组成路径节点的欧式距离总和;若最终路径与障碍物碰撞,则其适应度值为0。2.01.81.61.41.21.00.80.60.40.20收敛因子值原始算法中的k=1k=5k=1050 100 150 200 250 300 350 400 450 500迭代次数图2 非线性收敛因子对比图Fig.2 Comparison of nonlinear convergence factors 1771第 35 卷第 8 期2023 年 8 月Vol.35 No
22、.8Aug.2023系统仿真学报Journal of System Simulationhttp:/www.china-3算法流程算法流程图 3 为 PSO-GWO 算法的流程图,主要步骤如下。step 1:确定初始种群大小和最大迭代次数tmax、当前迭代次数t。step 2:PSO算法运行3次,对其路径长度进行排序,分别赋值给狼、狼、狼。step 3:根据式(14)更新收敛因子a,根据式(5)、(6)分别初始化A、C。step 4:计算路径及狼、狼、狼对应的适应度值并更新,当前迭代次数加1。step 5:若路径适应度值在一定迭代次数内未变化,利用式(19)(23)进行局部扰动;否则,执行st
23、ep 6。step 6:若当前迭代次数小于最大迭代次数,狼群根据式(7)(13)、(15)(18)更新其位置;若达到最大迭代次数,停止循环,输出最优位置W。4实验结果对比与分析实验结果对比与分析为验证PSO-GWO算法在路径规划中的可行性与优越性。本文采用3个地形来测试算法,分别是简单地图(地形 I)、U 型障碍地图(地形 II)、复杂地图(地形 III),将 GWO 算法、混合灰狼(HGWO)算法9、A*算法与PSO-GWO算法进行对比 分 析。实 验 环 境 为 Windows 10,MATLAB 2018a。表1为算法的具体参数。图4和表2为GWO、HGWO、PSO-GWO、A*算法在地
- 配套讲稿:
如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。