改进遗传算法的地对空防御武器系统多目标优化

宫 华，张 勇，许 可，刘大龙

(1.沈阳理工大学， 沈阳 110159； 2.光电信息控制和安全技术重点实验室， 天津 300308)

1 引言

军事防御是依托我方武器装备对来袭目标进行拦截打击，以保护我方阵地，主要包括地对空防御、舰艇防御、末端防御等[1]。地对空防御指我方防御阵地遭到空中来袭目标攻击时，战场指挥员针对空中来袭目标的威胁度、种类和武器攻击范围等信息，合理地分配防空武器以实现有效防御。防空武器包括光电干扰等软杀伤武器和导弹等硬攻击武器。地对空防御优化决策是对防御阵地中的武器分配方案进行优化，以实现最佳作战效能，对指挥辅助决策系统具有重大作用。

地对空防御决策模型分为单目标优化模型和多目标优化模型。地对空防御决策单目标优化模型的优化目标主要考虑敌方毁伤概率[2-7]、敌方存留总价值[8-9]、我方资产存留价值[10]、总体作战效率[11-12]等。优化模型主要通过传统优化算法和智能优化算法进行求解。传统优化算法包括可行方向法等[5]，智能优化算法包括人工免疫算法[3]、遗传算法[4，6]、贪婪蚁群算法[8]等。相对于传统优化算法而言，智能优化算法具有收敛速度快、结果精度高等优点。

地对空防御多目标优化模型一般将毁伤概率最大与武器消耗最小、敌人剩余威胁度最小、毁伤目标数量最大等综合考虑建立模型[13-17]。通过蚁群优化算法[16]、帕累托思维化算法[17]等对模型进行求解。Zhao Yang等[18]以敌人剩余威胁度最小和对敌毁伤概率最大为目标建立武器分配模型，提出了一种改进的混合遗传算法求解模型。Fu Guangyuan等[19]以毁伤概率最大和武器消耗最小为目标建立武器分配模型，提出了一种基于多种群协同进化的多目标粒子群优化算法求解模型。李天龙和张军超[20]以目标毁伤价值最大和武器损耗最小为目标建立机载空地多目标武器分配模型，设计了自适应遗传粒子群算法进行求解。贺小亮和毕义明[21]以空中编队对地攻击的毁伤概率最大和费用最小为目标建立模型，提出了模拟退火混合遗传算法进行求解。可以看出，虽然有较多学者对地对空防御问题展开研究，但是很少有文献考虑软硬武器协同作战建立地对空防御多目标优化模型。在多目标优化模型的处理上，也很少有考虑目标权重随着战场态势变化而变化的。

综上所述，本文考虑软硬武器协同作战和武器能力约束，以空中来袭目标毁伤概率最大和我方武器损耗价值最小为目标，建立地对空防御武器系统多目标优化模型。采用熵权法动态调整目标函数权重，将多目标优化模型转化为单目标优化模型。结合禁忌搜索算法，设计了基于相似度的禁忌遗传算法求解转换后的单目标优化模型。

2 地对空防御多目标优化模型的建立

2.1 问题描述

在地对空防御中，敌方派遣空袭部队袭击我方阵地，我方使用多种武器拦截敌方空袭部队。空中来袭目标是指战机、制导导弹、巡航导弹等多种来袭武器。我方阵地中用来拦截空中来袭目标的软杀伤武器单元包括烟雾弹、诱饵弹等，硬攻击武器单元包括中远程导弹、高射炮等。每种武器单元中武器数量不同。地对空防御决策问题需要根据敌我双方战场态势，给出武器分配方案。

假设：

1) 对于我方阵地中的武器，一个硬攻击武器只能攻打一个来袭目标，一个软杀伤武器只能作用一个来袭目标，即不考虑一个武器能同时作用于多个目标的情形。

2) 每种武器单元中的武器对同一个来袭目标的毁伤概率是相同的。

表1给出了相关参数以及变量符号定义。

表1 符号定义

2.2 多目标优化模型的建立

