无人机集群任务分配中群智能算法性能对比*

梁智韬，贾高伟，王建峰

（国防科技大学空天科学学院，长沙 410073）

0 引言

经过数十年的快速发展，无人机的自主性能不断提高，但单架无人机在复杂环境下完成复杂任务仍具有局限性。无人机集群能够充分发挥无人机平台机动灵活、成本低廉、应用广泛的优势，以能力组合的形式协同高效地完成多样化任务，逐渐成为航空武器装备发展的重要趋势。

无人机集群任务分配，是根据集群中的无人机数量、类型、所要执行的目标任务及载荷的不同，对无人机完成具体任务的预先设定与统筹管理，其本质是多约束条件下的优化求解问题。在具体实施过程中，需要考虑无人机动力学模型及其飞行性能、载荷性能、目标特性、通信及环境限制等约束条件，为无人机规划出合理的任务执行方案和飞行航迹，并确定载荷配置、使用方式与时间节点等，确保某一项或多项指标最优。

概括来讲，适合于无人机集群的任务架构包括集中式、分布式、集散式等多类，其中，集中式是当前最直接、最成熟的集群模式，无人机集群接受单个或多个中心控制。集中式任务分配求解方法又可以分为最优化方法和启发式方法。一般而言，最优化算法具有描述简洁、直接等特点，可以灵活调整约束条件来求解实际问题，具有理论最优解，但规模不宜过大，一般可用于无人机集群离线式任务分配。在启发式算法中，智能类算法的应用较多，尤其以蚁群算法、遗传算法、粒子群算法等居多。这几类算法通常具有较强的稳定性，适合分布式计算机制，也能够与多类其他算法结合。但这些智能类算法之间的相对优势缺乏深刻的、具有普遍意义的分析，尤其缺乏几类算法在运算速度、收敛速度、求解优化性方面的对比。

在无人机集群的诸多应用中，对敌防空打击（destroy of enemy air defenses，DEAD）涵盖任务类型多、有明确的逻辑约束和时间窗约束，是典型的复杂任务集合，是无人机集群的重要应用领域，可以作为研究无人机集群任务规划的典型对象。本文以对敌防空打击为任务样式，量化分析蚁群算法、遗传算法、粒子群算法在任务分配方案求解过程中的特性。

1 无人机集群协同任务分配模型

1.1 问题描述

式中，M是攻击任务，M是侦察任务。

无人机集群协同分配的根本出发点是提高对敌毁伤效能，降低己方损失，为此本文将无人机的损耗概率、目标的价值收益和飞行航程的长度作为评价作战效能的主要指标。

1.2 代价与收益

无人机集群执行协同侦察（攻击）任务，其代价主要来源于两方面：威胁代价和航程航时代价。由于威胁代价、航程航时代价以及收益指标的量纲存在差异，通过线性尺度变换法，将各个量转化为无量纲数值，范围在［0，1］，具体地：

威胁代价：目标阵地配备的高射炮、导弹以及其他武器对无人机造成的直接毁伤或者间接干扰而导致的代价。

航程代价：根据无人机执行任务的航迹计算航程代价。一方面，航程越长，无人机的携带的燃油损耗、机件损耗越大；另一方面，航程越长，对应的任务执行时间也越大。为反应集群的整体航程，本文设定航程代价由集群整体执行任务的时间衡量。航程代价C可表示为：

式中，t表示集群中单机执行任务的最长时间；t表示集群中单机执行任务的最短时间。

航时代价：仅考虑航程代价C存在任务分配平均化但总时长较长的局限性，因此，引入航时代价，以具体的时间指标来对整体任务分配计划进行约束。航时代价C可表示为：

式中，t 表示集群执行任务的总时间；t＇表示固定的时长衡量指标。

协同侦察（攻击）收益：定义无人机i 侦察（攻击）目标j 所获得的收益为：

1.3 目标函数

对应得到多无人机任务分配模型的优化目标解析表达式为：

式中，决策变量K是一个0-1 型变量。当K=1 时，表示无人机i 执行对目标j 的侦察（打击）任务。

