计算机科学 ›› 2021, Vol. 48 ›› Issue (12): 304-311.doi: 10.11896/jsjkx.201000021
郭启程1,2, 杜晓玉1,3, 张延宇1,2, 周毅1,2
GUO Qi-cheng1,2, DU Xiao-yu1,3, ZHANG Yan-yu1,2, ZHOU Yi1,2
摘要: 无人机三维路径规划是一个比较复杂的全局优化问题,其目标是在考虑威胁和约束的条件下,获得最优或接近最优的飞行路径。针对鲸鱼算法在进行无人机三维航迹规划时,存在容易陷入局部最优、收敛速度较慢、收敛精度不够高等问题,提出了一种基于莱维飞行(Lévy flight)的鲸鱼优化算法(Levy Flight Based on Whale Optimization Algorithm,LWOA),用于解决无人机三维路径规划问题。该算法在迭代过程中加入了Levy飞行对最优解进行随机扰动;引入了信息交流机制,通过当前全局最优解和个体记忆最优解以及邻域最优解来更新个体的位置,能够更好地权衡局部收敛和全局开发。仿真结果表明,所提路径规划算法可以有效避开威胁区,收敛速度更快,收敛精度更高,且更不易陷入局部最优解。当迭代次数为300次、种群个数为50时,LWOA算法求得的成本函数值是PSO算法的91.1%,是GWO算法的92.1%,是WOA算法的95.9%,航迹代价更小。
中图分类号:
[1]CHENG H H,YANG S,QI X H.Online Obstacle Avoidance Path Planning Method for Quadrotor UAVs in Urban Environment[J].Computer Science,2019,46(4):241-246. [2]YOU W J,DONG C,WU Q H.Survey of Layered Architecture in Large-scale FANETs[J].Computer Science,2020,47(9):226-231. [3]ZENG Y,ZHANG R.Energy-Efficient UAV Communication with Trajectory Optimization[J].IEEE Transactions on Wireless Communications,2017,16(6):3747-3760. [4]WANG H B,YIN P H,ZHENG W,et al.Mobile Robot Path Planning Based on Improved A* Algorithm and Dynamic Window Method[J].Robots,2020,42(3):346-353. [5]WANG S J,HU L K,WANG Y F.Path Planning of Indoor Mobile Robot based on Improved D* Algorithm[J].Computer Engineering and Design,2020,41(4):1118-1124. [6]TAN J H,XIAO Y L,LIU L M,et al.Improved PRM algorithm for path planning of UAV[J].Sensors and Microsystems,2020,39(1):38-41. [7]GUO Y C,LIU X X,ZHANG W G,et al.UAV 3D path planning method based on improved potential field method[J].Journal of Northwest Polytechnic University,2020,38(5):977-986. [8]YU M,LUO J J,WANG M M,et al.A Coordinated Path Planning by Integrating Improved RRT* and Quartic Spline[J].Chinese Journal of Mechanics,2020,52(4):1024-1034. [9]JIANG C K,LI Z,PAN S B,et al.Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm[J].Computer Science,2020,47(8):272-277. [10]LV Q,SUN X K,XIONG Y J.UAV path planning based on Improved Genetic Algorithm[J].Journal of Navigation and Positioning,2020,8(5):42-48. [11]WANG Y H,WANG S M.UAV path planning based on improved particle swarm optimization[J].Computer Engineering and Science,2020,42(9):1690-1696. [12]CAO Y,WEI W,BAI Y,et al.Multi-base multi-UAV cooperative reconnaissance path planning with genetic algorithm[J].Cluster Computing,2019,22:5175-5184. [13]WEI J,WANG J J,WANG J,et al.3D Path Planning Based on Improved Ant Colony Algorithm[J].Computer Engineering and Applications,2020,56(17):217-223. [14]PAN J,LIU N,CHU S.A Hybrid Differential Evolution Algorithm and Its Application in Unmanned Combat Aerial Vehicle Path Planning[J].IEEE Access,2020,8:17691-17712. [15]ZHOU J,CHEN P,LIU H,et al.Improved Path Planning for Mobile Robot Based on Firefly Algorithm[C]//2019 IEEE International Conference on Robotics and Biomimetics(ROBIO).IEEE,2019:2885-2889. [16]PANDEY P,SHUKLA A,TIWARI R.Three-dimensional path planning for unmanned aerial vehicles using glowworm swarm optimization algorithm[J].International Journal of System Assurance Engineering and Management,2018,9(4):836-852. [17]QU C,GAI W,ZHANG J,et al.A novel hybrid grey wolf optimizer algorithm for unmanned aerial vehicle(UAV) path planning[J].Knowledge-Based Systems,2020,194:105530. [18]LIN N,TANG J,LI X,et al.A Novel Improved Bat Algorithm in UAV Path Planning[J].Computers,Materials and Continua,2019,61(1):323-344. [19]WU K,TAN S C.UAV route planning based on improved whale optimization algorithm[J].Journal of Aeronautics,2020,41(S2):107-114. [20]MIRJALILI S,LEWIS A.The Whale Optimization Algorithm[J].Advances in Engineering Software,2016,95:51-67. [21]PAVLYUKEVICH I.Lévy flights,non-local search and simulated annealing[J].Journal of Computational Physics,2007,226(2):1830-1844. |
[1] | 陈俊, 何庆, 李守玉. 基于自适应反馈调节因子的阿基米德优化算法 Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor 计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150 |
[2] | 范星泽, 禹梅. 改进灰狼算法的无线传感器网络覆盖优化 Coverage Optimization of WSN Based on Improved Grey Wolf Optimizer 计算机科学, 2022, 49(6A): 628-631. https://doi.org/10.11896/jsjkx.210500037 |
[3] | 耿海军, 王威, 尹霞. 基于混合软件定义网络的单节点故障保护方法 Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks 计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051 |
[4] | 章菊, 李学鋆. 基于莱维萤火虫算法的智能生产线调度问题研究 Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm 计算机科学, 2021, 48(6A): 668-672. https://doi.org/10.11896/jsjkx.210300118 |
[5] | 刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136 |
[6] | 郑洁锋, 占红武, 黄巍, 张恒, 吴周鑫. Lévy Flight的发展和智能优化算法中的应用综述 Development of Lévy Flight and Its Application in Intelligent Optimization Algorithm 计算机科学, 2021, 48(2): 190-206. https://doi.org/10.11896/jsjkx.200500142 |
[7] | 郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146 |
[8] | 李阳, 李维刚, 赵云涛, 刘翱. 基于莱维飞行和随机游动策略的灰狼算法 Grey Wolf Algorithm Based on Levy Flight and Random Walk Strategy 计算机科学, 2020, 47(8): 291-296. https://doi.org/10.11896/jsjkx.190600107 |
[9] | 张严, 秦亮曦. 基于Levy飞行策略的改进樽海鞘群算法 Improved Salp Swarm Algorithm Based on Levy Flight Strategy 计算机科学, 2020, 47(7): 154-160. https://doi.org/10.11896/jsjkx.190600068 |
[10] | 张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法 Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints 计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078 |
[11] | 杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法 Bin Packing Algorithm Based on Adaptive Optimization of Slack 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132 |
[12] | 罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法 Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack 计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048 |
[13] | 张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法 Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS 计算机科学, 2019, 46(6A): 497-501. |
[14] | 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法 Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading 计算机科学, 2018, 45(4): 94-99. https://doi.org/10.11896/j.issn.1002-137X.2018.04.014 |
[15] | 单天羽, 管煜旸. 基于种群多样性的可变种群缩减差分进化算法 Differential Evolution Algorithm with Adaptive Population Size Reduction Based on Population Diversity 计算机科学, 2018, 45(11A): 160-166. |
|