在地对空防御决策中，针对敌方派遣的空中来袭目标，应在最大化有效打击空中来袭目标的前提下，使损耗的代价尽可能小。因此，本文以空中来袭目标毁伤概率最大和我方武器损耗价值最小为目标建立多目标武器分配优化模型。

(1)

(2)

(3)

(4)

xikj∈{0，1},i=1，…，b；k=1，…，mi；j=1，…，n

(5)

式(1)表示最大化来袭目标毁伤概率；式(2)表示最小化我方武器损耗价值；式(3)表示使用的第i种武器的数量限制；式(4)表示每个武器只能作用于一个来袭目标；式(5)表示决策变量为0～1变量。

由于毁伤概率和武器价值2个目标函数的量纲不一致，对2个目标函数进行0～1的归一化处理。如式(6)所示：

(6)

对于多目标优化问题要使各个目标都达到最优，是一个比较复杂的问题，尤其是本文中的2个优化目标存在相互冲突关系，通常可以通过加权求和将多目标转化为单目标，如式(7)所示：

maxV=μ1V1-μ2V2

(7)

式(7)中μ1和μ2分别为2个目标函数的权重。

3 基于熵权法的多目标权重动态调整

在通过加权求和将多目标优化问题转化为单目标优化问题时，确定权重是其中的难点，通常采用专家经验，或者原则偏差修正系数法[20]。为了克服主观因素的影响，本文采用熵权法[22]确定目标权重，根据武器数量充足与否，设计不同的初始策略生成方式，很好地适应战场态势。根据战场数据实时调整各目标的权重，使权重更加客观准确。基于熵权法的多目标权重动态调整具体步骤如下。

1) 确定策略矩阵。定义来袭目标的毁伤下界β，当我方武器对来袭目标的毁伤概率达到该下界时，认为对该来袭目标实现了有效毁伤，在本文中，定义毁伤下界β=0.8。防御阵地中武器总数为m，即m=m1+…+mb。当n>m时，不可能对所有来袭目标实现有效毁伤，此时认为武器数量不充足；当n≤m时，针对每个来袭目标，以毁伤概率最大优先的贪心策略寻找方案。如果该方案对每个来袭目标满足毁伤下界β，认为武器数量充足。为简化问题，其他情况认为武器数量不充足。

(8)

从满足毁伤下界的策略集中随机选取a-1个策略，T1，…，Ta-1与初始策略T0共同组成包含a个策略的初始策略集T=[T0T1…Ta-1]。当a取值较大时，搜索空间大，虽然可以得到较好的权重但计算时间过长；当a取值较小时，计算时间少但搜索空间小得到的权重较差。

② 当武器数量不足时，认为应该保证毁伤概率尽可能大。在尽可能多地攻击来袭目标的策略集中随机选取a个策略，组成初始策略集T。

(9)

(10)

对于正向目标函数d=1，令：

对于负向目标函数d=2，令：

计算第d个目标函数的差异指数ξd:

ξd=1-ψd

计算第d个目标函数的权重μd：

4 基于相似度的禁忌遗传算法设计

针对转换后的地对空防御单目标优化模型，依据空中来袭目标和武器数量，设计基于相似度的禁忌遗传算法求解。遗传算法[23]的基本思想是优胜劣汰、适者生存。它具有良好的全局和随机搜索能力，能够在解空间中快速求得最优解；但遗传算法的交叉操作无法保证生成的下一代种群中都是性能较好的解。引入禁忌搜索[24]对遗传算法中的交叉算子进行改进，保留适应度值较大的染色体，提高种群平均染色体质量。变异概率的大小是影响算法的关键因素，过小无法保证种群的多样性；过大可能会改变适应度较高个体的基因，不易于种群的进化[25]。采用染色体相似度[4]替代变异概率，当父代染色体差异较小时，可以通过变异增加种群多样性。因此，本文设计了基于相似度的禁忌遗传算法(STGA)对地对空防御优化模型进行求解。

4.1 编码

根据空中来袭目标个数和我方阵地武器个数采用整数编码，编码为