1.4 约束条件

在无人机集群对敌防空打击系统应用过程，结合实际需求，有如下条件约束：

1）每架无人机的任务最大执行能力约束：

式中，L是攻击无人机携带武器的数量。定义无人机每完成一次攻击任务消耗一枚导弹（炸弹）。

2）暂不考虑任务能力冗余配置，假定一项任务只能由一架无人机执行一次：

3）一般情况下，认为无人机集群能够将所有任务完成：

4）逻辑约束：要求同一个目标需经过侦察型无人机确认后，再由打击型无人机实施打击。具体表示为：

1.5 任务时序关系

在无人机集群对敌防空打击系统作战应用中，设定其侦察与打击的逻辑时序为：

Step 1：开展侦察任务规划，完成对侦察任务分配结果寻优，得到侦察任务时序表；

Step 2：侦察过程中一旦有目标得以确认，启动攻击任务规划，完成对地攻击任务分配结果寻优，得到攻击任务时序表；

Step 3：查看任务完成情况；若存在已确认目标未分配打击无人机，重复Step 2；若所有任务均已完成，进入Step4；

Step 4：输出对敌防空打击任务分配时序表。

图1 对敌防空打击任务分配流程图

2 算法的选择与说明

2.1 遗传算法的设置

遗传算法（genetic algorithm，GA）借鉴了进化生物学中的遗传、突变、自然选择和交叉等现象，通过建立多维数组来模拟生物的DNA 碱基序列。

2.1.1 遗传算法编码方式

设定每一个数组为一条DNA 序列，序列中DNA 碱基数目等于任务数目，碱基单位由数字构成。关于无人机能力和执行任务的准则在第1 章已经阐明。这里碱基单位的整数部分［A］表示任务对应的无人机序号，整数部分相同的目标任务分配在同一架无人机的任务序列中；小数部分A-［A］表示目标在该无人机任务序列中的优先程度，以升序关系对应任务执行次序。下页表1 给出了编码的样例：

表1 遗传算法编码示意

表中所示为3 架无人机对6 个目标执行协同侦察任务的编码表示，DNA 序列长度为6 维（序列长度应与目标数保持一致）。实数2.8 中2 代表无人机序号，0.8 代表目标1 在无人机2 对应的执行任务中的优先级，遗传算法中为了避免陷入局部最优，包含了交叉和变异两类典型操作。图2 和图3给出了采用此种碱基编码方式对应的交叉变异处理过程。

图2 交叉互换示意

图3 变异示意

设定种群中个体生产子代（即基因交叉互换）的概率为θ，子代出现基因变异的概率为Ω。同时为提升种群的寻优效率，设立环境淘汰概率ε。根据每轮循环结束后个体适应度值在种群整体适应度值中的占比进行淘汰。

2.1.2 遗传算法参数设置

遗传算法的参数设置主要包括：基因变异概率Ω，环境淘汰概率ε。

在智能算法中，各参数之间相互耦合，且对于算法性能产生非线性影响。因此，在参数选择的过程中主要采取试探性的实验，通过遍历范围内的所有参数选择以获取对于模型性能最优的参数组合。但随着参数数量的增加，参数组合遍历所需的实验次数以指数级增长，完全遍历耗时长且效率低下。对此，通过采取均匀设计的方法，以参数组合空间中的具备代表性的样本点为依据，极大地化简了参数选取实验的复杂程度。均匀设计方案的科学性已有文献［15-16］说明，在此不再详述。

本文采取文献［16］附录中的均匀设计表，对遗传算法的参数：基因变异概率Ω 和环境淘汰概率ε进行设计实验，每组试验重复20 次，随后采用基因变异概率为0.02，环境淘汰概率0.05。

2.2 粒子群优化算法的设置

将无人机集群对敌防空打击系统任务分配模型与粒子群优化算法各要素建立映射关系，完成模型与算法的结合，这是粒子群优化算法（particle swarm optimization，PSO）应用的关键。

2.2.1 粒子群优化算法编码方式

