基于自适应蜣螂算法的无人机三维路径规划方法

摘 要：山区地势具有陡峭、沟深壑大的环境特点，导致基于启发式算法的山区无人机路径规划速度慢、质量差，针对该问题提出了基于自适应动作策略蜣螂算法的路径规划方法。以路径长度、飞行安全性以及路径平滑度构建路径规划目标函数；在蜣螂算法中引入种群相似性动作变异策略和反向学习策略，平衡局部优化和全局优化能力；通过对比麻雀算法、蜣螂算法和灰狼算法在１２ 个基准函数上的算法性能，结果表明所提方法具有更快的收敛速度、不易陷入局部最优。山区路径规划仿真实验表明，所提方法比蜣螂算法的路径规划质量提高了３７． ６６％ 。

关键词：路径规划；蜣螂算法；反向学习；自适应动作策略

中图分类号：ＴＰ２４２；ＴＰ１８ 文献标志码：Ａ 开放科学（资源服务）标识码（ＯＳＩＤ）：

文章编号：１００３－３１０６（２０２４）０４－０９２８－０９

０ 引言

山区地形的复杂性、起伏高差较大和交通不便等特点常常导致部分区域难以通过传统方式进行探测、巡视和物资配送等工作，而无人机凭借其机动灵活的优势在山区得到广泛应用，因此在山区复杂环境下，高质量、快速地规划飞行路径对提高无人机任务效率具有重要意义［１－２］。

面向无人机三维路径规划问题，许多学者基于启发式算法展开了丰富的研究。蔺文轩等［３］针对三维路径规划问题，在粒子群算法中引入分组优化策略，并在小组粒子优化时采取模拟退火操作，有效避免了陷入局部最优和收敛慢的缺点。苏菲［４］在传统蝙蝠算法中引入黄金正弦算法，对最优个体进行全维和单维搜索，提高了收敛速度。黄鹤等［５］在飞蛾扑火算法中引入交叉算子和高斯变异算子，增强了全局搜索能力并提高了算法寻优精度。巫茜等［６］提出了改进信息素更新规则的蚁群算法并引入航迹导航因子，一定程度上克服了山区影响，避免路径陷入局部最优。郭启程等［７］在鲸鱼优化算法中加入莱维飞行进行随机扰动，并引入信息交流机制平衡搜索能力，提高收敛精度和速度。Ｚｅｎｇ 等［８］基于距离动态邻域设计粒子群算法速度更新机制并与差分进化算法进行融合以缓解过早收敛，增强搜索能力。段建民等［９］将遗传算法和改进的人工势场模型结合并行搜索，利用人工势场法优化遗传算法全局路径，增强跳出局部最优的能力。许诺［１０］将粒子群算法与遗传算法结合，设置动态惯性权重并引入步长因子平衡局部和全局搜索。

上述方法在一定程度上提升了规划路径的质量和算法的收敛速度，但是面向山区陡峭地势的复杂环境，仍存在路径规划效果差的问题。因此，本文分析无人机运动约束条件和路径规划要求，构建了山区环境中三维路径规划问题模型；结合蜣螂算法位置更新策略多的优势，引入反向学习策略和种群相似性变异策略，提出自适应变异蜣螂算法（ＡｄａｐｔｉｖｅＭｕｔａｔｉｏｎ Ｄｕｎｇ Ｂｅｅｔｌｅ Ａｌｇｏｒｉｔｈｍ，ＡＭＤＢＯ）使得在进行山区路径规划时蜣螂能自适应地选择动作，从而有效跳出局部最优，获得高质量路径。

１ 无人机三维路径规划目标函数

无人机三维路径规划问题属于优化问题，本文从路径长度、路径平滑度和飞行安全度方面构建路径规划目标函数。

① 路径长度

路径长度是判断路径质量的重要依据，路径长度越短，越有利于无人机节省能耗［１１］。因此路径长度为：

式中：ｎ 为航迹点数目，（ｘｉ，ｙｉ，ｚｉ）为第ｉ 个航迹点的位置。

② 路径平滑度

