全粒子推动野马优化算法的无人机三维路径规划

doi:10.16182/j.issn1004731x.joss.22-1252

摘要/Abstract

摘要：

针对无人机路径规划求解计算量大、难收敛等问题，提出了一种基于全粒子推动野马算法的路径规划方法。建立三维环境模型与路径代价模型，将路径规划问题转化为多维函数优化问题；采用一种自适应邻域搜索策略，改善算法的开发能力；利用高斯随机游走策略对个体的历史最优位置进行回溯搜索，改善算法的探索能力；考虑到自适应策略对初始种群多样性敏感的问题，结合Tent 混沌映射初始化种群，提高算法的鲁棒性以及全局寻优能力；将提出的改进算法在13个经典测试函数中进行性能验证，并移植于无人机三维路径规划问题中。在30峰、40峰、50峰的环境模型下进行测试，与遗传算法、粒子群算法、SRM-PSO(self-regulating and self-perception particle swarm optimization with mutation mechanism)算法以及野马算法对比，全粒子推动野马算法皆取得最短平均路径，且在所有测试中都找到满足约束、无碰的路径。仿真结果证明，在复杂环境下全粒子推动野马算法具有优秀的全局寻优能力以及较好的鲁棒性。

关键词: 野马算法, 自适应邻域搜索, 高斯随机游走, Tent混沌映射, 无人机路径规划, 全粒子推动

Abstract:

In view of large calculation amounts and difficult convergence in the unmanned aerial vehicle (UAV) path planning, a path planning method based on all particles driving wild horse optimizier (APDWHO) was proposed. A three-dimensional environment model and path cost model were established, by which the path planning problem was transformed into a multi-dimensional function optimization problem. An adaptive neighborhood search strategy (ANSS) was adopted to improve the exploitation ability of the algorithm. The Gaussian random walk strategy was used to search the historical optimal position of the individual to improve the exploration ability of the algorithm. Since the ANSS is sensitive to the diversity of the initial population, the Tent chaotic map was used to initialize the population to improve the robustness and the global optimization ability of the algorithm. The performance of the improved algorithm was verified in 13 classic test functions and transplanted to the 3D path planning problem of UAVs. The test was conducted under the environment models of 30, 40, and 50 peaks. Compared with genetic algorithm (GA), particle swarm optimization (PSO), self-regulating and self-perception particle swarm optimization with mutation mechanism (SRM-PSO), and wild horse optimizer (WHO), APDWHO achieved the shortest average path and found the path that satisfies constraints and is collision-free in all tests. The simulation results show that the APDWHO has excellent global optimization ability and good robustness in complex environments.

Key words: wild horse optimizer, adaptive neighborhood search, Gaussian random walk, Tent chaotic mapping, path planning of UAV, all particles driving

中图分类号:

V279

李高扬,黎向锋,赵康等 . 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.

Li Gaoyang,Li Xiangfeng,Zhao Kang,et al . Three-Dimensional Path Planning of UAV Based on All Particles Driving Wild Horse Optimizer Algorithm[J]. Journal of System Simulation, 2024, 36(3): 595-607.

图/表 11

图1

图2

图3

图4

表1

测试函数表