结合无人机集群特点，本节采用基于实数向量的编码方式。编码的基本思想与遗传算法中表1 对应的编码方式类似，这有利于后期的算法性能对比。为准确阐述，这里说明如下：设定粒子的维度等于任务数目、粒子位置的整数部分［B］表示任务对应的无人机序号，整数部分相同的目标任务分配在同一架无人机的任务序列中；粒子位置的小数部分B-［B］表示目标在该无人机任务序列中的优先程度，以升序关系对应任务执行次序。表2 给出了粒子编码的样例：

表2 粒子编码示意

表1 和表2 所述的编码方式简洁易懂，可在不增加维数的前提下，将无人机及其对应的目标序列在编码中表示出来，解码处理仅需进行一次排序和取整运算即可。当进行粒子状态更新时，重新调整各个粒子的状态也比较方便。

2.2.2 粒子群优化算法的调整

标准粒子群优化算法主要根据下列公式进行更新迭代：

粒子在优化问题定义范围进行搜索的物理含义是每个粒子的位置代表一个解，并构成解空间；解的适应度值与虚拟环境下的每个位置相对应。粒子群的更新机制，即是利用当前位置、全局极值和个体极值3 个信息，指导粒子的下一步迭代位置。粒子个体充分利用自身经验和群体经验调整自身的状态是粒子群优化算法具有优异特性的关键。

在应用中，传统粒子群优化算法面临的主要不足表现为：1）搜索扩张因子是粒子群优化算法的主要控制参数，当搜索过程较为复杂时（对敌防空打击任务属性），控制参数的线性调整不能很好地适应实际搜索过程，有必要对控制参数进行自适应调整。2）容易早熟收敛（尤其是在处理多峰搜索问题中），全局寻优能力较差等。

追求完全的全局搜索会带来巨大的时间消耗，因此，有必要引入改进机制，其核心机理是通过调整控制参数，优化搜索策略，规避局部最优并尽可能地获取全局最优解。具体引入以下两种修改机制：

1）自适应参数控制

2）混合更新机制

将上文中提到的遗传算法中的变异和交叉操作（如图2～图3 所示）引入粒子群优化算法，通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解，以此提高粒子群优化算法的全局寻优能力。

2.2.3 粒子群优化算法的参数设置

粒子群优化算法的参数设置主要包括：自适应参数控制中收敛性指标与聚集性指标的系数。同样采取文献［16］附录中的均匀设计表，对粒子群优化算法的参数进行设计实验，每组试验重复20 次。采用收敛性指标0.4，聚集性指标为0.18。

2.3 蚁群算法的设置

2.3.1 蚁群算法的模型映射

蚁群算法（ant colony optimization，ACO）在无人机集群任务分配中的应用基础仍在于模型映射，这里给出映射模型如下：

2.3.2 蚁群算法的调整

不同于遗传算法和粒子群优化算法，在基于蚁群算法的任务分配过程中，约束条件的增多使得求解规模和求解时间大幅增加。为此，另一种优化的调整方案是适当减少任务约束。在任务分配中，如果对于出现冲突的任务，受领该任务的无人机可以将此任务以拍卖的形式转交给其他有富余能力的无人机。这样处理仅对局部的无人机任务分配产生影响，带来的运算量较小，具有较好的实用性。

拍卖作为一种社会化的协商机制，通过“招标-投标-中标”机制实现任务的委派和迁移。一般包括以下4 个步骤：

Step 1 任务宣布：当无人机发现自己没有足够的能力处理当前的任务，就作为招标者把任务向外界公布。

Step 2 招标：其他无人机接收到招标信息后，根据任务要求和自己的能力，选择最合适的任务进行投标，公布自己参与投标的代价。

Step 3 中标：在达到预定的投标截止时间后，投标者对投标进行处理，挑出最合适的投标并对外广播。

Step 4 任务执行：中标无人机将中标任务加入到自己的任务执行序列中，完成任务的转接。

2.3.3 蚁群算法的参数设置

