基于信息素启发狼群算法的UAV集群火力分配

2021-03-26刘森琪王鸿于宁宇郝礼楷

北京航空航天大学学报 2021年2期

刘森琪，王鸿，于宁宇，郝礼楷

（中国人民解放军66133部队，北京100041）

随着无人机（Unmanned Aerial Vehicle，UAV）技术和人工智能的快速发展，利用大量具有自主作战能力且成本低廉的UAV组成UAV集群突破对手防御体系，对目标实施饱和打击以及对入侵机群进行空中拦截是UAV集群作战的重要手段［1-2］。美军已经开展了多项关于UAV集群研究及试验验证，并将UAV“蜂群”战术进一步向实战推进［3］。UAV集群作战系统在高对抗的战场环境中，如何充分发挥整体协调优势，高效合理进行攻击火力资源规划，实现多个作战单元协同攻击，同时尽可能减少作战单元消耗，使得作战效能最佳，是UAV集群遂行作战任务需要研究解决的重要问题。火力分配问题，即武器-目标分配（Weapon-Target Assignment，WTA）问题，历来是作战指挥辅助决策研究中的核心内容之一，其解空间随着武器数目和目标总数的增加而呈指数级递增，是多参数、多约束的离散非确定性多项式完全问题［4］。求解火力资源分配问题的算法，分为传统算法和智能优化算法。传统算法如文献［5］采用线性规划解决了舰空火力分配问题，其他算法还包括分支定界法、动态规划法等；智能优化算法如文献［6-7］分别采用改进的遗传算法，文献［8-9］采用蚁群算法，文献［10］提出了自适应灰狼优化算法；混合优化策略如文献［11-12］以粒子群算法为基础分别混合模拟退火、引力搜索算法，文献［13］以自适应蚁群优化（ACO）算法为基础结合了遗传算法和粒子群算法特点设计了融合算法，文献［14］采用了动态差分改进的蝙蝠算法等。这些算法都能够获得满意解，但不同程度存在以下缺陷：易早熟、进化速度慢或者算法设计实现困难。在实际允许的时间内求解其最优解是不现实的，只能根据假设的作战原则求其满意解。

狼群算法（Wolf Pack Algorithm，WPA）作为群体智能优化算法［15］，已成功在高维复杂函数优化、背包问题［16-17］、无人机航迹规划［18］等优化问题领域得到了很好的应用，但文献［19-20］指出了WPA还存在寻优精度较低、易陷局部最优、效率不高的弊端，并进行了有效改进。WPA在搜索能力方面还存在上升空间，本文引入了蚁群算法［21-22］中信息素启发规则改进WPA，针对游走行为中人工狼的更新规则，提出使用信息素引导搜索过程，通过不断更新信息素形成狼群对历次捕猎的“记忆”，并应用于狼群更新机制，以改善算法的全局搜索能力。本文将这种新的信息素启发狼群算法（Pheromone Heuristic Wolf Pack Algorithm，PHWPA）应用于UAV集进攻中的火力分配问题，构建了问题的数学模型，进而给出了算法实现过程，并通过仿真实验验证了该方法的可行性及有效性。

1 构建火力分配数学模型

UAV集群在进攻作战中突出系统整体优势，可根据目标情况进行调整，快速适应任务要求，进而协同作战，以较少的消耗达成作战目的。假设UAV集群作战攻击多个目标的具体场景如下：

所有v型UAV对第g个目标的综合杀伤概率Pg为

火力分配是以UAV集群作战系统的整体作战效能最优为目标的，即在保证任务完成的情况下，消耗较少的UAV作战单元，使得攻击后的目标价值收益F最大。本文采用了带有杀伤概率门限的火力分配数学模型［11］。

模型约束条件包括：

1）任务完成约束。每个目标至少分配1架UAV对其进行攻击。

式中：Ag为第g个目标分配的UAV总数。

2）有效杀伤约束。该约束条件要求对每个目标的综合杀伤概率大于预设的杀伤概率门限。

式中：Pdg为第g个目标的预设杀伤门限，可根据具体情况指定。

3）攻击消耗约束。用于攻击的任何一型UAV不能超过其数量限制。

整个模型的特征如下：