规划路径应尽量减少大角度偏航和高度的突变，需要保持路径平滑。由于山区陡峭、落差大的地形特点，无人机在山区飞行需要飞行路径满足自身最大爬升角和爬升率的要求［１２］。ｌｉ 表示２ 个航迹点之间的距离，式（２）和式（３）分别表示偏转角φｉ 和俯仰角ｉ，路径平滑度成本函数定义为式（４）。

③ 飞行安全性

路径规划中的路径还必须要确保无人机的安全运行，因此引入飞行安全性能够引导无人机躲避环境中的障碍物［１３］。如图１ 所示，空域内存在中心坐标为Ｏｋ，半径为Ｒｋ 的障碍物ｋ，无人机的飞行节点与障碍物的垂线距离ｄｋ 应该大于安全距离阈值Ｓ，即无人机必须限定在阴影之外的区域飞行，才能确保飞行的安全，飞行安全性的计算如下：

对上述各类成本函数进行加权综合，构成多目标路径规划问题的目标函数Ｆ：

Ｆ ＝ ω１ Ｆｌ ＋ ω２ Ｆｅ ＋ ω３ Ｆｓ ， （６）

式中：Ｆｌ、Ｆｅ、Ｆｓ 依次为上述３ 种代价函数，ω１ 、ω２ 、ω３ 分别为路径长度、航迹平滑度和飞行安全性的权重系数。目标函数值越小代表路径质量就越好。

２ 蜣螂优化算法

２． １ 原始蜣螂算法

蜣螂优化算法（Ｄｕｎｇ Ｂｅｅｔｌｅ Ｏｐｔｉｍｉｚｅｒ Ａｌｇｏｒｉｔｈｍ，ＤＢＯ）是一种新颖的群体智能算法，通过模拟蜣螂的滚球、繁殖、觅食和偷窃４ 个动作行为进行位置更新和优化，每种策略侧重的方向有所不同［１４］。蜣螂算法的多样化位置更新策略可以更加全面地探索搜索空间，在实际应用中能够有效地解决复杂的搜索和优化问题。

① 滚球行为

蜣螂滚球行为分为有障碍模式和无障碍模式。当无障碍时，光源的强度会影响蜣螂的位置，蜣螂在滚球行为过程中位置更新如式（７）所示；当遇到障碍物无法前进时，通过使用切线函数来模拟跳舞行为，位置更新如式（８）所示。

ｘｔ＋１ｉ ＝ ｘｔｉ＋ λ·ｋ·ｘｔ－１ｉ ＋ ｂ· ｘｔｉ－ ｘｗｏｒｓｔ ， （７）

ｘｔ＋１ｉ ＝ ｘｔｉ＋ ｔａｎ（θ） ｘｔｉ－ ｘｔ－１ｉ ， （８）

式中：ｘｔｉ为ｔ 次迭代时第ｉ 个个体的位置，λ 模拟自然因素随机取－１ 或１，ｋ 为［０，１］的随机偏转系数，ｂ为随机系数，ｘｗｏｒｓｔ 为最差个体位置。

② 繁殖行为

利用边界选择策略来模拟蜣螂产卵的安全区域，如式（９）所示；确定产卵区域后，雏球的位置随产卵区域进行动态变化，如式（１０）所示。

式中：ｘｌｂｅｓｔ 为局部最优解，Ｒ ＝ １－ ｔ／ｔｍａｘ，ｔｍａｘ 为最大迭代次数，ｔ 为当前迭代次数；Ｌｂ 为下界，Ｕｂ 为上界，ｂ１ 、ｂ２ 为２ 个Ｄ 维独立随机向量。

③ 觅食行为

觅食区域同样利用边界选择策略来动态模拟，如式（１１）所示。觅食蜣螂会在局部范围内进行觅食行为，蜣螂的位置更新如式（１２）所示。

式中：ｘｇｂｅｓｔ 为全局最优解，Ｃ１ 为服从正态分布的Ｄ维随机向量，Ｃ２ 为［０，１］的Ｄ 维随机向量。

④ 偷窃行为

最佳食物来源则是最适合竞争食物的地方，偷窃蜣螂的位置更新如下：

