具有停滞意识的自适应差分进化算法,用于高维且受限条件下的无人机路径规划
《Expert Systems with Applications》:Stagnation-Aware responsive differential evolution for high-dimensional and constrained UAV path planning
【字体:
大
中
小
】
时间:2026年09月28日
来源:Expert Systems with Applications 9.4
编辑推荐:
摘要
无人驾驶飞行器(UAV)需要在受限的静态二维和三维环境中找到可飞行的路径,而高维黑箱优化问题对基于种群的搜索在多模态景观下的应用提出了挑战。差分进化(DE)适用于这两种情况,但成功历史适应机制记录了哪些参数在没有使用种群级进展作为突变和交叉的共同时间信号的情况下仍然有效
摘要
无人驾驶飞行器(UAV)需要在受限的静态二维和三维环境中找到可飞行的路径,而高维黑箱优化问题对基于种群的搜索在多模态景观下的应用提出了挑战。差分进化(DE)适用于这两种情况,但成功历史适应机制记录了哪些参数在没有使用种群级进展作为突变和交叉的共同时间信号的情况下仍然有效。本文提出了一种名为“停滞感知响应差分进化”(SARDE)的方法,该方法无需训练,基于种群进展状态反馈来运行。一个平滑的中位数改进信号共同选择突变模式和交叉率:在进展足够时保持探索性的随机选择(rand/1),而在进展低于阈值时激活利用性的当前最佳值选择(current-to-pbest/1)。替换的父母档案为两种模式提供历史候选者,贪婪选择生成下一个状态,从而形成一个由档案支持的候选者循环。这些操作重用了DE已经产生的目标值,无需额外的函数评估。在CEC2017的30D测试中,SARDE的中位数内墙时间比率为1.125;在八个UAV场景中为1.021。在控制的共同种群协议下,SARDE与八种算法在CEC2017的10D、30D、50D和100D,以及CEC2022的10D和20D进行了比较,并且在D=14–45的四个2D和四个3D案例的八个静态UAV场景中也进行了比较。SARDE在CEC2017的50D和100D以及整个UAV集合中获得了最高的Friedman平均排名。
引言
无人驾驶飞行器(UAV)已成为农业、基础设施检查和搜救等领域的操作工具,它们执行调查、监控和交付任务,这些任务在其他情况下可能会非常缓慢或危险(Kim, Kim, Ju, Son, 2019; Lyu, Zhao, Huang, Huang, 2023; Phung, Quach, Dinh, Ha, 2017)。在这些应用中,飞行器必须穿过复杂的两维或三维工作空间到达目标地点,而生成这条路径的路径规划是实现自主飞行的核心技术(Aggarwal & Kumar, 2020)。规划器需要在避开障碍物和危险区域的同时,连接起始点和目标点,并满足路径长度和机动性约束,这使得问题变得非凸的;随着航点数量的增加,问题变得高维和多模态(Aggarwal, Kumar, 2020; Zheng, Li, Xu, Sun, Ding, 2005)。障碍物和威胁区域的交点创建了不连续的可行性边界,因此单个航点的微小变化可能会使路径从可行变为不可行(Deb, 2000; Phung, Ha, 2021)。这类问题的目标是由几何和约束项组成的黑箱,其维度很大,通常使用无导数的基于种群的优化算法来解决(Aggarwal, Kumar, 2020; Zheng, Li, Xu, Sun, Ding, 2005)。对于大规模连续问题,合作共进化与差分分组相结合提供了一个补充的分治策略(Omidvar, Li, Mei, & Yao, 2014)。
在基于种群的元启发式方法中,群体排序和进化方法(如粒子群优化(Kennedy & Eberhart, 1995)、灰狼优化器(Mirjalili, Mirjalili, & Lewis, 2014)和海洋捕食者算法(Faramarzi, Heidarinejad, Mirjalili, & Gandomi, 2020)因不需要导数信息且易于应用而受到青睐。差分进化(DE)是这一家族中最成熟的方法之一:它通过添加种群成员之间的缩放差异向量并通过二项式交叉重新组合这些向量来搜索连续空间,并且控制参数很少(Das, Suganthan, 2011; Storn, Price, 1997)。其行为主要受缩放因子和交叉率的影响,一系列研究通过从搜索历史中在线调整这些参数来消除手动调优的负担。JADE从最近成功值的均值中调整这两个参数,并引入了当前最佳值选择(current-to-pbest/1)以及可选的外部废弃解决方案档案(Zhang & Sanderson, 2009);SHADE用成功历史记忆替换了这些运行均值(Tanabe & Fukunaga, 2013);L-SHADE在评估预算消耗时线性减少种群规模(Tanabe & Fukunaga, 2014);jSO在这个基础上按预算依赖的计划重新加权缩放因子(Brest, Mau?ec, & Bo?kovi?, 2017)。这些适应机制记录了哪些控制参数最近成功了,但它们没有使用种群级进展作为突变选择和交叉率的共同时间信号(Das, Mullick, & Suganthan, 2016)。固定的低交叉率在旋转和强耦合的景观中可能保留太少的突变方向坐标。外部档案在传统的自适应DE中保留废弃解决方案,但它们的历史候选者角色本身不提供基于进展的时间控制或协调两种突变模式。较新的方法将操作符或参数的选择视为序列决策,并通过强化学习学习控制策略,例如通过深度Q网络选择突变操作符(Sharma, Komninos, López-Ibá?ez, & Kazakov, 2019),在线学习景观特征(Guo et al., 2025),或为受限问题指导协同进化的DE(Hu, Gong, Pedrycz, & Li, 2023)。这些控制器会对搜索状态做出反应,但它们在进化搜索之外添加了学习到的控制组件(Guo, Ma, Huang, Hu, Ma, Zhang, Gong, 2025; Hu, Gong, Pedrycz, Li, 2023; Sharma, Komninos, López-Ibá?ez, Kazakov, 2019)。目前仍存在的差距是一种无需训练的种群进展反馈架构,它可以同时控制突变和交叉,允许档案支持两种突变模式,并允许独立于利用性操作符进行受控的时间测试。为了解决这一差距,SARDE将传统的DE操作组织成一个种群进展反馈循环。探索性的随机选择(rand/1)和二项式交叉遵循标准DE,而当前最佳值选择(current-to-pbest/1)和外部档案源于JADE(Zhang & Sanderson, 2009)。其独特的设计在于它们之间的时间控制和数据流。种群中位数的平滑改进值确定一个状态,共同选择突变模式和交叉率;然后替换的父母档案为任一模式提供历史候选者;突变和交叉产生一个试验;贪婪选择更新种群和档案;下一个种群中位数生成下一个信号。因此,该循环支持候选者构建而不是决定控制状态。这个循环无需训练,并重用了DE已经计算的目标值,除了试验评估之外不需要额外的函数评估。
基于上述分析,本文的主要贡献总结如下:(1)SARDE通过种群进展状态反馈解决了缺失的共同时间信号问题,该反馈共同选择突变模式和交叉率。在适当的中间值进展期间保持探索性的随机选择(rand/1),并在信号超过阈值后激活利用性的当前最佳值选择(current-to-pbest/1)。(2)SARDE通过档案支持的候选者循环协调这种联合响应。替换的父母档案为任一突变模式提供历史候选者,而在下一个种群中位数关闭循环之前,贪婪选择更新种群和档案。随机选择(rand/1)、当前最佳值选择(current-to-pbest/1)、二项式交叉和档案保持它们的既定角色;其贡献在于它们的时间和数据流。(3)在控制的共同种群协议下,主要比较涵盖了CEC2017的10D、30D、50D和100D,CEC2022的10D和20D,以及八个包含四个2D和四个3D案例的静态UAV场景(D=14–45);SARDE在CEC2017的50D和100D以及整个UAV集合中排名第一。表8中的统一直接非反馈控制和组件移除显示,SARDE的成绩为21/5/3,而Always-pbest为20/5/3,无档案的情况为19/10/0,将反馈时间与补充的候选者支持分开。遥测、目标转移干预、敏感性分析和成本测量检查了操作轨迹、表示依赖性、参数范围和计算。
本文的其余部分组织如下:第2节回顾了关于控制参数适应、基于学习的控制和集成差分进化以及UAV路径规划的元启发式方法的相关工作。第3节将UAV路径规划任务表述为一个受限的单目标优化问题。第4节介绍了SARDE并分析了其成本。第5节报告了在基准测试集和UAV场景上的实验结果。第6节讨论了该方法的发现和局限性,第7节总结了本文。
相关工作
SARDE是一种用于高维连续优化以及满足几何可行性约束的静态2D和3D UAV路径规划的反馈控制差分进化(DE)算法。本节回顾了其建立的基础工作,按搜索适应的维度进行组织,包括控制参数适应、基于学习的反馈控制和集成多策略选择,然后调查了为UAV路径规划开发的元启发式方法。每种方法都根据其解决问题的方式进行了评估。
问题表述
本节阐述了所提出的算法旨在解决的路径规划任务。UAV需要穿过一个d维工作空间,其中d ∈ {2, 3},该空间包含障碍物、威胁区域,在三维情况下还包括不平坦的地形表面。飞行被转化为一个单目标最小化问题,其决策变量是参数化的路径,目标函数结合了飞行质量项和有限的违规惩罚,从而使任务得以解决。
提出的SARDE
本节介绍了SARDE算法,该算法最小化第3节中构建的目标函数F(x)。SARDE保留了标准DE的种群结构,仅改变了搜索对其自身进展的反应方式,从而使最终的优化器保持无需训练,并且每次试验只进行一次目标评估。标准DE通过突变、二项式交叉和贪婪选择来进化NP个体的种群,其中NP是种群规模。
实验和结果
在控制的共同种群协议下,本节将在CEC2017的10D、30D、50D和100D,以及CEC2022的10D和20D上,以及在D=14–45的八个受限静态UAV场景上,将SARDE与八种算法进行比较。主要结果显示,在CEC2017的50D和100D以及整个UAV集合中,SARDE在九种算法中排名第一。然后通过联合突变和...(原文此处内容不完整)
讨论
表8中的统一比较揭示了来自时间和组件角色的不同且依赖于问题的贡献。Always-pbest保留了当前最佳值选择(current-to-pbest/1)和替换的父母档案(replaced-parent archive),但去除了依赖于状态的时间控制。与这种直接的非反馈控制相比,SARDE的成绩为21/5/3,平均排名为2.31,而Always-pbest的排名仅为3.86。Always-pbest在F7、F9和F30上的更好结果表明,在某些测试函数中固定的利用策略仍然具有优势。
结论
本文提出了“停滞感知响应差分进化”(SARDE),它使用种群进展状态反馈来同时控制高维数值优化和受限静态2D和3D UAV路径规划的突变和交叉。一个平滑的中位数改进信号在进展足够时选择探索性的随机选择(rand/1),并在信号超过阈值后选择利用性的当前最佳值选择(current-to-pbest/1)。替换的父母档案提供了历史候选者...
作者贡献声明
Xin Cheng:方法论、软件、验证、写作——原始草稿。
Zhilin Wang:调查、形式分析、数据管理、写作——审阅与编辑。
Huiling Chen:监督、概念化、资源获取、项目管理、写作——审阅与编辑。
Xiangjun Cai:监督、写作——审阅与编辑。
利益冲突声明
作者声明他们没有已知的会影晌本文工作的竞争财务利益或个人关系。