Y=[y1…ymiymi+1…ym1+m2…ym]

(11)

式(11)中：染色体长度为m，与我方武器数量一致；yi为0～n的整数，yi=j表示把第i个武器分配给第j个目标，yi=0表示第i个武器没有分配目标。

假设我方阵地有3个武器，空中来袭目标有2个，则染色体长度为3，若染色体为Y=[2 1 0]表示第1个武器攻打第2个目标，第2个武器攻打第1个目标，第3个武器不攻打任何目标。

4.2 适应度函数

一般情况下可以采用目标函数作为适应度函数，但当种群中染色体的适应度函数值差别不大时，在采用轮盘赌方法选择染色体时，无法保证适应度值大的染色体被很好的选择。采用界限构造法[26]设计适应度函数能使适应度值大的染色体有更大的几率被选择。基于界限构造法的适应度函数如式(12)所示：

F(Yr)=V(Yr)-Cmin

(12)

式(12)中:Yr为第r条染色体，V(Yr)为第r条染色体对应的目标函数值，Cmin为目标函数的最小估计值。此时F(Yr)被选中的概率为：

(13)

式(13)中NIND为染色体种群数目。为了确定Cmin对染色体被选中概率的影响，对式(13)两边同时关于Cmin求导可得：

(14)

由式(14)可知，其分母恒为正值，当染色体Yr的适应度值在染色体平均适应度值之上时，式(14)恒大于0，因此随着Cmin的增大，种群中适应度值在平均适应度值之上的染色体被选中的概率就越大。

此外，还需要保证适应度值为正数，因此Cmin能取的最大值为当代种群中目标函数的最小值，适应度函数如式(15)所示：

(15)

4.3 遗传算子

遗传算子包括选择算子、交叉算子、变异算子。本文的选择算子为轮盘赌选择，按染色体自身适应度值在当代种群中所占的比例进行选择。交叉算子为基于禁忌搜索的两点交叉，变异算子为基于相似度的均匀变异。

4.3.1基于禁忌搜索的两点交叉操作

选择父代种群的前后染色体进行配对，当父代种群个数为奇数时，中间的染色体不进行交叉操作。两点交叉是在染色体中随机选取2个位置，对2个位置中间的基因片段进行交换操作。

在染色体交叉后加入禁忌搜索，对交叉策略进行改进，主要是运用“精英保留”策略：以父代染色体的适应度值构成禁忌表，以平均适应度值为期望水平。如果交叉产生的子代染色体的适应度值大于期望水平，则进入下一代。没有达到期望水平的染色体再查看是否在禁忌表中，不在禁忌表中的染色体进入下一代，否则将被禁忌；下一代中染色体不足的部分由父代中适应度值较大的染色体补足。

假设种群中有7个染色体，分别为Y1、Y2、Y3、Y4、Y5、Y6、Y7，适应度函数值分别为0.82、0.75、0.87、0.88、0.93、0.89、0.81，平均适应度函数值为0.85，则期望水平为0.85，禁忌表为[0.82 0.75 0.87 0.88 0.93 0.89 0.81]。采用两点交叉配对之后，Y4染色体不进行交叉操作，选择的2个父代染色体为Y1和Y7，随机选择2个点：

Y1=[1 5 6 … 7 5 7 3 2 … 4 6]

Y7=[3 5 7 … 6 4 7 2 0 … 1 3]

4.3.2基于相似度的均匀变异操作

利用相似度确定染色体是否进行变异操作，le为染色体的长度，用2个染色体向量之间的汉明距离与染色体长度的比值D(Yh1，Yh2)/le来表示染色体Yh1和Yh2之间的相似度，即用2个向量对应分量相同元素的个数与染色体长度的比值来表示相似度。设置阈值t，当D(Yh1，Yh2)/le≥t时，说明Yh1和Yh2染色体相似程度较大，对染色体Yh2执行变异操作。显然0 ≤t≤ 1，一般取t≥ 0.80。

