反导拦截中的目标分配问题研究

2021-05-12刘韬廖承城

现代计算机 2021年7期

刘韬，廖承城

（四川大学计算机学院，成都610065）

0 引言

拦截分导式弹道导弹的目标分配问题，本质上是一类多约束优化问题，也是一类武器-目标分配（Weapon-Target Assignment，WTA）问题。分导式弹道导弹再入大气层，完成弹头分离后，将形成多个独立的威胁目标。如何通过多枚拦截导弹拦截这些目标，WTA 问题是多导弹协同拦截中的重要部分。在任务过程中，针对我方多个装备同类型武器的作战单元与多个来袭威胁目标，如何对我方具有相同杀伤力的武器进行快速合理地分配，形成反应速度最快、拦截效率最大的反导拦截方案，将至关重要。

当前，关于WTA 的研究比较多，具体的目标分配方法包括：基于贪婪算法和枚举求最优解的目标分配方法[1]、基于匈牙利算法求解目标分配问题的方法[2]、基于改进遗传算法来求解目标分配的方法[3]、基于免疫蚁群算法求解目标分配的方法[4]、基于模糊多目标规划的目标分配方法[5]、基于改进粒子群算法的目标分配方法[6]。

本文主要根据现有研究成果，结合反导拦截作战特点，提出一种基于改进遗传算法的任务分配方案，以提高任务整体效能。

1 问题描述

本文主要讨论反导拦截过程中的拦截弹目标分配问题。具体问题可描述为，分导式弹道导弹再入大气层，完成弹头分导后，形成多个独立的威胁目标，向我方重要目标飞去，我方多个反导单元准备发射多枚拦截弹对来袭目标进行拦截。关于如何将多枚拦截弹分配给多个目标就是本文讨论的重点，而评判目标分配问题的标准就是发射的拦截弹能够最快且同时到达目标。

2 任务分配模型

2.1 弹头目标假设

本文主要讨论多枚拦截弹的目标分配问题，侧重于研究优化问题，因此，我们对目标的界定可以相对简化，认为所有目标均为一致的，存在差异的只是当前所处的位置。

2.2 拦截弹假设

对于拦截导弹，影响其拦截效率的因素较多，型号、速度、距离、角度等都有影响。考虑到本文的实际，对拦截弹也进行简化处理。假设所有拦截导弹的型号一致，分别部署在不同的火力单元。所以，对拦截导弹来说，唯一的区别在于其所处的火力单位到目标的距离，进而影响其到达目标的时间。

2.3 模型建立

假设有n 个来袭弹道导弹目标T1,T2,…,Tn，已再入大气层向我方区域飞来。在本区域配备有m 个导弹拦截火力单元W1,W2,…,Wm，其中，每个火力单元标配拦截导弹k 枚。为了充分发挥拦截武器性能，本文根据拦截目标的特点，对目标分配问题考虑以下约束条件：

（1）对所有的来袭目标都要分配一枚拦截导弹进行拦截；

（2）每一枚拦截导弹只能拦截一个来袭目标；

（3）单个火力单元中的导弹数量k 要小于来袭目标数量，全部火力单元中的导弹数量k·m 要大于来袭目标数量；

（4）为了避免来袭目标察觉拦截后，进行主动变轨，增加拦截难度，要求所有拦截导弹同时命中来袭目标；

（5）在实现上述约束条件的基础上，要求以最快的时间完成导弹目标拦截。

令火力单元到弹道导弹的距离为smn，矩阵表示为：

令火力单元是否拦截弹道导弹的决策变量xmn为：

则目标分配的决策矩阵为：

受限于每个火力单元的导弹数量，约束条件：

确定适应度函数时，要充分考虑目标分配问题的限制条件，在本文中，就是所有拦截弹最快且同时拦截目标。为了同时到达目标，在不改变导弹飞行参数的情况下，我们以最晚到达的导弹为准，前面的导弹依次晚于某个时点发射即可。故适应度函数的选择就是在每个可行解中选出最晚到达的目标时间，并与其他解进行比较，确定最优解。故适应度函数可表示为：

3 改进遗传算法设计

3.1 基因编码设计

染色体是由基因组成的串，一个染色体就是一次选择结果，也就是一个目标分配的决策矩阵。考虑到本文染色体的特殊性，在进行编码前可以将问题换一个表述方式，即拦截第i 个目标的拦截弹来自第j 个火力单元。当火力单元数量不多（m ＜10）时，可以比较方便地采用十进制的方式对染色体进行编码，将染色体表示为[ ]a1,a2,…,ai,…,an，代表对n 个来袭目标依次分配的结果，其中ai表示拦截第i 个目标的拦截弹来自火力单元ai。此外，当m ＞10，使用2n 个十进制数组成的基因串表示即可。

关于将染色体再转换为决策矩阵的问题，即解码过程比较简单，以ai为例，只需要将初始矩阵的第ai行i 列的元素设为1，以此类推，将n 个矩阵元素设为1后，剩下的矩阵元素设为0，即可。

在编码过程中，要注意约束条件的影响，即每个火力单元的拦截弹数量k，即每个火力单元对应数字在一个基因串中的出现次数不能超过k 次。

3.2 初始种群的选取及适应度计算

