# Research on Dynamic Weapon Target Assignment Based on Cross-Entropy

Authors: Lei Hu; GuoXing Yi; Chao Huang; Yi Nan; ZeYuan Xu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The weapon target assignment (WTA) is a classical problem of defense-related applications which is proved to be a NP-complete problem. In this paper, a practical and available dynamic weapon target assignment (DWTA) formulation is given which incorporates two meaningful and conflicting objectives, that is, minimizing weapon costs and maximizing combat benefits. As we know, heuristic methods have some shortcomings such as slow convergence speed and local optimum in solving the nonlinear integer optimization problem. To this end, a novel DWTA algorithm based on cross-entropy (CE) method is introduced, where the resources requirement condition for targets is taken into consideration. The CE method associates an estimation problem with the DWTA optimization problem, and then, the estimation problem is transformed into a convex optimization problem. The Karush–Kuhn–Tucker conditions are applied to solve the convex optimization problem, and the iteration formulas to find the optimal solution are deducted. Furthermore, in order to verify the performance of CE method in dealing with the DWTA problem, several simulations in different combat scenarios are implemented. The results reveal that, compared with the benchmark heuristic and Monte-Carlo (MC) methods, there are some notable advantages in solving the DWTA problem based on CE method with regard to the solution quality and time consumption.


---

## Body

## 1. Introduction

Weapon target assignment (WTA) problem is the core content in the research of combat command aided decision-making, which can be categorized as a combinatorial optimization problem and nondeterministic polynomial complete problem [1], whose solution space expands exponentially with the increasing of the number of weapons and targets. Generally, WTA problem can be divided into static weapon target assignment (SWTA) problem [2, 3] and dynamic weapon target assignment (DWTA) problem [4–6]. In SWTA, all weapons are assigned to targets simultaneously and all information is known; however, in DWTA, many dynamic changes such as time window and weapon consumption should be considered; in that case, the solving algorithm for DWTA problem must have the good real-time performance. Furthermore, some researchers pay much attention to sensor weapon target assignment problem [7–9], where small and sensitive sensors loaded by weapons play a critical role to enhance the combat effectiveness, and in order to fit the combat scene pertinently, multiobjective optimization problem [10, 11] is researched to depict the combat purpose in different perspectives.Concretely, Kline et al. [2] proposed a nonlinear branch and bound algorithm to solve the SWTA problem which sought to minimize the residual value of each target. Zhou et al. [3] proposed a discrete particle swarm optimization (PSO) algorithm to maximize the ratio of global operation effectiveness to the costs of consumed weapons. Lai and Wu [4] proposed an improved simplified swarm optimization method with two novel schemes to minimize the threat value in the multistage WTA. Chang et al. [5] proposed an artificial bee colony algorithm with heuristic factor initialization to get the minimal expected value of surviving targets for all stages. Mu et al. [7] built a sensor WTA model with the probability of detection and killing, and then multiscale quantum harmonic oscillator algorithm was applied to solve the optimization problem, and Chen et al. [8] used the particle swarm optimization algorithm to solve the sensor WTA problem while Xin et al. [9] proposed a marginal-return-based constructive heuristic method to deal with and solve sensor WTA problem. Juan et al. [12] built a multiobjective WTA formulation and NSGAII algorithm was applied to solve the problem, and Li et al. [10] compared the adaptive NSGAII algorithm and adaptive MOEA/D algorithm and gave a comparison study. Gao et al. [11] proposed the D-NSGA-III-A algorithm with the adaptive operator selection mechanism. Both NSGAII and D-NSGA-III-A are extensions of the GA algorithm.With the development of computer performance, numerous methods are developed to solve the WTA problems, such as branch and bound [2], PSO [3, 8, 13], artificial bee colony algorithm [5], genetic algorithm [10–12], large-scale neighborhood algorithm [14, 15], and ant colony algorithm [16, 17]. Some new methods are also applied to deal with the WTA problem such as simplified swarm optimization [4], multiscale quantum harmonic oscillator algorithm [7], marginal-return-based constructive heuristic [9], and Markov decision model [18]. Some scholars are also interested in hybrid algorithms [19–21]. Although the application of these methods provides a variety of ideas for solving WTA problems, it is necessary to further expand the optimization method for the realistic and dynamic combat scenarios. Rubinstein [22] indicated that it is feasible and effective to utilize CE method to estimate the probability of rare event and solve complicated nonlinear combination optimization problems. As a simple but powerful tool, CE method is available for numerous practical applications, such as combination optimization problems [23], deep learning [24], and multi-UAVs task allocation [25, 26].As an efficient deterministic optimization method, branch and bound method is involved to solve nonlinear optimization problem [2, 25]. Le Thi et al. [25] compared the performance of CE method and branch and bound method in terms of solving the nonlinear UAV task assignment problem. To evaluate the effectiveness of CE method, Huang et al. [26] applied it in various test problems and compared it with the exhaust search method. The comparable research, among CE method and other benchmark heuristic methods, is insufficient; in this paper, in order to verify the performance of solving the DWTA problem based on CE method, two benchmark heuristic algorithms (PSO and GA) and Monte-Carlo algorithm are compared with the CE method.The aim of this paper is to reveal the detail process of applying cross-entropy to solve the discrete nonlinear DWTA problem under the multiple resources requirement condition. The contribution of this paper is as follows:(i)
A novel DWTA formulation with two significant and conflicting objectives is constructed, which minimize the weapon costs and maximize the combat benefits. Multiple resources requirement conditions changeable are taken into consideration which limit the feasibility of weapon in multistage combat. The kill probability is randomly selected between zero and one which is distinct from those models with an assumption that all firepower units have the same kill probability for different types of targets [15]. With these considerations, the DWTA formulation given in this paper is more practical and realistic.(ii)
The idea of estimating rare event probability with CE is extended to the solution of discrete nonlinear DWTA problem. To be specific, the DWTA problem depicted in this paper is transformed into an estimation problem, and then it is subsequently transformed into a convex optimization problem, detailed iteration formulas are deducted in the following text, and then the algorithm of solving DWTA problem based on CE method is acquired.(iii)
24 DWTA problems of different scales are simulated to cover the different combat scenarios; furthermore, the benchmark heuristic and Monte-Carlo methods are implemented to verify the performance of CE method.The rest of the paper is structured as follows: in Section2, a DWTA formulation based on weapon costs and combat benefits under multiple resources requirement condition is presented. Furthermore, in Section 3 we apply CE method to solve the DWTA problem and give the elaborate deduction procedure based on Lagrange multiplier method and KKT conditions. Section 4 employs several combat scenarios to verify the performance of CE method compared with benchmark heuristic and MC methods. Section 5 summarizes the research contents of this paper and prospects the follow-up research work.


## 2. DWTA Formulation

### 2.1. Combat Scenario

The purpose of WTA problem is to get maximal combat benefits by utilizing weapons to intercept targets under certain or uncertain combat environment. In this paper, we present a DWTA formulation based on consumed weapon costs and combat benefits incorporating multiple resources requirement condition, and a typical scenario of the weapons against the targets is shown in Figure1. We assume that there are n targets and m types of weapon, and each target has different combat ability value and resources requirement in the combat scenario; at the same time, the resources contained by each weapon and the inventory quantity of each weapon are taken into consideration. The solution of the DWTA problem is based on the following assumptions.Assumption 1. The kill probability of using the same weapon to intercept different target is different and the kill probability of using different weapon to intercept the same target is different. The value of kill probability is randomly selected.Assumption 2. The weapon satisfied with the resources requirement condition of target can be used to interception task. As depicted in Figure1, weapon 1 can intercept target 1; however, weapon 2, which does not satisfy the resources condition of target 1, is limited to intercept target 1.Assumption 3. Every type of weapon can be launched once simultaneously, so the objective of WTA is to assignm weapons to n targets in every stage, and then the evaluation of the combat result is implemented, which allows us to decide whether to go on the next weapon target assignment. Actually, this DWTA model belongs to shoot-look-shoot variant.Assumption 4. The evaluation process is deterministic as long as the solution of WTA is acquired, which allows us to decide the next procedure according to the cessation conditions. The detail of cessation conditions will be described later.Figure 1
Drawing of DWTA.