1）保证每个目标均能被有效杀伤。通过衡量目标综合杀伤概率是否超过预设杀伤概率门限，判定目标是否被有效杀伤，若低于预设杀伤概率门限，则认为对目标的分配为无效分配。

2）目标价值Wg可以保证高价值目标被优先分配。

3）Ag的大小比pzg对Pg值的影响更大，Ag值越小，综合杀伤概率的平均值就越大，所以模型可以保证使用较少的UAV火力单元。

4）Pg保证目标g在分配UAV火力单元目相同的情况下，即Ag相同，选择Pg大的UAV组合，使综合杀伤概率尽可能大。

上述模型带有非线性约束，采用罚函数法将其转化为一个无约束优化问题来求解。该问题属于非线性整数规划问题，这里采用PHWPA进行解决。

2 算法实现

2.1 狼群算法

狼群组织严密，分工明确，通过各自履行责任进而完成共同协作，保证狼群的生存和发展。WPA模拟狼群分工协作式捕猎行为、猎物分配规则，通过狼群个体对猎物气味、环境信息的探知、人工狼群相互间信息的共享和交互以及人工狼基于自身职责的个体行为决策最终实现了狼群捕猎的全过程，相互关系如图1所示［15］。

图1 狼群的捕猎模型Fig.1 Hunting model of wolf pack

根据狼群特征，WPA采用基于人工狼主体的自下而上的设计方法和基于职责分工的协作搜索路径结构，将人工狼区分为头狼、探狼、猛狼，整个捕猎过程抽象为游走、召唤、围攻3种智能行为以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制，相关含义参见文献［15］。

2.2 求解火力分配问题的W PA

围绕火力分配模型，首先进行了火力分配问题的算法描述，并借鉴文献［17］中运动算子设计方法，重新设计了游走、召唤2个算子改进WPA，以便于问题的求解；进而给出了头狼产生规则、游走行为、召唤行为、围攻行为、狼群更新机制等智能行为的详细描述以及新算子在具体智能行为中的应用。

在解决WTA问题中采用了基于整数的编码方式，分配方案X=（x1，x2，…，xj，…，xm），变量xj为0～n之间的整数，xj=t表示将第j架UAV分配给第t个目标；xj=0表示第j架UAV没有分配给任一目标［6］。用人工狼的位置代表一种候选分配方案，设人工狼位置矢量维度为m（UAV总数量），N为人工狼总数，在N×m的欧式空间中人工狼i的位置X=（xi1，xi2，…，xij，…，xim），xij为第i（i=1，2，…，N）匹人工狼在第j（j=1，2，…，m）维变量空间中所处的位置。人工狼感知到的猎物气味浓度Y=f（X），即目标函数值；人工狼p与人工狼q之间距离dpq为两者位置编码的Manhattan距离：

定义1游走算子Ω（Xi，Ma，r），人工狼i的位置为Xi=（xi1，xi2，…，xij，…，xim），Ma= ｛1，2，…，m｝为编码位集合，可理解为人工狼的可活动范围，r为进行改变的编码位的数目，可理解为人工狼的游走步长。游走算子表示在Ma中随机选择r个编码位形成集合R，将xij（j∈R）改变为第j维变量空间中选取的随机数。

定义2召唤算子Ψ（Xi，Mb，r），人工狼i的位置为Xi=（xi1，xi2，…，xij，…，xim），Mb为人工狼位置Xi和头狼位置Xd不相同编码位的集合且不为空集，集合Mb为

式中：j=1，2，…，m；k的初值为1；null表示空值；xdj表示头狼位置第j维取值。召唤算子Ψ 为在Mb中随机选择r个编码位形成集合R，并将xij值按式（9）进行改变，可理解为人工狼i接收到了头狼传递的部分信息。

WPA的规则和智能行为［15-17］如下：

1）头狼产生规则。算法中具有最优目标函数值的人工狼为头狼，迭代过程中根据目标函数进行头狼更替，头狼不执行游走、召唤、围攻行为。

4）围攻行为。将头狼所在位置Xd视为猎物的位置，参与围攻的人工狼i的位置Xi依式（10）进行位置变换得到新位置：比较人工狼实施围攻行为前后在新旧位置所感知到的猎物气味浓度并进行贪婪决策。

上述智能行为所涉及的游走步长stepa、奔袭步长stepb、围攻步长stepc皆为整数，表示人工狼搜索的精细程度。

