基于改进QGA 的有/无人机编队多任务联盟生成*

薄 宁，李相民，唐嘉钰，庞 威，代进进

（1.海军航空大学，山东 烟台 264001；2.解放军91213 部队，山东 烟台 264000；3.解放军31102 部队，南京 210000）

0 引言

随着无人机技术的不断发展，无人机与有人机混合编队共同执行任务将成为无人机作战运用的一种新型样式［1］。任务分配是有/无人机编队作战指挥控制过程的关键步骤。受资源或能力所限，复杂任务一般难以由单架飞机独立完成，采用联盟方法成为一种新的解决思路。

联盟方法由Shehory 等人提出［2］，近年来已成为解决多智能体系统（Multi Agent System，MAS）中任务分配问题热点方法之一［3］，并应用于求解军事领域有关问题［6］。文献［8］使用分阶次优联盟快速组建算法（MSOCFA）求解无人机协同搜索联盟组建问题，但其本质上仍是单联盟形成问题。文献［9］使用拍卖算法求解有/无人作战智能体联盟问题，但所建模型中缺少任务完成时限等时间约束。在问题求解方法上，多采用以拍卖算法、合同网等方法为代表的分布式求解方法［7，10］，虽可以克服集中式方法中心节点计算负载大的缺点，但由于需进行多轮信息协同，通信开销较大，对通信传输能力要求较高［10］。

本文采用一种改进的QGA 算法对有/无人机编队多任务联盟生成问题进行集中式求解。根据有/无人机协同执行任务特点，确定问题的约束条件与目标函数，建立优化问题数学模型；从多分组并行演化、观测值修正、动态旋转角调整3 个方面对原始QGA 算法进行改进用于问题求解，提高算法搜索效率，并结合实际算例对设计的方法进行仿真分析。

1 问题描述与要素定义

1.1 问题描述

有/无人机编队指控系统根据编队使命形成了多个任务。由有人机和无人机形成多个任务联盟，对应完成多个不同的作战任务。联盟生成问题的目标是求解确定联盟中各作战智能体的数量，使联盟能力与任务需求可以有效匹配，并按照一定的准则使得效果最优。

1.2 要素定义

为便于问题建模，在借鉴文献［10］的基础上，对有/无人机作战智能体、作战联盟、作战任务等关键要素，作出定义和说明。

2 联盟生成问题建模

作战联盟生成优化问题建模时，优化目标选取需要考虑任务执行收益、付出代价等因素，考虑的约束主要有完成时限、任务时序、任务时窗、飞行时间、执行任务数量等约束。因此，首先给出涉及到的各因素参数的计算方法，再形成联盟生成优化问题模型。定义有/无人机编队任务分配决策矩阵：

2.1 联盟收益

2.1.1 无时窗约束任务收益Cj执行Tj得到的任务收益根据下式计算：

其中，Suc（Tn，Ψ，A）为任务完成判断函数，当任务Tn在分配决策Ψ 下满足完成条件时，取值为1，否则为0。

2.1.2 时窗约束任务收益

对于时间窗约束处理，通常采用将任务收益表示为到达时刻的函数形式［11］，难以准确反映任务执行过程时间对任务效果的影响。本文采用实际执行时间窗与任务需求时间窗重合度来表示时窗任务的完成效果影响概率，即：

2.1.3 总收益

2.2 联盟成本

联盟付出成本是指联盟Cj在执行Tj时，联盟内成员被毁伤的总代价期望值，即：

2.3 目标函数

形成的多任务联盟应使得任务完成收益最大，代价最小，且完成时间尽可能小。因此，定义有/无人机联盟形成问题目标函数如下：

2.4 约束条件

2.4.1 任务资源约束

每个任务的资源能力需求向量的分量应大于形成联盟的能力向量分量，即：

2.4.2 智能体加入联盟数量约束

每个智能体加入的联盟总数不得超过加入联盟上限NMAX_C，即：

2.4.3 联盟指挥控制能力约束

是指任一个联盟中，决策能力值总和应大于等于0，即：

2.4.4 平台飞行时间约束

仅对无人机飞行时间进行限定。每架无人机执行任务总用时应小于剩余可飞时间：

2.4.5 任务组完成时限约束

任意一任务的结束时间应小于等于任务集合T规定的完成时限tend，即：

其中，tend为要求的任务组完成时限。

2.5 联盟生成问题数学模型

综合式（6）、式（8）～式（14），可得有/无人机编队多任务联盟生成数学模型：

3 问题求解

所建问题模型是一个复杂的组合优化问题，传统仿生智能算法用于求解此类问题时存在收敛速度较慢、易陷入局部最优等问题。文献［12］将量子比特和量子旋转门引入到遗传算法中，提出了QGA算法，具有收敛速度快，全局寻优能力强等特点，近年来得到了广泛的研究应用与改进［13］。传统QGA算法存在演化目标单一、量子旋转角取值不灵活等不足。本文采用建立多个独立的初始种群，每个种群分别进行QGA 寻优操作；然后根据问题约束进行观测值修正，提高可行解搜索效率，并建立量子旋转角动态调整机制，改进原算法中固定旋转角的不足，从而改进QGA 算法求解本文问题求解效率。

3.1 染色体编码

3.2 并行量子演化计算

假设分组数量为Nq_team，首先随机生成种群规模为NSEED_MAX的关于Ψ 初始种群W={Ψ1，Ψ2，…，ΨNSEED_MAX}，然后将NSEED_MAX个初始量子染色体平均分配至每个分组中，每个分组单独运行QGA 算法，旋转角确定时依据的目标状态为各分组自身单独的目标状态。每隔一定迭代次数，分组之间通过优秀染色体交换和演化目标互换两种方式实现交互，达到共同加快收敛速度的目的。