蚁群算法的参数设置主要包括：将式（10）所示约束略去，改用拍卖算法调整不可完成任务；信息素蒸发系数ρ，信息素权重系数α，启发因子权重系数β。同样采取文献［15］中的均匀设计表U（12），对蚁群算法的参数进行设计实验，每组试验重复20次。得到信息素蒸发系数1.7，信息素权重系数2，启发因子权重系数0.57。

3 任务分配的仿真

3.1 仿真环境设置

本节通过仿真分析验证上述所提出的遗传算法、粒子群优化算法和蚁群算法。具体地，设有12架无人机执行任务，其中，7 架为侦察无人机，5 架为打击无人机。目标数量为15 个，目标属性为地面固定目标且方位已知，需要侦察无人机予以确认，并安排打击无人机予以消除。战场区域面积设置为120×120 km，目标与无人机机场布置如图4 所示。

图4 战场环境示意图（红星号代表无人机机场，蓝圆点代表目标点）

无人机集群和敌方目标的参数设置如表3～表5 所示。在不影响任务分配算法验证的前提下简化仿真实验过程，设定侦察无人机的探测半径同转弯半径一致，且当目标进入飞机的探测半径即代表已完成侦察任务。

表3 目标参数

表4 侦察无人机参数

表5 攻击无人机参数

3.2 各算法仿真分配结果

3.2.1 遗传算法仿真结果

结合2.1.1 节阐述的遗传算法编码方式，将交叉互换概率θ，基因变异概率Ω，环境淘汰概率ε分别设定为1、0.05、2%。得到的任务分配结果如表6、表7 所示。

表6 侦察任务分配结果

表7 打击任务分配结果

引入甘特图展示任务执行的时间属性，如图5所示。图中纵坐标代表无人机序号，时间条中编码对应目标序号。绿色矩形代表侦察任务部分，蓝色矩形部分代表打击任务部分；横坐标代表任务执行时间。

图5 遗传算法求解得到任务分配甘特图

绘制基于Dubins 优化的无人机飞行轨迹，如图6 所示。

图6 任务执行航迹图

3.2.2 粒子群优化算法仿真结果

表8 侦察任务分配结果

表9 打击任务分配结果

引入甘特图进行表征，如图7 所示。

图7 粒子群优化算法求解得到任务分配甘特图

根据甘特图所得结果，同样可以得到任务执行航迹图，为简洁篇幅，这里不再展示。

3.2.3 蚁群算法仿真结果

针对蚁群算法，设蚁群规模M=20，最大寻优次数NC_Max=500。将信息素增加强度系数Q，信息素蒸发系数ρ，信息素权重系数α，启发因子权重系数的值分别设定为1、1.7、2、0.57。得到的任务分配结果如表10、表11 所示。

表10 侦察任务分配结果

表11 打击任务分配结果

引入甘特图展示任务执行的时间属性，如图8所示。

图8 蚁群算法求解得到任务分配甘特图

3.3 仿真结果的对比分析

针对无人机集群对敌防空打击协同任务分配，按照前文的任务设定，在Windows10 操作系统上，基于Matlab 环境实现本文算法的仿真实验，PC 机配置为Intel（R）Corel（TM）i7-9750H CPU E5300@2.60 GHz 2.59 GHz，16 G 内存。在相同的目标和无人机参数设置情况下，设定一致的迭代（进化）次数500 次，对于3 类智能算法及其改进形式进行50 次蒙特卡洛仿真，将计算结果对比如下。

3.3.1 蚁群算法改进结果分析

图9 展示了经典蚁群算法和改进蚁群算法的50 次仿真运行时间，可以看出拍卖机制的引入有效降低了算法的运行时间，符合前文中的预期。

图9 蚁群算法运行时间对比图

3.3.2 粒子群优化算法改进结果分析

图10 展示了粒子群优化算法和改进粒子群优化算法在50 次蒙特卡洛仿真过程中的适应度值收敛结果。可以看出通过参数自适应控制和交叉变异操作，粒子群优化算法的寻优能力有所提升，易陷入局部最优解的情况也有所改善。

图10 粒子群优化算法运行结果对比图

3.3.3 算法运行时间