5）狼群更新机制。按照狼群更新机制进行群体更新，即淘汰Nnew匹人工狼，Nnew为［N/（2U），N/U］之间的随机整数，U为更新比例因子。算法模拟自然界狼群繁衍方式，新人工狼作为头狼子女继承头狼的优良基因，即头狼的部分编码位，新的人工狼位置Xnew由式（11）计算得到：

式中：Xd为头狼所在位置；Ma=｛1，2，…，m｝；编码位改变的数目L由式（12）计算得到：

2.3 蚁群算法中的信息素启发规则

蚁群算法模拟自然界中蚁群觅食机制，采用了分布式正反馈并行计算机制［21-22］。WTA问题中蚂蚁各自构建其目标分配方案，蚂蚁从第1架UAV开始在所有目标中选择一个目标分配给该UAV；接着对第2架UAV，蚂蚁s在当前运行分配的目标集合中选择一个目标分配给该UAV；依此顺序分配，指导完成全部目标分配［8］。算法中信息素启发的具体规则如下：

1）状态转移规则。蚂蚁s依据伪随机规则选择目标g分配给第u架UAV。

式中：τut（k）为k时第u架UAV与目标t之间的信息素，k即迭代次数；ηut为与问题相关的启发信息，在火力分配问题中，ηut根据数学模型的最优准则给定，本文设为第u架UAV对目标t单次杀伤概率与目标t价值的积；α和β分别为τut和ηut的相对重要性；q为0～1之间均匀分布的随机数；q0（0≤q0≤1）为一个指定常数；G为依据如下随机比例规则从alloweds中选择一个目标。

式中：alloweds为蚂蚁s当前可分配的目标集；ηug为第u架UAV对目标g单次杀伤概率与目标g价值的积；τug（k）为k时第u架UAV与目标g之间的信息素。

2）信息素更新规则。当一次迭代过程结束后，根据当前最优目标函数值Fmax及其对应解Xbest，按式（15）全局更新规则对信息素进行调整：

式中：Δτug为第u架UAV选择目标g相应信息素增量；ρ为信息素挥发因子，0＜ρ＜1。

式中：Q为信息素强度，是一个常数；Fmax（k）为第k次迭代目标函数最优值；Xbest（k）为对应的最优解。

2.4 算法改进策略

为强化对解空间的学习，避免陷入局部最优，提高算法寻优效率，在求解火力分配的WPA基础上提出了PHWPA，针对WPA的游走行为和更新机制做出如下改进：

1）在人工狼搜索过程中，增加信息素引导，可以理解为狼群搜捕猎物的过程形成了一定记忆。在游走行为中，对人工狼位置执行游走算子时，相应编码位由选取随机数改为按照式（13）、式（14）选取新位置。

2）在更新狼群过程中使用信息素，这一过程可以理解为：一方面新的人工狼继承了头狼的优良基因，另一方面采用信息素引导使新的人工狼传承了整个狼群在捕猎中形成的“智慧”，符合自然界种群繁衍进化的特点。在狼群更新机制中，新人工狼按照式（12）产生时，同样其编码位按照式（13）、式（14）计算其改变值。

信息素更新的时机选择在每次迭代时狼群完成围猎之后、更新狼群之前，利用头狼位置信息及其目标函数值按式（15）对信息素进行全局更新，不断更新的信息素代表着狼群在整个捕猎过程中形成的捕猎“智慧”，有利于该智能优化算法对解空间进行更好的学习。

2.5 PHWPA的实现步骤

步骤1初始化。人工狼总数N，初始化每匹人工狼的位置Xi，最大迭代次数kmax，更新比例因子U，最大游走次数Tmax，各步长stepa、stepb、stepc，判定距离dnear，信息素的启发因子α，期望启发因子β，信息素强度Q，信息素挥发因子ρ以及常数q0，信息素初值τinitial，最大值τmax，最小值τmin。

步骤2计算各人工狼的目标函数值。选取头狼，其余人工狼执行游走行为，利用式（13）、式（14）更新，直到某匹人工狼感知的猎物气味浓度（目标函数值）大于头狼感知的气味浓度，或达到最大游走限制次数，转入步骤3。