假设染色体Y3=[3 7 6 0 1 5 3 2 4 6]，Y5=[3 7 3 0 1 5 7 2 4 6]，取t=0.8，计算染色体Y3和Y5的相似度D(Y3，Y5)/le=8/10=0.8=t，则对Y5进行变异。

采用均匀变异，随机选取染色体中待变异的基因，用符合编码范围内的均匀分布的随机数，代替该染色体的基因，例如：

4.4 算法步骤

算法流程图如图1所示，基于相似度的禁忌遗传算法(STGA)步骤如下所示。

步骤1：参数设置：确定种群数量NIND，最大迭代次数MAXGEN，当前迭代次数gen，相似度的阈值t，交叉概率pc，禁忌表的长度JL；

步骤2：初始化种群；

步骤3：计算染色体的适应度值，以染色体的适应度值生成禁忌表，并计算平均适应度值；

步骤4：采用轮盘赌的方式选择NIND-1个待交叉变异的父代染色体，并保存当代最优的染色体；

步骤5：按交叉概率pc进行两点交叉。以父代染色体的平均适应度值为期望水平，以染色体的适应度值为禁忌对象；

步骤6：如果交叉生成的子代染色体的适应度值大于期望水平，则直接加入下一代种群中，否则执行步骤7；

步骤7：查看该染色体是否被禁忌，没有被禁忌的子代染色体加入到下一代种群中；下一代种群中染色体个数不足NIND-1的部分选择适应度最大的染色体进行补足；

步骤8：计算各个染色体之间的相似度确定染色体是否进行变异，当染色体相似度大于等于阈值t时，该染色体进行变异操作；

步骤9：将子代种群和保留的最优染色体组成新的种群；

步骤10：判断是否达到最大迭代次数，若达到最大迭代次数输出最优解，否则gen=gen+1，转到步骤步骤3。

图1 STGA流程框图

5 仿真实例

为了验证算法的有效性，采用Pycharm-Community-2017.3.4编译器，python3.7解释器对算法进行编译。在Intel(R) Core(TM) i3- 4170 CPU@3.70 GHz处理器，内存为8 GB的计算机上进行实验。

设我方防御阵地中有5种武器单元，分别为毫米波(M1)、诱饵弹(M2)、烟雾弹(M3)、防空导弹(M4)、高炮(M5)，其中M1、M2、M3为软攻击武器单元，M4、M5为硬攻击武器单元。采用A、B两组不同数量的防御武器进行测试，防御武器数量以及各个武器的价值参数如表2所示。

表2 防御武器数量及价值参数

设空中来袭目标有导弹和战机两大类，目标总数12个，根据目标类型、速度、航路捷径、电子干扰能力等指标确定来袭目标的威胁度。针对3种不同的战场态势，计算得出相应的空中来袭目标的威胁度Wi=(w1，…，wn)，i=1，2，3；每种武器对各个目标的毁伤概率以及威胁度如表3所示。

表3 空中目标威胁度及毁伤概率

设种群数量NIND=50，禁忌表长度JL=50，为了确定STGA的最大迭代次数、交叉概率pc、相似度阈值t进行对比实验。威胁度选取W1，分别采用两组武器数据进行实验。其中A组武器数量m小于来袭目标个数n，属于武器数量不充足。B组武器数量m大于来袭目标个数n，并且以毁伤概率最大优先的贪心策略找到了染色体Y=[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 0 0 0 0 0 0]，满足每个来袭目标毁伤概率大于毁伤下界，即B组武器数量充足。根据我方2组武器数量确定a=10和a=35。采用基于熵权法的多目标权重动态调整方法计算出A组武器数量和B组武器数量的权重为μ1= 1，μ2= 0和μ1= 0.514，μ2= 0.486。对不同参数组合分别进行10次实验，目标函数取平均值，表4、表5分别为两组实验数据。

表4 STGA参数A组实验数据

表5 STGA参数B组实验数据

可以看出，在A组和B组数据中最大迭代次数为200，交叉概率pc=0.8，染色体相似度阈值t=0.95时，得到的目标函数值最好。