### 2.2. Design of DWTA Formulation

After the description of the combat scenario in Figure1, the detailed DWTA formulation will be introduced in this subsection, cost function constituted by consumed weapons and benefit function described by the combat ability value in each combat stage are defined at first, and the DWTA formulation is built based on a tradeoff between cost function and benefit function. Some notations used in this paper are described in Table 1.Table 1
Notation description.
n: number of targets, J is the target set and J=1,…,n, target j (j∈J) represents the j-th targetn + 1: hypothetical target, J˜ is the target set and J˜=J+n+1m: number of weapon types, W is the weapon set and W=1,2,…,m, weapon i (i∈W) represents the i−th type of weaponT: final combat stage, t represents the t stage and t=1,…,TK: number of the resource types, k represents the k-th kind of resource and k=1,…,Kujt: combat ability value of target j at stage tci: unit cost of weapon ivit: inventory quantity of weapon i at stage tXt=xitm×1: decision vector at stage t, xit is the i-th decision variablegxit,j: auxiliary function of decision variable at stage thi,j,t: auxiliary function of combat feasibility at stage tQt=qjktn×K: resources matrix of targets at stage tRt=riktm×K: resource matrix of weapons at stage tΩt=ωijtm×n: kill probability matrix at stage tSCXt: cost of consumed weapons at stage tSBXt: combat ability values of targets at stage tSXt: objective function at stage tα1, α2: weight parametersς∗: expected combat purposeX∗: optimum solution and S∗is the corresponding objective function valueTCE: iteration number of CE method, and TCEt is the iteration number of CE method at stage tD: iteration number of GA and PSO methodNum: population size of GA and PSO methodNMC: sample size of MC methodIn order to describe the cost of consumed weapons clearly,gxit,jis the auxiliary function of decision variable we defined, which depicts whether to assignweapon i to target j at stage t, the specific definition is as follows:(1)gxit,j=1,ifxit=j,0,otherwise,∀i∈W,j∈J,xi∈J.Furthermore, we define the auxiliary function of combat feasibilityhi,j,t which is utilized to decide whether the weapon i could intercept the target j:(2)hi,j,t=1,∀k=1,…,K,s.t.rikt≥qjkt,0,otherwise,∀i∈W,j∈J,t=1,2,…,T,where rikt is the number of resource k contained by weapon i at stage t, qjkt is the number of resource k required by target j at stage t, and both rikt and qjkt are nonnegative integers. Weapon i can be used to intercept target j if and only if the available resource number of the weapon i meets the requirement condition of target j.Consequently, we get the cost function at staget.(3)SCXt=∑j∈J∑i∈Wcigxit,jhi,j,t.After thet stage, the benefit function is equal to the sum of the combat ability value of all targets.(4)SBXt=∑j∈Jujt∏i∈W1−ωijtgxit,jhi,j,t.Hence, we have built the cost function and the benefit function, weight strategy is adopted to balance the two conflicting objectives, and the DWTA objective function at staget is acquired as follows:(5)SXt=α1SCXt+α2SBXt=α1∑j∈J∑i∈Wcigxit,jhi,j,t+α2∑j∈Jujt∏i∈W1−ωijtgxit,jhi,j,t,where α1+α2=1, α1 and α2 are the weight parameters. Let α1=0, which means destroying targets regardless of cost, and let α2=0, which means destroying targets at the lowest cost.The constraint conditions of the WTA problem are depicted in the following formulas:(6)∑j∈Jgxit,j=1,∀i∈W,t=1,…,T,(7)∑j∈Jgxit,j≤vit,∀i∈W,t=1,…,T,(8)xit∈Jandxitis a positive integer.Constraint (6) depicts that each weapon must be assigned to one of the targets at stage t. Constraint (7) depicts that it is necessary to stockpile enough weapons to complete weapon target assignment. Constraint (8) limits the range of xit; that is, xit is a positive integer and belongs to the set J. There are two noticeable situations as follows:Situation 1.
A certain type of weapon is exhausted.Situation 2.
A certain type of weapon does not satisfy the resource requirement condition of any target.
In these two conditions which mean that this weapon cannot intercept any target, in order to deal with the two situations, we set up a new hypothetical target named targetn + 1 and get a new target set J˜=J+n+1, we can assign this type of weapon to target n + 1, and we set gxit,j=0,∀xit=n+1,i∈W. It is an excellent technique to deal with these two situations. Consequently, we can summarize that the DWTA formulation at stage t(9)minXtSXt=α1SCXt+α2SBXt=α1∑j∈J˜∑i∈Wcigxit,jhi,j,t+α2∑j∈J˜ujt∏i∈W1−ωijtgxit,jhi,j,t,∑j∈J˜gxit,j=1,∀i∈W,∑j∈J˜gxit,j≤vit,∀i∈W,xit∈J˜andxitis a positive integer.


## 2.1. Combat Scenario

The purpose of WTA problem is to get maximal combat benefits by utilizing weapons to intercept targets under certain or uncertain combat environment. In this paper, we present a DWTA formulation based on consumed weapon costs and combat benefits incorporating multiple resources requirement condition, and a typical scenario of the weapons against the targets is shown in Figure1. We assume that there are n targets and m types of weapon, and each target has different combat ability value and resources requirement in the combat scenario; at the same time, the resources contained by each weapon and the inventory quantity of each weapon are taken into consideration. The solution of the DWTA problem is based on the following assumptions.Assumption 1. The kill probability of using the same weapon to intercept different target is different and the kill probability of using different weapon to intercept the same target is different. The value of kill probability is randomly selected.Assumption 2. The weapon satisfied with the resources requirement condition of target can be used to interception task. As depicted in Figure1, weapon 1 can intercept target 1; however, weapon 2, which does not satisfy the resources condition of target 1, is limited to intercept target 1.Assumption 3. Every type of weapon can be launched once simultaneously, so the objective of WTA is to assignm weapons to n targets in every stage, and then the evaluation of the combat result is implemented, which allows us to decide whether to go on the next weapon target assignment. Actually, this DWTA model belongs to shoot-look-shoot variant.Assumption 4. The evaluation process is deterministic as long as the solution of WTA is acquired, which allows us to decide the next procedure according to the cessation conditions. The detail of cessation conditions will be described later.Figure 1
Drawing of DWTA.


## 2.2. Design of DWTA Formulation