步骤3除头狼外的所有人工狼执行召唤行为，向发出召唤的头狼进行奔袭。若奔袭过程中，人工狼感知的气味浓度大于头狼所感知的气味浓度，则进行头狼更替，之后人工狼向新的头狼位置奔袭，直到人工狼与头狼的距离d≤dnear，转入步骤4。

步骤4除头狼外的所有人工狼执行围攻行为。将头狼所在位置视为猎物的位置，参与围攻的人工狼位置根据式（10）进行变换并进行贪婪决策。

步骤5全局信息素更新。根据当前头狼位置信息及其所感知的猎物气味浓度，根据式（15）、式（16）对全局信息素进行更新。

步骤6狼群更新。按照狼群更新机制，更新Nnew匹人工狼，新人工狼变化的编码位相应数值按照式（13）、式（14）计算得到。

步骤7判断是否结束。判断是否达到优化精度要求或最大迭代次数kmax，若达到则输出头狼的位置，即所求问题的最优解，否则转步骤2。

综上，可得出基于PHWPA的火力分配流程，如图2所示。

图2 基于PHWPA的火力分配流程Fig.2 WTA flowchart based on PHWPA

3 算法验证及仿真

为验证PHWPA求解火力分配问题的可行性和有效性，进行了仿真实验，算例参考文献［11］。

设UAV集群共有4种型号，每型4架，需要协同攻击10个目标。UAV编号与目标标号如表1所示。

表1 无人机编号与目标编号Table 1 UAV number and target number

UAV集群中作战单元对目标的杀伤概率矩阵为P。

各目标的杀伤概率门限Pdj均设为0.9。各目标的价值矩阵W =［0.6，0.7，0.3，0.5，0.6，0.35，0.65，0.55，0.4，0.75］。

采用本文的PHWPA、WPA、ACO算法、最大最小蚁群（MMAS）算法、模拟退火离散粒子群算法（SA-DPSO）［11］以及仅在更新狼群时使用信息素的PHWPA1、仅在探狼搜索过程使用信息素引导的PHWPA2分别对该火力分配问题进行优化求解。最大迭代次数均为100，涉及WPA的参数：狼群规模Nw=32，更新比例因子Uw=6，游走次数Tmax=10，游走步长stepa=2，奔袭步长stepb=4，围攻步长stepc=1，判定距离dnear=2stepb；涉及ACO算法的参数：蚁群规模Na=32，α=2，β=5，Q=20，ρ=0.4，q0=0.8，信息素初始值τinitial=10，信息素最大值τmax=10，信息素最小值τmin=2。

图3表示采用PHWPA得出的最优方案，该火力分配方案共使用4型13架UAV攻击10个目标，具体UAV与目标对应分配情况如表2所示。表3中各目标杀伤概率均达到杀伤概率门限指标要求，方案表明在保证任务完成的情况下减少了UAV作战单元的消耗，有利于保持UAV集群整体优势。

图3 无人机-目标最优分配方案Fig.3 Optimal UAV-target assignment

表2 最优攻击分配方案Table 2 Optimal UAV-target assignment

表3 各目标杀伤概率Table 3 Kill probability of each target

图4 各算法最优值迭代过程Fig.4 Iterative process of optimal value of each algorithm

图5 PHWPA与其他算法迭代过程比较Fig.5 Comparison of iterative process between PHWPA and other algorithms

由图4、图5可看出，因为初始狼群、蚁群是随机产生的，所以每次迭代会略有不同，为检验PHWPA的收敛性，并证明其有效性。对各算法分别进行了100多次仿真实验，算法收敛趋势基本一致，PHWPA与各算法目标函数值变化情况如图5所示，可以看出，PHWPA能够迅速收敛至全局最优解，并且每次仿真均可以收敛至最优解；WPA收敛至全局最优解时间较长，收敛速度相对较慢，且部分解是局部最优解；基本ACO算法收敛速度慢，且常陷入局部最优解；MMAS算法收敛趋势与WPA 相近，且部分解为局部最优解；SA-DPSO算法能够稳定收敛，但常陷入局部最优解；PHWPA1、PHWPA2收敛趋势与PHWPA较为接近，但实验中这2种算法也存在收敛速度慢、陷入局部最优解的情况，不如PHWPA收敛情况稳定。因此，本文提出的PHWPA能够有效提高对全局最优解的寻优效率。