2025年ASOC SCI2区TOP，协同搜索框架自适应算法+多无人机巡检规划，深度解析+性能实测

---

1.摘要

多无人机巡检路径规划已成为在数据采集截止时间前完成巡检任务的重要研究课题，本文提出了一种名为 Sa-VCO自适应启发式算法，结合协同搜索框架，用于解决多无人机巡检路径规划问题。Sa-VCO设计了一种区域网格化分散方法，将原始目标区域转化为一组标准的目标子区域，从而允许多个无人机共同完成高成本区域的巡检任务；提出了一种自适应初始解生成策略，利用所有目标构建的图结构信息；建立了一个协同搜索框架，用来增强搜索效率并提升种群多样性。

2.模型描述和区域网格离散设计

区域网格离散设计

本文采用了一种基于网格的方法，将巡检区域划分为较小的标准子区域，每个子区域作为一个独立的目标进行处理。设定初始网格大小为摄像机在单位时间内的拍摄范围，并计算所有目标区域的离散网格数量。找出各目标区域网格的最大公因数，并根据此更新标准子区域的面积，以使得目标区域能通过多个无人机共同巡检。

模型描述

通过将巡检区域转换为标准子区域，原本的多区域覆盖全球路径规划问题可以转化为对离散中心点集合的巡检规划。假设所有子区域的巡检能耗一致，该规划问题可以采用MTSP模型来描述。
$$\mathrm{Cos}{t}_{total}=\sum _{k=1}^m\sum _{i=1}^n\sum _{j=1;i\ne j}^n(d_{ij}\times x_{ij}^k)$$
$$\mathbf{Cos}{t}_{\max }=\max (\sum _{i=1}^n\sum _{i=1}^n(d_{ij}\times x_{ij}^k))\forall k=1,2,\cdots ,m$$

3.Sa-VCO算法

初始化

Sa-VCO充分考虑了多无人机路径规划问题的解结构，强调该问题并非简单的离散序列，而是具有实际意义的图结构。通过合理的任务预分配和基于任务之间空间关系的巡检顺序规划，能够有效避免大量不必要的搜索成本。首先利用聚类算法将目标尽可能均匀地分配给参与巡检的无人机。根据子路径中目标数量的多少，自适应生成初始的目标巡检顺序。通过设定目标数量阈值Dmax辅助策略选择，对于目标较少的子路径，同时采用ACO方法和随机贪心选择方法进行竞争选择；而对于目标较多的子路径，则仅使用随机贪心方法，以降低计算消耗。

P-聚类方法

P-聚类方法通过改进的基于极坐标的聚类方法，将目标预分配到不同的无人机上，该方法以目标到起始仓库的距离和连接目标与起始仓库的直线相对于水平正方向的角度作为聚类依据，这两个特征能够有效反映目标与图结构中其他目标的关系。首先建立一个新的坐标系，起始仓库作为原点，水平方向为x轴，垂直方向为y轴，然后计算所有目标点在该坐标系中的极坐标作为其新的坐标。所有目标根据新坐标进行分类，将目标分配为与无人机数量相同的m个类别。如果目标数量不均，则剩余目标被分配到最后一类。每个类别假设有一个中心，并根据设计的成本指标评估任务量，该成本指标考虑了类别内目标的紧密程度以及类别中心到起始仓库的距离，从而优化任务分配。
$$C_i=2\times (d_i-d_{\min })+\sum _{j=1}^{nu{m}_i}{d}_{cj}i=1,2,\cdots ,m;j=1,2,\cdots ,nu{m}_i$$

ACO初始化方法

在目标较少的子路径中使用ACO作为初始化方法，从而得到更优的初始解，减少计算消耗，并通过仅一次使用ACO方法来避免更新信息素矩阵时的高时间成本。

为了提高搜索效率，在初始种群生成后，完整的种群将被划分为三个子种群：精英子种群、常规子种群和劣质子种群。精英子种群中的个体质量最高，因此在寻找全局最优解时具有最大的价值。常规子种群包括那些与精英个体距离较近，但解的质量不如精英个体的个体。我们通过精英子种群与常规子种群之间的合作来探索搜索空间，有效地将搜索空间划分为优质和劣质的区域。

种群的划分是基于个体的适应度值、每个个体与当前最优解的相似性以及子种群大小控制参数，个体与当前最优个体之间的相似度：
$$S_j=\sum _{i=1}^{UA{V}_{num}}\frac{{\sum }_{k=1}^{U_{num}}{S}_{best}^{jik}}{nu{m}_j^i}$$

其中，$S_{best}^{ijk}$是第$k$个目标在个体$j$的第$i$子路径与当前最优解相应子路径之间的相似度：
$$S_{best}^{ijk}=\frac{U_{best}^{ijk}}{nu{m}_{best}^i}$$

由于种群中个体的分布在不同阶段可能会发生变化，在迭代结束时，种群大多会向最优解附近的区域移动，因此在算法执行过程中，子种群的接受概率会进行动态调整:
$$p_d=p_{binitial}+0.4\times \left(\frac{1}{1+e^{-\frac{6\times iter}{Iter}}}-0.5\right)$$
$$p_b=p_{binitial}+0.4\times \left(\frac{1}{1+e^{-\frac{6\times iter}{lter}}}-0.5\right)\times \frac{l_e}{l_e+l_c}$$

精英种群库策略

精英种群库策略通过精英个体与所有精英子种群个体共享信息，生成精英信息数据库，从而提升搜索效率。

平衡搜索策略

平衡搜索策略利用常规个体和精英个体之间的差异，分析和划分搜索空间。通过记录常规个体和精英个体中频繁出现的路径段，并清除它们之间的重叠，确保每个记忆库中保留独特的路径段。此外引入学习机制，常规个体通过从精英子种群中随机选择个体进行学习，生成粗略的后代结构，并通过更新记忆库，防止搜索陷入劣质解领域，提升搜索效率。

扩展搜索领域策略

扩展搜索领域策略针对劣质子种群，假设个体解中每次访问的节点并非最优，因此，通过调整节点而非仅调整访问顺序，可能会获得更好的解。

4.结果展示

5.参考文献

[1] He C, Ouyang H, Huang W, et al. An adaptive heuristic algorithm with a collaborative search framework for multi-UAV inspection planning[J]. Applied Soft Computing, 2025, 174: 112969.

6.代码获取

xx

7.算法辅导·应用定制·读者交流