多无人艇协同目标分配算法研究

曹 璐

（中国船舶重工集团有限公司第七一〇研究所，湖北 宜昌 443003）

0 引言

在未来战争中，面对动态复杂的环境、不可预知的潜在危险和多样化的任务使命，单一无人艇受限于自身搭载的有限的载荷与系统，显得势单力薄。与此同时，由多艘无人艇联合起来构成的协同系统，具有更强的鲁棒性、通信能力、机动性、灵活性、更高的作业效率和更广的作业范围。考虑到现代战争对于多兵种、多武器、多方位的综合协同作战需要，多无人艇协同系统可完善无人作战系统的发展使用[1]。协同目标分配是多无人艇协同系统中的关键技术，其目的是充分发挥各无人艇的优势，实现资源的优化配置，提高无人艇的战场动态适应能力以及整体作战效能。

虽然国内外学者运用不同方法对协同目标分配进行了研究，但还是存在一些不足，如基于整数规划模型的算法在求解大规模组合优化问题时存在时间、空间复杂性等不足[2]；遗传算法由于其本质上的随机性导致其在大规模组合优化问题的求解中效率和精度不高[3]；基于合同网方法的优化能力建立在协商和竞争的基础上，当问题规模较大时会导致协商通信量大大增加[4]。贝叶斯优化算法通过构造和学习贝叶斯网络来替代传统遗传算法的交叉重组和变异等操作，实现对解空间的指导性搜索和连锁学习，已经在多目标分配上得到应用[5-6]。但随着问题规模的增加，贝叶斯优化算法计算量和空间占用量会急剧增加。DBOA采用决策图增强对贝叶斯网络结构的表达和学习，减小计算量和空间占用量，具有更强的局部搜索能力。因此，本文根据多无人艇协同目标分配问题的特点，在分析多约束多目标优化问题的基础上，提出了一种基于DBOA的多无人艇协同目标分配方法。

1 决策图贝叶斯优化算法

贝叶斯优化算法（Bayesian Optimization Algorithm，BOA）是一种分布估计算法，是在遗传算法（Genetic Algorithm，GA）的基础上发展起来的一种优化算法[7]。其主要思想是把自然进化算法和构造性数学分析方法相结合，以指导对问题空间的有效搜索。与遗传算法不同的是，该算法不是采用交叉和变异的方法来产生新的个体，而是采用贝叶斯网络对上一代群体中的优秀个体集合进行描述，估计变量之间的概率分布关系，然后根据此概率分布产生新的子集，用新的子集替换上一代群体中的部分个体形成新一代群体，如此反复，直到满足算法的终止条件。具体过程如图1所示。

传统进化算法通过基因的微观操作实现群体的进化，BOA通过建立优选解的概率模型来描述随机变量之间的概率依赖关系，从宏观上指导种群的进化，因此可以捕获变量关系结构、确认并操作关键构造块，避免了微观操作对构造块的破坏，具有较强的求解高阶构造块问题的能力[8]。但随着问题规模的增加，计算量和空间占用量会急剧增加，导致BOA无法求解，而基于决策图的贝叶斯优化算法有着更强的局部搜索能力，能够减小计算量和空间占用量[9]。

图1 贝叶斯优化算法示意图Fig.1 Schematic diagram of Bayesian optimization algorithm

DBOA采用决策图增强对贝叶斯网络结构的表达和学习，由此可以减少大量参数的存储。决策图是一有向无环图，用来代表变量的条件概率分布，每一个变量Xi对应一个决策图Gi，Gi中非叶节点为Xi的父节点，叶节点保存Xi的条件概率。决策图贝叶斯网络的建立仅通过修改所有变量的决策图来实现，不但简化了过程，而且还避免了对贝叶斯网络的直接操作而影响网络的质量。

2 协同目标分配数学模型

多无人艇协同目标分配是以整个无人艇编队的整体作战效能最优为目标的，而无人艇的消耗（USV Attrition）、目标价值的毁伤（Target Value Damage，TVD）和执行任务预计耗费时间（Task Expending Time，TET）是评价作战效能的主要指标。本文首先分析了影响这3项指标的关键因素，分别建立了无人艇消耗模型、目标价值毁伤模型和任务耗费时间模型。然后通过量纲转换和加权求和，将多目标优化问题转换为单一目标函数，得出了无人艇优势函数。由于作战过程中无人艇内部存在着协作关系，因此建立了无人艇整体优势函数，进而得到了多无人艇协同目标分配数学模型。

1）USV消耗模型。

在USV对目标进行打击的同时，目标也对其进行反击，造成了USV的消耗。设第u艘USV打击目标t的生存概率为PSut，则USV的消耗模型为

2）目标价值毁伤模型。

综合考虑目标的价值、确认概率、杀伤概率、USV相对于目标的生存概率，则使用第u艘USV攻击目标t时，目标价值毁伤模型为

式中：Pc表示USV准确到达任务区域、发现目标以及正确识别出目标的概率；PK表示 USV对目标的杀伤概率；Vt表示摧毁目标t获得的收益。

3）耗费时间模型。

通常USV到达目标区域越早，发现和打击目标就越早，所以用到达时间来近似估计USV执行任务耗费的时间，USV到达目标的时间与其和目标间的距离成正比。设第u艘USV与目标t间的距离为Dut，则耗费时间模型为

