1 引言
武器目标分配(weapon target assignment，WTA)问题是战场上作战指挥与控制(C2)[1]自动化的关键问题之一，是军事运筹学领域中典型的带有约束条件的非线性组合优化问题，并且已被证明是NP(non-deterministic polynomial)完全问题[2]。它的基本目标是在武器资源有限的情况下，产生的武器打击分配方案，使得武器对来袭目标的毁伤程度最大化。武器目标分配的最优化是充分发挥武器系统的作战效能,达到对敌最佳毁伤效果的重要因素[3]。
WTA通常被分为两类，一类是静态武器目标分配(static weapon target assignment，SWTA)，另一类是动态武器目标分配(dynamic weapon target assignment，DWTA)[4]。SWTA模型中，已知该问题的所有参数，在一次武器打击过程中将所有武器分配完，而DWTA模型，是武器平台的武器分成几个阶段打击目标，并且一个阶段产生的武器分配方案对目标的毁伤效果，影响下一个阶段的交战分配策略，是一个动态决策的过程[5]。
使用武器打击来袭目标，并获取最佳的打击收益，受武器资源、目标威胁和武器成本等多方面的战场环境约束。DWTA是一个多阶段的分配过程，在整个决策过程中需考虑其不断变化的战场信息，打击目标过程通常采用“观察-射击-观察”的策略[6]，因此DWTA要比SWTA要复杂很多。现有的WTA研究，主要集中在SWTA的研究，在早期，SWTA问题主要使用枚举法，分支定界算法，动态规划等传统算法进行求解[7-8]，伴随着智能算法的兴起和计算机技术的快速发展，出现了进化算法[9]、粒子群算法[10]、模拟退火[11]等优化算法。例如，Jun Wang等[12]将灰狼优化算法与本地搜索算法结合提出HDGWOA算法，验证了所提算法的可行性和大规模WTA问题可扩展性。王力超等[13]提出改进粒子群优化算法，提高求解武器目标分配问题算法的效率和准确性。王平等提出用模拟退火算法对WTA问题进行求解，但在具体的实验中，参数的选择有局限性。相对来说只有较少的关于DWTA问题的研究，Bin Xin等[14]通过设计本地搜索运算符，避免重复产生相同的决策，但其求解质量不高，计算过程过于复杂，Chyh-Ming Lai等[15]为减小算法的复杂性，提出一种简化粒子群优化算法，通过生成初始化方案和交换分配方案简化计算过程，提高了目标分配效率。Tianqing Chang等[16]针对ABC算法在求解DWTA问题中存在收敛速度慢和搜索效率低的问题，提出一种改进ABC算法，改进ABC结合多种启发式因子初始化武器分配方案，提高DWTA收敛速度。但这都仅仅以目标的毁伤程度为目标。
为满足现代化战争需求，本文建立一种以目标生存值最小和武器消耗最小为目标，设计一种多目标的DWTA数学模型，提出一种非支配排序的多目标鲸鱼优化算法(Non-dominated sorting Multi-objective whale optimization algorithm，NSMWOA)用于提高寻优精度。通过3个多目标测试函数验证本文算法的性能，并与NSGA-Ⅱ和MOPSO进行比较，实验结果表明本文所提算法寻优能力明显优于其他算法，在DWTA的数学模型中进行仿真测试，实验结果表明本文所提算法得出PF优于其他算法，所得出的武器分配方案更合理。
2 基本概念
2.1 多目标优化
多目标优化问题指将多个子目标同时寻优，但是这些子目标之间的利益存在相互冲突的问题，很难客观地使各个子目标都达到最优解，所以对于一个多目标优化问题，没有绝对的或者说是唯一的最好解[17]。一个多目标优化问题可以被描述如下所示：
min f(x)=[f1(x),f2(x),…,fn(x)]T
(1)
约束条件：
其中：x=(x1,x2,…,xi,…,xn)，xi表示第i个决策变量，gi(x)≤0表示不等式约束条件，hi(x)≤0表示等式约束条件，D表示n维决策空间，Rm表示基本空间。
任意的2个决策变量xa,xb，如果满足下面2个条件，则称xa支配xa。
1)∀i∈{1,…,n}，都有fi(xa)≤fi(xb)成立。
2)∃i∈{1,…,n}，都有fi(xa)<fi(xb)成立。
所有非支配解的集合称为非支配集或非劣解集，对于不存在其他决策变量能支配该变量，则称该决策变量为非支配解。在n维决策空间中，多个目标函数都找不到其他的解能够优于当前解，则称该解为Pareto最优解。所有的Pareto最优解构成Pareto最优解集，所有Pareto最优解组成的曲面为Pareto前沿。对于单目标优化问题与多目标优化问题相比较，一个很大的区别就是多目标的解并不是唯一的，而是存在一个最优解的集合。
2.2 鲸鱼优化算法
鲸鱼优化算法(whale optimization algorithm,WOA)是2016年由Seyedali Mirjalili教授提出的一种群智能优化算法，通过模仿鲸鱼在海洋中捕捉食物的搜寻过程，来寻找最优解。该算法具有结构简单、自身参数少的特点，在多元函数求解方面比传统粒子群优化算法和遗传算法的速度更快、精度更高[18]。
座头鲸能够识别猎物的位置并将其包围，鲸鱼优化算法的数学模型包括以下3个方面：搜索猎物、包围猎物和泡泡网攻击[19]。
1) 搜索猎物。座头鲸根据彼此间的位置信息随机搜索猎物，数学模型如下：
D1=|C·Xrand(t)-X(t)|
(2)
X(t+1)=Xrand(t)-A·D1
(3)
其中:Xrand(t)表示随机选择的鲸鱼位置，X(t)表示当前鲸鱼的位置信息，D1表示随机选择的鲸鱼与当前鲸鱼之间的距离，t表示当前的迭代次数，A,C表示向量系数，定义如下：
其中：a是从2线性减小到0的收敛因子，r表示0～1之间的随机数。
2) 包围猎物。座头鲸在找到猎物后将其包围，数学模型如下所示：
D2=|C·X*(t)-X(t)|
(4)
X(t+1)=X*(t)-A·D2
(5)
其中：X*(t)表示猎物的位置,D2表示当前鲸鱼距离猎物个体之间的位置距离。
3) 泡泡网攻击。座头鲸在找到猎物后以螺旋方式不断减小包围范围，数学模型如下：
D3=|X*(t)-X(t)|
(6)
X(t+1)=D3·ebl·cos(2πl)+X*(t)
(7)
其中：D3表示当前鲸鱼距离猎物之间的位置距离，b表示螺旋方式的常数，l表示[-1,1]之间的随机数。
3 动态武器目标分配数学模型
DWTA模型与SWTA有很多类似的地方，但DWTA是一个多阶段的武器目标分配问题，前一个阶段的分配结果产生的打击收益会对下一个阶段的分配方案产生影响。简单的说，SWTA在整个防御阶段由武器和目标配对构成，DWTA是由武器、目标和阶段3个进行配对组成，DWTA可以简单看出是多个阶段的SWTA[20]。
DWTA模型取决于许多的因素，例如打击策略、目标和武器的特征以及实战情况。不同的场景可能需要不同的模型，针对DWTA模型的特点，描述DWTA如下所示：假设某次战争，有m种不同类型的武器平台，每种武器平台所拥有的武器数量矩阵为[wi]，有n个打击目标，用[vj]表示目标的价值矩阵，
表示武器i打击目标j的毁伤概率矩阵，
表示在h阶段，第i个武器平台对第j个打击目标的毁伤概率值，xij用于表示第i个武器平台分配给第j个目标的武器数量，考虑到不同阶段目标的毁伤程度的变化，用
表示在h阶段，第i个武器平台对第j个打击目标的打击成本值。建立DWTA数学模型,如下所示：
(8)
(9)
约束条件：
其中，式(8)、式(9)是建立DWTA的2个目标函数，F1和F2分别表示目标生存期望值和武器打击成本，约束1表示在每个阶段中，武器打击目标的能力，通常ni设置为1，表示一个武器在同一阶段对一个目标打击一次，约束2表示武器的弹药量，使用的武器数量不能超出武器所拥有的数量，约束3中xij取值范围1或者0，表示打击或者不打击。
4 多目标鲸鱼优化算法求解DWTA
Mirjalili等在2016年提出的WOA算法是一种模拟座头鲸的觅食行为的群体智能优化算法，其中通过最佳搜索代理来模拟捕猎行为，使得WOA本身具有精英指导能力，但WOA算法本身鲸鱼位置是随机初始化，可能出现种群聚集的情况，并且该算法只能求解单个目标函数问题，对于多目标优化问题无法处理。Logistic映射是一种非常简单却被广泛应用的经典混沌映射,该模型看来似乎很简单,并且是确定性的,但具有极为复杂的动力学行为，Logistic映射序列还具有较好的自相关性和互相关性[21]。因此，本文通过两次logistic映射初始化种群，使得种群分布均匀，对鲸鱼种群间个体进行支配关系和拥挤度进行排序，对传统WOA进行改进，使得改进WOA算法可以解决多目标优化问题的能力。
4.1 编码
为直观反映出解决方案，本文采用十进制编码，设计出一种阶段-武器-目标三者配对的十进制编码方式，在计算中对出现的浮点数进行了取整操作。设第i个鲸鱼个体的位置结构
编码方式如图1所示。
图1 DWTA分配编码
Fig.1 DWTA assignment code
h1表示第一个打击阶段，h2表示第二个打击阶段，Wi表示第i个武器单元，Ti表示打击的目标单位，取值范围为 [1,n]之间的整数。
4.2 种群初始化
群智能优化算法中初始种群位置的选取对算法的收敛速度和寻优精度的影响是至关重要的，一个分布均匀的种群，有利于算法搜索范围更广，提高收敛精度，相反一个随机产生的种群，造成的种群个体将分布不均衡，导致算法搜索速度慢，增加算法陷入局部最优的概率。Logistic映射是经典的混沌映射之一，具有计算量小，易实现的特点，而在WOA算法中，鲸鱼种群间个体都是采用随机初始化的，为增加这种随机性，采用Logistic映射初始化种群，表达式如下所示：
zk+1=uzk(1-zk) zk∈(0,1)
(10)
其中，μ∈[0,4]，当3.569 945≤μ≤4时，Logistic映射才具有混沌性质，但Logistic本身产生的伪随机序列，两端部分的分布情况相比其他部分过于密集，为增加混沌效果，本文采用两次Logistic映射初始化，在第一次Logistic映射产生的鲸鱼位置信息的基础上，在增加一次Logistic映射，使得种群间分布均匀。
4.3 排序
由于智能优化算法在迭代过程中存在部分的随机性，有时产生的子代个体并没有父代个体优秀，另一方面，有些父代个体虽没有其子代个体优秀，但优于其他子代个体，如果只是简单的将子代个体替换父代个体，降低了算法的收敛精度。因此，本文中先将父代与子代个体合并，对合并后的种群根据非支配等级和拥挤度大小进行排序，保留优秀个体。
4.3.1 非支配等级
WOA算法只适合处理目标函数只有一个的问题，而对于拥有多个优化目标的函数问题来说，鲸鱼个体对应的多个目标函数值之间存在相互冲突的问题，由于无法处理各个目标函数值之间的关系，导致WOA无法处理这类问题。为此，将鲸鱼个体间引入一种非支配关系，计算出每个个体的非支配等级，进而比较种群间个体的优劣，非支配等级计算具体流程如下所示：
Step1 遍历鲸鱼种群个体，计算每个个体的被支配个数和支配解的集合；
Step2 找出被支配个数为0的个体，记为第一支配层；
Step3 将第一支配层的个体，从剩余个体中删除，剩余个体的支配个数减一；
Step4 重复Step2-Step3步骤，算出其他层的支配个体，直到鲸鱼种群分层完为止。
4.3.2 拥挤度大小
对于合并后的种群，如果只是筛选非支配等级高的个体，导致种群个体出现聚集的情况，不利于算法的全局寻优，为增加种群的多样性，通过计算种群中距离最近的两个个体之间形成的面积，称为拥挤度。拥挤度越小，表明当前种群间的分布越密集，反之，表明种群之间的多样性越大。在相同的非支配等级下根据每一目标函数值的大小的升序顺序对种群进行排序，其中边界解指定为无穷大的解，鲸鱼个体i的拥挤度等于与i相邻的2个个体i+1和i+1之间形成的矩形边长和，拥挤度具体计算过程如下：
Step1 初始化种群个体拥挤度di=0；
Step2 根据目标函数值，对非支配等价相同的个体进行排序，并记录最大的目标函数值fmax，fmin。
Step3 将非支配等价相同的个体的边界指定为无穷大，其他鲸鱼个体根据di=di+(fk(i+1)-fk(i-1))/(fmax-fmin)计算拥挤度计算；
4.4 算法流程
基于多目标鲸鱼优化算法的DWTA问题的步骤描述如下：
Step1 初始化鲸鱼种群大小NP，最大迭代次数tmax，通过2次Logistic映射生成分布均匀的鲸鱼种群；
Step2 根据式(2)—式(7)产生第一代鲸鱼种群，当前代与新产生的一代进行合并；
Step3 计算合并后所有鲸鱼个体的非支配等级并依据该等级从小到大排序；
Step4 在Step3的顺序上，计算非支配等级相同的个体的拥挤度大小，并对等级相同的个体进行拥挤度从大到小排序；
Step5 根据Step3、Step4的排序结果，筛选最大值作为优秀个体，并记录最优鲸鱼个体位置信息x(t)；
Step6 t=t+1，判断是否达到最大迭代次数，若是，输出武器目标分配方案，否则跳转到Step2。
5 仿真与分析
5.1 多目标函数测试函数
为了验证本文中所提NSMWOA算法的优势，测试3个多目标函数ZDT1，ZTD2，ZTD3，与NSGA-Ⅱ[22]，MOPSO[23]作对比实验。另外，因为原始WOA算法存在一定的缺陷，无法解决多目标问题，所以本文中未加入消融实验。为保证实验的公平性，所有测试都在Windows 10(64位)操作系统，编程软件使用MATLAB R2016a的计算机上设计实现。3种算法的种群大小均为50，迭代次数均为100。为减小算法在测试函数中带来的随机性，独立重复20次实验并记录各个评价指标的平均值，如表2所示。仿真结果如图2—图4所示。
表1 3个多目标测试函数
Table 1 3 multi-objective test functions
函数函数定义约束条件ZTD1F1(x1)=x1F2(x)=g(1-(F1/g))g(x)=1+9∑mi=2xi/(m-1)n=30,xi∈[0,1]ZTD2F1(x1)=x1F2(x)=g(1-(F1/g)2)g(x)=1+9∑mi=2xi/(m-1)n=30,xi∈[0,1]ZTD3F1(x1)=x1F2(x)=g(1-F1/g- (F1/g)sin(10πF1))g(x)=1+9∑mi=2xi/(m-1)n=30,xi∈[0,1]
表2 3个函数评价指标平均值
Table 2 Average value of evaluation indexes of the three functions
函数指标NSGA-ⅡMOPSONSMWOA平均提升/%ZDT1Spacing1.48E-023.78E-021.15E-0245.937IGD3.38E-018.27E-029.15E-0393.114HV3.08E-015.81E-017.15E-0177.603GD5.83E-023.30E-022.57E-0499.390ZDT2Spacing8.18E-032.78E-031.54E-0362.889IGD6.54E-015.52E-012.83E-0152.730HV1.94E-023.23E-027.85E-02223.837GD7.62E-025.63E-034.96E-0599.527ZDT3Spacing1.54E-029.29E-037.57E-0334.679IGD4.13E-013.12E-011.23E-0296.540HV3.08E-015.17E-016.96E-0180.298GD6.67E-021.75E-028.37E-0496.981
从图2—图4中可以看出，本文中所提算法相比文献[19]NSGA-Ⅱ和文献[21]MOPSO算法更加贴近真实的Pareto前沿，表明本文算法寻优精度明显优于其他算法，为减小文章篇幅，只列出3个算法在ZTD1函数上的世代距离(GD)、反世代距离(IGD)、超体积指标(HV)、空间度量指标(Spacing)指标来说明算法的性能，如图5—图8所示。
图2 ZDT1测试曲线
Fig.2 ZDT1 test curve
图3 ZDT2测试曲线
Fig.3 ZDT2 test curve
图4 ZDT3测试曲线
Fig.4 ZDT3 test curve
图5 GD曲线
Fig.5 GD curve
图6 HV曲线
Fig.6 HV curve
图7 IGD曲线
Fig.7 IGD curve
图8 Spacing曲线
Fig.8 Spacing curve
如表2所示，GD值越小，说明算法的收敛性越好，HV值越大，说明算法的综合性越好，IGD值越小，说明算法的综合性越好，Spacing值越小，说明该解集越均匀。从图可以看出NSMWOA算法在收敛性、综合性能明显优于其他算法。平均提升效果均在34%以上，其中，在目标函数ZDT2中的HV指标上更是有223.837%的提升效果。
5.2 NSMWOA在DWTA分配中的应用
假设某次军事行动中，有10种类型的武器平台打击8个来袭目标，每个武器平台所用的武器数量均为2，每个武器在每个阶段只能使用一次，并且武器只能打击一个目标，武器对目标的毁伤概率、目标的价值以及武器每个阶段的使用成本值采用文献[24]方法生成。以目标函数式(8)、式(9)为DWTA模型，种群大小和迭代次数均设置为100，对比算法求解DWTA问题得出的Pareto前沿，如图9所示。
图9 3种算法得出DWTA的Pareto前沿对比
Fig.9 Pareto frontier comparison of DWTA obtained by the three algorithms
为了增加实验的公平性，将独立重复运行20次，取函数F1、函数F2的平均值。为了便于分析，表3展示了3种算法的武器成本F2为13.21时，对应的目标函数F1的值，由于函数F1是毁伤概率的倒数，F1值越小，表明毁伤效果值就越大，由表3中数据可知本文所提算法的在武器成本一样的情况下，得出的武器分配方案使得目标的毁伤效果最大。
表3 3种算法性能对比
Table 3 Performance comparison of the three algorithms
指标NSGA-ⅡMOPSONSMWOA函数F10.20310.404150.08392函数F213.2113.2113.21
6 结论
本文中建立一种多目标优化的动态武器目标分配模型，并提出一种多目标鲸鱼优化算法用于求解，首先通过两次logistic映射对鲸鱼种群进行初始化，使得种群分配均匀，其次合并父代与子代种群，并引入非支配等级和拥挤度大小对种群间个体进行排序，筛选优秀个体。通过与其他算法在3个多目标函数中，独立重复20次实验记录的各个评价指标的平均值表明，本算法的在Spacing、IGD、HV、GD上均有不小于34%的效果提升，收敛较好；在动态武器目标分配模型测试中，在打击成本相同的前提下，所得出的分配方案使得目标的毁伤效果最好，寻优精度更高。
[1] Athans M.Command and control (C2) theory:A challenge to control science[J].IEEE Transactions on Automatic Control,1987,32(04):286-293.
[2] 杨进帅,李进,王毅.武器-目标分配问题研究[J].火力与指挥控制,2019,44(05):6-11.
Yang J S,Li J,Wang Y.Research on weapon-target assignment problem[J].Fire control &command control,2019,44(05):6-11.
[3] Cao W H,Jiao H G,Wei J H.Application of genetic algorithm in weapon target allocation[J].Journal of Sichuan Ordnance Engineering,2008,124(05):119-121.
[4] Mathematics C.Harbin university researchers describe new findings in mathematics (research on dynamic weapon target assignment based on cross-entropy)[J].Journal of Mathematics,2020(12):47-55.
[5] Hu L,Yi G X,Huang C,et al.Research on dynamic weapon target assignment based on cross-entropy[J].Mathematical Problems in Engineering,2020(05):121-128.
[6] 石章松,吴鹏飞,刘志超.基于最小资源损耗的武器目标动态分配[J].海军工程大学学报,2019,31(04):64-71.
Shi Z S,Wu P F,Liu Z C.Weapon target dynamic allocation based on minimum resource loss[J].Journal of naval university of engineering,2019,31(04):64-71.
[7] Ahuja R K,Kumar A,Jha K C,et al.Exact and heuristic algorithms for the weapon-target assignment problem[J].Operations Research,2007,55(06):25-32.
[8] Chen J,Xin B,Peng Z H,et al.Evolutionary decision-makings for the dynamic weapon-target assignment problem[J].Science in China Series F:Information Sciences,2009,52(11):104-112.
[9] Engineering.Researchers at northwestern polytechnic university target engineering(Constrained multi-objective weapon target assignment for area targets by efficient evolutionary algorithm)[J].Journal of Mathematics,2020(07):75-83.
[10] 苏丁为,王毅,周创明.基于直觉模糊熵的改进粒子群算法求解WTA问题[J].计算机科学,2016,43(12):255-259.
Su D W,Wang Y,Zhou C M.Improved particle swarm optimization algorithm for WTA problem based on intuitionistic fuzzy entropy[J].Computer science,2016,43(12):255-259.
[11] 吴平,梁青.武器-目标分配问题的模拟退火算法[J].计算机工程与应用，2006(04):112-119.
Wu P,Liang Q.Simulated annealing algorithm for weapon-target assignment problem[J].Computer Engineering and Applications,2006(04):112-119.
[12] Wang J,Luo P C,Hu X W,et al.A hybrid discrete grey wolf optimizer to solve weapon target assignment problems[J].Discrete Dynamics in Nature and Society,2018(10):46-54.
[13] 王力超,乔勇军,李永胜.基于CE-CAPSO武器目标分配优化算法[J].火力与指挥控制,2020,45(11):82-87.
Wang L C,Qiao Y J,Li Y S.Target allocation optimization algorithm based on CE-CAPSO[J].Fire control &command control,2020,45(11):82-87.
[14] Xin B,Chen J,Zhang J,et al.Efficient decision makings for dynamic weapon-target assignment by virtual permutation and tabu search heuristics.[J].IEEE Trans.Systems,Man,and Cybernetics,Part C,2010,40(06):39-46.
[15] Lai C M,Wu T H.Simplified swarm optimization with initialization scheme for dynamic weapon-target assignment problem[J].Applied Soft Computing Journal,2019,82(01):75-83.
[16] Chang T Q,Kong D P,Hao N,et al.Solving the dynamic weapon target assignment problem by an improved artificial bee colony algorithm with heuristic factor initialization[J].Applied Soft Computing Journal,2018(04):127-135.
[17] Liang J,Qiao K J,Yue C T,et al.A clustering-based differential evolution algorithm for solving multimodal multi-objective optimization problems[J].Swarm and Evolutionary Computation,2021,60(06):81-87.
[18] 刘磊,白克强,但志宏,等.一种全局搜索策略的鲸鱼优化算法[J].小型微型计算机系统,2020,41(09):1820-1825.
Liu L,Bai K Q,Dan Z H,et al.A whale optimization algorithm for global search strategy[J].Journal of small microcomputer systems,2020,41(09):1820-1825.
[19] Qiao W B,Yang Z,Kang Z Y,et al.Short-term natural gas consumption prediction based on volterra adaptive filter and improved whale optimization algorithm[J].Engineering Applications of Artificial Intelligence,2020,87(02):1210-1217.
[20] 钟鸣,吴军,杨任农,等.改进分解进化算法的飞行器动态火力分配[J].空军工程大学学报(自然科学版),2018,19(05):7-11.
Zhong M,Wu J,Yang R N,et al.Improved decomposition evolutionary algorithm for aircraft dynamic fire allocation[J].Journal of air Force Engineering University (Natural Science Edition),2018,19(05):7-11.
[21] 谢建全,谢勍,阳春华，等.基于Logistic映射的加密算法的安全性分析与改进[J].小型微型计算机系统,2010,31(06):1073-1076.
Xie J Q,Xie Q,Yang C H,et al.Security analysis and improvement of encryption algorithm based on logistic mapping[J].Microcomputer Systems,2010,31(06):1073-1076.
[22] Srinivas N,Kalyanmoy D.Muiltiobjective optimization using nondominated sorting in genetic algorithms[J].IEEE Trans Systems,1994,2(03):221-248.
[23] 何羚,舒文江,陈良,等.改进的多目标粒子群优化算法及其在雷达布站中的应用[J].电子科技大学学报,2020,49(06):806-811.
He L,Shu W J,Chen L，et al.Improved multi-objective particle swarm optimization algorithm and its application in radar station[J].Journal of University of Electronic Science and Technology of China,2020,49(06):806-811.
[24] Xin B,Chen J,Peng Z H,et al.An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem.[J].IEEE Trans Systems Man and Cybernetics Part A,2011,41(03):91-97.