测试函数	区间	最小值
$f 1 (x) = ∑ i = 1 n x i 2$	[-100,100]	0
$f 2 (x) = ∑ i = 1 n x i + ∏ i = 1 n x i$	[-10,10]	0
$f 3 (x) = ∑ i = 1 n ∑ j = 1 i x j 2$	[-100,100]	0
$f 4 (x) = m a x {x i, 1 ≤ i ≤ n}$	[-100,100]	0
$f 5 (x) = ∑ i = 1 n - 1 100 (x i + 1 - x i 2) 2 + (x i - 1) 2$	[-30,30]	0
$f 6 (x) = ∑ i = 1 n ([x i + 0.5]) 2$	[-100,100]	0
$f 7 (x) = ∑ i = 1 n i x i 4 + r a n d 0, 1$	[-1.28,1.28]	0
$F 8 (x) = ∑ i = 1 n - x s i n (x i)$	[-500,500]	-12 569.5
$F 9 (x) = ∑ i = 1 n [x i 2 - 10 c o s (2 π x i) + 10$	[-5.12,5.12]	0
$F 10 (x) = - 20 e x p (- 0.2 1 n ∑ i = 1 n x i 2) - e x p (1 n ∑ i = 1 n c o s (2 π x i)) + 20 + e$	[-32,32]	0
$F 11 (x) = 14000 ∑ i = 1 n x i 2 - ∏ i = 1 n c o s (x i i) + 1$	[-600,600]	0
$F 12 (x) = π n 10 s i n (π y 1) + ∑ i = 1 n - 1 (y i - 1 2 1 + 10 s i n 2 π y i + 1)] + (y n - 1) 2 + ∑ i = 1 n u (x i, 10,100, 4$ $y i = 1 + x i + 1 4, u (x i, a, k, m) = k (x i - a) m, x i > a 0, - a < x i < a k (- x i - a) m, x i < - a$	[-50,50]	0
$F 13 (x) = 0.1 s i n 2 (3 π x i) + ∑ i = 1 n (x i - 1 2 1 + s i n 2 (3 π x i + 1)] + (x n - 1 2 1 + s i n 2 (2 π x n)] + ∑ i = 1 n u (x i, 5,100, 4$	[-50,50]	0

表1

表2

表3

算法测试结果

函数	指标	PSO	GA	GWO	SSA	WHO	APDWHO
f₁(x)	Min	6.485 1E-08	1.342 2E+00	5.923 0E-30	2.499 2E-08	1.295 4E-51	0.000 0E+00
	Max	1.178 1E-04	9.464 9E+00	2.002 4E-26	1.747 3E-06	9.508 9E-43	4.331 2E-270
	Avg	7.613 1E-06	1.886 1E+00	1.602 1E-27	2.079 6E-07	3.736 8E-44	4.337 7E-272
	Std	3.253 1E-05	3.432 0E+00	2.820 2E-27	2.989 9E-07	1.739 5E-43	0.000 0E+00
	Rank	5	6	3	4	2	1
f₂(x)	Min	5.236 0E-05	3.535 0E-01	1.297 6E-17	1.024 4E-03	1.415 3E-28	1.211 7E-166
	Max	3.140 2E-01	6.546 7E-01	2.939 6E-16	7.390 8E+00	6.327 8E-23	4.013 8E-125
	Avg	1.650 3E-02	4.654 3E-01	9.798 5E-17	1.925 6E+00	3.473 8E-24	4.013 8E-127
	Std	6.401 2E-02	8.453 5E-2	6.846 0E-17	1.560 8E+00	1.316 4E-23	4.013 8E-126
	Rank	4	5	3	6	2	1
f₃(x)	Min	5.785 0E+01	2.744 3E+03	1.743 1E-08	2.785 2E+02	1.891 4E-34	1.368 2E-137
	Max	3.978 4E+02	9.543 0E+03	8.911 5E-04	5.633 5E+03	6.607 0E-24	2.228 1E-78
	Avg	1.506 1E+02	4.543 2E+03	3.135 7E-05	1.621 4E+03	2.986 6E-25	2.237 8E-80
	Std	8.789 1E+01	1.345 3E+03	1.293 61E-04	9.399 0E+02	1.237 4E-24	2.22 8E-79
	Rank	4	6	3	5	2	1
f₄(x)	Min	7.610 2E-01	5.045 3E+00	7.799 9E-08	4.049 5E+00	8.390 1E-2	2.681 1E-144
	Max	4.754 1E+00	1.434 5E+01	8.354 3E-06	2.009 6E+01	1.032 0E-15	4.088 4E-65
	Avg	2.501 2E+00	8.854 2E+00	9.004 8E-07	1.128 1E+01	5.111 3E-17	4.089 2E-67
	Std	7.541 4E-01	2.543 7E+00	1.088 9E-06	3.323 7E+00	1.906 8E-16	4.088 3E-66
	Rank	4	5	3	6	2	1
f₅(x)	Min	1.359 9E+01	1.241 3E+02	2.584 6E+01	2.639 5E+01	2.545 4E+01	2.667 3E+01
	Max	1.589 4E+02	1.242 9E+03	2.874 8E+01	2.049 2E+03	8.208 7E+01	2.788 3E+01
	Avg	4.907 3E+01	3.986 7E+02	2.705 4E+01	2.990 4E+02	2.884 9E+01	2.644 3E+01
	Std	3.448 6E+01	2.322 1E+02	7.638 0E-01	4.376 6E+02	1.013 5E+01	2.004 9E-01
	Rank	4	6	2	5	3	1
f₆(x)	Min	9.284 7E-08	1.576 3E+00	1.265 8E-04	1.480 8E-08	7.585 6E-06	2.181 4E-06
	Max	1.621 4E-05	1.398 9E+01	2.002 2E+00	2.341 2E-06	3.289 0E-01	3.769 1E-05
	Avg	1.887 3E-06	4.457 3E+00	7.833 2E-01	2.128 6E-07	1.420 0E-02	1.076 6E-05
	Std	2.934 6E-06	2.568 0E+00	3.672 7E-01	3.204 9E-07	6.010 0E-02	6.752 3E-06
	Rank	2	6	5	1	4	3
f₇(x)	Min	1.210 0E-02	4.500 0E-02	4.026 0E-04	4.444 9E-02	5.168 4E-05	1.123 3E-04
	Max	4.080 0E-02	2.489 0E-01	8.670 5E-03	4.614 5E-01	9.600 0E-03	3.270 5E-03
	Avg	2.380 0E-02	1.302 0E-01	2.050 2E-03	1.671 1E-01	1.300 0E-03	8.813 9E-04
	Std	8.200 0E-03	4.040 0E-02	1.206 3E-03	7.759 6E-02	1.700 0E-03	5.601 8E-04
	Rank	4	5	3	6	2	1
F₈(x)	Min	2.116 4E+00	-1.145 7E+04	-7.835 4E+03	-9.807 1E+03	-1.049 1E+04	-1.065 4E+04
	Max	2.116 4E+00	-1.024 9E+04	-4.287 3E+03	-5.697 3E+03	-7.939 7E+03	-7.327 8E+03
	Avg	2.116 4E+00	-1.023 4E+04	-5.988 9E+03	-7.471 9E+03	-9.024 7E+03	-9.110 4E+03
	Std	2.116 4E+00	3.342 4E+02	7.0599 E+02	7.642 6E+02	6.513 2E+02	5.515 5E+02
	Rank	6	1	5	4	3	2
F₉(x)	Min	2.143 2E+00	3.423 2E+00	0.000 0E+00	1.492 4E+01	0.000 0E+00	0.000 0E+00
	Max	1.096 4E+02	1.249 8E+01	2.001 5E+01	1.094 4E+02	3.386 6E-07	0.000 0E+00
	Avg	4.814 4E+01	8.022 9E+00	2.882 7E+00	5.652 1E+01	1.369 4E-08	0.000 0E+00
	Std	2.156 4E+01	2.005 6E+00	4.214 0E+00	1.631 8E+01	6.277 3E-08	0.000 0E+00
	Rank	5	4	3	6	2	1
F₁₀(x)	Min	9.496 6E-05	2.234 0E-01	6.483 7E-14	8.323 9E-02	8.8818E-16	8.881 8e-16
	Max	2.322 2E+00	1.653 2E+00	1.501 1E-13	5.412 6E+00	4.4409E-15	4.440 9e-15
	Avg	1.134 6E+00	8.003 4E-01	1.037 7E-13	2.646 2E+00	1.5987E-15	4.014 6e-15
	Std	8.146 1E-01	4.271 3E-01	1.917 5E-14	9.145 9E-01	1.4454E-15	1.160 3e-15
	Rank	5	4	3	6	1	2
F₁₁(x)	Min	9.613 3E-08	8.514 0E-01	0.000 0E+00	4.637 0E-04	0.0000E+00	0.000 0E+00
	Max	2.121 0E-01	1.057 2E+00	3.196 4E-02	6.416 9E-02	0.0000E+00	0.000 0E+00
	Avg	2.852 0E-02	1.015 9E+00	2.944 2E-03	1.838 7E-02	0.0000E+00	0.000 0E+00
	Std	4.320 0E-02	5.370 0E-02	6.742 4E-03	1.271 3E-02	0.0000E+00	0.000 0E+00
	Rank	5	6	3	4	1.5	1.5
F₁₂(x)	Min	1.117 6E-08	3.600 0E-03	1.265 2E-02	1.132 9E+00	1.0591E-05	6.474 3E-08
	Max	5.153 0E-01	2.267 0E-01	2.849 1E-01	2.548 2E+01	1.0420E-01	1.945 8E-06
	Avg	5.823 0E-02	3.408 0E-02	4.739 3E-02	8.270 6E+00	1.0600E-02	4.065 2E-07
	Std	1.114 0E-01	4.698 0E-02	3.213 0E-02	3.800 1E+00	3.1600E-02	3.037 9E-07
	Rank	5	4	2	6	3	1
F₁₃(x)	Min	7.397 7E-08	1.436 9E-01	1.034 7E-01	2.178 2E-02	3.1600E-02	1.288 2E-06
	Max	2.422 3E-01	7.533 0E-01	1.288 7E+00	6.058 6E+01	4.6828E-06	1.100 0E-02
	Avg	1.850 0E-02	3.460 0E-01	6.291 6E-01	1.730 0E+01	1.6370E-01	7.808 1E-04
	Std	4.447 0E-02	1.383 0E-01	2. 181 6E-01	1.517 4E+01	3.4000E-02	3.157 7E-03
	Rank	2	4	5	6	3	1

表3

表4

图5

图6

图7

参考文献 26

1	付兴武, 胡洋. 基于改进粒子群算法的三维路径规划[J]. 电光与控制, 2021, 28(3): 86-89.
	Fu Xingwu, Hu Yang. Three-Dimensional Path Planning Based on Improved PSO Algorithm[J]. Electronics Optics & Control, 2021, 28(3): 86-89.
2	刘光才, 马寅松, 齐福强, 等. 基于改进A^*-人工势场法的城市物流无人机路径规划[J]. 飞行力学, 2022, 40(6): 16-23.
	Liu Guangcai, Ma Yinsong, Qi Fuqiang, et al. Flight Path Planning for Urban Logistics UAV Based on Improved A^*-APF Algorithm[J]. Flight Dynamics, 2022, 40(6): 16-23.
3	詹京吴, 黄宜庆. 融合安全A^*算法与动态窗口法的机器人路径规划[J]. 计算机工程, 2022, 48(9): 105-112, 120.
	Zhan Jingwu, Huang Yiqing. Path Planning of Robot Combing Safety A^*Algorithm and Dynamic Window Approach[J]. Computer Engineering, 2022, 48(9): 105-112, 120.
4	蔡旻, 薛杰, 高涵文, 等. 基于成本函数优化的柔性针RRT路径规划算法[J]. 计算机应用与软件, 2022, 39(11): 245-249, 296.
	Cai Min, Xue Jie, Gao Hanwen, et al. Flexible Needle Rrt Path Planning Algorithm Based on Cost Function Optimization[J]. Computer Applications and Software, 2022, 39(11): 245-249, 296.
5	陈法法, 蒋浩, 李振, 等. 基于改进RRT的智能巡检机器人狭窄通道路径规划[J]. 组合机床与自动化加工技术, 2022(10): 40-45.
	Chen Fafa, Jiang Hao, Li Zhen, et al. Narrow Channel Path Planning of Intelligent Inspection Robot Based on Improved RRT[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2022(10): 40-45.
6	杨思明, 单征, 曹江, 等. 基于模型的强化学习在无人机路径规划中的应用[J]. 计算机工程, 2022, 48(12): 255-260, 269.
	Yang Siming, Shan Zheng, Cao Jiang, et al. Application of Model-based Reinforcement Learning in Path Planning of Unmanned Aerial Vehicle[J]. Computer Engineering, 2022, 48(12): 255-260, 269.
7	李东华, 江驹, 姜长生. 多智能体强化学习飞行路径规划算法[J]. 电光与控制, 2009, 16(10): 10-14.
	Li Donghua, Jiang Ju, Jiang Changsheng. A Flight Path Planning Algorithm Based on Multi-agent Reinforcement Learning Method[J]. Electronics Optics & Control, 2009, 16(10): 10-14.
8	徐菱, 付文浩, 江文辉, 等. 基于16方向24邻域改进蚁群算法的移动机器人路径规划[J]. 控制与决策, 2021, 36(5): 1137-1146.
	Xu Ling, Fu Wenhao, Jiang Wenhui, et al. Mobile Robots Path Planning Based on 16-directions 24-neighborhoods Improved Ant Colony Algorithm[J]. Control and Decision, 2021, 36(5): 1137-1146.
9	孔维立, 王峰, 周平华, 等. 改进蚁群算法的无人机三维路径规划[J]. 电光与控制, 2023, 30(3): 63-69.
	Kong Weili, Wang Feng, Zhou Pinghua, et al. Three-dimensional Path Planning of UAVs Based on Improved Ant Colony Algorithm[J]. Electronics Optics & Control, 2023, 30(3): 63-69.
10	智灵飞(北京)科技有限公司. 一种基于贪心算法的无人机RRT路径优化方法: CN201811477330.4[P]. 2019-03-12.
11	刘景森, 吉宏远, 李煜. 基于改进蝙蝠算法和三次样条插值的机器人路径规划[J]. 自动化学报, 2021, 47(7): 1710-1719.
	Liu Jingsen, Ji Hongyuan, Li Yu. Robot Path Planning Based on Improved Bat Algorithm and Cubic Spline Interpolation[J]. Acta Automatica Sinica, 2021, 47(7): 1710-1719.
12	赵畅, 刘允刚, 陈琳, 等. 面向元启发式算法的多无人机路径规划现状与展望[J]. 控制与决策, 2022, 37(5): 1102-1115.
	Zhao Chang, Liu Yungang, Chen Lin, et al. Research and Development Trend of Multi-UAV Path Planning Based on Metaheuristic Algorithm[J]. Control and Decision, 2022, 37(5): 1102-1115.
13	Mirjalili Seyedali, Seyed Mohammad Mirjalili, Lewis Andrew. Grey Wolf Optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61.
14	Mirjalili Seyedali, Gandomi A H, Seyedeh Zahra Mirjalili, et al. Salp Swarm Algorithm: A Bio-inspired Optimizer for Engineering Design Problems[J]. Advances in Engineering Software, 2017, 114: 163-191.
15	Naruei Iraj, Keynia Farshid. Wild Horse Optimizer: A New Meta-heuristic Algorithm for Solving Engineering Optimization Problems[J]. Engineering With Computers, 2022, 38(4): 3025-3056.
16	Zheng Rong, Hussien Abdelazim G, Jia Heming, et al. An Improved Wild Horse Optimizer for Solving Optimization Problems[J]. Mathematics, 2022, 10(8): 1311.
17	刘园园, 贺兴时. 基于Tent混沌映射的改进的萤火虫算法[J]. 纺织高校基础科学学报, 2018, 31(4): 511-518.
	Liu Yuanyuan, He Xingshi. An Improved Firefly Algorithm Based on Tent Chaotic Map[J]. Basic Sciences Journal of Textile Universities, 2018, 31(4): 511-518.
18	周鹏, 董朝轶, 陈晓艳, 等. 基于Tent混沌和透镜成像学习策略的平衡优化器算法[J]. 控制与决策, 2023, 38(6): 1569-1576.
	Zhou Peng, Dong Zhaoyi, Chen Xiaoyan, et al. An Equilibrium Optimizer Algorithm Based on a Tent Chaos and Lens Imaging Learning Strategy[J]. Control and Decision, 2023, 38(6): 1569-1576.
19	聂春芳. 融合黄金正弦和随机游走的哈里斯鹰优化算法[J]. 智能计算机与应用, 2021, 17(7): 113-119, 123.
	Nie Chunfang. Harris Hawk Optimization Algorithm Combining Golden Sine and Random Walk[J]. Intelligent Computer and Applications, 2021, 17(7): 113-119, 123.
20	吕鑫, 慕晓冬, 张钧, 等. 混沌麻雀搜索优化算法[J]. 北京航空航天大学学报, 2021, 47(8): 1712-1720.
	Xin Lü, Mu Xiaodong, Zhang Jun, et al. Chaos Sparrow Search Optimization Algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(8): 1712-1720.
21	Liu Qing, Li Jin, Ren Haipeng, et al. All Particles Driving Particle Swarm Optimization: Superior Particles Pulling Plus Inferior Particles Pushing[J]. Knowledge-Based Systems, 2022, 249: 108849.
22	Hu Yuntong, Xiao Fuyuan. Network Self Attention for Forecasting Time Series[J]. Applied Soft Computing, 2022, 124: 109092.
23	She Bin, Fournier Aimé, Yao Mengjie, et al. A Self-adaptive and Gradient-based Cuckoo Search Algorithm for Global Optimization[J]. Applied Soft Computing, 2022, 122: 108774.
24	Saremi S, Mirjalili S, Lewis A. Grasshopper Optimisation Algorithm: Theory and Application[J]. Advances in Engineering Software, 2017, 105: 30-47.
25	Mirjalili S. SCA: A Sine Cosine Algorithm for Solving Optimization Problems[J]. Knowledge-Based Systems, 2016, 96: 120-133.
26	Chen Yanjie, Liang Jinglin, Wu Yangning, et al. Self-regulating and Self-perception Particle Swarm Optimization with Mutation Mechanism[J]. Journal of Intelligent & Robotic Systems, 2022, 105(2): 30.

算法	参数	取值
WHO	交叉概率	0.13
	领导者比例	0.2
	交叉方式	Mean
APDWHO	交叉概率	0.13
	领导者比例	0.2
	交叉方式	Mean
	放牧行为置信因子栖息地竞争行为置信因子	8 1
	随机游走概率	0.1
PSO	拓扑结构	全连接
	个体认知/社会认知	2
	惯性权重	ω∈[0.4,0.9]
GA	方式	实数编码
	选择方式	轮盘赌
	交叉概率	0.8
	变异概率	0.3
GWO	收敛参数	由2线性减少到0
SSA	领导者位置更新概率	0.5

环境模型	测试设置		指标	GA	PSO	SRM-PSO	WHO	APDWHO
30峰	种群规模	100	最优值	181.36	163.34	162.29	162.52	162.42
	种群规模	100	平均值	207.93	175.42	166.29	179.32	166.17
	迭代次数	30	方差	50.64	9.21	4.21	15.49	4.19
			有效路径率/%	100	100	100	100	100
			收敛到200适应度平均用时/s	—	5.72	6.41	14.12	6.37
40峰	种群规模	100	最优值	192.73	182.09	181.06	180.40	180.84
	种群规模	100	平均值	43 062.78	70 986.66	53 179.16	19 461.87	185.97
	迭代次数	100	方差	71 715.43	89 461.54	61130.46	11.03	5.17
			有效路径率/%	76	56	67	93	100
			收敛到220适应度平均用时/s	—	—	—	—	12.62
50峰	种群规模	100	最优值	187.76	180.58	179.40	179.35	179.36
	种群规模	100	平均值	17 752.22	74 209.84	64 432.96	26 154.86	180.60
	迭代次数	100	方差	21 046.31	96 072.86	79 053.39	9.00	0.83
			有效路径率/%	90	54	60	85	100
			收敛到220适应度平均用时/s	—	—	—	—	7.31

[1]	桂雪琪, 李春涛. 基于视野和速度引导的无人机集群避障算法[J]. 系统仿真学报, 2024, 36(3): 545-554.
[2]	焦嵩鸣, 丁辉, 钟宇飞, 姚鑫, 郑家豪. 一种基于SiamRPN的无人机目标跟踪及控制算法[J]. 系统仿真学报, 2023, 35(6): 1372-1380.
[3]	赵静, 王鹏, 丁筱茜, 蒋国平, 徐丰羽, 孙雁飞. 基于观测器的四旋翼容错控制及仿真研究[J]. 系统仿真学报, 2022, 34(1): 1-10.
[4]	王彪, 唐超颖, 孔大庆. 基于改进自抗扰技术的四旋翼姿态控制[J]. 系统仿真学报, 2018, 30(8): 3124-3129.
[5]	张志伟, 陶建武, 邵校. 基于“τ-τ”的无人机规避告警准则分析[J]. 系统仿真学报, 2018, 30(5): 1877-1885.
[6]	吴华兴, 黄伟, 康凤举, 毛红保. 基于前置攻击瞄准的UCAV自主拦截方法研究[J]. 系统仿真学报, 2016, 28(9): 2246-2253.