After the description of the combat scenario in Figure1, the detailed DWTA formulation will be introduced in this subsection, cost function constituted by consumed weapons and benefit function described by the combat ability value in each combat stage are defined at first, and the DWTA formulation is built based on a tradeoff between cost function and benefit function. Some notations used in this paper are described in Table 1.Table 1
Notation description.
n: number of targets, J is the target set and J=1,…,n, target j (j∈J) represents the j-th targetn + 1: hypothetical target, J˜ is the target set and J˜=J+n+1m: number of weapon types, W is the weapon set and W=1,2,…,m, weapon i (i∈W) represents the i−th type of weaponT: final combat stage, t represents the t stage and t=1,…,TK: number of the resource types, k represents the k-th kind of resource and k=1,…,Kujt: combat ability value of target j at stage tci: unit cost of weapon ivit: inventory quantity of weapon i at stage tXt=xitm×1: decision vector at stage t, xit is the i-th decision variablegxit,j: auxiliary function of decision variable at stage thi,j,t: auxiliary function of combat feasibility at stage tQt=qjktn×K: resources matrix of targets at stage tRt=riktm×K: resource matrix of weapons at stage tΩt=ωijtm×n: kill probability matrix at stage tSCXt: cost of consumed weapons at stage tSBXt: combat ability values of targets at stage tSXt: objective function at stage tα1, α2: weight parametersς∗: expected combat purposeX∗: optimum solution and S∗is the corresponding objective function valueTCE: iteration number of CE method, and TCEt is the iteration number of CE method at stage tD: iteration number of GA and PSO methodNum: population size of GA and PSO methodNMC: sample size of MC methodIn order to describe the cost of consumed weapons clearly,gxit,jis the auxiliary function of decision variable we defined, which depicts whether to assignweapon i to target j at stage t, the specific definition is as follows:(1)gxit,j=1,ifxit=j,0,otherwise,∀i∈W,j∈J,xi∈J.Furthermore, we define the auxiliary function of combat feasibilityhi,j,t which is utilized to decide whether the weapon i could intercept the target j:(2)hi,j,t=1,∀k=1,…,K,s.t.rikt≥qjkt,0,otherwise,∀i∈W,j∈J,t=1,2,…,T,where rikt is the number of resource k contained by weapon i at stage t, qjkt is the number of resource k required by target j at stage t, and both rikt and qjkt are nonnegative integers. Weapon i can be used to intercept target j if and only if the available resource number of the weapon i meets the requirement condition of target j.Consequently, we get the cost function at staget.(3)SCXt=∑j∈J∑i∈Wcigxit,jhi,j,t.After thet stage, the benefit function is equal to the sum of the combat ability value of all targets.(4)SBXt=∑j∈Jujt∏i∈W1−ωijtgxit,jhi,j,t.Hence, we have built the cost function and the benefit function, weight strategy is adopted to balance the two conflicting objectives, and the DWTA objective function at staget is acquired as follows:(5)SXt=α1SCXt+α2SBXt=α1∑j∈J∑i∈Wcigxit,jhi,j,t+α2∑j∈Jujt∏i∈W1−ωijtgxit,jhi,j,t,where α1+α2=1, α1 and α2 are the weight parameters. Let α1=0, which means destroying targets regardless of cost, and let α2=0, which means destroying targets at the lowest cost.The constraint conditions of the WTA problem are depicted in the following formulas:(6)∑j∈Jgxit,j=1,∀i∈W,t=1,…,T,(7)∑j∈Jgxit,j≤vit,∀i∈W,t=1,…,T,(8)xit∈Jandxitis a positive integer.Constraint (6) depicts that each weapon must be assigned to one of the targets at stage t. Constraint (7) depicts that it is necessary to stockpile enough weapons to complete weapon target assignment. Constraint (8) limits the range of xit; that is, xit is a positive integer and belongs to the set J. There are two noticeable situations as follows:Situation 1.
A certain type of weapon is exhausted.Situation 2.
A certain type of weapon does not satisfy the resource requirement condition of any target.
In these two conditions which mean that this weapon cannot intercept any target, in order to deal with the two situations, we set up a new hypothetical target named targetn + 1 and get a new target set J˜=J+n+1, we can assign this type of weapon to target n + 1, and we set gxit,j=0,∀xit=n+1,i∈W. It is an excellent technique to deal with these two situations. Consequently, we can summarize that the DWTA formulation at stage t(9)minXtSXt=α1SCXt+α2SBXt=α1∑j∈J˜∑i∈Wcigxit,jhi,j,t+α2∑j∈J˜ujt∏i∈W1−ωijtgxit,jhi,j,t,∑j∈J˜gxit,j=1,∀i∈W,∑j∈J˜gxit,j≤vit,∀i∈W,xit∈J˜andxitis a positive integer.


## 3. Algorithm Design Based on Cross-Entropy

### 3.1. The Cross-Entropy Method

Originally, CE method is based on importance sampling and used to estimate the probability of rare event, and Rubinstein [22] put forward an optimization method based on the idea of CE, which could solve the discrete multiextreme value problems. Consider the following general minimization problem: let S be a real-valued function on χ, where χ is a finite set of states. Our goal is to find the minimum of S over χ, which is denoted as γ∗, and X∗ is the corresponding state.(10)SX∗=γ∗=minX∈χSX.The basic idea of CE method applied to formula (10) is to associate an estimation problem with the optimization problem. In that case, the optimization problem is converted into an estimation problem with probability density function (pdf) f⋅,β.(11)l=ΡβSX≤γ=ΕβISX≤γ,where γ is a value close to γ∗, Ρβ is the probability measure, Εβ denotes the corresponding expectation operator, and ISX≤γ is the indicator function.(12)ISX≤γ=1,ifSX≤γ,0,ifSX>γ.A better way to estimatel is to use another pdf g, and we can represent l as in the following formula:(13)l=∫ISX≤γfXgXgXdx=ΕβISX≤γfXgX.An unbiased estimator ofl is depicted in the following formula:(14)l^=1N∑i=1NISXi≤γfXi;βgXi,where X1,X2,…,XN is generated from pdf g.It is well known that the best way to estimatel is to use the change of measure with the pdf g∗X:(15)g∗X=ISXi≤γfX;βl.In order to choose the pdfg∗ from the family of pdf f⋅;δ, the idea is to choose the reference parameter δ such that the distance between the densities gand f⋅;δ is minimal. Minimizing the Kullback–Leibler distance between the densities gand f⋅;δ is equivalent to the following formula:(16)minδDδ=minδΕg∗lng∗XfX;δ=minδ∫g∗Xlng∗XdX−∫g∗XlnfX;δdX.It is obvious that minimizing problem (16) is equivalent to solving the minimization problem.(17)minδ−∫g∗XlnfX;δdX=minδ−∫ISXi≤γfX;βllnfX;δdX.Finally, formula (17) is converted into the following formula:(18)minδ−ΕβISXi≤γlnfX;δ=minδ−1N∑i=1NISXi≤γlnfXi;δ,where X1,X2,…,XN is the random sample from f⋅;β. In typical applications, the function Dδin formula (16) is convex and differentiable with respect to δ [27]. Thus, we can get the solution of (18) from the following equation:(19)−1N∑i=1NISXi≤γ∇lnfXi;δ=0,where the gradient is with respect to δ.The idea of CE method is to construct simultaneously two sequences of levelsγ1,γ2,…,γTCE and parameters δ1,δ2,…,δTCE, where γTCE is close to the optimal γ∗ and δTCE is the corresponding parameter of pdf g∗. In other words, each iteration of the CE method has two main phases. In the first phase, γtCE is updated, and in the secondδtCE is updated. To be specific, starting δ0=β, we can obtain the two sequences as follows:Phase 1: adaptive updating ofγtCEFor a fixedδtCE−1, let γtCE be a θ-quantile of SX under δtCE−1; that is, γtCE satisfies(20)ΡβSX≤γ≥θ,whereX is generated from f⋅;δtCE−1.A simple estimatorγ^tCE of γtCE can be obtained by drawing a random sample X1,X2,…,XN from f⋅;δtCE−1, calculating the performances SXi for all I, ordering them from the smallest to the biggest, S1≤S2≤⋯≤SN, and evaluating the θ-quantile as(21)γ^tCE=SθN.Phase 2: adaptive updating ofδtCEFor fixedγtCE and δtCE−1, derive δtCE from the solution of (19), to be specific


### 3.2. Solving DWTA Problem Based on CE Method

