基于交叉熵-遗传算法的武器目标分配问题研究

马金慧,杨 玉,李存华,戴红伟

(江苏海洋大学计算机工程学院,江苏 连云港 222005)

武器目标分配(weapon target assignment,WTA)问题[1]是作战指挥辅助决策研究的重要问题,是一种N-P完全问题. WTA问题的关键就在于如何将不同损伤能力的武器分配到具有不同攻击态势威胁的来袭目标,以达到来袭目标损伤效果最大的结果.

WTA问题作为非线性整数优化问题中的一种,一直备受各国学者的关注. 虽然不同学者提出了不同求解WTA问题的算法,但在算法的有效性、稳定性方面还有提高的空间,因此研究WTA问题具有重要的理论与实际意义.

一般来说,WTA问题可分为静态武器目标分配(static weapon target assignment,SWTA)问题[2-4]和动态武器目标分配(dynamic weapon target assignment,DWTA)问题[5-7]. 在SWTA中,所有武器同时分配给目标,所有信息都是已知的. 然而在DWTA中,应该考虑许多动态变化,例如,时间窗和武器消耗. 在这种情况下,DWTA问题的求解算法必须具有良好的实时性. 对WTA问题的求解,传统的数值优化算法,如分支定界法、枚举法、梯度下降法等,往往不适合求解较为复杂的WTA问题. 目前主要采用智能优化算法进行求解. 文献[8]提出一种基于遗传算法的一类武器目标分配方法研究,设计的编码方式将有约束的优化问题转化为无约束的优化问题. 文献[9]针对武器目标分配问题设计了一种改进的混合粒子群优化算法,增强了算法前阶段的全局寻优能力和后阶段的收敛能力,使得算法性能有明显改善. 文献[10]提出一种改进遗传算法的求解方法,对遗传操作过程进行改进并融入模拟退火机制,以增强算法对模型的寻优能力. 文献[11]将改进差分进化算法应用在解决武器目标分配问题,增强了算法的全局搜索能力与求解精度. 文献[12]提出统一效率矩阵,创建可适用于所有类型目标分配问题的可适应匈牙利算法来求解WTA问题,验证了其正确性与可行性. 尽管目前对WTA问题求解的算法很多,在寻优精度方面也有了一定的改进,但算法在收敛速度、易陷入局部最优解等方面还不尽如人意,尤其是面对大规模复杂问题,仍有进一步改进的空间.

本文提出了一种交叉熵-遗传算法来求解武器目标分配问题. 首先,对本文解决的武器目标分配问题进行了详细的介绍. 其次,介绍交叉熵算法、遗传算法的相关概念及其流程. 然后,分别针对二维的单目标函数优化问题和WTA问题进行计算对比,计算结果验证了交叉熵-遗传算法的有效性与鲁棒性. 最后,总结了本文的研究成果,并对后续的研究工作进行了展望.

1 WTA问题描述和数学模型

1.1 WTA问题描述

本文以水面舰艇编队联合防空作战为背景,在每座舰艇具备的武器数量有限的情况下,将舰艇防空武器合理与来袭目标进行关联,以实现对空中目标进行拦截并实现毁伤效果最大化. 具体描述如下:假设水面舰艇编队有m座防空装置,每座防空装置分别有μi个(i=1,2,…,m)火力通道,空中来袭的目标数量为n,每个目标的威胁系数为ωj(j=1,2,…,n),其含义是第j个来袭目标对舰艇的威胁值. 武器i对目标j的毁伤概率为pij(i=1,2,…m,j=1,2,…,n),不同的武器对同一个目标的毁伤效果不同,同一个武器对不同的目标毁伤效果也是不同的.xij(i=1,2,…m,j=1,2,…,n)表示第i个防空装置是否拦截目标j.若拦截,xij=1,否则xij=0.

1.2 数学模型

以作战武器对拦截目标毁伤最大化为目标,建立的武器目标分配模型为[13]

(1)

(2)

式中,i=1,2,…m,j=1,2,…,n.目标函数(1)即为本文的适应度函数,约束条件xij∈{0,1}表示每座防空装置i对目标j进行拦截时,防空装置的火力通道数不能超过μi个,约束条件xij∈{0,1}表示决策变量xij的约束条件.

2 交叉熵-遗传算法

2.1 交叉熵算法[14]

交叉熵算法(cross entropy algorithm,CEA)是1997年由Rubinstein等提出的一种针对小概率事件估计的重要度采样方法,该算法充分运用重要度采样技术,通过Kullback-Leibler(K-L)距离来对两个概率分布的差异进行度量并让其最小化.