ｘｔ＋１ｉ ＝ ｘｇｂｅｓｔ ＋ Ｓ × ｇ × （ ｘｔｉ－ ｘｇｂｅｓｔ ＋ ｘｔｉ－ ｘｌｂｅｓｔ ），（１３）

式中：Ｓ 为常数，ｇ 为服从正态分布的Ｄ 维随机向量。

从４ 种个体行为的位置更新公式可知，只有滚球行为在算法各时期都具有较好的全局搜索能力；觅食行为在自身位置附近根据动态上下界范围进行搜索，动态上下界会越来越小，使得觅食行为随着迭代次数的增加从全局搜索变为局部搜索；繁殖行为和偷窃行为则是在最佳个体的附近根据动态上下界范围进行局部搜索。

２． ２ 自适应蜣螂算法

２． ２． １ 混沌序列初始化种群

在处理复杂的优化问题时，原始蜣螂算法采用随机生成种群的方法进行种群初始化，可能会导致种群多样性低、种群分布不均匀和快速收敛到局部最优解等问题。Ｔｅｎｔ 混沌映射可以生成均匀遍布解空间和相关性较强的初始种群［１５］，因此本文引入Ｔｅｎｔ 混沌映射作为改善蜣螂算法初始化种群多样性的方法，从而提高智能算法的求解精度和收敛速度。Ｔｅｎｔ 混沌映射公式如下所示：

对ｘ０ 赋初值，经过循环迭代，可以得到［０，１］的随机序列，该序列具有良好的统计特性，通常用于生成算法的初解，以增加物种的多样性。当控制参数α ＝０． ４５ 时，初始总体（一维）分布如图２ 所示。

蜣螂种群初始化过程如下：先随机生成一个［０，１］的Ｄ 维向量作为初始混沌序列；然后将Ｄ 维向量的每一维数值依次带入式（１４）计算生成一个新的Ｄ 维向量作为第２ 个混沌序列，重复上述步骤，直到生成Ｎ 个混沌序列；最后将全部混沌序列映射到种群个体的取值范围内，生成Ｔｅｎｔ 混沌初始化蜣螂种群。

２． ２． ２ 自适应的蜣螂行为变异策略

针对原始蜣螂算法４ 种动作行为的分配比例不均匀，且每个个体只能进行一种动作行为，可能会导致对解空间的搜索不充分或收敛速度慢的问题，本文提出了基于种群相似性的蜣螂动作变异策略和反向学习策略。

① 基于种群相似性的蜣螂动作变异策略

为了使每个蜣螂都能执行４ 种动作行为，本文用迭代次数模拟时间变化，每隔Ｍ 次迭代进行一次蜣螂的动作变异，将当前动作行为变异为下一种行为策略。本文利用余弦相似度来衡量种群相似性，种群多样性表示如下：

当Ｄｉｖｅｒ 大于０． ５ 时，种群多样性过低，可能会陷入局部最优，而滚球蜣螂和觅食蜣螂的数量决定了算法对解空间的探索能力和收敛速度。因此将执行繁殖和觅食行为的个体变异为执行滚球行为的个体，增强算法的全局搜索能力以增强物种多样性，找到新的最佳个体或达到变异个体迭代阈值Ｔｍａｘ 后将变异个体重新恢复为原来的行为个体继续搜索。

② 反向学习策略

由于繁殖和偷窃行为的全局搜索能力会随着迭代次数的增加而下降，而反向学习策略［１６］的思想主要是通过生成当前可行解的反向解，并将反向解与原解进行适应度比较选出更好的解，本文利用反向学习策略增强繁殖和偷窃行为的全局搜索能力：

式中：ｘｔｒ 为反向解，ｌｂ 和ｕｂ 为Ｄ 维向量表示每一维的下界和上界，ｒａｎｄ（）为Ｄ 维随机向量，ｘｔｉ为当前可行解。

综上所述，ＡＭＤＢＯ 算法流程如图３ 所示。

３ 仿真实验与分析