In this paper, our purpose is to apply CE method to solve the DWTA problem modeled above, and interested readers can get detailed theory of CE method in [22, 28]. In order to solve formulation (9) at stage t, we construct the following discrete Probability Distribution Matrix (PDM) Mt:(22)Mt=p11,t⋯pn1,tpn+11,tp12,t⋯pn2,tpn+12,t⋮⋮⋮p1m,t⋯pnm,tpn+1m,tm×n+1,where the element pji,t in PDM denotes the probability of allocating weapon i to target j at stage t, and if every element pji,t belongs to 0,1, we can get the final solution according to the PDM. Furthermore, the PDM Mt satisfies the following constraint condition:(23)∑j∈J˜pji,t=1,∀i∈W,t=1,…,T,where the set J˜=J+n+1 because we use target n + 1 to deal with Situation 1 and Situation 2, and it is obvious that constraint condition (6) is equivalent to constraint condition (23). It is worth noting that initializing the PDM M0t at stage t according to the following formula can assure that sample X generated from PDM Mt meets the resources requirement:(24)pji,t=1∑j∈J˜hi,j,t,ifhi,j,t≠0,0,ifhi,j,t=0,∀i∈W,t=1,…,T.According to the PDMMt at stage t, we can get the probability distribution function fXt;Mt:(25)fXt;Mt=∏i∈Wpxiti,t,where pxiti is the element of column xit in line i of PDM Mt.Furthermore, we can get the following probability distribution function:(26)fXt;Mt=∏i∈Wpxiti,t=∏i∈W∏j∈J˜pji,tgxit,j,where formulas (25) and (26) are equivalent, and the reader can refer to Appendix for details.In each iteration process of CE method,X1t,…,XNt are N samples generated from the PDM Mt, and we can compute the objective function values SXlt,∀l=1,…,N, and then we sort the N objective function values in ascending order, and we can get the sequence of objective function values SX1t≤⋯≤SXNt and the sequence of samples X1t,…,XNt; let H=⌊θN⌋, and ⌊⌋ is the symbol of rounding down, which is the θ-quantile. We select H samples corresponding to the H minimum objective function values; that is, X1t,…,XHt, to update the PDM Mt. We can get the following optimization problem according to formula (18):(27)minMt−∑s=1HlnfXt;Mt,s.t.∑j∈J˜pj|i,t=1,∀i∈W,t=1,…,T,pji,t≥0,∀i∈W,j∈J˜,t=1,…,T.According to formula (26), we can simplify formula (27):(28)minMt−∑s=1HlnfXst;Mt=minMt−∑s=1Hln∏i∈Wpxisti,t=minM−∑s=1Hln∏i∈W∏j∈J˜pji,tgxist,j=minM−∑s=1H∑i=1m∑j=1n+1gxist,jlnpji,t.In order to simplify the description, letrjit=pji,t, bjist=gxist,j, and then optimization problem (27) can be rewritten as follows:(29)minMt−∑s=1H∑i=1m∑j=1n+1bjistlnrjit,s.t.∑j=1n+1rjit=1,∀i∈W,t=1,…,T,rjit≥0,∀i∈W,j∈J˜,t=1,…,T.It is obvious that problem (29) belongs to a convex optimization problem, and we can construct the Lagrange function as follows:(30)Lrjit,λit,αjit=−∑s=1H∑i=1m∑j=1n+1bjistlnrjit+∑i=1mλit∑j=1n+1rjit−1+∑i=1m∑j=1n+1αjit−rjit.According to Karush–Kuhn–Tucker conditions, we can get the following formula:(31)−∑s=1Hbjistrjit+λit−αjit=0,αjit−rjit=0,∑j=1n+1rjit−1=0,αjit≥0,−rjit≤0,λit>0,and the following formula is derived according to the upper formula (31):(32)rjit=∑s=1HbjistH,αjit=0,λit=H.Then, the elementpji,t in PDM Mt can be updated according to the following formula:(33)pji,t=∑s=1HbjistH=∑s=1Hgxist,jH.Before the cessation conditions of the DWTA are analyzed, we give the updated formula of the remaining weapon inventory and the remaining combat ability value after thet stage.(34)vit+1=vit−∑j∈Jgxit,j,ujt+1=ujt∏i∈W1−ωijtgxit,jhi,j,t,where j∈J˜,i∈W,t=1,…,T.The cessation conditions of the DWTA include two points:Cessation condition 1: all available weapons are exhaustedCessation condition 2: the combat purpose is implemented, which means the percentage of the remaining combat ability value is less than the preselected percentageς∗Consequently, we can get the DWTA algorithm based on CE method as follows (Algorithm1).Algorithm 1: The DWTA algorithm based on CE method.
Input: t,n,m,K,uj,ci,νi,ζ∗,Q,R,Ω,θ,NOutput: T,S∗,X∗(1)
Lett = 1, begin the dynamic weapon target assignment.(2)
Compute the initial PDMM0t according to formula (24) and let tCE = 0.(3)
GenerateN samples θ=0.1 according to PDM MtCEt.(4)
Compute the objective function valuesSX1t,…,SXNt.(5)
Sort theN objective function values in ascending order and select H samples corresponding to the H minimum objective function values.(6)
Update the PDMMtCEt using the H samples according to formula (33).(7)
If all elements of PDMMtCEt belong to {0, 1}, set TCE=tCE, output the optimum X∗ and S∗, else let tCE=tCE+1, goto step 3 until the CE method achieves the convergence conditions.(8)
Update the remaining combat ability value of every targetujt+1 and the remaining weapon inventory vit+1.(9)
If any of the two cessation conditions is reached, letT=t, output T,S∗t,X∗t. Otherwise, let t=t+1, go to step 2.


### 3.3. Complexity Analysis

LetN denote the sample size, TCE denote the iteration number of CE method, m denote the number of weapon types, and T denote the final combat stage. The computational cost of CE method includes four parts: the initialization (Cini), sample (Csample), sort (Csort), and update (Cupdate); the computational complexity of CE method can be denoted as CCE=Cini+Csample+Csort+Cupdate, to be specific, CCE=m+TCEmN+N+mθN; therefore, the time complexity of the CE method can be computed as OTCEmN, and the time complexity of the DWTA algorithm based on CE method can be denoted as OTTCEmN. Let Num denote the population size of PSO and GA. Let D denote the iteration number of PSO and GA, and we can get the complexity of DWTA algorithm based on PSO ang GA denoted as OTD⋅Num.


## 3.1. The Cross-Entropy Method

