基于自适应进化策略的层次化粒子群优化在无人水面艇全局路径规划中的应用

《Engineering Applications of Artificial Intelligence》：Hierarchical particle swarm optimization with adaptive evolutionary strategies for unmanned surface vehicle global path planning

　　吴一文|林帆奇|杨德权|李贤能 中国大连理工大学经济管理学院，大连116024 摘要 粒子群优化算法被广泛用于无人水面艇的全球路径规划，但现有变体可能存在过早收敛的问题，且往往未能充分利用单个粒子中的航点信息。本文提出了AESHPSO，这是一种具有自适应进化策略的分层粒子群优化算法，包含三个子群体：领头粒子群、普通粒子群和边缘粒子群。在搜索陷入停滞时，领头粒子群采用两阶段变异策略，结合不同子群体间的差分变异以及基于角度成本的航点优化，从而降低累积角度成本，并有助于进行规划层面的转弯半径筛选。普通粒子群则利用正弦-余弦函数调度来调整惯性和加速度系数，而边缘粒子群则通过坐标下降特征搜索，判断性能较差粒子的航点是否能够改进当前的最佳全局路径。对于种群规模为N的情况，完整的路径评估成本为Cpath，常规迭代的时间复杂度为O(NCpath)；排序、变异和特征搜索等操作仅在搜索停滞时才会发生。在均匀水流和Lamb-Oseen涡流作用下的分散型及迷宫式障碍环境中进行的实验表明，AESHPSO相比所测试的其它粒子群优化基线算法，具有更低的综合适应度值和累积角度成本。与各项指标和场景下表现最佳的粒子群优化算法相比，AESHPSO平均可使平均适应度、路径长度和累积角度成本分别降低4.9%、2.4%和37.1%，同时仍能保持具有竞争力的考虑水流影响的行驶时间成本。进一步的分析研究了角度成本构成、对水流扰动的敏感性、搜索动态以及跟踪压力测试。在所有四个基准测试场景中，AESHPSO生成的路径均通过了规划层面的碰撞检测和转弯半径检验。引言 无人水面艇被越来越多地应用于海洋勘探、环境监测、应急救援、水文测量等各类海上任务中（Bai等人，2022）。全球路径规划是自主无人水面艇导航的核心组成部分，因为它决定了本地控制器应遵循的行进路线。一个有效的全球路径应当能够避开障碍物、减少不必要的绕行、保持适合平台跟踪的规则航点几何结构，同时还要考虑到不同航向上环境水流对地面速度的影响（H. Zhang等人，2023）。这些要求使得无人水面艇的路径规划不同于单纯的几何最短路径问题：在静水中看似最短的路径，在考虑到局部转弯限制和环境水流后，可能会变得效率更低或更难以跟踪。基于种群的元启发式算法常被用于这类问题，因为它们无需梯度信息即可处理非线性目标、不连续的碰撞惩罚以及复杂的障碍物布局。其中，粒子群优化算法因其简单的更新规则和相对较低的计算成本而备受关注（Kennedy和Eberhart，1995）。在基于粒子群优化的路径规划器中，每个粒子都可以编码一条完整的候选路径，整个种群通过利用个体最佳信息和全局最佳信息来逐步改进路径集合。这种结构便于基于航点的路径规划，但也存在一个常见的缺陷：随着粒子越来越倾向于跟随自身的历史最佳位置以及种群层面的全局最佳位置，种群的多样性会降低，搜索可能过早地收敛到某个局部最优的路径结构上（Ho等人，2005；Ahmed等人，2024）。为提升搜索能力，人们提出了多种混合粒子群优化策略。GAPSO（遗传算法与粒子群优化混合算法）（Shi等人，2005）引入了遗传算法中的交叉和变异操作来维持种群多样性。DEMPSO（差分进化与改进型粒子群优化混合算法）（Mao等人，2017）将差分进化算法与粒子群优化相结合，采用两阶段更新方式，先进行差分变化处理，再进行粒子群优化更新。EPSODE（集成粒子群优化与差分进化算法）（Wang等人，2020）则将种群分为粒子群优化子和差分进化子群，之后再合并筛选出的最优解。这些研究展示了结合不同搜索算子的有效方法，但这些额外的进化步骤也会引入更多参数，在某些设计中还会增加每次迭代的成本。对于需要在不同地图或参数设置下反复运行的规划器来说，这一成本依然具有重要意义。其他混合方法则为粒子群优化增加了不同的搜索机制。ACOPSO（Dubey等人，2021）融入了蚁群优化算法中的信息素引导搜索机制（Zhang和Pang，2022），而SAPSO（Lu和Zhang，2021）则采用了模拟退火算法中的次优解接受策略（Kirkpatrick等人，1983；Tsang和Wiese，2010）。这类设计能够扩大有效搜索范围，或帮助粒子摆脱不良的局部状态。不过它们也需要额外的参数设定，而且其对于最终路径的贡献往往难以与粒子群优化更新本身的贡献区分开来。因此，人们致力于开发既能提升路径质量，又能保持各附加算子作用可解释性的搜索设计。另一类研究思路则着眼于这样一个事实：对所有粒子应用相同的更新规则会导致粒子行为趋同，增加过早收敛的风险（Zhu等人，2025；Pi等人，2024）。基于子群体的策略通过根据粒子的当前状态为其分配不同的搜索任务来解决这一问题。例如，ACVDEPSO（参数、圆柱向量及不同进化算子的自适应调整算法）（Huang等人，2023b）将粒子分为精英粒子群、普通粒子群和劣质粒子群，并为不同群体设置不同的参数。IMSaDE（具有改进变异策略的自适应差分进化算法）（Wang等人，2018）通过区分精英群体和非精英群体来优化变异策略。CPSO（组合型粒子群优化算法）（Jarboui等人，2007）则形成动态集群，而DPGABC（双子群人工蜂群算法）（Guo等人，2024）则结合分层子群划分与差异化的搜索策略。MSCPSO（多子群协作型粒子群优化算法）（Tang等人，2024）也通过多个子群来选择不同的更新策略。这些研究表明，种群划分确实能够增强搜索的多样性，但同时也留下了一个重要的设计问题：如何在不同质量水平的粒子之间实现信息交流？对于路径规划而言，这个问题尤为重要，因为一个粒子并非仅仅是某个标量形式的候选解，它是由多个航点构成的结构化路径。一个成本较高或性能较差的粒子可能会与障碍物相撞，或者包含不必要的绕行路径，但其某个航点仍可能代表一条有用的局部通道或转弯方案。DEPSO（自适应差分进化与粒子群优化混合算法）（Wang等人，2019）就认识到非精英粒子也可能包含有用的组件级信息。AMCPSO（自适应多群竞争型粒子群优化算法）（Kong等人，2019）、DPCPSO（动态种群协作型粒子群优化算法）（Li等人，2022）以及MSPSO（多群粒子群优化算法）（Qiu，2020）则通过竞争、重组或重构等方式来处理性能不佳或非精英粒子。TSLPSO（基于维度学习策略的粒子群优化算法）（Xu等人，2019）进一步提出，粒子无需一次性从完整路径中学习。这些理念对于基于航点的路径规划具有直接意义：与其直接丢弃或重构非精英粒子对应的整条路径，不如先检测这些粒子中的单个航点是否能够改进当前的最佳全局路径。路径的角度质量和安全性又带来了第三个挑战。Bézier-PSO（受贝塞尔曲线约束的粒子群优化算法）（Song等人，2021）和Hybrid-GA（Luan和Thinh，2023）采用贝塞尔曲线来平滑规划路径。A?-PSO（A?算法与粒子群优化算法混合算法）（Huang等人，2023a）则先利用A?算法（Zuo等人，2024）生成初始路径，然后再对选定的节点进行优化。PSO-MFB（混合粒子群优化算法与频率蝙蝠算法）（Ajeil等人，2020）则在目标函数中加入了累积角度偏差项。类似地，M. Zhang等人（2023）在三维无人机轨迹规划模型中，还将转弯角度项与地形威胁、飞行距离、飞行高度和能量消耗等因素一起纳入考量。这些研究都表明，路径的规则性以及局部转弯行为通常会被视为明确的规划准则，但仅凭单一的累积角度得分，并无法区分全局的方向一致性以及局部的转弯需求。许多规划研究还会报告几何筛选结果，却未在平台级跟踪仿真中对路径进行实际测试。对于无人水面艇而言，这种区分非常重要，因为即使某条折线路径在表面上看起来可行，但若考虑到最小转弯半径、偏航响应以及水流漂移等因素，其实际执行难度可能仍然很高。考虑水流影响的评估同样需要精确的标准。本研究并未试图构建经过校准的推进力-能量模型，而是通过计算每段路径上的有效地面速度，进而得出相应的行进时间项。这一项反映了有利和不利水流对路径评估的规划层面影响，因此本研究中所采用的考虑水流影响的指标属于行进时间成本，而非经过实测或校准的能量数值。基于上述讨论，本研究旨在解决以下三个问题：（1）混合粒子群优化变体虽能提升搜索能力，但额外的进化算子可能会增加计算成本并提高对参数的依赖性；（2）非精英粒子往往会被直接变异、重构或作为整条路径被丢弃，而并未事先检测其单个航点是否能够改进当前路径；（3）角度路径质量指标虽有助于规范基于航点的路径，但单一的累积角度得分并不能明确区分全局的方向一致性以及局部的转弯需求，也无法确保规划出的路径在闭环执行过程中仍易于跟踪。为解决这些问题，本文提出了AESHPSO，这是一种具有自适应进化策略的分层粒子群优化算法，可用于无人水面艇的全球路径规划。该算法首先根据粒子的适应度对其进行排序，然后将其划分为领头粒子群、普通粒子群和边缘粒子群。这种固定的层级结构是一种经验性的设计方案，其各子群的比例随后会通过敏感性分析进行研究。当检测到搜索陷入停滞时，AESHPSO会对领头粒子群应用两阶段变异策略。第一阶段采用差分变异，整合来自不同子群的信息；第二阶段则针对那些存在过度角度偏差或违反规划层面转弯半径要求的航点进行针对性变异，之后再使用与其他候选路径相同的评价标准和筛选流程来评估该候选路径。在常规搜索迭代过程中，AESHPSO为普通粒子群设计了基于正弦和余弦函数的动态参数调度策略。该调度策略利用正弦函数与余弦函数之间的相位差，在优化过程中调整惯性和加速度系数，旨在在早期迭代阶段保持更广泛的搜索范围，而在后期迭代阶段则更多地依靠集体信息。对于边缘粒子群，AESHPSO则采用基于坐标下降的特征搜索策略，判断那些成本较高的边缘粒子所对应的航点特征是否能够改进当前的最佳全局路径。这样一来，就能够直接利用那些整体路径适应度较低的路径中的局部信息。本研究通过规划层面指标、考虑水流影响的行进时间成本，以及基于典型无人水面艇参数设定的简化三自由度跟踪仿真器，对AESHPSO进行了性能评估。实验评估还包括敏感性测试、沿岸场景测试、因子消减法分析以及故障模式分析，以了解所提算法组件的工作条件及其局限性。本研究的主要贡献如下：（1）我们为领头粒子群设计了两阶段变异策略。第一阶段利用来自三个子群的信息进行差分变异；第二阶段则针对存在过度角度偏差或违反规划层面转弯半径要求的航点进行处理，之后再通过统一的评价标准和筛选流程对候选路径进行评估。（2）我们设计了一种基于正弦和余弦函数的动态参数调度方法，用于在粒子群优化过程中调整惯性和加速度系数。（3）我们为边缘粒子群引入了基于坐标下降的特征搜索策略，无需直接丢弃成本较高的边缘粒子，而是先检测这些粒子中的单个航点是否能够改进当前的最佳全局路径。（4）我们通过规划层面指标、考虑水流影响的行进时间成本、简化的跟踪压力测试、敏感性分析、搜索动态诊断、因子消减法分析以及故障模式分析，对所提方法进行了全面评估。本文的其余部分结构如下：第2节回顾了作为本方法算法基础的粒子群优化算法、差分进化算法以及MRPSODE算法；第3节阐述了无人水面艇路径规划的目标和约束条件；第4节介绍了AESHPSO的三个核心组成部分：两阶段变异策略、自适应参数调度策略以及坐标下降特征搜索策略；第5节报告了实验评估结果及其局限性；第6节对全文进行总结。片段 粒子群优化算法 粒子群优化算法（Kennedy和Eberhart，1995）是一种基于种群的随机优化方法。在路径规划应用中，每个粒子对应一条候选路径，粒子的位置则表示搜索空间中的一个点。每个粒子还存储有一个速度向量，用于确定其下一个位移方向。在第k次迭代时，粒子的更新会以两个参考位置为依据：即粒子i找到的自身最佳位置Pi,bestk，以及整个种群找到的全局最佳位置Gbestk。问题表述
无人水面艇的全球路径规划问题被构建为一个在二维水平工作空间中的受限标量化多准则优化问题。其目标是在满足碰撞避免以及规划层面的转弯半径限制条件的前提下，寻找从起始位置到目标位置的路径，同时确保路径长度、累积角度成本以及考虑当前状况的行驶时间尽可能低。