本文的仿真实验分为两部分：① 在ＣＥＣ２０１７中选择具有不同特征的基准函数［１７］，对比不同算法最优解的搜索速度和搜索质量，验证ＡＭＤＢＯ 算法的收敛性能、是否具备跳出局部最优的能力；② 构建山区路径规划环境，对比不同算法路径搜索速度和路径质量，验证ＡＭＤＢＯ 算法在复杂山区环境是否仍具有较快的收敛速度和寻优能力。

３． １ 基于多样性基准函数的算法性能分析

为了验证ＡＭＤＢＯ 算法的寻优性能，本文选取ＤＢＯ、改进灰狼算法（Ｉｍｐｒｏｖｅｄ Ｇｒｅｙ Ｗｏｌｆ ＯｐｔｉｍｉｚｅｒＡｌｇｏｒｉｔｈｍ，ＩＧＷＯ）和麻雀搜索算法（Ｓｐａｒｒｏｗ ＳｅａｒｃｈＡｌｇｏｒｉｔｈｍ，ＳＳＡ）在ＣＥＣ２０１７ 中的１２ 个具有不同特征的基准函数上进行算法性能的对比分析。其中，选择５ 个单峰基准函数（Ｆ１ ～ Ｆ５ ）分析各算法的单目标求解能力，选择４ 个多峰基准函数（Ｆ６ ～ Ｆ９ ）和３ 个混合基准函数（Ｆ１０ ～ Ｆ１２ ）分析算法能否跳出局部最优。测试函数具体信息如表１ 所示。

为了提高测试结果的可靠性，降低启发式算法随机性的影响，本文将所有算法的种群大小和迭代次数分别设置为３０ 和５００，对每个基准函数都运行３０ 次［１８］，得到３０ 次独立运行下的最优值（该最优值指的是本次运行下取得的目标函数最优值），并统计出平均值（Ｍｅａｎ）、最佳值（Ｂｅｓｔ）和标准差（Ｓｔｄ），统计对象为３０ 次独立运行下的最优值结果。平均值表现的是算法对该目标函数的平均的优化能力；最佳值表现的是３０ 次算法运行中对目标函数的最佳优化效果；标准差表现的是算法在该目标函数上优化能力的稳定性。４ 种优化算法对１２ 个基准函数的测试结果对比如表２ 所示。

在５ 个单峰基准函数（Ｆ１ ～ Ｆ５ ）测试中，ＡＭＤＢＯ在Ｆ１ ～ Ｆ４ 基准函数上的Ｍｅａｎ、Ｓｔｄ 和Ｂｅｓｔ 均优于其他３ 种算法。对比Ｆ５ 基准函数下Ｍｅａｎ、Ｓｔｄ 和Ｂｅｓｔ的具体数值比较可知：ＤＢＯ 的Ｂｅｓｔ 比ＡＭＤＢＯ 的Ｂｅｓｔ仅高５７． ７６％ ，但是ＡＭＤＢＯ 的Ｍｅａｎ、Ｓｔｄ 分别比ＤＢＯ的值高了７３． ８０％ 和１０９． ５２％ 。综合Ｆ１ ～ Ｆ５ 的整体表现，ＡＭＤＢＯ 的整体性能优于其他３ 种算法。

在４ 个多峰基准函数（Ｆ６ ～ Ｆ９ ）测试中，ＡＭＤＢＯ的Ｍｅａｎ 和Ｂｅｓｔ 均获得了第一且精度高于ＤＢＯ 和ＩＧＷＯ；ＡＭＤＢＯ 的Ｓｔｄ 除了在Ｆ６ 上略低于ＳＳＡ，在其他多峰基准函数上都远远优于ＩＧＷＯ 和ＤＢＯ。

在３ 个混合基准函数（Ｆ１０ ～ Ｆ１２ ）的测试中，４ 种算法的Ｂｅｓｔ 均能取得理论最优解；ＡＭＤＢＯ 的Ｍｅａｎ和Ｓｔｄ 在Ｆ１０ 和Ｆ１１ 上略低于ＩＧＷＯ，但也都优于ＳＳＡ 和ＤＢＯ；在混合基准函数Ｆ１２ 上，４ 种算法都能得到理论最优的Ｍｅａｎ 和Ｂｅｓｔ，但ＡＭＤＢＯ 的Ｓｔｄ 优于其他３ 种算法。虽然其他算法的Ｍｅａｎ 和Ｂｅｓｔ 都能达到理论最优值，但是ＡＭＤＢＯ 的收敛速度更快、迭代次数更少。图４（ｊ）～ 图４（ｌ）为混合基准函数（Ｆ１０ ～ Ｆ１２ ）测试的收敛曲线，ＡＭＤＢＯ 的收敛速度仅次于ＳＳＡ，优于ＤＢＯ 和ＩＧＷＯ。

