融合多策略的蜣螂算法的三维无人机航迹规划

Three-dimensional UAV path planning based on Dung Beetle Algorithm fused with multiple strategies

摘要

针对蜣螂算法在无人机航迹规划中存在的种群多样性匮乏、收敛迟缓和全局探索力不足等问题，提出了一种融合多策略的更优蜣螂优化算法（BDBO）.该算法将动态学习的佳点集初始化、基于时间选择的主动并行双边搜索、自然衰减种群机制及融合Sigmoid的边界收敛策略嵌入航迹规划全过程：在全局阶段迅速扩大可行航迹空间，在局部阶段精细调整航迹最优点，从而同步提升收敛速度与求解精度.以航迹长度、飞行安全、平滑度及高度代价的加权和为目标函数，在CEC2017及三维山地环境进行验证.结果表明：BDBO 所得航迹的适应度值较对比的四种算法平均降低19.47%、25.51%、20.85%和3.97%，充分证明了BDBO在无人机三维航迹规划中的有效性与优越性.

Abstract

To address the deficiencies of the Dung Beetle Optimizer （DBO） in UAV path planning—namely， insufficient population diversity， slow convergence， and weak global exploration， a multi-strategy-enhanced variant termed BDBO is proposed. The algorithm seamlessly integrates four synergistic components throughout the entire planning process： dynamic-learning-based good-point set initialization， time-triggered active parallel bilateral search， a natural population-decay mechanism， and a boundary convergence strategy fused with a Sigmoid function. Collectively， these strategies rapidly expand the feasible flight-corridor during the global phase and refine waypoint positions in the local phase， thereby accelerating convergence and improving solution accuracy simultaneously. A composite objective function aggregating path length， flight safety， trajectory smoothness， and altitude cost is minimized on both CEC2017 benchmarks and a realistic 3-D mountainous scenario. Experimental results reveal that BDBO reduces the best fitness value by 19.47 %， 25.51 %， 20.85 %， and 3.97 % compared with four state-of-the-art counterparts， unequivocally demonstrating its effectiveness and superiority for three-dimensional UAV path planning.

Graphical abstract

关键词

蜣螂算法 / 主动并行双边搜索 / 自然衰减种群优化法 / 选择边界收敛策略

Key words

Dung Beetle algorithm / active parallel bilateral search / natural decay population optimization / selected boundary convergence strategy

自动化技术趋于成熟，无人机的运用领域日益宽广，如在植保^［1］、防灾^［2］、物流^［3］等方面，无人机都发挥了显著的作用.航迹规划是无人机的相关运用中的关键技术之一，先进的航迹规划技术可以实现快速精准打击目标、节约成本.众多学者对航迹规划算法进行了研究，目前可将其分为传统算法和智能优化算法.传统算法有A*算法^［4］、快速探索随机树算法（Rapidly-Exploring Random Tree Algorithm，RRT）^［5］等.A*算法对启发式函数的依赖性强，搜索效率低下；RRT算法随机性高，航迹结果不够平滑且在狭窄区域搜索速度慢.因此智能算法逐渐成为了优化问题的主流.智能算法种类繁杂，有灰狼算法（Grey Wolf Optimizer，GWO）^［6］、蚁群算法（Ant Colony Algorithm，ACA）^［7］等.但GWO存在收敛速率低下、局部最优解的困扰、参数选择难度大；ACA计算复杂度高，收敛速度慢，在高维空间中计算量指数级增长.因此寻找收敛速度快、精度高、环境适应性强的智能算法是航迹规划问题中研究的主要目标.

蜣螂算法（Dung Beetle Optimizer，DBO）^［8］是依靠模拟蜣螂不同行为的分布式智能算法，其特点在于寻优能力强、收敛速度快，能够有效探索问题空间，近来年被广泛使用于航迹规划领域中^［9］.DBO算法在初期种群分布过于随机，使得算法搜索效率遭受影响，且算法收敛边界采用线性收敛，易导致算法收敛速率过快，陷于局部最优.针对上述困扰，研究人员们提出了很多改进措施，文献［10］将DBO与GWO融合，提高收敛速率和航迹质量，但未解决收敛精度低的问题；文献［11］引入了莱维飞行和纵横交叉策略，提高收敛速率，但是并未改善算法易陷入局部最优解的风险，不适用于山地环境下的航迹规划问题.