式中，Dmax为USV与目标间最远（最长到达时间）距离。

选取淀粉颗粒浓度分别为10%（m/V），OSA淀粉颗粒取代度为 1.43%，添加一定量的缓冲液配制淀粉颗粒分散液，油相比例分别为0.1、0.2、0.3、0.4、0.5，制备乳液，乳化方法同1.3.4。

4）USV整体优势函数。

将多目标决策问题转换为单目标优化问题的常用方法是加权求和，即为各子目标函数赋予相应的权值，权值的大小体现了各子目标函数的重要程度，因此，本文采用这一方法将多目标优化问题转换为单目标最优化问题。将各量纲转化为[0,1]集合内的数值，令目标的价值V取0～1之间的数值。因此，USV优势函数为

式中，ω1、ω2、ω3为权系数，反映了每个子目标的重要程度。

在作战过程中，不仅敌我双方存在着冲突，而且己方内部也存在着冲突。在合作的同时，各无人艇都会尽量取得对敌目标较大的优势，但在实际应用中，有时候一部分无人艇的优势获得是以另一部分无人艇的态势损失为代价的。因此，不仅要确定敌我双方的权重，而且还需要确定己方内部各无人艇的权重分配。对于己方内部的权重分配采用多人层次分析法获取，因此可以得到USV的整体优势函数为

式中，ωm是己方内部各无人艇的权重。

5）协同目标分配数学模型。

目标分配的目的是使USV编队的总体优势达到最大，从而形成合理的作战方案。目标分配不但要有衡量分配方案优劣的标准，而且还需要满足一定的限制条件，由此可得多无人艇协同目标分配模型为

3 基于DBOA的协同目标分配

通过建立协同目标分配的数学模型，并采用二进制编码方案，以整体优势函数作为适应度函数，即将USV消耗最小、价值毁伤最大以及任务耗费时间最短作为待优化的性能指标，得到了基于DBOA的多无人艇协同目标分配的基本步骤：

1）根据多无人艇协同目标分配的数学模型确立相关参数；

2）生成各艘无人艇对相应目标的优势函数值，从而得到无人艇优势矩阵；

3）计算无人艇编队内部的权重，在优势矩阵的基础上生成多无人艇整体优势函数；

4）进行DBOA参数设置，运用DBOA进行多无人艇协同目标分配。

因此，多无人艇协同目标分配 DBOA流程图如图2所示。

图2 多无人艇协同目标分配DBOA流程Fig.2 DBOA flow of multi-USV cooperative target assignment

4 仿真及结果分析

4.1 仿真初始条件设定

仿真中设定无人艇数量为4，目标数量为4，为了计算的简便，做出如下假设：1）无人艇的生存概率已知；2）无人艇能准确到达任务区域、发现并正确识别出目标，则Pc= 1；3）无人艇携带的武器对目标的杀伤概率为已知数；4）目标的价值已确定；5）通过USV自身的生存、对目标的杀伤、以及完成任务耗费时间三者的重要程度可以确定权值ω1、ω2、ω3。

4.2 仿真计算与分析

根据USV消耗模型、目标价值毁伤模型以及耗费时间模型可以计算出无人艇优势函数值，从而得到无人艇相对目标的优势矩阵，如表1所示。

表1 无人艇优势矩阵Table1 USV superiority matrix

根据多人层次分析法可以确定4艘无人艇的权重分别为ωu1=0.157 9、ωu2=0.3158、ωu3=0.105 2、ωu4=0.421 1。在确定无人艇优势矩阵以及内部权重的基础上，经过 21步运行后寻找到最优分配结果，得到的最优分配结果编码为0011010000100001。化成矩阵形式即目标3分配给USV1，目标4分配给USV2，目标2分配给USV3，目标1分配给USV4，最终的适应度值为0.273 46。图3给出了各代群体中个体适应度的最大值、最小值与平均值，从图中可以看出DBOA能够快速找到个体适应度的最大值，个体适应度的平均值也呈现出快速上升的趋势，具有良好的收敛性且速度快。

图3 适应度变化曲线图Fig.3 Fitness curve

为了说明DBOA的优越性，本文分别采用GA和 BOA对多艘无人艇协同目标分配问题进行求解。图4给出了50代内3种算法在上述条件下对目标进行分配的最优解曲线，从图中可以看出GA的运行速度最慢，而DBOA和BOA在运行速度上具有相当大的优势，并且DBOA的进化代数更少，收敛速度最快。

图4 DBOA和BOA、GA的最优值比较Fig.4 Comparison of optimal values among DBOA and BOA，GA

5 结束语

本文对多艘无人艇协同作战过程中的协同目标分配问题进行了仿真研究。针对协同目标分配过程中的多参数、多约束条件，提出了基于 DBOA的协同目标分配方法。DBOA是一种处理多目标优化问题的有效方法，作为BOA的改进，不仅具有BOA较强的优化能力，避免逼近局部最优或早熟，而且通过决策图增强了对贝叶斯网络结构的表达，减少了存储。因此，将 DBOA应用于多艘无人艇协同目标分配中，能快速对多约束条件下的多目标优化问题进行求解，并能反映多艘无人艇作战的协同性与对抗性。