Originally, CE method is based on importance sampling and used to estimate the probability of rare event, and Rubinstein [22] put forward an optimization method based on the idea of CE, which could solve the discrete multiextreme value problems. Consider the following general minimization problem: let S be a real-valued function on χ, where χ is a finite set of states. Our goal is to find the minimum of S over χ, which is denoted as γ∗, and X∗ is the corresponding state.(10)SX∗=γ∗=minX∈χSX.The basic idea of CE method applied to formula (10) is to associate an estimation problem with the optimization problem. In that case, the optimization problem is converted into an estimation problem with probability density function (pdf) f⋅,β.(11)l=ΡβSX≤γ=ΕβISX≤γ,where γ is a value close to γ∗, Ρβ is the probability measure, Εβ denotes the corresponding expectation operator, and ISX≤γ is the indicator function.(12)ISX≤γ=1,ifSX≤γ,0,ifSX>γ.A better way to estimatel is to use another pdf g, and we can represent l as in the following formula:(13)l=∫ISX≤γfXgXgXdx=ΕβISX≤γfXgX.An unbiased estimator ofl is depicted in the following formula:(14)l^=1N∑i=1NISXi≤γfXi;βgXi,where X1,X2,…,XN is generated from pdf g.It is well known that the best way to estimatel is to use the change of measure with the pdf g∗X:(15)g∗X=ISXi≤γfX;βl.In order to choose the pdfg∗ from the family of pdf f⋅;δ, the idea is to choose the reference parameter δ such that the distance between the densities gand f⋅;δ is minimal. Minimizing the Kullback–Leibler distance between the densities gand f⋅;δ is equivalent to the following formula:(16)minδDδ=minδΕg∗lng∗XfX;δ=minδ∫g∗Xlng∗XdX−∫g∗XlnfX;δdX.It is obvious that minimizing problem (16) is equivalent to solving the minimization problem.(17)minδ−∫g∗XlnfX;δdX=minδ−∫ISXi≤γfX;βllnfX;δdX.Finally, formula (17) is converted into the following formula:(18)minδ−ΕβISXi≤γlnfX;δ=minδ−1N∑i=1NISXi≤γlnfXi;δ,where X1,X2,…,XN is the random sample from f⋅;β. In typical applications, the function Dδin formula (16) is convex and differentiable with respect to δ [27]. Thus, we can get the solution of (18) from the following equation:(19)−1N∑i=1NISXi≤γ∇lnfXi;δ=0,where the gradient is with respect to δ.The idea of CE method is to construct simultaneously two sequences of levelsγ1,γ2,…,γTCE and parameters δ1,δ2,…,δTCE, where γTCE is close to the optimal γ∗ and δTCE is the corresponding parameter of pdf g∗. In other words, each iteration of the CE method has two main phases. In the first phase, γtCE is updated, and in the secondδtCE is updated. To be specific, starting δ0=β, we can obtain the two sequences as follows:Phase 1: adaptive updating ofγtCEFor a fixedδtCE−1, let γtCE be a θ-quantile of SX under δtCE−1; that is, γtCE satisfies(20)ΡβSX≤γ≥θ,whereX is generated from f⋅;δtCE−1.A simple estimatorγ^tCE of γtCE can be obtained by drawing a random sample X1,X2,…,XN from f⋅;δtCE−1, calculating the performances SXi for all I, ordering them from the smallest to the biggest, S1≤S2≤⋯≤SN, and evaluating the θ-quantile as(21)γ^tCE=SθN.Phase 2: adaptive updating ofδtCEFor fixedγtCE and δtCE−1, derive δtCE from the solution of (19), to be specific


## 3.2. Solving DWTA Problem Based on CE Method

In this paper, our purpose is to apply CE method to solve the DWTA problem modeled above, and interested readers can get detailed theory of CE method in [22, 28]. In order to solve formulation (9) at stage t, we construct the following discrete Probability Distribution Matrix (PDM) Mt:(22)Mt=p11,t⋯pn1,tpn+11,tp12,t⋯pn2,tpn+12,t⋮⋮⋮p1m,t⋯pnm,tpn+1m,tm×n+1,where the element pji,t in PDM denotes the probability of allocating weapon i to target j at stage t, and if every element pji,t belongs to 0,1, we can get the final solution according to the PDM. Furthermore, the PDM Mt satisfies the following constraint condition:(23)∑j∈J˜pji,t=1,∀i∈W,t=1,…,T,where the set J˜=J+n+1 because we use target n + 1 to deal with Situation 1 and Situation 2, and it is obvious that constraint condition (6) is equivalent to constraint condition (23). It is worth noting that initializing the PDM M0t at stage t according to the following formula can assure that sample X generated from PDM Mt meets the resources requirement:(24)pji,t=1∑j∈J˜hi,j,t,ifhi,j,t≠0,0,ifhi,j,t=0,∀i∈W,t=1,…,T.According to the PDMMt at stage t, we can get the probability distribution function fXt;Mt:(25)fXt;Mt=∏i∈Wpxiti,t,where pxiti is the element of column xit in line i of PDM Mt.Furthermore, we can get the following probability distribution function:(26)fXt;Mt=∏i∈Wpxiti,t=∏i∈W∏j∈J˜pji,tgxit,j,where formulas (25) and (26) are equivalent, and the reader can refer to Appendix for details.In each iteration process of CE method,X1t,…,XNt are N samples generated from the PDM Mt, and we can compute the objective function values SXlt,∀l=1,…,N, and then we sort the N objective function values in ascending order, and we can get the sequence of objective function values SX1t≤⋯≤SXNt and the sequence of samples X1t,…,XNt; let H=⌊θN⌋, and ⌊⌋ is the symbol of rounding down, which is the θ-quantile. We select H samples corresponding to the H minimum objective function values; that is, X1t,…,XHt, to update the PDM Mt. We can get the following optimization problem according to formula (18):(27)minMt−∑s=1HlnfXt;Mt,s.t.∑j∈J˜pj|i,t=1,∀i∈W,t=1,…,T,pji,t≥0,∀i∈W,j∈J˜,t=1,…,T.According to formula (26), we can simplify formula (27):(28)minMt−∑s=1HlnfXst;Mt=minMt−∑s=1Hln∏i∈Wpxisti,t=minM−∑s=1Hln∏i∈W∏j∈J˜pji,tgxist,j=minM−∑s=1H∑i=1m∑j=1n+1gxist,jlnpji,t.In order to simplify the description, letrjit=pji,t, bjist=gxist,j, and then optimization problem (27) can be rewritten as follows:(29)minMt−∑s=1H∑i=1m∑j=1n+1bjistlnrjit,s.t.∑j=1n+1rjit=1,∀i∈W,t=1,…,T,rjit≥0,∀i∈W,j∈J˜,t=1,…,T.It is obvious that problem (29) belongs to a convex optimization problem, and we can construct the Lagrange function as follows:(30)Lrjit,λit,αjit=−∑s=1H∑i=1m∑j=1n+1bjistlnrjit+∑i=1mλit∑j=1n+1rjit−1+∑i=1m∑j=1n+1αjit−rjit.According to Karush–Kuhn–Tucker conditions, we can get the following formula:(31)−∑s=1Hbjistrjit+λit−αjit=0,αjit−rjit=0,∑j=1n+1rjit−1=0,αjit≥0,−rjit≤0,λit>0,and the following formula is derived according to the upper formula (31):(32)rjit=∑s=1HbjistH,αjit=0,λit=H.Then, the elementpji,t in PDM Mt can be updated according to the following formula:(33)pji,t=∑s=1HbjistH=∑s=1Hgxist,jH.Before the cessation conditions of the DWTA are analyzed, we give the updated formula of the remaining weapon inventory and the remaining combat ability value after thet stage.(34)vit+1=vit−∑j∈Jgxit,j,ujt+1=ujt∏i∈W1−ωijtgxit,jhi,j,t,where j∈J˜,i∈W,t=1,…,T.The cessation conditions of the DWTA include two points:Cessation condition 1: all available weapons are exhaustedCessation condition 2: the combat purpose is implemented, which means the percentage of the remaining combat ability value is less than the preselected percentageς∗Consequently, we can get the DWTA algorithm based on CE method as follows (Algorithm1).Algorithm 1: The DWTA algorithm based on CE method.
Input: t,n,m,K,uj,ci,νi,ζ∗,Q,R,Ω,θ,NOutput: T,S∗,X∗(1)
Lett = 1, begin the dynamic weapon target assignment.(2)
Compute the initial PDMM0t according to formula (24) and let tCE = 0.(3)
GenerateN samples θ=0.1 according to PDM MtCEt.(4)
Compute the objective function valuesSX1t,…,SXNt.(5)
Sort theN objective function values in ascending order and select H samples corresponding to the H minimum objective function values.(6)
Update the PDMMtCEt using the H samples according to formula (33).(7)
If all elements of PDMMtCEt belong to {0, 1}, set TCE=tCE, output the optimum X∗ and S∗, else let tCE=tCE+1, goto step 3 until the CE method achieves the convergence conditions.(8)
Update the remaining combat ability value of every targetujt+1 and the remaining weapon inventory vit+1.(9)
If any of the two cessation conditions is reached, letT=t, output T,S∗t,X∗t. Otherwise, let t=t+1, go to step 2.


## 3.3. Complexity Analysis

