1.摘要
针对多AUV在大规模复杂海底环境中执行多目标任务时面临的路径规划难题，本文突破传统单目标静态建模方式，将问题建模为动态多目标优化问题，并提出一种协同进化计算算法。该方法采用双层编码结构表示投放位置与任务访问顺序，结合多目标多种群框架、基于重组的采样策略以及环境变化下的增量响应机制，以提升解的多样性与收敛性能。基于新西兰海底地形数据构建的大规模复杂场景实验表明，该方法在解的多样性和最优性方面优于现有先进算法。
2.问题背景
问题阐述
本文研究多自主水下航行器（Multi-AUV）在大尺度复杂海洋环境中执行多目标任务的路径规划优化，设任务集为 $M = {m_1, \dots, m_N}$，多个AUV通过水面移动平台投放并可进行多次往返航行。要求每个目标任务仅被一次航次访问，且每个航次的总载荷不超过AUV最大载荷 $L_{\max}$，同时航次能量消耗不超过最大可用能量 $E_{\max}$。由于海洋环境与任务可能随时间变化，问题被建模为动态多目标优化模型：
$\min F(X, t) = (f_1(X, t), f_2(X, t))$
其中，$f_1$ 表示所有航次的总运行成本
$f_1(X, t) = \sum_{j=1}^{n_v} g_j + w_e \cdot n_v$
综合考虑航行能耗与AUV发射回收的固定成本，$f_2$ 表示所有航次中的最大完成时间
$f_2(X, t) = \max_{1 \leq j \leq n_v} h_j$
其用于衡量任务负荷均衡性。约束条件包括任务唯一分配约束
$\sum_{j=1}^{n_v} x_{ij} = 1$
载荷约束
$\sum_{i=1}^{N} l_i x_{ij} \leq L_{\max}$
能量约束
$g_j \leq E_{\max}$
其中，单个航次的能量消耗定义为
$g_j = w_1 \text{len}(p_j) + w_2 \text{ht}(p_j) + w_3 \text{turn}(p_j) + w_4 \text{risk}(p_j)$,
分别对应路径长度代价、地形高度变化代价、转向代价和风险代价。路径长度代价
$\text{len}(p_j) = \sum |w_j^{i,k} - w_j^{i,k+1}|$
高度代价
$\text{ht}(p_j) = \sum \text{height}(w_j^{i,k}, w_j^{i,k+1})$
转向代价
$\text{turn}(w_j^{i,k}) = 1 - \cos(\theta_j^{i,k})$
风险代价与风险区域的空间分布相关：
$\text{risk}(p_j) = \sum rt(w_j^{i,k}), \quad rt(w) = \sum_{r=1}^{n_r} RI \cdot \max(0, R_r - |w - r_c^r|)/R_r.$
动态多目标优化
动态多目标优化需要持续跟踪变化的帕累托最优解，现有方法主要包括帕累托局部搜索、元启发式算法和学习驱动方法。帕累托局部搜索通过邻域搜索与存档优化提升效率，元启发式算法借助遗传算法、粒子群、蚁群等机制增强多样性与收敛性，学习方法则利用高斯过程、图神经网络或注意力模型构建或预测解。针对环境动态变化，常用策略包括解重用、预测、迁移学习和强化学习，但在稳定性、泛化能力与数据需求方面各有局限。
3.协同进化计算算法
水下环境建模
三维水下环境被离散为规则立方体网格并构建为搜索图 $G = (V, E)$，立方体中心坐标为
$x = (i + 0.5)L_C, \quad y = (j + 0.5)W_C, \quad z = (k + 0.5)H_C$
相邻立方体之间建立边连接，障碍或地形冲突的节点被删除，风险区域节点赋予风险值。与水面相交的节点构成发射回收集合 $V_S$，包含任务的节点构成目标集合 $V_T$。
在加权图中，边权表示能量与时间成本，路径代价为边权之和，若能量与时间互不支配，则优先选择能量更低的路径。最短路径通过SPFA算法计算。为降低规模，仅保留 $V_S \cup V_T$ 构成子图