考虑一般最大化问题,假设χ是一个有限状态集合,S为χ上的实值性能函数,优化目标是找到在有限状态集χ上函数S的最大值以及最大值所对应的状态,因此

(3)

式中,γ*为函数S的最大值,X*是γ*对应的状态,X是统计样本. 将式(3)中的优化问题与式(4)对应的估计问题关联起来:

l(γ)=Pβ(S(X)≥γ)=EβI{S(X)≥γ}.

(4)

式中,γ为接近γ*的值,Pβ是条件{S(X)≥γ}的概率度量,Eβ是对应的期望,I{S(X)≥γ}为指标函数,当满足条件{S(X)≥γ}时,其值为1,否则为0.

对概率l(γ)最直接的估计方法是:生成N个随机样本X1,X2,…,XN,然而当概率l(γ)很小时,则需要很多的样本才能达到对罕见事件概率l(γ)估计的精度,因此采用重要度采样技术来对l(γ)进行估计,即根据一个重要度采样密度函数g(X)来随机产生样本,对l(γ)的无偏估计量为:

(5)

(6)

g*(X)和未知的l(γ)有关,考虑寻找一个参数β,使得g*(X)与f(·,β)之间的K-L距离最小,即:

(7)

将式(6)代入式(7),最终可得到如下最大化问题:

(8)

CE算法同时构造阈值序列{γk,k≥0}和参数序列{βk,k≥0}两个序列,在经过T次迭代求解之后所求得的γT接近γ*,βT对应g*(X)中的参数,在初始化γ0与β0后,传统CEA的迭代求解的过程步骤如下[15]:

步骤1 设在第k(k>0)次迭代中,参数β取值为βk-1,从概率密度函数f(X,βk-1)中随机生成N个样本X1,X2,…,XN,分别计算N个样本的目标函数值S(X),并将其降序排序S(X1)≥S(X2)≥…≥S(XN).

步骤2 更新参数γk. 根据公式γk=S(XθN)来更新γk,其中θ为提前设定的稀薄参数,通常取值在0.01～0.1之间.

步骤3 更新第k+1次迭代过程的参数βk.

传统CEA的优点是能够有效地处理大部分的简单优化问题,且收敛速度较快,其不足之处是当待优化的目标函数较为复杂或者约束函数数目较多时,传统的CEA很可能会出现计算精度不足或陷入局部最优的情况. 因此,本文提出采用混合交叉熵-遗传算法来提高CEA求解武器目标分配问题的性能.

图1 CEGA整体流程图Fig.1 The overall flow chart of CEGA

2.2 遗传算法

遗传算法(genetic algorithm,GA)[16]是由美国的Holland教授于1975年提出的一类随机化搜索方法,是通过借鉴生物界的进化规律演化而来的. 它首先确定实际问题的编码方案,随机产生一个初始种群,然后模拟繁殖机制生成新的种群,再通过预先设定的适应度评价函数评价新种群个体的优劣,依据适者生存,优胜劣汰遗传机制以决定个体是否遗传到下一代,引导进化过程向着最优逼近. 该算法具有内在的隐并行性和较好的全局快速寻优能力,在诸多领域得到应用,但也存在着收敛速度慢的缺陷[17].

2.3 交叉熵-遗传算法

本文提出的交叉熵-遗传算法(cross entropy and genetic algorithm,CEGA),将GA融入CEA寻求精英样本的过程中,CEGA整体流程图如图1所示.

为了解决本文构建的WTA模型,构建一个离散概率分布矩阵M,

(9)

式中,p(i,j),i=1,2,…m,j=1,2,…,n,表示作战单元i分配武器给目标j的概率,当矩阵M中所有元素的取值都为0或1时,则式(9)中的矩阵M即为最终的分配方案解.

离散概率分布矩阵M的初始化,

(10)

(11)

(12)

式中,i=1,2,…m,j=1,2,…,n.

根据离散概率分布矩阵M随机生成N个样本,分别记为X1,X2,…,XN,其中样本表示为Xk=(x1,x2,…,xn).xj表示拦截第j个目标的防空装置号. 在生成N个样本之后,利用GA中的选择、交叉、变异操作,对N个样本进行多次迭代更新,寻找更多优秀的样本,具体过程为:

(1)选择:将N个样本按照适应度值大小降序排序,从中选择适应度值较高的15%的样本复制2份,中间的70%复制1份,剩下的样本直接淘汰.

(2)交叉:采用单点随机定位的交叉运算,根据交叉概率确定N个样本中进行交叉运算的样本个数,从中随机选择两个样本,在样本中随机选择一个交叉点,从交叉点到样本的最后一位编码之间进行交叉运算.