LetN denote the sample size, TCE denote the iteration number of CE method, m denote the number of weapon types, and T denote the final combat stage. The computational cost of CE method includes four parts: the initialization (Cini), sample (Csample), sort (Csort), and update (Cupdate); the computational complexity of CE method can be denoted as CCE=Cini+Csample+Csort+Cupdate, to be specific, CCE=m+TCEmN+N+mθN; therefore, the time complexity of the CE method can be computed as OTCEmN, and the time complexity of the DWTA algorithm based on CE method can be denoted as OTTCEmN. Let Num denote the population size of PSO and GA. Let D denote the iteration number of PSO and GA, and we can get the complexity of DWTA algorithm based on PSO ang GA denoted as OTD⋅Num.


## 4. DWTA Simulations

### 4.1. Parameter Setting for DWTA

The following contents in this subsection include three parts: parameters setting rules of combat scenario, parameters selection of algorithms, performance index design and parameters setting of combat scenario. The first part is the parameters setting rules of combat scenario which is depicted in Table2. Both the number of weapon types (m) and the number of targets (n) are integers between 1 and 80, that is, m,n∈1,80. The combat ability value of every target at the first stage is a random number between 70 and 200, that is, uj1∈70,200,∀j∈J; it is worth noting that the combat ability value of the hypothetical target is equal to zero, that is, un+1t=0,∀t=1,…,T. The cost of every single weapon is a random number between 20 and 80, that is, ci∈20,80,∀i∈W. The kill probability of weapon i to target j is a random number between 0.5 and 1, that is, ωijt∈0.5,1. qjkt is integer between 0 and 3. rikt is integer between 0 and 5. The expected combat purpose ς∗ is a random number between 0 and 1.Table 2
Combat scenario parameter setting rules.
ParameterParameter setting rulesnThe number of weapon types (m) is integer between 1 and 80mThe number of targets (n) is integer between 1 and 80KThe number of the resource types is integer between 1 and 9uj1The combat ability value of targetj at the first stage is a random number between 70 and 200 and un+11=0ciThe cost of every single weapon is a random number between 20 and 80vi1The inventory quantity of weaponi at the first stage is integer between 0 and 10qjktThe quantity of resourcek required by target j at stage t is integer between 0 and 3riktThe quantity of resourcek contained by weapon i at stage t is integer between 0 and 5ωijtThe kill probability of weaponi to target j is a random number between 0.5 and 1ς∗The expected combat purpose is a random number between 0 and 1Subsequently, we give the scheme of parameter selection of CE, PSO, GA, and MC methods in Table3. The CE method includes two parameters, sample size and quantile, and the main parameters of PSO and GA methods are population size Num and iteration number D, and we set sample size of MC method equal to 5e4 in the simulation.Table 3
Parameters setting of different methods.
MethodParameterParameter setting rulesCENThe sample size of CE method is integer between 50 and 200θThe quantileθ is a random number between 0 and 1PSONumThe population size of PSO is integer between 50 and 200DThe iteration number of PSO is integer between 50 and 100GANumThe population size of GA is integer between 50 and 200DThe iteration number of GA is integer between 50 and 100MCNMCThe sample size of MC method is 5e4The third part is performance index design depicted in Table4 which measures the solution quality of different algorithms. The percentage between the sum of the cost of weapon consumed in all stages and the total value of weapons, denoted as PSCWC, is to depict combat costs in whole combat.(35)PSCWC=∑t=1T∑j∈J˜∑i∈Wcigxi∗t,j∑i∈Wcivi1×100%.Table 4
Description of several indexes.
IndexDescriptionPSCWCThe percentage between the sum of the cost of weapon consumed in all stages and the total value of weaponsPRCAVTThe percentage between the remaining combat ability value of targets at stageT and the initial combat value of targetsCIThe composite index which is the product of the index PRCAVT and the index PSCWCavg-PSCWCThe average of PSCWC corresponding to the six DWTA problemsavg-PRCAVTThe average of PRCAVT corresponding to the six DWTA problemsCTComputation time of all stagesThe index PRCAVT denotes the percentage between the remaining combat ability value of targets atT stage and the initial combat value of targets, which measures whether to achieve the expected combat purpose.(36)PRCAVT=∑j∈JujT∑j∈Juj1×100%.The index CI is the product of the index PRCAVT and the index PSCWC. The index avg-PSCWC is the average of PSCWC corresponding to the six DWTA problems. The index avg-PRCAVT is the average of PRCAVT corresponding to the six DWTA problems. The computation time (CT) is used to depict the solving speed of different algorithms.Finally, we categorize the number of weapon stockpiles and weight parameters of DWTA model into the following four situations so as to cover different combat scenarios.Scenario 1.
Weapon stockpiles are sufficient, and the weapon costs are important the same as with the combat benefits.(37)vi=6+4⋅randm,1,α1=α2=0.5.Scenario 2.
Weapon stockpiles are sufficient, and the combat benefits are more important than the weapon costs.(38)vi=6+4⋅randm,1,α1=0.1,α2=0.9.Scenario 3.
Weapon stockpiles are not sufficient, and the weapon costs are important the same as with the combat benefits.(39)vi=2+1⋅randm,1,α1=α2=0.5.Scenario 4.
Weapon stockpiles are not sufficient, and the combat benefits are more important than the weapon costs.(40)vi=2+1⋅randm,1,α1=0.1,α2=0.9.
It is worth noting that the same scale DWTA problems inScenario 1 and Scenario 2 have the same parameters such as the inventory quantity of weapons and kill probability, and the same is true for Scenario 3 and Scenario 4. Besides, in order to describe the effectiveness of the DWTA model and the advantages of CE method in solving different scales of DWTA problems, we set up the following six scales DWTA problems. The choices of parameter m and parameter n are shown in Table 5.
We set the expected combat purposeς∗=10% in advance, which depicts that we stop the combat task when the index PRCAVT is less than ς∗; note that another stop condition is that all available weapons are exhausted. We set the relevant parameters of CE, PSO, and GA methods as follows, N=200 and θ=0.1, Num=50, D=100. In this paper, ten simulations of the same scale DWTA problem are carried out to calculate the statistical average of PSCWC, PRCAVT, and CT. All algorithms are implemented in an Intel Core I5 @ 3.06 GHz processor with 8 GB RAM.Table 5
Six DWTA problems of different scales.
No.123456n122425404564m161632325454


### 4.2. Results and Analysis