威胁度选取W1，pc=0.8，t=0.95，最大迭代次数为200，进行实验，两组数据下得到的迭代收敛曲线如图2和图3所示。

图2 A组实验数据迭代过程曲线

图3 B组实验数据迭代过程曲线

图2为A组实验迭代曲线图，可以看出A组实验在150代左右收敛。图3为B组实验迭代曲线图，可以看出B组实验在160代左右收敛。因此A组实验和B组实验都能在200代内达到收敛，与表4和表5中确定的迭代次数一致。

将STGA与遗传算法(GA)和基于相似度的遗传算法(SGA)比较。采用表2和表3的数据及前面确定的参数，在6组不同数据下分别进行10次实验，将每组的平均值和最优值进行比较。表6为3种算法优化结果，图4为种群平均适应度值的迭代过程曲线，图5为目标函数值的迭代过程曲线。

表6 3种算法优化结果

图4 平均目标函数值迭代过程曲线

图5 最优目标函数值迭代过程曲线

可以看出，STGA在威胁度和武器数量规模不同的6组测试中，目标函数最优值、平均值均大于其他2种算法。在威胁度为W2，武器组数为B时，STGA得到的最优目标函数值和平均目标函数值比GA分别高5.2%、7.0%，比SGA分别高3.3%、4.5%。

由图4可以看出STGA整体曲线表现更优，比其他2种算法得到的种群平均适应度值更好，保证种群中染色体基本都有一个较好的染色体适应度值。

图5可以看出GA在115代左右收敛，STGA在160代左右收敛，SGA在190代左右收敛。虽然GA的收敛速度更快，但是STGA能够获得更好的全局最优解。因此，整体来看STGA优于其他2种算法，在收敛速度和寻求最优值方面都具有优势。

将基于熵权法的多目标权重动态调整方法与原则偏差修正系数法进行比较。原则偏差修正系数法中取δ=0.95，相当于μ2=0.487，其中μ1=0.513。采用表2和表3的数据及前面实验确定的算法参数，在6组不同参数组合下分别进行10次实验，将每组的毁伤概率、总价值和目标函数值进行比较。表7为2种方法求解的优化结果。

从表7中可以看出：本文提出的基于熵权法的多目标权重动态调整方法，在威胁度和武器数量规模不同的6组数据下得到的毁伤概率和目标函数值都优于原则偏差修正系数法。当威胁度取W2，在B组数据下，基于熵权法的多目标权重动态调整方法得到的目标函数值比原则偏差修正系数法得到的目标函数值高3.6%。在A组数据下原则偏差修正系数法得到的目标函数值都小于0.1，并且得到的价值较小，这是因为原则偏差修正系数法得到的权重μ1=0.513，μ2=0.487只适用在我方阵地武器充足的情况下，本文提出的算法能够根据战场态势调节权重，在我方阵地武器充足或不充足的情况下都能够得到较好的方案。

表7 2种方法的优化结果

图6为毁伤概率值迭代过程曲线，图7为武器损耗总价值迭代过程曲线。

图6 毁伤概率迭代过程曲线

图7 武器消耗总价值迭代过程曲线

图6和图7中可以看出，与原则偏差系数法相比，基于熵权法的多目标权重动态调整方法在得到较大毁伤概率的同时得到较小的武器损耗总价值。

6 结论

针对地对空防御多目标武器分配模型，设计了基于熵权法的多目标权重动态调整方法，将多目标模型转化为单目标模型，根据战场态势动态调整权重，使权重更加客观。提出了STGA求解转化后的单目标武器分配模型，通过禁忌搜索算法提高种群质量；通过相似度提高种群多样性。实验结果表明，基于熵权法的多目标权重动态调整方法与原则偏差系数法相比，在我方阵地武器充足和不充足的情况下都能得到合理的武器分配方案，更符合战场实际情况。STGA与SGA、GA相比较，求得的目标函数值和平均值均较好。下一步的研究中，我们将考虑带有环境因素的动态地对空防御武器分配问题，并设计相应的求解方法。