图11 展示了3 种算法在50 次运算中花费的时间。蚁群算法的平均运行时间为69.89 s，粒子群优化算法的平均运行时间为18.31 s，遗传算法的平均运行时间为17.57 s。图11 表明粒子群优化算法和遗传算法的运行时间相近，而蚁群算法所需时间远超于粒子群优化算法和遗传算法。其原因为：对于粒子群和遗传算法来说，其编码形式和进化方式相似，因此，运行时间相近。其简易的编码方式也大大降低了程序的运算量，在耗时上更具优势。而蚁群算法为了实现察打一体任务的时间约束，采用的定时响应机制导致算法需要以固定时间间隔逐步推进，因而耗时较大，尽管它已经采用拍卖步骤减小了求解空间。

图11 算法运行时间对比图

3.3.4 算法收敛速度在50 次蒙特卡洛过程中，分别对每次迭代的适应度值进行平均，并随迭代次数呈现出来，得到图12 所示收敛曲线。由图可知，遗传算法收敛速度缓慢，且收敛程度低。粒子群优化算法和蚁群算法收敛趋势明显，尤其是蚁群算法的收敛结果优于其他算法。其原因是蚁群算法中蚂蚁始终统一从蚁巢出发向目标点前进寻优的方式优于遗传算法和粒子群优化算法中个体在解空间内部“洒点”式的寻优方式。因此，使得蚁群算法在运行前期就存在显著的优势。

图12 算法收敛速度对比图

3.3.5 分配结果优化性对比

图13 展示了3 种算法在50 次仿真运算中的最优收敛结果。结果与收敛速度图一致，蚁群算法寻优结果最好，遗传算法最差。粒子群优化算法由于引入了遗传算法的交叉变异操作，因此，在寻优结果上优于遗传算法。但同样因为前文提及的寻优原理差异导致粒子群优化算法和遗传算法的寻优结果不稳定，最优适应度值震荡幅度大，能够产生出优于蚁群算法的结果，也会产生出劣于蚁群算法的结果。而蚁群算法的运行结果更为稳定。

图13 算法运行结果对比图

4 结论

在无人机集群任务分配与应用中，需要完成对复杂任务的分解与数学描述、目标函数与代价函数的设置、准确的特征描述方法。在此基础上，模型的求解同样至关重要，影响求解结果的最优性、时效性和鲁棒性。

本文以相同的约束条件、优化目标以及任务规划策略，对比分析了3 种群智能算法在任务分配中的性能。从仿真分析结果可以看出，3 种算法均可适应于无人机集群对敌防空打击任务分配，最终得到可行的分配结果。但从优化效益看，蚁群算法的最终收敛结果更好，且寻优结果更稳定，耗时较长，更适用于对任务的事前规划。粒子群优化算法和遗传算法的寻优结果随机性强，耗时较短，能够应对战场突发情况，动态适应性更强。具体分析包括：

1）粒子群优化算法对应的参数较少，通过搜索到的当前最优解共享信息，本质上是一种单项信息共享策略，因此，对问题维数的敏感度不高。且自适应参数控制机制和交叉变异机制的引入对于增大粒子寻优范围和避免陷入局部最优解的起到了一定的效果。

2）蚁群算法是基于正反馈机制的进化算法，但仅能感知局部信息，不能利用全局信息，因此，蚁群算法往往需要更长的搜索时间。不过“蚂蚁”寻优过程中信息素机制使得其更易受到适应度值的影响，因此，收敛效率和最优性强于粒子群优化算法和遗传算法。但信息素机制对于寻优结果的固化使蚁群算法也存在陷入局部最优解的可能性。

3）对于遗传算法而言，仅仅依靠交叉变异和自然淘汰的方式寻优效率过低。算法易受到初始种群在解空间中生成位置的影响。因为交叉互换和自然淘汰仅仅作用于种群内部，对于解空间其他位置的搜索仅依靠碱基变异的方式效率很低且结果不稳定。

本文综合分析了3 类算法在无人机集群任务分配中的特点与优势，这对任务分配求解算法的选择，具有重要参考意义。