The results of simulation are presented in Figures2–4 and Tables 6–8. What needs to be pointed out is that the smaller the indexes PSCWC and avg-PSCWC are, the smaller the cost of weapons consumed is. The smaller the indexes PRCAVT and avg-PRCAVT are, the greater the combat benefits are. The smaller the index CI is, the better the solution quality is. The smaller the CT index is, the faster the solving speed is.Figure 2
Comparative results of CE, GA, PSO, and MC methods with respect to PSCWC index. (a) Scenario 1. (b) Scenario 2. (c) Scenario 3. (d) Scenario 4.
(a)(b)(c)(d)Figure 3
Comparative results of CE, GA, PSO, and MC methods with respect to PSCWC index. (a) Scenario 1. (b) Scenario 2. (c) Scenario 3. (d) Scenario 4.
(a)(b)(c)(d)Figure 4
Comparative results of CE, GA, PSO, and MC methods with respect to the index CI. (a) Scenario 1. (b) Scenario 2. (c) Scenario 3. (d) Scenario 4.
(a)(b)(c)(d)Table 6
Comparative results of CE, GA, PSO, and MC methods with respect to the statistic average PSCWC index.
MethodCE (%)GA (%)PSO (%)MC (%)Scenario 121.9829.9837.1644.96Scenario 229.6435.1941.8148.84Scenario 361.3161.6263.6164.46Scenario 467.6967.3066.9966.37Table 7
Comparative results of CE, GA, PSO, and MC methods with respect to the index avg-PRCAVT.
MethodCE (%)GA (%)PSO (%)MC (%)Scenario 17.978.287.186.85Scenario 24.716.966.836.41Scenario 327.1933.3037.6142.82Scenario 424.8231.9735.9642.15Table 8
Comparative results of CE, GA, PSO, and MC methods with respect to the index CT (s).
No.MethodScenario 1Scenario 2Scenario 3Scenario 41CE0.510.260.130.14GA6.782.591.231.22PSO3.812.681.311.32MC24.6618.168.678.792CE0.970.620.210.21GA8.065.421.421.41PSO7.655.491.791.8MC5046.971111.033CE1.431.020.530.54GA10.85.942.882.93PSO9.527.463.833.95MC59.5751.6521.7722.464CE2.731.760.780.75GA15.2311.873.473.46PSO19.9515.845.025.01MC135.52121.4928.2228.25CE2.853.051.501.52GA18.4813.486.036.02PSO24.5619.568.698.7MC156.1159.4248.7148.966CE5.834.082.042GA26.7823.317.347.26PSO34.3434.7211.3111.11MC261.23260.3762.4362.31Figures2(a), 3(a), and 4(a) depict the combat results in Scenario 1; the index PSCWC has the ascending sequence, that is, CE < GA < PSO < MC; furthermore, Figure 4(a) indicates that the value of index CI for CE method is the smallest among others, and from Tables 6 and 7, the indexes avg-PSCWC of CE, GA, PSO, and MC methods are 21.98%, 29.98%, 37.16%, and 44.96%, and the indexes avg-PRCAVT of CE, GA, PSO, and MC methods are 7.97%, 8.28%, 7.18%, and 6.85%, which indicates that the solution of CE method is more excellent than these solutions of GA, PSO, and MC methods; that is, the expected combat purpose is achieved and multitudes of weapon costs are saved. The same conclusion can be reached in Scenario 2.As forScenario 3, the CE, GA, PSO, and MC methods have nearly the same PSCWC index depicted in Figure 2(c), and from Figure 3(c), the PRCAVT index has the ascending sequence, that is, CE < GA < PSO < MC, and Figure 4(c) indicates that the value of index CI for CE method is the smallest among others; furthermore, from Tables 6 and 7, the indexes avg-PSCWC of CE, GA, PSO, and MC methods are 61.31%, 61.62%, 63.61%, and 64.46%, and the indexes avg-PRCAVT of CE, GA, PSO, and MC methods are 27.19%, 33.30%, 37.61%, and 42.82%. Consequently, compared with the GA, PSO, and MC methods, the assignment results of CE method are more effective in the condition that the number of weapons consumed is the same. According to the combat result of Scenario 3, we can get the conclusion that the defense can get better combat benefits when using CE method to complete the DWTA task under the condition that the weapons are inadequate. The same conclusion can be reached in Scenario 4.ComparingScenario 1 with Scenario 2 and comparing Scenario 3 with Scenario 4, the simulation results are shown in Figures 2 and 3. From the indexes PSCWC and PRCAVT, the defense gets more combat benefits in Scenario 2 and Scenario 4 but spends more weapon costs. We can get the conclusion that the defense can save weapon costs to some extent by adjusting weight parameters α1 and α2 in different scenarios.The computation time of solving the different scales DWTA problem is recorded in the four combat scenarios, and the relevant results are shown in Table8; it is obvious that the index CT presents ascending sequence, that is, CE<GA≈PSO<MC, and the computation cost of CE method is one-order-of-magnitude lower than that of GA and PSO method; consequently, we could get that the CE method has great advantage in solving speed over GA, PSO, and MC methods.


## 4.1. Parameter Setting for DWTA

The following contents in this subsection include three parts: parameters setting rules of combat scenario, parameters selection of algorithms, performance index design and parameters setting of combat scenario. The first part is the parameters setting rules of combat scenario which is depicted in Table2. Both the number of weapon types (m) and the number of targets (n) are integers between 1 and 80, that is, m,n∈1,80. The combat ability value of every target at the first stage is a random number between 70 and 200, that is, uj1∈70,200,∀j∈J; it is worth noting that the combat ability value of the hypothetical target is equal to zero, that is, un+1t=0,∀t=1,…,T. The cost of every single weapon is a random number between 20 and 80, that is, ci∈20,80,∀i∈W. The kill probability of weapon i to target j is a random number between 0.5 and 1, that is, ωijt∈0.5,1. qjkt is integer between 0 and 3. rikt is integer between 0 and 5. The expected combat purpose ς∗ is a random number between 0 and 1.Table 2
Combat scenario parameter setting rules.
ParameterParameter setting rulesnThe number of weapon types (m) is integer between 1 and 80mThe number of targets (n) is integer between 1 and 80KThe number of the resource types is integer between 1 and 9uj1The combat ability value of targetj at the first stage is a random number between 70 and 200 and un+11=0ciThe cost of every single weapon is a random number between 20 and 80vi1The inventory quantity of weaponi at the first stage is integer between 0 and 10qjktThe quantity of resourcek required by target j at stage t is integer between 0 and 3riktThe quantity of resourcek contained by weapon i at stage t is integer between 0 and 5ωijtThe kill probability of weaponi to target j is a random number between 0.5 and 1ς∗The expected combat purpose is a random number between 0 and 1Subsequently, we give the scheme of parameter selection of CE, PSO, GA, and MC methods in Table3. The CE method includes two parameters, sample size and quantile, and the main parameters of PSO and GA methods are population size Num and iteration number D, and we set sample size of MC method equal to 5e4 in the simulation.Table 3
Parameters setting of different methods.
MethodParameterParameter setting rulesCENThe sample size of CE method is integer between 50 and 200θThe quantileθ is a random number between 0 and 1PSONumThe population size of PSO is integer between 50 and 200DThe iteration number of PSO is integer between 50 and 100GANumThe population size of GA is integer between 50 and 200DThe iteration number of GA is integer between 50 and 100MCNMCThe sample size of MC method is 5e4The third part is performance index design depicted in Table4 which measures the solution quality of different algorithms. The percentage between the sum of the cost of weapon consumed in all stages and the total value of weapons, denoted as PSCWC, is to depict combat costs in whole combat.(35)PSCWC=∑t=1T∑j∈J˜∑i∈Wcigxi∗t,j∑i∈Wcivi1×100%.Table 4
Description of several indexes.
IndexDescriptionPSCWCThe percentage between the sum of the cost of weapon consumed in all stages and the total value of weaponsPRCAVTThe percentage between the remaining combat ability value of targets at stageT and the initial combat value of targetsCIThe composite index which is the product of the index PRCAVT and the index PSCWCavg-PSCWCThe average of PSCWC corresponding to the six DWTA problemsavg-PRCAVTThe average of PRCAVT corresponding to the six DWTA problemsCTComputation time of all stagesThe index PRCAVT denotes the percentage between the remaining combat ability value of targets atT stage and the initial combat value of targets, which measures whether to achieve the expected combat purpose.(36)PRCAVT=∑j∈JujT∑j∈Juj1×100%.The index CI is the product of the index PRCAVT and the index PSCWC. The index avg-PSCWC is the average of PSCWC corresponding to the six DWTA problems. The index avg-PRCAVT is the average of PRCAVT corresponding to the six DWTA problems. The computation time (CT) is used to depict the solving speed of different algorithms.Finally, we categorize the number of weapon stockpiles and weight parameters of DWTA model into the following four situations so as to cover different combat scenarios.Scenario 1.
Weapon stockpiles are sufficient, and the weapon costs are important the same as with the combat benefits.(37)vi=6+4⋅randm,1,α1=α2=0.5.Scenario 2.
Weapon stockpiles are sufficient, and the combat benefits are more important than the weapon costs.(38)vi=6+4⋅randm,1,α1=0.1,α2=0.9.Scenario 3.
Weapon stockpiles are not sufficient, and the weapon costs are important the same as with the combat benefits.(39)vi=2+1⋅randm,1,α1=α2=0.5.Scenario 4.
Weapon stockpiles are not sufficient, and the combat benefits are more important than the weapon costs.(40)vi=2+1⋅randm,1,α1=0.1,α2=0.9.
It is worth noting that the same scale DWTA problems inScenario 1 and Scenario 2 have the same parameters such as the inventory quantity of weapons and kill probability, and the same is true for Scenario 3 and Scenario 4. Besides, in order to describe the effectiveness of the DWTA model and the advantages of CE method in solving different scales of DWTA problems, we set up the following six scales DWTA problems. The choices of parameter m and parameter n are shown in Table 5.
We set the expected combat purposeς∗=10% in advance, which depicts that we stop the combat task when the index PRCAVT is less than ς∗; note that another stop condition is that all available weapons are exhausted. We set the relevant parameters of CE, PSO, and GA methods as follows, N=200 and θ=0.1, Num=50, D=100. In this paper, ten simulations of the same scale DWTA problem are carried out to calculate the statistical average of PSCWC, PRCAVT, and CT. All algorithms are implemented in an Intel Core I5 @ 3.06 GHz processor with 8 GB RAM.Table 5
Six DWTA problems of different scales.
No.123456n122425404564m161632325454