综合上述测试，在３ 类基准函数上ＡＭＤＢＯ 的Ｍｅａｎ 和Ｂｅｓｔ 大部分优于其他３ 种算法；在收敛到相同精度的结果时，ＡＭＤＢＯ 所用的迭代次数也更低。ＤＢＯ 性能略差于ＡＭＤＢＯ，但是大部分测试结果相比ＳＳＡ 和ＩＧＷＯ 较优或齐平。

３． ２ 面向山区三维路径规划分析。

读取某一山区环境的数字高程模型地图，该地区最大高度落差超过２ ｋｍ，地势起伏剧烈分布沟壑众多，在该地形中随机生成环境扰动如图５ 所示（粉色圆柱）。设置无人机的起点和终点分别为（１０，９０，１． １１５）和（１３０，１０，１． ３６７），单位为ｋｍ。由３． １ 中的算法性能实验可知ＤＢＯ 与ＳＳＡ、ＩＧＷＯ 相比，性能更优，因此路径规划实验中选取ＤＢＯ 与ＡＭＤＢＯ 进行对比。算法中种群个体数量统一为３０，最大迭代次数为５００。基于ＡＭＤＢＯ 和ＤＢＯ 生成的路径如图５ 和图６ 所示，图中，线路１ 为ＡＭＤＢＯ 算法路径规划结果，线路２ 为ＤＢＯ 算法路径规划结果。

对比ＤＢＯ 和ＡＭＤＢＯ 的飞行路径可以看出，原始ＤＢＯ 在进行迭代时陷入了局部最优，且飞行路径长没有规避环境扰动，飞行高度低没有保障离地安全高度；而ＡＭＤＢＯ 算法的飞行路径平滑，有效规避了环境扰动并且保障了与障碍物之间的距离和离地安全高度。

目标函数收敛曲线如图７ 所示。可以看出，原始ＤＢＯ 的收敛较慢，在２５０ 次迭代之后逐渐开始收敛。本文算法在开始时能够快速地持续搜索，在２００ 次迭代之后逐渐收敛，且收敛值低于ＤＢＯ，结果表明ＤＢＯ 在迭代次数达到９５ 和１５０ 时都陷入了局部最优，验证了ＡＭＤＢＯ 具备跳出局部最优的能力。

综合各类表现看，本文算法具有更快的收敛速度且能快速跳出局部最优解，能够在山区复杂环境中规划出较高质量的路径。

４ 结束语

受山区环境影响，基于启发式算法的路径规划易陷入局部最优且收敛速度慢，本文在蜣螂算法进行初始化时引入混沌初始化使得种群分布更均匀，有效提高了种群多样性；构建了种群相似性动作变异策略和反向学习策略，平衡局部优化和全局优化能力。对基于多个基准函数的寻优能力进行对比分析，结果表明ＡＭＤＢＯ 相比ＤＢＯ、ＳＳＡ、ＩＧＷＯ 具有更好的求解速度和精度；山区环境中的路径规划结果表明ＡＭＤＢＯ 比ＤＢＯ 收敛更快，能较快地跳出局部最优，路径质量更高。下一步研究将考虑如何提升山区多目标点的路径规划质量。

参考文献

［１］ 路晶，史宇，张书畅，等． 无人机航迹规划算法综述［Ｊ］． 航空计算技术，２０２２，５２（４）：１３１－１３４．

［２］ 雷耀麟，丁文锐，李雅，等． 群体智能支撑的无人机群航路规划应用综述［Ｊ］． 无线电工程，２０２３，５３ （７）：１５０９－１５１９．