3.3 观测值修正

3.4 动态量子旋转角机制

原始QGA 算法中，当前状态、目标状态以及两者观测值的适应度值确定后，θi是固定值，搜索过程不够灵活。采用动态量子旋转角调整机制［16］对文献［12］设计的θi取值查询表中Δθi项进行改进：

其中，Δθ 为固定角，ξ 为［0，1］之间的常系数，n 为当前迭代次数，LoopNum 为最大迭代次数。θi使用改进后的查询表进行取值。在迭代初期，θi绝对值较大，可以进行快速大范围搜索，随着迭代的不断进行，θi绝对值不断变小，同时各染色体不断向最优解靠近，有利于在最优解附近展开精细搜索。

3.5 算法流程

改进的QGA 实现步骤如下：

Step 1：参数初始化。令k=0，随机生成Nq_team个种群规模为Nper_team的关于φ（Ψ）的初始种群。

Step 2：对于每个分组中的每个染色体个体，分别执行多次观测，选择适应度值最高的观测作为状态Ψ（0）。

Step 3：从所有染色体的Ψ（0）中为每个种群选择最高适应度值的观测作为演化目标。

Step 4：判断是否满足退出条件，若满足，则退出；否则转Step 5。

Step 5：k=k+1。

Step 6：判断是否满足染色体和演化目标交换条件，若满足，执行染色体移民和演化目标交换，并进行种群更新。转Step 7。

Step 7：对于每个分组中的每个染色体个体，分别执行一次观测，得到一个状态Ψ（k）。

Step 8：计算所有观测的适应度值。

Step 9：记下最优个体及对应的适应度值。

Step 10：对每个染色体进行量子旋转门操作，得到更新的种群。

Step 11：更新各种群演化目标及全局最优适应度值。转Step 4。

改进的QGA 算法流程如图1 所示。

图1 改进的QGA 算法流程

4 案例仿真与结果分析

采用计算机仿真验证提出的有/无人机编队多任务联盟生成方法的性能。计算机基本配置为：Intel Pentium（R）Dual E2180 2 GHz，2 G 内存，Windows XP操作系统。仿真平台软件及版本为matlab 2014a。

4.1 初始参数设定

假定任务背景为有/无人机编队对敌方防空阵地、机场、指挥所、移动目标等多个地面目标实施攻击。战场区域为200 km×200 km 的矩形区域。无人机待战集结区中心坐标为（20，20），有人机待战机场坐标为（-40，40），单位为km。每个待攻击目标对应一个任务，分别编号为T1～T8。假定任务序列已预先规划，如图2 所示。

图2 任务间的时序关系

各任务属性如表1 所示。

表1 作战任务属性

假设共有8 架有人机、16 架无人机可供分配使用。有人机或无人机挂载有反辐射导弹、对地攻击武器类型1、对地攻击武器类型2、侦察搜索设备类型A、侦察搜索设备类型B、目标指示设备等类型载荷，载荷类型分别为r1CA～r6CA。作战智能体属性如下页表2 所示。

4.2 仿真结果与分析

图3 原始QGA 与改进QGA 寻优搜索结果对比

由图3 可以看出，从收敛速度、解质量上，改进的QGA 算法均优于经典QGA 算法。两种方法进行100 次蒙特卡洛仿真后，求解最优值情况统计结果分别如图4、图5 所示，其中最优适应度为0 表示未搜索到可行解。

表2 作战智能体属性

图4 原始QGA 蒙特卡洛仿真结果

图5 改进QGA 蒙特卡洛仿真结果

由图4、图5 对比可以看出，改进后的QGA 算法，从搜索得到最优解适应度最大值、搜索成功次数、最优解均值3 个统计指标上，均优于原始QGA算法。二者关键性能参数具体统计结果对比如表3所示。

表3 原始QGA 与改进QGA 统计结果对比

由表3 可以看出，两者收敛时间均较长，这是由于本文设定的问题初始较为严苛，搜索过程中存在大量的非可行解；并且单次迭代中，任务执行时间一项，计算较为复杂，计算量较大导致。改进QGA算法2 次仿真中未搜索到可行解，说明在条件较为严苛的离散变量规划中，改进的QGA 方法无法保证每次均能搜索到可行解。

改进的QGA 算法求解得出的最优联盟生成结果如表4 所示。

表4 联盟生成问题求解结果

由表4 可以看出，所得结果中，每个联盟均由2～3 个作战智能体构成，联盟成员数量分布均衡。使用的作战智能体数量总计为12 个，可以为其他后续任务保持能力冗余。每个联盟并不要求有人作战智能体和无人作战智能体均加入，如任务T2即由无人机联盟完成。所得结果与实际情况较为一致。

5 结论

1）本文提出的方法可以有效解决有/ 无人机编队任务联盟形成问题，解质量较高，与实际应用较为符合，对其他相近问题的求解也具有一定的参考借鉴意义。

2）由于单次迭代过程中计算内容复杂性特点，算法整体计算时间较长，较适用于使命预先规划阶段相关问题求解。若应用于实时规划阶段中，需在求解时间与解质量上进行折中。

3）该算法在条件较为严格的条件下，无法保证在可接受的求解时间内每次均能搜索到可行解，下步将考虑通过与其他类型搜索算法相结合，进一步改进算法的性能。