## 4.2. Results and Analysis

The results of simulation are presented in Figures2–4 and Tables 6–8. What needs to be pointed out is that the smaller the indexes PSCWC and avg-PSCWC are, the smaller the cost of weapons consumed is. The smaller the indexes PRCAVT and avg-PRCAVT are, the greater the combat benefits are. The smaller the index CI is, the better the solution quality is. The smaller the CT index is, the faster the solving speed is.Figure 2
Comparative results of CE, GA, PSO, and MC methods with respect to PSCWC index. (a) Scenario 1. (b) Scenario 2. (c) Scenario 3. (d) Scenario 4.
(a)(b)(c)(d)Figure 3
Comparative results of CE, GA, PSO, and MC methods with respect to PSCWC index. (a) Scenario 1. (b) Scenario 2. (c) Scenario 3. (d) Scenario 4.
(a)(b)(c)(d)Figure 4
Comparative results of CE, GA, PSO, and MC methods with respect to the index CI. (a) Scenario 1. (b) Scenario 2. (c) Scenario 3. (d) Scenario 4.
(a)(b)(c)(d)Table 6
Comparative results of CE, GA, PSO, and MC methods with respect to the statistic average PSCWC index.
MethodCE (%)GA (%)PSO (%)MC (%)Scenario 121.9829.9837.1644.96Scenario 229.6435.1941.8148.84Scenario 361.3161.6263.6164.46Scenario 467.6967.3066.9966.37Table 7
Comparative results of CE, GA, PSO, and MC methods with respect to the index avg-PRCAVT.
MethodCE (%)GA (%)PSO (%)MC (%)Scenario 17.978.287.186.85Scenario 24.716.966.836.41Scenario 327.1933.3037.6142.82Scenario 424.8231.9735.9642.15Table 8
Comparative results of CE, GA, PSO, and MC methods with respect to the index CT (s).
No.MethodScenario 1Scenario 2Scenario 3Scenario 41CE0.510.260.130.14GA6.782.591.231.22PSO3.812.681.311.32MC24.6618.168.678.792CE0.970.620.210.21GA8.065.421.421.41PSO7.655.491.791.8MC5046.971111.033CE1.431.020.530.54GA10.85.942.882.93PSO9.527.463.833.95MC59.5751.6521.7722.464CE2.731.760.780.75GA15.2311.873.473.46PSO19.9515.845.025.01MC135.52121.4928.2228.25CE2.853.051.501.52GA18.4813.486.036.02PSO24.5619.568.698.7MC156.1159.4248.7148.966CE5.834.082.042GA26.7823.317.347.26PSO34.3434.7211.3111.11MC261.23260.3762.4362.31Figures2(a), 3(a), and 4(a) depict the combat results in Scenario 1; the index PSCWC has the ascending sequence, that is, CE < GA < PSO < MC; furthermore, Figure 4(a) indicates that the value of index CI for CE method is the smallest among others, and from Tables 6 and 7, the indexes avg-PSCWC of CE, GA, PSO, and MC methods are 21.98%, 29.98%, 37.16%, and 44.96%, and the indexes avg-PRCAVT of CE, GA, PSO, and MC methods are 7.97%, 8.28%, 7.18%, and 6.85%, which indicates that the solution of CE method is more excellent than these solutions of GA, PSO, and MC methods; that is, the expected combat purpose is achieved and multitudes of weapon costs are saved. The same conclusion can be reached in Scenario 2.As forScenario 3, the CE, GA, PSO, and MC methods have nearly the same PSCWC index depicted in Figure 2(c), and from Figure 3(c), the PRCAVT index has the ascending sequence, that is, CE < GA < PSO < MC, and Figure 4(c) indicates that the value of index CI for CE method is the smallest among others; furthermore, from Tables 6 and 7, the indexes avg-PSCWC of CE, GA, PSO, and MC methods are 61.31%, 61.62%, 63.61%, and 64.46%, and the indexes avg-PRCAVT of CE, GA, PSO, and MC methods are 27.19%, 33.30%, 37.61%, and 42.82%. Consequently, compared with the GA, PSO, and MC methods, the assignment results of CE method are more effective in the condition that the number of weapons consumed is the same. According to the combat result of Scenario 3, we can get the conclusion that the defense can get better combat benefits when using CE method to complete the DWTA task under the condition that the weapons are inadequate. The same conclusion can be reached in Scenario 4.ComparingScenario 1 with Scenario 2 and comparing Scenario 3 with Scenario 4, the simulation results are shown in Figures 2 and 3. From the indexes PSCWC and PRCAVT, the defense gets more combat benefits in Scenario 2 and Scenario 4 but spends more weapon costs. We can get the conclusion that the defense can save weapon costs to some extent by adjusting weight parameters α1 and α2 in different scenarios.The computation time of solving the different scales DWTA problem is recorded in the four combat scenarios, and the relevant results are shown in Table8; it is obvious that the index CT presents ascending sequence, that is, CE<GA≈PSO<MC, and the computation cost of CE method is one-order-of-magnitude lower than that of GA and PSO method; consequently, we could get that the CE method has great advantage in solving speed over GA, PSO, and MC methods.


## 5. Conclusion

In this paper, a novel DWTA model under the resource requirement condition which is shoot-look-shoot variant is constructed, where weight parameters are introduced to balance the weapon costs and combat benefits. Subsequently, a hypothetical target is constructed to deal with the resource requirement condition, a new dynamic weapon target assignment method based on CE is introduced, and the detailed derivation process of using CE method to solve DWTA problem is given. Finally, to evaluate the solution quality of CE method, the dynamic weapon target assignment task based on CE, GA, PSO, and MC methods is simulated in several combat scenarios. Three conclusions are summarized based on the simulation results. Firstly, the expected combat purpose is achieved and a good supply of weapon costs are saved by dealing with the DWTA problem based on CE method under the condition that weapon inventory is adequate. Secondly, more combat benefits are acquired by dealing with the DWTA problem based on CE method under the condition that weapon inventory is inadequate. Thirdly, the solving speed of CE method is obviously faster than GA, PSO, and MC methods which more fit the real-time combat scenario. Besides, another strong point of the DWTA formulation is that adjusting weight parameters in different scenarios can save weapon costs to some extent.For future research, we will focus on the promotion of CE method in its efficiency and time consumption by sample selection and appropriate parameter settings.



---

*Source: 8618065-2020-09-02.xml*