提出方法
如第1节所述，现有的基于粒子群优化的路径规划算法存在子群体间协作不足、未能充分利用非最优粒子的信息，以及对局部转弯行为控制能力有限等问题。AESHPSO通过监控全局最优解的演变情况，在某固定时间窗口内的改进幅度低于预设阈值时触发分层更新机制。此时，粒子会按照适应度由高到低排序，并被分为障碍物场景和当前场景两类。

仿真设置
仿真采用了1.6米级商用无人水面艇的典型参数：最大水下速度Vmax=5m/s，最小转弯半径Rmin=3m，艇体长度Lusv=1.6m。该艇体长度也被用作方程(23)–(24)中点质量无人水面艇模型的安全尺寸参数。由于规划出的路径段通常远大于此转弯半径，因此方程(13)仅作为规划层面的转弯半径筛选条件，而非闭环执行性标准。

结论
本文提出了AESHPSO，这是一种用于无人水面艇考虑当前状况的全球路径规划的分层粒子群优化算法。为克服传统均匀搜索策略的局限性，AESHPSO根据粒子的适应度对种群进行划分，并为每个子群体应用专门的优化操作。该算法通过两阶段变异机制，整合不同子群体间的信息，针对角度偏差过大或违反规划层面转弯半径限制的情况调整路径节点。

CRediT作者贡献声明
吴艺文：论文撰写——初稿、方法论、概念设计。林帆奇：软件实现、方法论、实验分析。杨德全：可视化处理、软件开发。李贤能：论文润色与编辑、研究指导、方法论设计。

利益冲突声明
作者声明不存在任何可能影响本文研究结果的已知财务利益关系或个人关系。

致谢
本研究得到了科学挑战计划（项目编号TZ2025005）以及中国国家自然科学基金（项目编号72071029和72231010）的支持。