［３］ 蔺文轩，谢文俊，张鹏，等． 基于分组优化改进粒子群算法的无人机三维路径规划［Ｊ］． 火力与指挥控制，２０２３，４８（１）：２０－２５．

［４］ 苏菲． 基于改进蝙蝠算法的无人机三维路径规划［Ｊ］．无线电工程，２０２２，５２（１２）：２２２９－２２３６．

［５］ 黄鹤，吴琨，王会峰，等． 基于改进飞蛾扑火算法的无人机低空突防路径规划［Ｊ］． 中国惯性技术学报，２０２１，２９（２）：２５６－２６３．

［６］ 巫茜，黄浩，曾青，等． 改进ＡＣＯ 算法的ＵＡＶ 航迹规划在山区物流配送中的应用研究［Ｊ］． 重庆理工大学学报（自然科学），２０２２，３６（１０）：１８５－１９１．

［７］ 郭启程，杜晓玉，张延宇，等． 基于改进鲸鱼算法的无人机三维路径规划［Ｊ］． 计算机科学，２０２１，４８ （１２）：３０４－３１１．

［８］ ＺＥＮＧ Ｎ Ｙ，ＷＡＮＧ Ｚ Ｄ，ＬＩＵ Ｗ Ｂ，ｅｔ ａｌ． Ａ Ｄｙｎａｍｉｃ Ｎｅｉｇｈｂｏｒｈｏｏｄｂａｓｅｄ Ｓｗｉｔｃｈｉｎｇ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｙｂｅｒｎｅｔｉｃｓ，２０２２，５２（９）：９２９０－９３０１．

［９］ 段建民，陈强龙． 基于改进人工势场－遗传算法的路径规划算法研究［Ｊ］． 国外电子测量技术，２０１９，３８（３）：１９－２４．

［１０］ 许诺． 基于改进ＰＳＯ 算法的ＵＡＶ 三维路径规划研究［Ｊ］． 电子测量技术，２０２２，４５（２）：７８－８３．

［１１］ 陈明强，李奇峰，冯树娟，等． 基于改进粒子群算法的无人机三维航迹规划［Ｊ］． 无线电工程，２０２３，５３（２）：３９４－４００．

［１２］ 许乐，赵文龙． 基于新型灰狼优化算法的无人机航迹规划［Ｊ］． 电子测量技术，２０２２，４５（５）：５５－６１．

［１３］ 赵棣宇，郑宾，殷云华，等． 改进粒子群算法的ＵＡＶ 突防路径规划［Ｊ］． 电光与控制，２０２３，３０（４）：１２－１６．

［１４］ ＸＵＥ Ｊ Ｋ，ＳＨＥＮ Ｂ． Ｄｕｎｇ Ｂｅｅｔｌｅ Ｏｐｔｉｍｉｚｅｒ：Ａ Ｎｅｗ Ｍｅｔａ-ｈｅｕｒｉｓｔｉｃ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］Ｓｕｐｅｒｃｏｍ-ｐｕｔ，２０２３，７９：７３０５－７３３６．

［１５］ 宋立业，胡朋举． 改进ＳＳＡ 在三维路径规划中的应用［Ｊ］． 传感器与微系统，２０２２，４１（３）：１５８－１６０．

［１６］ 冯增喜，何鑫，崔巍，等． 混合随机反向学习和高斯变异的混沌松鼠搜索算法［Ｊ］． 计算机集成制造系统，２０２３，２９（２）：６０４－６１５．

［１７］ 舒聪． 面向无人机航迹规划的改进麻雀搜索算法及应用［Ｄ］． 广州：广州大学，２０２２．

［１８］ 欧阳城添，唐风，朱东林． 融合禁忌搜索的ＳＳＡ 算法及其路径规划的应用［Ｊ］． 电子测量技术，２０２２，４５（２２）：３２－４０．

作者简介

远翔宇 男，（１９９９—），硕士研究生。主要研究方向：路径规划、目标分配。

杨风暴 男，（１９６８—），博士，教授。主要研究方向：信息融合、不确定信息推理。

杨童瑶 女，（１９９７—），博士研究生。主要研究方向：威胁评估、意图估计与态势预测。