一种新型启发式PSO算法求解市区最优路径规划研究
|
摘要
针对粒子群算法收敛速度差、局部寻优能力弱的缺点,利用市区地图数据通过数学公式推导得到算法环境模型,结合A*算法思想,初始化具有启发信息的粒子群体,提出一种求解市区最优路径的新型启发式PSO算法。该算法考虑时间约束、运动约束、距离约束等,采用新的启发函数和非线性动态调整算法惯性权重,在路径长度的基础上引入平滑度概念,寻找最优路径。与已有算法相比,实验结果表明,所提出的模型及改进算法能有效搜索最优路径,降低运行时间,提高算法收敛速度和搜索能力。
Aiming at the shortcomings of particle swarm optimization and poor local optimization ability,grid method with binary information is used to model the environment. Combined with improved A* algorithm to initialize the particle group,improved PSO algorithm is proposed based on map data which mathematical model to derive the algorithmic environment model. The algorithm considers the collision avoidance constraint,the motion constraint and the distance constraint. The new heuristic function and the nonlinear dynamic adjustment are used to study inertia weight. Based on the path length,the concept of smoothness is introduced to find the optimal path. Compared with algorithms,the experimental results show that proposed model and improved algorithm can effectively avoid obstacles,search the optimal path,reduce the running time,improve convergence rate and search ability of the algorithm.
Aiming at the shortcomings of particle swarm optimization and poor local optimization ability,grid method with binary information is used to model the environment. Combined with improved A* algorithm to initialize the particle group,improved PSO algorithm is proposed based on map data which mathematical model to derive the algorithmic environment model. The algorithm considers the collision avoidance constraint,the motion constraint and the distance constraint. The new heuristic function and the nonlinear dynamic adjustment are used to study inertia weight. Based on the path length,the concept of smoothness is introduced to find the optimal path. Compared with algorithms,the experimental results show that proposed model and improved algorithm can effectively avoid obstacles,search the optimal path,reduce the running time,improve convergence rate and search ability of the algorithm.
引文
[1]Dillmann R,Zoellner R,Ehrenmann M.Interactive Natu-ral Programming of Robots:Introductory Overview[C]//Pro.of IEEE-RAS Joint Workshop on Technical Challengefor Dependable Robots in Human Environments.Tolous,France:[s.n.],2002:253-258.
[2]Choset H,Nagatani K.Topological Simultaneous Localiza-tion and Mapping(SLAM):Toward Exact LocalizationWithout Explicit Localization[J].IEEE Transactions onRobotics and Automation,2001,17(2):125-137.
[3]宫金超,李晓明.基于粒子群优化算法的小型足球机器人路径规划[J].机电工程,2010,27(12):116-121.GONG Jinchao,LI Xiaoming.Path planning of a small soc-cer robot based on particle swarm optimization algorithm[J].Mechanical and electrical engineering,2010,27(12):116-121.
[4]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005:108-119.DUAN Haibin.Principle and application of ant colony al-gorithm[M].Beijing:Science Press,2005:108-119.
[5]Kennedy J,Eberhart R.Particle swam optimization[C]//Proceedings of IEEE International Conference on NeuralNetwork.Perth,Australia,1995:1942-1948.
[6]Eberhart R,Kennedy J.A new optimizer using particlesswarm theory[C]//Proceedings of the Sixth InternationalSymposium on Micro Machine and Human Science.Na-goya,1995:39-43.
[7]张万绪,张向兰,李莹.基于改进粒子群算法的智能机器人路径规划[J].计算机应用,2014,34(2):510-513.ZHANG Wanxu,ZHANG Xianglan,LI Ying.Path plan-ning of intelligent robots based on Improved ParticleSwarm Optimization[J].Computer applications,2014,34(2):510-513.
[8]张铁虎,俞经虎,王琨.基于ACO-PSO算法的点胶路径规划与分析[J].计算机应用,2016,36(S2):89-92.ZHANG Tiehu,YU Jinghu,WANG Kun.Dispensing pathplanning and analysis based on ACO-PSO algorithm[J].Computer applications,2016,36(S2):89-92.
[9]张成,凌有铸,陈孟元.改进蚁群算法求解移动机器人路径规划[J].电子测量与仪器学报,2016,30(11):1758-1764.ZHANG Cheng,LING Youzhu,CHEN Mengyuan.Pathplanning of mobile robot based on an improved ant colonyalgorithm[J].Journal of electronic measurement and in-strumentation,2016,30(11):1758-1764.
[10]汪冲,李俊,李波,等.改进的蚁群与粒子群混合算法求解旅行商问题[J].计算机仿真,2016,33(11):274-279.WANG Chong,LI Jun,LI Bo,et al.Improved ant colo-ny-particles swarm hybrid algorithm for solving TSP[J].Computer simulation,2016,33(11):274-279.
[11]毛琪波,余震虹.改进的粒子群算法在传感器温度补偿中的应用[J].计算机工程与应用,2016,52(23):229-235.MAO Qibo,YU Zhenhong.Improved PSO and its applica-tion to sensor temperature compensation[J].ComputerEngineering and Applications,2016,52(23):229-235.
[12]孙凯,吴红星,王浩,等.蚁群与粒子群混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.SUN Kai,WU Hongxing,WANG Hao,et al.Ant colony and particle swarm optimization algorithm for TSP prob-lem[J].Computer engineering and applications,2012,48(34):60-63.
[13]朱莹莹,王宇嘉.求解复杂旅行商问题的混合粒子群算法[J].轻工机械,2015,33(3):42-44.ZHU Yingying,WANG Yujia.Hybrid particle swarm op-timization for solving complex traveling salesman prob-lems[J].Light industry,2015,33(3):42-44.
[14]Clerc,Maurice,Discrete Paxirticle Swam Optimization[M].New Optimization Techniques in Engineering,2004:219-240.
[15]吕方兴,方昕.一种求解最优路径的新型混合PSO算法研究[J].计算机与现代化,2013,41(2):165-168.LV Fangxing,FANG Xin.A new hybrid PSO algorithmfor solving optimal path[J].Computer and modern,2013,41(2):165-168.
[2]Choset H,Nagatani K.Topological Simultaneous Localiza-tion and Mapping(SLAM):Toward Exact LocalizationWithout Explicit Localization[J].IEEE Transactions onRobotics and Automation,2001,17(2):125-137.
[3]宫金超,李晓明.基于粒子群优化算法的小型足球机器人路径规划[J].机电工程,2010,27(12):116-121.GONG Jinchao,LI Xiaoming.Path planning of a small soc-cer robot based on particle swarm optimization algorithm[J].Mechanical and electrical engineering,2010,27(12):116-121.
[4]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005:108-119.DUAN Haibin.Principle and application of ant colony al-gorithm[M].Beijing:Science Press,2005:108-119.
[5]Kennedy J,Eberhart R.Particle swam optimization[C]//Proceedings of IEEE International Conference on NeuralNetwork.Perth,Australia,1995:1942-1948.
[6]Eberhart R,Kennedy J.A new optimizer using particlesswarm theory[C]//Proceedings of the Sixth InternationalSymposium on Micro Machine and Human Science.Na-goya,1995:39-43.
[7]张万绪,张向兰,李莹.基于改进粒子群算法的智能机器人路径规划[J].计算机应用,2014,34(2):510-513.ZHANG Wanxu,ZHANG Xianglan,LI Ying.Path plan-ning of intelligent robots based on Improved ParticleSwarm Optimization[J].Computer applications,2014,34(2):510-513.
[8]张铁虎,俞经虎,王琨.基于ACO-PSO算法的点胶路径规划与分析[J].计算机应用,2016,36(S2):89-92.ZHANG Tiehu,YU Jinghu,WANG Kun.Dispensing pathplanning and analysis based on ACO-PSO algorithm[J].Computer applications,2016,36(S2):89-92.
[9]张成,凌有铸,陈孟元.改进蚁群算法求解移动机器人路径规划[J].电子测量与仪器学报,2016,30(11):1758-1764.ZHANG Cheng,LING Youzhu,CHEN Mengyuan.Pathplanning of mobile robot based on an improved ant colonyalgorithm[J].Journal of electronic measurement and in-strumentation,2016,30(11):1758-1764.
[10]汪冲,李俊,李波,等.改进的蚁群与粒子群混合算法求解旅行商问题[J].计算机仿真,2016,33(11):274-279.WANG Chong,LI Jun,LI Bo,et al.Improved ant colo-ny-particles swarm hybrid algorithm for solving TSP[J].Computer simulation,2016,33(11):274-279.
[11]毛琪波,余震虹.改进的粒子群算法在传感器温度补偿中的应用[J].计算机工程与应用,2016,52(23):229-235.MAO Qibo,YU Zhenhong.Improved PSO and its applica-tion to sensor temperature compensation[J].ComputerEngineering and Applications,2016,52(23):229-235.
[12]孙凯,吴红星,王浩,等.蚁群与粒子群混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.SUN Kai,WU Hongxing,WANG Hao,et al.Ant colony and particle swarm optimization algorithm for TSP prob-lem[J].Computer engineering and applications,2012,48(34):60-63.
[13]朱莹莹,王宇嘉.求解复杂旅行商问题的混合粒子群算法[J].轻工机械,2015,33(3):42-44.ZHU Yingying,WANG Yujia.Hybrid particle swarm op-timization for solving complex traveling salesman prob-lems[J].Light industry,2015,33(3):42-44.
[14]Clerc,Maurice,Discrete Paxirticle Swam Optimization[M].New Optimization Techniques in Engineering,2004:219-240.
[15]吕方兴,方昕.一种求解最优路径的新型混合PSO算法研究[J].计算机与现代化,2013,41(2):165-168.LV Fangxing,FANG Xin.A new hybrid PSO algorithmfor solving optimal path[J].Computer and modern,2013,41(2):165-168.