在生成初始种群时，一方面以目标到火力单元的距离属性作为启发式信息，例如，若某一火力单元到目标的距离较之其他火力单元明显小一些，则优先考虑选择该火力单元。通过这种启发式的方式可以产生一部分初始种群，这部分种群的适应度较好。另一方面，还需要保持初始种群的多样性，本文考虑通过Tent 映射再生成一部分种群[7]。结合这两种方式生成的初始种群将同时具有多样性和高适应性，这将有利于后续算法的收敛，提高运算效率。

Tent 映射产生混沌序列的表达式是：

式中，z(t)∈[0 ,1] 。运算时，在[0 ,1] 的区间内生成1个的随机数，按照（6）式进行混沌变换，依次循环，直达在[0 ,1] 的区间内生成n 个混沌变量。再将混沌变量映射到变量空间，即乘以m 后，向上取整，完成一个染色体的生成，重复数次完成另一部分初始种群的生成。

由于每个火力单元对应的数字出现频率不能超过k，故需要采用计数器的方式，在生成初始种群过程中进行控制，对不满足条件的基因重新生成。

生成初始种群后，按照3.1 小节中所述的方法将染色体转化为决策矩阵的形式，并依照式（5）的适应度计算方法，计算初始种群个体的适应度。

3.3 选择操作

轮盘赌选择算法作为选择操作的常用方法，优势明显，有利于适应度高的个体被选中。但在个体适应度很相近时，存在缺陷，有导致种群进化停滞的可能。本文结合实际问题，对选择操作进行了改进，首先将种群个体按照适应度的大小进行排序[8]，借鉴精英保留原则的思想，将适应度最高的个体直接复制到子代中。在选择过程中，直接选择适应度位于优势位置前1/3 的个体，再对剩余需求在种群中进行随机选择。具体方法是：随机抽取两个个体，将其适应度进行比较，将适应度较高者选择出来，再重复抽取两个个体进行比较，直至完成选择量要求为止。这种选择方式将有助于提高选出种群的适应度，在选择出适应度较高个体的同时，兼顾种群的多样性，提高遗传算法的效率和实用性。

3.4 交叉和变异操作

交叉操作是基因进化的基础，进行基因重组，生成相对父代波动较大的基因，故交叉概率pc主要控制种群新群体产生的速度。若pc取值太大，会破坏个体的优良遗传特征；若pc取值太小，可能导致最优解出现过早的收敛。变异操作是基因进化的补充，是保持遗传多样性的重要途径，是对交叉过程可能丢失的某种遗传基因进行修复和补充，可有效避免遗传算法过快收敛到局部最优解[9]。变异概率pm主要控制基因扰动，若pm取值过大，会使算法变成随机搜索算法；若pm取值过小，可避免某种单个基因的丢失。

本文引入一种改进的自适应调节思想，使得交叉概率pc和遗传概率pm，能够根据进化进度调整大小[10]。目的是使得交叉概率pc在遗传算法初期较大，后期变得较小；变异概率pm在遗传算法初期较小，后期变得较大。概率pc和pm表达式为：

式中，pc1和pm1分别是交叉概率和变异概率的初始值，i 是当前进化代数，n 是最高进化次数，count 是累积最优解不改变的次数。当count 为0 的时候，pc为pc1，pm为pm1/2。交叉概率pc大，变异概率pm小。当count 变大时，交叉概率pc小，变异概率pm大。

交叉操作，本文根据交叉概率pc，选取两个父代个体x=( x1,x2,…xm)∈[ L,U ]，y=( y1,y2,…yn)∈[ L,U ]，进行两点交叉，交叉点为i1和i2，交叉后的两个子代分别为：

其中：

式中，[ L,U ]={(x1,x2,…,xm)||li≪xi≪ui,i=1,2,…,

表示可行解空间，a 和b 是[0,1]区间的随机数。完成交叉操作后判断是否满足约束条件，如不满足，则恢复到交叉前的数据，重新进行交叉操作，直到满足条件为止。采用这种混合交叉算子的交叉方式获得子代个体，可在进化前期，加快收敛速度。

变异操作，本文根据交叉概率pm，对交叉后的子代，随机选择某一位，改变其数值，并判断是否满足约束条件，如不满足，则再次变换数值，产生一个新个体。

3.5 算法描述

Step1 设置初始Gen、Pc1、Pm1。

Step2 根据启发信息及Tent 映射生成初始种群。

Step3 计算种群适应度值，并按适应度值大小进行排序。

Step4 执行精英保留操作，根据适应度值，进行选择操作。

Step5 更新交叉概率Pc、变异概率Pm的值

Step6 根据概率Pc、Pm，进行交叉操作、变异操作，产生新的种群。

Step7 判断是否满足终止条件，若满足，输出最优解；不满足，则Gen=Gen+1，跳转至Step3 继续执行。

4 仿真实验

本文使用MATLAB 工具进行仿真实验，实验数据为8 个来袭分导式弹头目标，5 个拦截火力单元，每个火力单元标配拦截导弹3 枚，各火力单元到各导弹的距离如表1 所示。

表1 火力单元到目标的距离

对遗传算法参数进行设定，初始种群数量为40，最大进化代数为100，交叉概率初始值为0.7，变异概率初始值为0.1。根据设定条件，分别采用标准遗传算法和改进遗传算法进行迭代仿真实验。其实验结果，以遗传代数为横轴，平均适应度值为纵轴，通过MTALAB软件生成坐标图直观地表现出来。如图1 所示，改进遗传算法的计算结果更接近最优值，且收敛性好，能够较好地解决反导拦截中的目标分配问题。