(3)变异:采用单点随机定位的变异运算,根据变异概率确定N个样本中进行变异运算的样本个数,从每个参与变异运算的样本中随机选择一个变异位进行变异运算.

GA迭代之后,得到更新寻优后的N个样本,分别计算这N个样本的适应度值F(X),并将这N个样本根据样本的适应度值降序排序F(X1)≥F(X2)≥…≥F(XN),令H=θN,从N个样本中选择前H个目标函数值较大的初始样本X1,X2,…,XH,确定为最终的H个精英样本,根据H个精英样本更新离散概率分布矩阵M,根据式(8)可得到优化问题(13):

(13)

式中,i=1,2,…m,j=1,2,…,n.

温针灸治疗:患者取得仰卧位的治疗姿势,对穴位进行消毒处理之后,垂直进针足三里、阳陵泉、梁丘和外膝眼、绝骨穴位,之后,点燃清艾条套入上述穴位的针柄上,距离皮肤1寸,待燃尽艾条段后再重复上述步骤1次;进针三阴交(0.5~0.8寸),而阳陵泉、内膝眼和血海进针1.0~1.5寸,待得气之后将其静留针处理[1]。

将式(11)代入式(13)得如下优化问题(14),

(14)

式中,i=1,2,…m,j=1,2,…,n.问题(14)属于凸优化问题,因此可构造拉格朗日函数,

(15)

根据Karush-Kuhn-Tucker(KKT)条件,可推导出

(16)

因此,可得到离散概率分布矩阵M的迭代更新公式

(17)

3 实验与分析

为了验证CEGA算法的有效性和鲁棒性,分别针对带约束的二维的单目标Benchmark问题和WTA问题,采用不同的对比算法进行验证. 本实验的软件环境为MATLAB R2020b,硬件环境为Intel(R)Core(TM)i5-9500 CPU@3.00GHz,8GB内存.

3.1 单目标函数优化问题

针对二维的单目标函数优化问题,本文选取5种不同的带约束的二维单目标优化测试函数[18](5种测试函数均为求最小值且最小值都为0),对比CEGA、CEA、GA 与禁忌搜索算法(SA)、粒子群算法(PSO)、差分进化算法(DEA)这6种算法,比较计算30次所求函数最小值均值和标准差这两个指标上的性能,实验结果如表1 所示. CEGA与CE算法设置相同的均值与方差,样本数为100,θ=0.1,另4种算法的种群规模皆为100,6种算法的收敛条件均为迭代次数达到100. 其中SA、PSO、DEA的实验结果来自PlatEMO3.0[19]平台.

由表1可知,在收敛条件相同时,在5种测试函数上,本文提出的CEGA所求的最小值均值和标准差都更优于另5种算法,因此具有更优的寻优精度和更好的鲁棒性.

表1 单目标优化函数实验结果Table 1 Experimental results of single objective optimization function

3.2 WTA问题

为进一步验证CEGA算法性能,将CEGA针对3种不同规模WTA问题求解,每种算法实验计算200次,CEA与本文提出的CEGA的实验结果性能对比如表2所示.

表2 WTA问题求解结果Table 2 Experimental results of WTA problem

由表2的实验结果可以得知,本文提出的CEGA算法在3种规模下,所求的平均适应度值与最高适应度值都明显高于传统的CEA、GA两种算法所求的结果,而且大大提高了收敛速度,故实验计算时间也相对减少. 本文提出的CEGA算法在寻优能力、收敛性、稳定性上都是优于传统的CEA、GA两种算法的.

为更加清晰对比不同算法收敛过程的差异,图2、图3、图4给出了CEA、GA与CEGA求解3种规模下的收敛过程.

图2 当m=5,n=15时迭代收敛过程Fig.2 Iterative convergence process when m=5,n=15

图3 当m=10,n=25时迭代收敛过程Fig.3 Iterative convergence process when m=10,n=25

图4 当m=22,n=37时迭代收敛过程Fig.4 Iterative convergence process when m=22,n=37

4 结论

为提高求解WTA问题的精度和鲁棒性,本文在一般CEA求解WTA问题的基础上,提出了一种融合GA的CEGA算法来求解WTA问题. 在随机生成样本之后,加入了遗传算法中选择、交叉、变异操作,来提高样本的多样性以及精英样本的质量. 为验证本文提出的CEGA算法求解WTA问题的有效性,分别针对3种不同规模WTA问题,传统CEA、GA与本文提出的改进的CEGA算法进行对比,实验结果验证了本文提出的CEGA算法的有效性. 对比一般CEA,CEGA算法具有寻优精度高、稳定性强、收敛速度较快的优点. 在未来的研究中,将通过样本选择和适当的参数设置,重点关注计算效率和复杂多目标优化问题的应用.