为了更好解决DBO的收敛速度慢、收敛精度低、可能陷入局部最优解的局限性，本文建立了一种结合动态学习的佳点集初始化、基于时间选择的主动并行双边搜索、自然衰减种群优化法和融合Sigmoid函数选择边界收敛的融合多策略的更优蜣螂算法（Better Dung Beetle Optimizer，BDBO）.该算法能够有效降低航迹成本、提升航迹平滑度以及收敛精度.将BDBO与DBO、GWO等在CEC2017函数上进行仿真对比.在山地仿真环境下，将BDBO与DBO、狐猴算法（Lemurs Optimizer，LO）^［12］、开普勒算法（Kepler Optimization Algorithm，KOA）^［13］、蜘蛛胡蜂算法（Spider Wasp Optimizer，SWO）^［14］进行仿真对比.

1 无人机航迹规划问题建模

1.1 飞行航迹长度函数

无人机的飞行航迹是由许多航迹点拟合构成.采用欧氏距离方法构建飞行航迹长度函数.设三维空间中，某一航迹点o的坐标为p_o=(x_o,y_o,z_o)，则无人机飞行的航迹函数f_L，如公式（1）所示：

\left\{\begin{array}{l}{f}_L={\displaystyle \sum _{o=\mathrm{1}}^n}{L}_o\\ L_o=\sqrt[]{(x_{o+\mathrm{1}}-x_o{)}^{\mathrm{2}}+(y_{o+\mathrm{1}}-y_o{)}^{\mathrm{2}}+(z_{o+\mathrm{1}}-z_o{)}^{\mathrm{2}}}\end{array}\right.，（1）

式中：L_o表征的是第o段航迹的欧氏长度.

1.2 飞行安全代价函数

无人机易受到来自外部威胁的干扰，导致飞行任务失败，致使无人机坠毁.因此应当确保无人机在飞行过程中的安全，如公式（2）所示：

，（2）

式中：R_i为空间中第i个障碍物的半径大小，d_o为航迹L_o到与其相距最近的障碍物中心点的距离，M为安全阈值.威胁区域俯视平面图如图1所示：

1.3 航迹平滑成本函数

无人机在执行任务过程中，应当避免转向角度或升降幅度过大的情况.因此，其俯仰角和偏转角必须满足相关约束限制，否则航迹是不满足飞行性的.数学模型如公式（3）、公式（4）所示：

{\varphi }_o=\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{a}\mathrm{n}\left(\frac{‖L_o{L}_{o+\mathrm{1}}‖}{L_o{L}_{o+\mathrm{1}}}\right)，（3）

{\phi }_o=\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{a}\mathrm{n}\left(\frac{z_{o+\mathrm{1}}-z_o}{\sqrt[]{(x_{o+\mathrm{1}}-x_o{)}^{\mathrm{2}}+(y_{o+\mathrm{1}}-y_o{)}^{\mathrm{2}}}}\right)，（4）

每一段航迹的偏转角度和俯仰角度之和可求得航迹平滑程度函数f_E，如公式（5）所示：

f_E={\displaystyle \sum _{o=\mathrm{1}}^{n-\mathrm{2}}}{\varphi }_o+{\displaystyle \sum _{o=\mathrm{1}}^{n-\mathrm{1}}}\left({\phi }_o-{\phi }_{o-\mathrm{1}}\right)，（5）

式中：{\varphi }_o、{\phi }_o为无人机飞行过程中处于第o段航迹所对应的偏转角度和俯仰角度.

1.4 高度代价成本函数

无人机飞行高度应当处在一个合理的区间内，低于区间会提高飞行风险，高过区间会增加飞行成本，高度代价成本函数f_H如公式（6）所示：

，（6）

式中：h_o为第o段航迹对应无人机飞行高度，h_{\mathrm{m}\mathrm{i}\mathrm{n}}和h_{\mathrm{m}\mathrm{a}\mathrm{x}}为可飞行的最小和最大高度.

1.5 总目标函数

对其上所有函数进行权重综合，构建无人机航迹规划问题目标函数F_C，如公式（7）所示：

F_C=f_L+f_S+f_E+f_H，（7）

当F_C取得最小值时，即可得最优航迹.

2 BDBO算法

2.1 DBO算法的基本理论

DBO通过模拟滚球（跳舞）、繁殖、觅食以及偷窃的不同行为来模拟迭代进行位置更新.蜣螂通过滚动粪球进行全局搜索，当前方未出现阻碍物时，其位置更新如公式（8）所示：

\begin{array}{l}{x}_i(t+\mathrm{1})=x_i(t)+\alpha \times k\times x_i(t-\mathrm{1})\\ +b\times \left|x_i(t)-X^{\omega }\right|\end{array}，（8）

前方出现阻碍物时，其位置更新如公式（9）所示：

x_i(t+\mathrm{1})=x_i(t)+\mathrm{t}\mathrm{a}\mathrm{n}(\theta )\times \left|x_i(t)-x_i(t-\mathrm{1})\right|，（9）

式中，x_i(t)代表第\mathrm{i}只蜣螂在第\mathrm{t}迭代时的位置，k是一个0到0.2间的常量.b是0到1之间的常量，\alpha取值为1或-1，X^{\omega }为全局最差解，\theta \in (\mathrm{0},\pi ).

蜣螂会在一个逐渐收敛的边界区间中进行产卵，产卵边界范围的数学模型如公式（10）所示：

\left\{\begin{array}{l}{L}_b^{*}=\mathrm{m}\mathrm{a}\mathrm{x}(X^{*}\times (\mathrm{1}-R),L_b)\\ U_b^{*}=\mathrm{m}\mathrm{i}\mathrm{n}(X^{*}\times (\mathrm{1}+R),U_b)\end{array}\right.，（10）

边界收敛因子R的数学模型如公式（11）所示：

R=\frac{\mathrm{1}-t}{M_t}，（11）

繁殖蜣螂的位置更新如公式（12）所示：

\begin{array}{l}{x}_i(t+\mathrm{1})=X^{*}+b_{\mathrm{1}}\times (x_i(t)-L_b^{*})\\ +b_{\mathrm{2}}\times (x_i(t)-U_b^{*})\end{array}，（12）

式中：L_b^{\mathrm{*}}、U_b^{\mathrm{*}}代表产卵区域的上下界，L_b、U_b表示待求解问题的上下边界，M_t表示最大迭代次数，X^{\mathrm{*}}表示当前局部最优解，b_{\mathrm{1}}、b_{\mathrm{2}}是2个独立的随机向量，大小为\mathrm{1}\times D，D代表待求解问题的维度.

蜣螂会进行觅食行为，觅食边界的数学模型如公式（13）所示：

\left\{\begin{array}{l}{L}_b^b=\mathrm{m}\mathrm{a}\mathrm{x}(X^b\times (\mathrm{1}-R),L_b)\\ U_b^b=\mathrm{m}\mathrm{i}\mathrm{n}(X^b\times (\mathrm{1}+R),U_b)\end{array}\right.，（13）

蜣螂觅食行为位置更新如公式（14）所示：

\begin{array}{l}{x}_i(t+\mathrm{1})=x_i(t)+C_{\mathrm{1}}\times (x_i(t)-L_b^b)\\ +C_{\mathrm{2}}\times (x_i(t)-U_b^b)\end{array}，（14）

式中：L_b^b、U_b^b代表觅食区域的上下界，C_{\mathrm{1}}是满足正态分布的随机数，C_{\mathrm{2}}是0到1的随机向量.

部分蜣螂会选择偷盗其他蜣螂的粪球，偷盗行为的位置更新如公式（15）所示：

\begin{array}{l}{x}_i(t+\mathrm{1})=X^b+S\times g\\ \times \left(\left|x_i(t)-X^{*}\right|+\left|x_i(t)-X^b\right|\right)\end{array}，（15）

式中：S为常数，g是满足正态分布的随机数，大小为\mathrm{1}\times D.

2.2 BDBO算法改进策略

2.2.1 结合动态学习的佳点集初始化

DBO采用伪随机数的方法生成初始种群的位置，但此方法全局遍历性差，寻优效率低下.因此，本文提出结合动态学习的佳点集方法^［15］进行种群初始化，丰富种群层次、使得全局遍历区域更广，能够有效提高全局搜索效率，两者对比如图2所示：

由图2可以看出，结合动态学习的佳点集初始化时序散点分布更加均匀，面对高维问题时具备更好的稳定性.

结合动态学习的佳点集方法的数学模型如公式（16）、（17）所示：

x_i(t)=(U_b-L_b)g\left\{r_j^{(i)}\times k\right\}+L_b，（16）

x_{i+\mathrm{1}}(t)=x_i(t)+m_{\mathrm{1}}\times (m_{\mathrm{2}}(L_b+U_b)-x_i(t))-x_i(t)，（17）

式中：r_j^{(i)}表示第j维度下所对应的佳点，m_{\mathrm{1}}和m_{\mathrm{2}}是两个独立随机值，k\in (\mathrm{1},n).

2.2.2 基于时间选择的主动并行双边搜索

DBO中，觅食行为依赖于全局最佳位置进行搜寻，其局部开发能力不足，收敛精度低，易陷入局部最优解.在此提出一种新的搜索思想——主动并行双边搜索策略.该策略不再单一的依靠全局最优位置，而是将另外的蜣螂信息和当前种群的最佳位置联立，引导整个蜣螂种群朝着最佳食物源进行位置更新.首先，选择适应度值最高的4只觅食蜣螂作为一个种群集，计算当前离食物源最近的觅食蜣螂同另外3只觅食蜣螂的距离，然后随机从中选择1-2个位置作为权重参数，引导整个蜣螂群体向最佳位置靠拢.距离l_d表示如公式（18）所示：

l_d=(X^{\mathrm{*}}-X_{if}^T)i=\mathrm{1,2}\dots n，（18）

式中：X_{if}^T表示第T次迭代时，第i只觅食蜣螂的位置.

为了强化种群中各蜣螂间的相互交流，引入时间选择策略.选择任意两只觅食蜣螂，比较二者距全局最佳位置的距离，由比较结果设置权重参数，其数学模型如公式（19）、公式（20）所示：

{\omega }_D=\left|X_{if}^T-X_{jf}^T\right|，（19）

{\omega }_S=J\times {\omega }_D，（20）

式中；J为随机常量，{\omega }_D为两只蜣螂间距离，{\omega }_S代表权重参量.

采用时间选择机制，能够提高种群的多样性.当迭代次数满足一定条件时采用双边搜索策略进行位置更新；若不满足则按照主动选择策略进行位置更新.设置时间参量T(t)和时间常量T(\mathrm{0})，如公式（21）所示，本文中T(\mathrm{0})取值为0.5.

T(t)=\left|\left(\mathrm{1}-(\mathrm{1}-t/M_t)\right)\times J\right|，（21）

优化后的觅食行为位置更新策略如公式（22）所示：

.（22）

2.2.3 自然衰减种群优化法

DBO中，种群中各蜣螂比重是不变的，导致种群的多样性差.受自然选择思想^［16］的启发，种群最开始在整个空间中广泛寻找合适的居住地和食物源，此时滚球蜣螂的数量占比较大.当多数滚球蜣螂找到了优质食物源后便会在此繁衍后代.小部分滚球蜣螂因未找到合适的区域会逐渐死亡，通过自然选择行为实现种群结构的动态调整.

在迭代前期让滚球蜣螂占有较大比重，使得前期全局搜索能力强；后期提高繁殖蜣螂和觅食蜣螂的比重，使得后期局部寻优能力高.自然衰减种群优化法的数学模型如公式（23）所示：

，（23）

式中：\mathrm{r}\mathrm{N}\mathrm{u}\mathrm{m}代表滚球蜣螂的数量，r_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}}代表滚球蜣螂在整个蜣螂种群中的比重，N_{\mathrm{P}\mathrm{o}\mathrm{p}}代表总体蜣螂的数量，v_{\mathrm{1}}、v_{\mathrm{2}}、v_{\mathrm{3}}表示与迭代次数相关的权重常量.

2.2.4 融合Sigmoid函数选择边界收敛策略

在DBO中，繁殖和觅食蜣螂的搜索边界都是一条线性的直线.R的大小对应了搜索区域的范围，通过调整R来平衡算法的全局搜索和局部搜索能力.但DBO算法采用线性衰减，存在收敛速度过快的问题，易使算法陷入局部最优解.如图3所示，实线代表融合Sigmoid函数收敛条件，虚线代表线性收敛条件.对比线性收敛的方式，融合Sigmoid函数^［17］选择边界收敛策略.在迭代前期，较高R的值能够提高全局搜索能力；在迭代后期，较低R的值在能够提高局部寻优精度，便于在二者之间达到平衡.

改进后的边界收敛曲线R_{\Delta }的数学模型如公式（24）所示：

.（24）

2.3 BDBO算法流程图

本文BDBO算法流程图如图4所示：

3 仿真实验及结果分析

实验语言采用matlabR2023a，仿真环境为windows11（64位），处理器为AMD Ryzen5 7600 6-CoreProcessor，3.8GHz，16.0GB.

3.1 标准算法在测试函数中的仿真比较

为了论证本文提出的算法性能，本文采用CEC2017测试函数^［18］进行基础实验对比，CEC2017函数集如表1所示.

本文将BDBO同DBO、GWO、WOA^［19］和PSO算法^［20］与本文提出的BDBO算法进行对比实验，统一设置5种算法的参数，种群大小为30，最大迭代次数为500，基础参数设置如表2所示.

为降低单次实验的偶然性，每个算法独立重复运行30次.计算求得最优值、平均值和标准差记录于表3.其中最优值可以反映算法的优化能力，平均值反映算法的平均性能，标准差表征算法的稳定程度.

图5给出了测试函数的收敛曲线.

从表3和图5可以看出，在面对高维单峰函数F1、F2、F3时，仅有BDBO能够找到最优的解；对于高维多峰函数F4、F5，BDBO能够寻找到更精确解；对于低维多峰函数F6，仅有BDBO可以得到最优解；对于低维多峰函数F7，BDBO的性能也是排在前列的.因此BDBO不仅在面对简单问题求解时能够有着较快的收敛速率，其在面对复杂问题时，求解能力更强，具备更好的稳定性.由此可以证明BDBO克服了DBO收敛速度慢、收敛精度低的缺陷，可适用于复杂环境下无人机航迹规划问题.

3.2 三维山地环境无人机航迹仿真实验

为了进一步论证BDBO在无人机最优航迹规划问题中的有效性，将其与DBO、LO、KOA、SWO算法在山地场景中进行仿真对比实验.所有算法的种群数量设置为30，迭代次数上限为500.

5种算法的航迹图和适应度收敛曲线如图6-图7所示：

通过图6可知，BDBO所生成的航迹平滑程度均高于其他算法；由图7可知，BDBO所求得的适应度值更低，收敛速度更快.为减少单次实验所带来的偶然性，重复实验30次，并将结果记录在表4中.

从表4可知，BDBO的平均路径分别降低了19.47%、25.51%、20.85%和3.97%.综上，无论是在航迹和飞行成本还是响应速度上，BDBO在无人机三维航迹规划问题上都展现出优越的性能.

4 结论

本文提出一种融合多策略的更优蜣螂算法（BDBO），通过引入动态学习的佳点集初始化、基于时间选择的主动并行双边搜索、自然选择种群优化法以及融合Sigmoid函数选择边界收敛策略，解决了DBO算法存在的搜索实时性低下、遍历性不充分、局部开发能力不足、种群结构单一等问题，有效降低航迹成本，提高收敛速度，减少陷入局部最优解的风险，经CEC2017测试函数集以及三维地图仿真实验验证，其性能优于DBO和其他算法的.但该算法也存在不足，如加入的额外参数提高了对参数的敏感度，运行时间还需进行后续优化.

参考文献

[1] 于少猛， 闫铭， 王鹏飞， 等. 丘陵山地果园植保无人机三维路径规划［J］. 浙江大学学报（工学版）， 2025， 59（3）： 635-642.

[2] 唐东旭. 无人机技术在森林生态遥感监测中的应用与探讨［J］. 智慧中国， 2024（12）： 80-81.

[3] 王芸. 基于模拟退火算法的末端车载无人机物流配送路径规划研究［J］. 自动化与仪器仪表， 2025（2）： 247-251.

[4] 汪国安， 王红军， 马宁， 等. 复合作业模式下基于A*-PPO算法的AGV调度［J/OL］. 计算机集成制造系统， 2025： 1-24. （2025-04-17）.

[5] 宋俊辉， 刘宇庭， 郭世杰. 动态环境下AIP-RRT^*与DGF-APF融合的机器人路径规划［J］. 仪器仪表学报， 2025， 46（3）： 51-64.

[6] 孙波， 周健康， 赵玉清， 等. 基于改进灰狼优化算法的机器人全局路径规划［J］. 科学技术与工程， 2024， 24（33）： 14287-14297.

[7] 毛文平， 李帅永， 谢现乐， 等. 基于自适应机制改进蚁群算法的移动机器人全局路径规划［J］. 控制与决策， 2023， 38（9）： 2520-2528.

[8] Xue J， Shen B. Dung beetle optimizer： A new meta-heuristic algorithm for global optimization［J］. The Journal of Supercomputing， 2023， 79（7）： 7305-7336.

[9] 蒋翱徽， 刘文红. 基于改进蜣螂优化算法的无人机三维路径规划［J］. 电子测量技术， 2024， 47（13）： 128-135.

[10] 陈琦， 王亚杰， 孙云飞， 等. 基于蜣螂和灰狼复合算法的无人机三维路径规划［J］. 电光与控制， 2025， 32（6）： 8-15.

[11] 李为瀚， 刘媛华. 融合多策略改进的蜣螂优化算法［J/OL］. 重庆工商大学学报（自然科学版）， 2025： 1-10. （2025-02-24）.

[12] Abasi A K， Makhadmeh S N， Al-Betar M A， et al. Lemurs optimizer： A new metaheuristic algorithm for global optimization［J］. Applied Sciences， 2022， 12（19）： 10057.

[13] Abdel-Basset M， Mohamed R， Abdel Azeem S A， et al. Kepler optimization algorithm： A new metaheuristic algorithm inspired by Kepler’s laws of planetary motion［J］. Knowledge-Based Systems， 2023， 268： 110454.

[14] Abdel-Basset M， Mohamed R， Jameel M， et al. Spider wasp optimizer： A novel meta-heuristic optimization algorithm［J］. Artificial Intelligence Review， 2023， 56（10）： 11675-11738.

[15] 李书群， 陈钰， 杨雨婷， 等. 基于佳点集人工鱼群的点云配准算法［J］. 合肥工业大学学报（自然科学版）， 2023， 46（9）： 1203-1209.

[16] 郝武帮， 施磊. 融合自然选择机理和遗传算法的多峰MPPT优化控制［J］. 舰船电子工程， 2024， 44（11）： 186-191， 203.

[17] 李俊毅， 邓志祥. 双曲正切函数的新型变步长LMS算法［J］. 计算机与数字工程， 2024， 52（8）： 2272-2278.

[18] 毛清华， 赵冰， 李阳. 融合多项式差分学习与逐维变异的混沌蜉蝣算法［J/OL］. 北京航空航天大学学报， 2024： 1-15. （2024-06-28）.

[19] 杨桂芹， 刘志琦， 张国庆， 等. 基于鲸鱼优化算法改进的SDN网络流量预测模型［J］. 兰州交通大学学报， 2025， 44（2）： 19-29.

[20] 朱凯鹏， 王全政， 杨文政， 等. 基于改进粒子群优化算法的船舶避碰研究［J］. 传感器与微系统， 2025， 44（4）： 40-43， 47.

基金资助

中国高校产学研创新基金资助项目(2021ZYA04004)