Distributed MMAS for weapon target assignment based on Spark framework

Abstract

Weapon target allocation (WTA) is a classic NP-complete problem in the field of military operations research. In this paper, we addressed the multi-constraint WTA problems in multilayer defense scenario. To solve large-scale WTA problems effectively, a distributed MAX-MIN Ant System (MMAS) algorithm based on distributed computing framework Spark was developed and improved. An experiment environment comprising virtual machines was built for implementing the distributed MMAS. First, a small-scale WTA example, whose theoretical optimal solution can be obtained by existing optimization software, was taken as a benchmark problem to assess the performance of distributed MMAS. The result shows that it can find high-quality and robust approximate solutions. Then a large-scale WTA problem was constructed and used to further evaluate the performance of distributed MMAS in the experiment environment. The result shows that the distributed MMAS can also achieve high-quality approximate solutions with high robustness and computational efficiency even for large scale WTA problems. Our study demonstrates it is a promising approach for solving large-scale iteration-dependent optimization problems like WTA by means of incorporating heuristic optimization algorithms such as Ant Colony Optimization into distributed computing framework.

Keywords

Weapon target allocation (WTA)distributed computing Spark heuristic algorithm MAX-MIN ant system (MMAS).

1 Introduction

The Weapon Target Assignment (WTA) problem is a basic problem growing out of defense-related applications of operations research. This problem is to find an appropriate assignment of defensive weapons to targets with the objective of maximizing the survival asset value. Research on WTA problems stretched back to the 1950s and 1960s, in which the modeling issues for WTA problems were investigated [1, 2]. At that time, because of limited computing power and the less advanced research level, researchers had to make a number of simplified assumptions when modeling WTA problems and they could solve only small-scale problems by using mathematical programming methods, such as the Branch and Bound method or Dynamic Programming. In the past 30 years, when mentioning the WTA problem, many researchers have made increasing extensions and improvements on its mathematical model and relevant algorithms, including extensions from single-layer to multi-layer defense scenarios; from only considering weapon availability constraints to simultaneously considering more constraints in which some factors as manpower, budget and space availability could be concerned; from a static to a dynamic assignment situation; and from exact algorithms for solving small-scale problems to heuristic algorithms for solving large-scale problems.

The WTA problem is a representative constrained combinatorial optimization problem. In 1986, Lloyd and Witsenhausen [3] proved that the WTA problem with multi-type weapons was NP-complete for the first time. Exact algorithms based on mathematical programming theory usually resulted in an exponential increase in the computational requirements, regardless of whether the problem scale was large or small. Thus, the exact algorithms focused on only static WTA problems, with some restrictive conditions, such as that all of the weapons were identical [4] or that the targets could receive at most one weapon [5]. Recent researches mainly focused on dynamic WTA problems [6 –8] or WTA problems based on multiple agent [9]. Researchers were interested in dynamic resource allocation problem and engaged in developing more effective algorithms for a significant computational runtime improvement.

An efficient solution of the WTA problem is of great interest in military operations research. The reason is that in an engagement with the enemy, the problem must be solved in real time. The enormous combinatorial complexity of the problem implies that even with the supercomputers which are available today, exact optimal solutions cannot be obtained in real time. Many researchers have been working on modern heuristic algorithms, for example ant colony optimization. Recent an algorithm research presents a hybrid approach which combines an ant colony optimization with a greedy algorithm [10].

Distributed computation technology has brought about changes on the compute mode in the distributed computation epoch. Unlike traditional compute mode featured with small amount of data and stand-alone compute environment, distributed computation refers to datasets that are terabytes to petabytes (and even exabytes) in size, and are stored on computational clusters instead of one or several devices.

Various types of data which derive from all aspects of human life [11 –16] have been stored in nodes of various clusters. The situation is bringing new challenges to computation and analysis. Large amounts of data mean that they need to be processed in parallel rather than in sequence, and be handled in cluster mode rather than in stand-alone mode. Now computational processes dealing with data processing and data analysis have been handled using parallelized way through clusters, where each node is well-organized and might be stand-alone. The large distributed compute architecture has formed in rapidly developing distributed computation realm. Therefore, in the new computation architecture, algorithms which originated from stand-alone environment need to re-model and redesign for tackling new problems more efficiently.

This paper deals with how to solve a large-scale multi-constraint WTA problem in multilayer defense scenario [2 , 17–19]. Distributed computation is a promising approach to this kind of problem [20]. For example, large batches of Traveling Salesman Problems [21] was solved with distributed computation. Recent researches on solving heuristic problems adopted distributed computation [22 –25]. In this paper, we developed a distributed MAX-MIN Ant System (MMAS) algorithm [26, 27] based on Spark framework [28] to solve WTA problems. Spark has been a common computing framework in data analysis [29, 30]. The implementation schemes and some improvements of the proposed algorithm were presented. The experiment environment for implementing distributed computing based on Spark framework was built. Under the experiment environment, a small-scale WTA example taken as a benchmark was used to assess the performance of the algorithm. Furthermore the proposed algorithm was used to solve a large scale WTA problem. The solution quality and computational efficiency were presented and evaluated. The result shows that the distributed MMAS algorithm based on Spark framework are effective for even larger scale WTA problems. In addition, many heuristic algorithms can be incorporated into Spark framework for solving large-scale iterative optimization problems like WTA.

2 Mathematical model for WTA problem

We addressed the multi-constraint WTA problem in a multi-layer defense scenario. The solution for the problem aims to find a proper assignment of weapons to defend targets from attack with the objective of maximizing the survival asset value attained. The literature on WTA problem can be categorized mainly into two classes. First class relates to defense allocation models in which defensive weapons are assigned to targets without taking into account the behavior of the opposing side. The second class considers the opposing side’s actions as well as the defensive actions. However, we will only consider WTA from the defender’s point of view with known opponent’s attacking plan [31, 32].

Suppose that the defender sets up a multilayer defense system which contains D kinds of intercept weapons, for protecting its S strategic assets. These assets may be attacked by the attackers with A kinds of weapons. In general, each layer of the defense system is deployed only with the same type of weapon, for example, the low-altitude defense utilizing flak gun, high-altitude defense utilizing surface-to-air missile, space defense utilizing ballistic missile. Therefore we assume that the number of layers of the defense system is the same as the number of types of weapons owned by the defense system, that is, the number of layers of the defense system is D. Obviously, S assets are the targets intended to be protected by the defense system; on the other hand, the enemy’s offensive weapons are the targets intended to be intercepted by the defense system.

The WTA problem is to determine the number of different types d (d = 1, 2, ⋯ , D) of defending weapons deployed against the possible incoming enemy attacking weapons of type a (a = 1, 2, ⋯ , A), which will give maximum survivability to the assets s (s = 1, 2, ⋯ , S).

Decision variables of this problem are:

x_dsa: Number of defending weapons type d to be deployed to intercept attacking weapon type a to defend asset s (defense plan).

The total number of decision variables is D × S × A. The definitions of other notation are given in Table 1.

Table 1
Notation definitions

v_s: Value of asset s k_dsa: Probability of successful interception by one defending weapon of type d deployed to defend an asset s against an attacking weapon of type a (effectiveness) n_sa: Number of attacking weapons of type a aimed at asset s (attack plan)

B_d: Number of defending weapons of type d C_max: Maximum operating cost of weapons deployed c_d: Cost of operating one defending weapon of type d

g_sa: Probability that a single attacking weapon of type a destroys the asset s when it can penetrate the defending weapons (damage probability) M_d: Maximum available manpower to operate defending weapons of type d m_d: Manpower required per defending weapon of type d

G_s: Ground area available at asset s t_d: Ground area required by each defending weapon of type d

The probability that weapons deployed in d^th layer will not be able to intercept a single attacking weapon of type a on asset s is given by $(1 - k_{dsa})^{\frac{x_{dsa}}{n_{sa}}}$ . The probability that a single attacking weapon of type a is not intercepted by any layer on asset s is given by $\prod_{d = 1}^{D} (1 - k_{dsa})^{\frac{x_{dsa}}{n_{sa}}}$ . The probability that single attacking weapon type a destroys asset s is described as ${\prod_{d = 1}^{D} (1 - k_{dsa})^{\frac{x_{dsa}}{n_{sa}}}} g_{sa}$ . Then the survival probability P_surv of asset s by multiple layer defense when attacked by a types of attacking weapons is given by: $H (s) = P_{surv} = \prod_{a = 1}^{A} {[1 - {\prod_{d = 1}^{D} {(1 - k_{dsa})}^{\frac{x_{dsa}}{n_{sa}}}} g_{sa}]}^{n_{sa}}$

The total expected surviving value of all the assets being the objective function is to be maximized is $f (X) = \sum_{s = 1}^{S} v_{s} H (s)$ . Suppose that the enemy’s attack plan has been known, i.e., n_sa (s = 1, 2, . . . , S, a = 1, 2, . . ., A) has been given, then the mathematical model of WTA problem in multilayer defense scenario can be described as follows:

Objective function:

$\begin{matrix} max f (X) = & \sum_{s = 1}^{S} v_{s} \\ \prod_{a = 1}^{A} {1 - [\prod_{d = 1}^{D} (1 - k_{dsa})^{\frac{x_{dsa}}{n_{sa}}}] g_{sa}}^{n_{sa}} \end{matrix}$ (1)

Subject to constraints: $\sum_{s = 1}^{S} \sum_{a = 1}^{A} x_{dsa} \leq B_{d} d = 1, 2, \dots, D$ (2) $\sum_{d = 1}^{D} \sum_{a = 1}^{A} t_{d} x_{dsa} \leq G_{s} s = 1, 2, \dots S$ (3)

$\sum_{d = 1}^{D} \sum_{s = 1}^{S} \sum_{a = 1}^{A} c_{d} x_{dsa} \leq C_{max}$ (4) $\sum_{s = 1}^{S} \sum_{a = 1}^{A} m_{d} x_{dsa} \leq M_{d} d = 1, 2, \dots D$ (5)

The objective function Equation (1) is to maximize the total expected surviving value of all the protected assets. Constraint Equation (2) indicates the total number of defending weapons type d to be deployed at all assets against all attacking weapons must be equal or less than the total available number of weapons type d. Constraint Equation (3) indicates the total ground area required at each asset s allocated for each type d of defending weapon to be deployed shall be equal or less than the area available at each asset. Constraint Equation (4) indicates the total required cost for procurement, deployment and operation of each defending weapon must be equal or less than the total available budget for all types of defending weapons which are deployed at all assets against all attacking weapons. Constraint Equation (5) indicates the total required manpower to operate all deployed weapons of type d at all assets should be equal or less than the total available manpower which operate weapons of type d.

Equations (1)∼(5) comprise a general mathematical model of the WTA problem in the multi-layer defense scenario. One can make some simplification or extension to this general model to form a variety of WTA problems. The above WTA model is a nonlinear integer programming problem that has been proven to be NP-complete. This result means that its optimal solution cannot be obtained within polynomial time when using an exact algorithm based on conventional mathematical programming theory.

3 MAX-MIN ant system algorithm and improvement

The MMAS is an ACO (ant colony optimization) algorithm derived from Ant System and is one of the best ACO algorithms for the Traveling Salesman Problem (TSP). The MMAS algorithm can be formulated in Fig. 1, which is less formal than the original specification.

Fig.1

Sequential implementation of the MMAS.

We adopted an integer coding scheme when implementing MMAS algorithm. A complete solution to the WTA problem, which has D × S × A decision variables x_dsa, is represented as a row vector on the following order:

$\begin{matrix} X = [x_{1, 1, 1}, x_{1, 1, 2}, \dots, x_{1, 1, A}, \dots, x_{d, s, a}, \\ \dots, x_{D, S, 1}, x_{D, S, 2}, \dots, x_{D, S, A}] \end{matrix}$ (6)

The search space is divided into L stages, as shown in Fig. 2. The number of stage is equal to the number of decision variables, i.e. L = D × S × A. Each decision variable is associated with a stage in order of sequence of decision variables, i.e., stage 1 corresponds to x_1,1,1, stage 2 corresponds to x_1,1,2,..., the last stage corresponds to x_D,S,A. At stage i, there are U_i + 1 nodes numbered from 0 to U_i. The number at a node indicates the value taken by the decision variable at the stage where the node is situated. U_i is the maximum value possible for the decision variable at stage i to take.

Fig.2

Search space.

Suppose the decision variable associated with stage i is x_d,s,a. Then the possible maximum value at stage i, U_i can be simply set to B_d (the available number of defense weapon of type d). Or, in order to reduce the search space for large-scale WTA problems, taking constraints Equations (2)∼ (5) into account, U_i is determined as following. $U_{i} = (int) \min [B_{d}, \frac{G_{s}}{t_{d}} | s = 1, 2, \dots, S, \frac{C_{max}}{c_{d}}, \frac{M_{d}}{m_{d}}]$ (7)

Symbol (int) means taking the integer part of a real number. Equation (7) implies that when all decision varia1bles, except for the given variable x_d,s,a, are set to zero, and all constraints are satisfied, the maximum value that x_d,s,a can attain. At each stage in the search space, an ant chooses one node to pass through. Then all nodes stopped over by an ant from the first to last stage are lined up sequentially to construct a searching path which indicates a solution to the problem. Different to the regular ACO algorithm, in this paper pheromone trails are resided on nodes rather than on routes between two nodes. More pheromone trail one node possesses, more ants will be attracted to stop over that node. At iteration t and stage i, the probability of ant k choosing node j of stage i is also termed as transfer probability, which is denoted by $p_{ij}^{k} (t)$ . $p_{ij}^{k} (t)$ is calculated by the following formula: $p_{ij}^{k} (t) = {\begin{matrix} \frac{τ_{ij} (t - 1)}{\sum_{j \in {allow}_{i}^{k} (t)} τ_{ij} (t - 1)} for j \in {allow}_{i}^{k} (t) \\ 0 otherwise \end{matrix} i = 1, 2, . . ., L$ (8)

where τ_ij (t - 1) is the pheromone trail on node j of stage i at iteration $t - 1, {allow}_{i}^{k} (t)$ is the set of allowable nodes at stage i for ant k at iteration t that do not result in violation on all constraints. Of course set ${allow}_{i}^{k} (t)$ depends on the specific values taken by those decision variables of previous i-1 stages. ${allow}_{i}^{k} (t)$ can be determined through feasibility check done as follows: Given the values of previous i-1 decision variables, the values of decision variables after stage i are fixed to zero, only the value of decision variable x_d,s,a of stage i is allowed to change. Then we set x_d,s,a to 0, 1, 2,..., in turn, to check whether some constraint is violated. Once we find a value, to say num, results in violation in constraint, then stop the check and obtain set ${allow}_{i}^{k} (t)$ , which is a set of number 0, 1,. . ., num-1. Obviously, limiting the stop-over node at stage i to set ${allow}_{i}^{k} (t)$ grantees the solution constructed by an ant in search space is a feasible solution.

When each searching iteration is completed, the node’s pheromone trails need to update. Usually an elitist strategy can be used to update pheromone trail, namely, only the pheromone trails on nodes of the global optimal path (the path with maximum objective function) so far are strengthened, while the pheromone trails on other nodes are evaporated. When iteration t is completed, the pheromone trail on node j of stage i is updated to τ_ij (t), which is calculated by the following formula: $τ_{ij} (t) = {\begin{matrix} (1 - ρ) τ_{ij} (t - 1) + τ_{0} \frac{f_{best_so_far}}{f_{average} (t)}, node \\ j of stage i on the global optimal path \\ (1 - ρ) τ_{ij} (t - 1) othewise \end{matrix}$ (9)

where ρ is the evaporation factor of pheromone trail, τ₀ is the initial pheromone trail, f_{best
_s
o
_f
ar} is the best objective function so far, and f_average (t) is the average value of objective functions over all ants at iteration t. In the meantime, to prevent premature of the search process, we refer to the practice of MMAS, to limit node’s pheromone trail to an interval [τ_min, τ_max]. According to defacto experiment results, we made several improvements on MMAS abovementioned. First, it was possible that after limited iterations, all ants finally assembled to same path because the pheromone trail on the path associated with the best ant did not change again, which means the algorithm could not explore better solutions. And then, we changed pheromone trail updating strategy, instead of only considering the global optimal ant, the locally best optimal ant in each iteration was also taken into account for pheromone trail updating. A complementary pheromone trail updating rule was proposed: $τ_{ij} (t) = {\begin{matrix} (1 - ρ) τ_{ij} (t - 1) + τ_{0} \frac{f_{best_local}}{f_{average_local} (t)}, node \\ j of stage i on the every iteration \\ (1 - ρ) τ_{ij} (t - 1) othewise \end{matrix}$ (10)

Equations (9) and (10) constitute a combinatorial strategy for pheromone trail updating. After the locally best ant updating rule (Equation (10)) was applied m times consecutively, the globally optimal ant updating rule (Equation (9)) was executed once.

Second, for some randomly selected or the smallest decision variable x_d,s,a in stage i, we utilized greedy strategy to increase its value by an incremental Δx. If x_d,s,a + Δx meets constraints Equations (2)– (5), we reset x_d,s,a to x_d,s,a + Δx.

Third, at each iteration n ants’ moves were actually irrelevant, so we could deal with their moves concurrently. We utilized a kind of data structure called RDD (Resilient Distributed Datasets) in Spark framework to compute the objective function and constraints of WTA problem, so as to best utilize the parallel ability of Spark.

In Ref. [33], Marco Dorigo and Thomas Stützle have proved the convergence property of ACO algorithm. In general the computational complexity of an algorithm is measured by time complexity and space complexity. The time complexity is defined by O(g(N)), where N is the size of the problem; while the space complexity reflects the way the data are stored and retrieved. With the rapid development of computer technology and the dramatic improvement of storage capacity, nowadays the issue of space complexity is becoming less and less severe especially in a distributed computing environment. As a heuristic algorithm, the MMAS is a kind of polynomial time algorithm. This means it is able to find a solution to the WTA problem within a reasonable amount of computation time. In practice, as a surrogate, we can use the CPU time spent for solving an NP-hard problem which reflects the computational efficiency to measure the computational complexity of a heuristic algorithm.

4 Building experimental environment and numerical examples

We adopted Spark framework as the kernel of the distributed compute architecture. Now Spark technology is becoming an important and effective way to process big data through distributing executable code to every compute node for realizing program concurrency. Spark provides a series modules including real-time analysis, batch analysis, DataFrame framework (a kind of function similar to SQL queries), machine learning, graph analysis framework and so on. It can process structured, semi-structured and unstructured data, and quickly respond to business system.

We utilized Spark 2.1 on Hadoop 2.7 [34] version for our experiment. In our experiment architecture, the Hadoop tool mainly focused on data storage and the input data files were stored to HDFS file structure which could be accessed by Spark conveniently. Spark mainly focused on distributed computation. We set one master (driver) node and n work (compute) nodes in virtual machine to realize distributed computation. Of course the experiment configuration should be modified according to experiment requirements such as the number of work nodes. In this paper, we set two work nodes. Every compute node in virtual machine had one CPU core and 3GB RAM and linux ubuntu operation system to run some executors, while one executor set up N tasks to handle RDD datasets concurrently. The distributed compute architecture was shown in Fig. 3. The principle of Spark framework is to deploy source code to every work (compute) node without moving data files, and then run the source code concurrently by transmitting messages between nodes.

Fig.3

Architecture of ‘yarn-client’ mode in Spark framework.

We conducted our experiments in ‘yarn-client’ mode of Spark framework. One node was set as driver and another two nodes served as compute nodes. The jobs waiting for execution were controlled in driver node and actually executed in compute nodes. In every compute node, one or many executors (according to the parameters given in spark-submit command) were set up to store states and run jobs; while in every executor some tasks (according to the partition given in the program) were set up to complete jobs in parallel. Our programs were distributed to executors to run. Executors communicated with the driver node. Due to our hardware limitation, the Spark framework in the virtual machine allocated only two executors for our experiments.

In order to test the effectiveness and performance of the distributed implementation of the MMAS, a small-scale WTA problem was constructed. In Ref. [18], a numerical example of a small-scale WTA problem in a multi-layer defense scenario with the dimension of 2 × 3 ×2 was given, in which the defender deployed two types of defensive weapons at three assets against attacks from two types of offensive weapons, i.e., D = 2, S = 3 and A = 2.

We made a modification to some of the data in this example to construct a slightly different example. The theoretical optimal solution to the modified example will be taken as a benchmark to assess the performance of MMAS for solving the WTA problem. We call this modified example the “benchmark problem”. The parameters in the benchmark problem are set as follows.

The maximum number of available defending weapons of type 1 is B₁ = 100 and that of type 2 is B₂ = 50. The number of attacking weapons of type 1 and 2 is 50 and 29, respectively. The values of the first, second and third assets are v₁ = 400, v₂ = 300 and v₃ = 200. The attack plan is known to be n₁₁ = 5, n₁₂ = 9, n₂₁ = 25, n₂₂ = 7, n₃₁ = 20 and n₃₂ = 13. The area available at assets 1, 2 and 3 is G₁ = 2250, G₂ = 1500 and G₃ = 1950, respectively. The area required by defending weapons of type 1 and 2 (to be deployed) is t₁ = 34 and t₂ = 51, respectively. The cost of defending weapons of type 1 and 2 is C₁ = 20 and C₂ = 30, where the total allocated budget is C_max = 3800. The maximum manpower that is available for defending weapons of type 1 and 2 is M₁ = 350 and M₂ = 320, while the manpower required for operating each defending weapon of type 1 and 2 is m₁ = 5 and m₂ = 4. The effectiveness of defending weapons and the damage probability of the attacking weapons are given in Table 2.

Table 2

Interception and damage probabilities

Defending weapons type d	Asset s	Attacking weapons type a	Interception probability k_dsa	Damage probability g_sa
1	1	1	0.20	0.015
1	1	2	0.35	0.055
1	2	1	0.25	0.075
1	2	2	0.20	0.040
1	3	1	0.35	0.060
1	3	2	0.25	0.075
2	1	1	0.60	0.015
2	1	2	0.50	0.055
2	2	1	0.50	0.075
2	2	2	0.45	0.040
2	3	1	0.45	0.060
2	3	2	0.65	0.075

The parameters for MMAS are set as follows: Size of ant colony m = 40; Initial pheromone trail τ₀ = 1; Pheromone evaporation factor ρ = 0.01; Maximum pheromone trail τ_max = 10_{τ
₀}; Minimum pheromone trail τ_min = 0 . 01_{τ
₀}; Stopping criteria is that the maximum iteration times of 1000 are reached. For the benchmark problem, there are 12 decision variables (2 × 3 ×2, two types of weapons available to defend three assets against two types of attacking weapons), so the search space consists of 12 stages.

The benchmark problem has only 12 decision variables, for which the theoretical optimal solution can be obtained by existing optimization software. By using LINGO 11.0, we obtained the optimal objective function value of f^* = 537.516 or expressed it as a normalized value, $f^{*} = 537.516 / \sum_{s = 1}^{3} v_{s} = 0.59724$ . The theoretical optimal solution obtained was x₁₁₁ = 0, x₁₁₂ = 43, x₁₂₁ = 0, x₁₂₂ = 0, x₁₃₁ = 27, x₁₃₂ = 0 ; x₂₁₁ = 6, x₂₁₂ = 0, x₂₂₁ = 29, x₂₂₂ = 0, x₂₃₁ = 0, x₂₃₂ = 15 .

This optimal solution indicated that the total number of defending weapons of type I to be deployed was 70 and that of type II was 50. At the theoretical optimal solution, all of the constraints were met; two constraints, the available weapons of type II and the available manpower for weapons of type I, were tight to upper bound, while the other constraints were loose. This result provided a guideline for how to improve the optimal solution. For example, the decision-maker could improve the survival value of assets by reducing part of the weapons of type I and using the saved resources to augment weapons of type II.

We also constructed another 3 × 20 × 3 numerical example of the WTA problem. This example can be considered to be a large-scale WTA problem relative to the small-scale benchmark problem. The scenario of the problem was set as follows.

Defender: The defender plans to build a three-layer defense system with D = 3, in which ordinary missiles, tactical missiles and ballistic missiles are deployed at the first to the third layer, respectively. The number of strategic assets needed to be protected by the defender is 20, namely, S = 20. The available numbers of defensive weapons of types 1, 2 and 3 are B₁ = 560, B₂ = 300 and B₃ = 140, respectively. The manpower needed to operate per defensive weapon of type 1, 2 and 3 is m₁ = 6, m₂ = 5 and m₃ = 4, respectively. The available number of professionals to operate defensive weapons of types 1, 2 and 3 are M₁ = 3500, M₂ = 1600 and M₃ = 500, respectively. The operation and maintenance cost per defensive weapon of type 1, 2 and 3 is c₁ = 20, c₂ = 30 and c₃ = 40, respectively. The overall operation and maintenance budget for defensive weapons is C_max = 25000. The ground area that is required for deploying individual defensive weapons of type 1, 2 and 3 is t₁ = 32, t₂ = 48 and t₃ = 72, respectively. The value of each asset and the space available for deploying defensive weapons at each asset are listed in Appendix A of our prior work [20]. The successful intercept probabilities of various defensive weapons are given in Appendix B of our prior work [20].

Attacker: The enemy has three types of offensive weapons, A = 3. The number of attacking weapons of type 1, 2 and 3 is A₁ = 275, A₂ = 170, A₃ = 95, respectively. The enemy’s attacking plan and the destroy probabilities of various offensive weapons are given in Appendix C of our prior work [20].

5 Solving results and evaluation

We used MMAS algorithm to solve the benchmark problem under the experiment environment based on Spark cluster with Intel 2.6GHz and 3GB RAM on every node. The best objective function value over 10 random runs was 0.596377, the corresponding optimal solution was: $\begin{matrix} x_{1, 1, 1} & = 0, x_{1, 1, 2} = 43, x_{1, 2, 1} \\ = 0, x_{1, 2, 2} = 0, x_{1, 3, 1} = 26, x_{1, 3, 2} = 1 \end{matrix}$ $\begin{matrix} x_{2, 1, 1} & = 6, x_{2, 1, 2} = 1, x_{2, 2, 1} \\ = 28, x_{2, 2, 2} = 1, x_{2, 3, 1} = 0, x_{2, 3, 2} = 14 \end{matrix}$

Note that this solution was close to the theoretical optimal solution. At this solution, the numeric constraint on the weapons of type II and the manpower constraint on the weapons of type I were tight to upper bound, while other constraints were loose. This scenario was consistent with the features of the theoretical optimal solution. The results obtained for 10 consecutive random runs were listed in Table 3.

Table 3
Results of 10 MMAS Random Runs (2 × 3 ×2 problem)

Runs Optimum objective relative deviation

1 0.596377 −0.1445%

2 0.595043 −0.3679%

3 0.594565 −0.4479%

4 0.594535 −0.4529%

5 0.594431 −0.4703%

6 0.594389 −0.4774%

7 0.594378 −0.4792%

8 0.594326 −0.4879%

9 0.594321 −0.4888%

10 0.594320 −0.4889%

Table 3 also gave the relative deviations of the objective functions attained from the theoretical optimum. The coefficient of variation, denoted by CV, was used to measure the stability or robustness of an algorithm. $CV = \frac{σ}{μ}$ (11)

where μ and σ was the average value and standard deviation of the objective function over 10 runs, respectively. The smaller the coefficient of variation was, the more robust or stable the algorithm was. The CV for the benchmark problem was only 0.1073%. Very small relative deviations as well as coefficients of variation, means that MMAS algorithm can obtain satisfactory solution to the benchmark problem with high robustness.

For the 3 × 20 × 3 WTA problem, there are a total of 180 integer decision variables for which optimization software like Lingo is inapplicable. Now we applied MMAS to solve this problem. In order to get better solution, we set the size of ant colony m = 1000 and the maximum iteration 2000. Ten random runs were performed under the same experiment environment as that of benchmark problem. The results obtained for 10 random runs were listed in Table 4. The CV was 0.2714%. The average CPU time over 10 runs was 19.2 minutes. Very small coefficient of variation implied that even for a large-scale WTA problem, MMAS could obtain a robust result.

Table 4

Results of 10 MMAS Random Runs(3 × 20 × 3 problem)

Runs	Optimum objective
1	0.655402
2	0.655103
3	0.654436
4	0.654151
5	0.653614
6	0.653285
7	0.651935
8	0.651835
9	0.651311
10	0.650000
average CPU Time	19.2min

We also compute some results under the same scheme and parameter settings, except that the size of ant colony m = 2000 and the maximum iteration was increased to 5000. We obtained the best objective function value of 0.66803, whose optimal solution was shown in Table 5.

Table 5

Optimal Solution to the 3 × 20 × 3 WTA Problem

	Protected assets	Defense plan x_d,s,a
		Against attacking weapon type
		a = 1	a = 2	a = 3
Defending weapon type d = 1	s = 1	19	25	5
	s = 2	24	17	35
	s = 3	13	0	0
	s = 4	11	17	16
	s = 5	2	30	20
	s = 6	3	62	6
	s = 7	44	9	3
	s = 8	14	20	6
	s = 9	14	23	0
	s = 10	1	0	16
	s = 11	1	13	1
	s = 12	0	15	1
	s = 13	0	12	2
	s = 14	0	10	5
	s = 15	0	0	0
	s = 16	0	12	0
	s = 17	11	1	0
	s = 18	0	0	0
	s = 19	3	0	0
	s = 20	0	0	8
Defending weapon type d = 2	s = 1	16	7	6
	s = 2	2	2	0
	s = 3	0	7	4
	s = 4	4	4	7
	s = 5	3	9	2
	s = 6	3	0	2
	s = 7	3	2	1
	s = 8	11	4	2
	s = 9	0	0	1
	s = 10	3	12	3
	s = 11	18	2	18
	s = 12	23	0	17
	s = 13	0	15	5
	s = 14	0	5	13
	s = 15	0	6	0
	s = 16	0	0	0
	s = 17	5	26	8
	s = 18	0	4	0
	s = 19	0	0	3
	s = 20	0	6	6
Defending weapon type d = 3	s = 1	1	0	4
	s = 2	2	0	1
	s = 3	9	3	10
	s = 4	0	5	0
	s = 5	1	0	1
	s = 6	0	0	4
	s = 7	1	6	1
	s = 8	3	0	1
	s = 9	2	0	6
	s = 10	7	0	0
	s = 11	2	0	0
	s = 12	8	0	0
	s = 13	11	6	0
	s = 14	20	0	0
	s = 15	0	3	6
	s = 16	0	0	0
	s = 17	0	0	1
	s = 18	0	0	0
	s = 19	0	0	0
	s = 20	0	0	0

At this optimal solution, the total cost required was 25000 which was tight to upper bound. The numbers of various defensive weapons actually deployed and manpower required for each weapon type were listed in Table 6. The spaces actually occupied at each asset were listed in Table 7.

Table 6

Numbers of various weapons deployed and manpower required

Weapon d	number deployed	Manpower required
1	550	3300
2	300*	1500
3	125	500*

*constraint was exactly satisfied.

Table 7

Spaces required at each asset

Asset s	Ground area required	Asset s	Ground area required
1	3320	11	2448
2	2840	12	3008
3	2528	13	2632
4	2488	14	2784
5	2480	15	936
6	2800	16	384
7	2656	17	2328
8	2384	18	192
9	1808	19	240
10	1912	20	832

Next we evaluated the distributed computation performance of the algorithm. We built an extreme case in which the algorithm performed only one iteration but generated 1000 ants by using one executor and two executors respectively. Each executor set up only one task. The snapshots of the results were shown in Figs. 4 and 5.

Fig.4

Result for generating 1000 ants using one executor.

Fig.5

Result for generating 1000 ants using two executors.

We found that the number and input data size of total tasks (accumulatively created rather than generated simultaneously) distributed to two executors was equal to that distributed to one executor. The distributed compute worked actually and assigned jobs to two executors almost equally. The run time recorded in Spark was optimized slightly, because the pheromone trail updating in the algorithm necessitated shuffling all objective function values computed by ants. The shuffling procedure consumed some time. Of course the computation efficiency can be improved by amplifying the number of executors.

Abovementioned experiment set only one task to run the program in each executor. However each executor could set up N tasks running concurrently like threads in computer system. Then we deliberated whether the computation efficiency could be optimized by using more tasks. We set different partitions to arouse needed tasks. Figure 6 depicts the relationship between the running time for one iteration generating 1000 ants with the number of tasks. Here the running time refers to the average time over 10 random runs.

Fig.6

Run time(ms) for tasks num from 1-10.

From Fig. 6 we found that the best computation efficiency derived from 4 tasks set by each executor. For more than 4 tasks, with the number of tasks increased the computation efficiency declined. This is because there were no enough threads in computer node to set up more tasks so that many tasks had to share one thread in fact. The experiment illustrated that the tasks set in every executor worked and the computation efficiency could be optimized by setting proper number of tasks.

Abovementioned experiment and analysis only addressed the benchmark problem. Furthermore we considered the large-scale WTA problem with 180 decision variables. The aim is to demonstrate whether the computation efficiency was still satisfactory when using Spark framework to large scale WTA problems. We still performed one time of iteration generating 1000 ants under 2 × 3 ×2 problem and 3 × 20 × 3 problem respectively, where 2 executors were set up with 4 tasks in each executor. The results were shown in Figs. 7 and 8.

Fig.7

Task Time in 2 × 3 ×2 problem.

Fig.8

Task Time in 3 × 20 × 3 problem.

Both experiments produced a total of 21 tasks (accumulatively created). Because the number of variables in 3 × 20 × 3 problem was 15 times larger than that in benchmark problem, the large-scale problem had more input data size (288.5M compared to 10.9M). However the task running time for 3 × 20 × 3 problem was just about 2 times longer than that for the benchmark problem (19s compared to 10s or 8s). This demonstrates that the Spark framework is suitable for large-scale iterative heuristic computation. It may achieve satisfactory performance in both solution quality and computational efficiency when used to even larger scale WTA problems as well as similar combinatorial optimization problems.

6 Conclusion

The WTA problem is a classic NP-complete problem from military operations research. In big data environment new algorithm using more effective computation framework needs to put forward for disposing of this kind of problem. In this paper, addressing the WTA problem in a multi-layer defense scenario, a distributed MMAS algorithm based on Spark framework were developed. The algorithm implementation schemes were presented. Through a small-scale benchmark problem and a large-scale problem, the performance of the algorithm was assessed. The results show that the distributed MMAS algorithm based on Spark framework are effective for WTA problems and can achieve a high-quality approximate solution with high robustness. From performance improvement point of view, many heuristic algorithms can be incorporated into Spark framework for solving such large-scale iterative optimization problems as WTA problem.

References

Manne

A.S.

, A Target-assignment problem, Operations Research 6 (1958), 346–351.

Day

R.H.

, Allocating weapons to target complexes by means of nonlinear programming, Operation Research 14 (1966), 992–1013.

Lloyd

S.P.

, Witsenhausen

H.S.

, Weapons allocation is NP-complete, in Proceedings of IEEE Summer Conference on Simulation, pp. 1054–1058, Reno, Nevada, 1986.

DenBroader

G.G.

, Ellison

R.E.

and Emerling

, On optimum target assignments, Operation Research 7 (1959), 322–326.

Orlin

, Optimal weapons allocation against layered defenses, Naval Research Logistics 34 (1987), 605–617.

Frini

, Guitouni

and Benaskeur

, Solving Dynamic Multi-Criteria Resource-Target Allocation Problem Under Uncertainty: A Comparison of Decomposition and Myopic Approaches, International Journal of Information Technology & Decision Making 16 (2017), 1465–1496.

Davis

M.T.

, Robbins

M.J.

and Lunday

B.J.

, Approximate dynamic programming for missile defense interceptor fire control, European Journal of Operational Research 259 (2017), 873–886.

, Xing

and Tian

, MOQPSO-D/S for Air and Missile Defense WTA Problem under Uncertainty, Mathematical Problems in Engineering 2017 (2017), 1–13.

Shalumov

and Shima

, Weapon– Target-Allocation Strategies in Multiagent Target– Missile– Defender Engagement, Journal of Guidance, Control, and Dynamics 40 (2017), 2452–2464.

10.

Rezende

M.D.

, De Lima BSLP and Guimarães

, A Greedy Ant Colony System for Defensive Resource Assignment Problems, Applied Artificial Intelligence 32 (2018), 138–152.

11.

Kum

H.C.

, Joy Stewart

, Rose

R.A.

and Duncan

D.F.

, Using big data for evidence based governance in child welfare, Children and Youth Services Review 58 (2015), 127–136.

12.

Kopriva

, Calderwood

, Weckopp

S.C.

and Koprivova

, Plant sulfur and Big Data, Plant Science 241 (2015), 1–10.

13.

Hong

, Murray

A.T.

and Rey

, Obstacle-avoiding shortest path derivation in a multicore computing environment, Computers, Environment and Urban Systems 55 (2016), 1–10.

14.

Fan

, Xiao

, Madsen

and Wang

, Temporal knowledge discovery in big BAS data for building energy management, Energy and Buildings 109 (2015), 75–89.

15.

Marx

, Biology: The big challenges of big data, Nature 498 (2013), 255–260.

16.

Chen

H.C.

, Chiang

R.H.L

and Storey

V.C.

, Business Intelligence And Analytics: From Big Data To Big Impact, Mis Quarterly 36 (2012), 1165–1188.

17.

Jaiswal

N.K.

, Shrotri

P.K.

and Nagabhushana

B.S.

, Optimal weapon mix, deployment and allocation problems in multiple layer defence, American Journal of Mathematical and Management Sciences 13 (1993), 53–82.

18.

Jaiswal

N.K.

, Military operations research: Quantitative decision making. Norwell: MA: Kluwer Academic Publishers; 1997.

19.

Fang

and Shi

, Swarm Intelligence Optimization Algorithms for Weapon Target Allocation Problem in Multilayer Defense Scenario, Mathematics in Practice & Theory 43 (2013), 76–84.

20.

Cao

, Fang

, Distributed Computation Based on Spark Framework: A Solution for Weapon Target Assignment Decision Making, in Proceedings of Service System Engineering Conference & Symposium on Analytics and Risk 2017, pp. 125–137, Shanghai, China, 2017.

21.

Ozden

S.G.

, Smith

A.E.

and Gue

K.R.

, Solving large batches of traveling salesman problems with parallel and distributed computing, Computers & Operations Research 85 (2017), 87–96.

22.

Archibald

, Maier

, McCreesh

, Stewart

and Trinder

, Replicable parallel branch and bound search, Journal of Parallel and Distributed Computing 113 (2018), 92–114.

23.

Chongdarakul

, Sophatsathit

and Lursinsap

, Theoretical and heuristic aspects of heterogeneous system scheduling with constraints on client’s multiple I/O ports, Future Generation Computer Systems 78 (2018), 901–919.

24.

Juarez

, Ejarque

and Badia

R.M.

, Dynamic energy-aware scheduling for parallel task-based application in cloud computing, Future Generation Computer Systems 78 (2018), 257–271.

25.

Sahni

and Vidyarthi

D.P.

, A Cost-Effective Deadline-Constrained Dynamic Scheduling Algorithm for Scientific Workflows in a Cloud Environment, IEEE Transactions on Cloud Computing 6 (2018), 2–18.

26.

Stützle

and Hoos

H.H.

, MAX-MIN Ant System, Future Generation Computer Systems 16 (2000), 889–914.

27.

Abdelali

, Fang

, Decision Making Using Parallel Ant Colony Optimization On Weapon Target Assignment In Multilayer Air Defense, Proceedings of the 11th International Conference on Industrial Management, pp. 9–18, Tokyo, 2012.

28.

Spark

, Spark 2015. Available from: http://spark.apache.org/docs/latest/.

29.

Qiao

, Zhang

, Li

, Ding

, Jia

and Wang

, A Parallel Approach for Frequent Subgraph Mining in a Single Large Graph Using Spark, Applied Sciences 8 (2018), 230–248.

30.

, Li

, Zhuang

, Wang

, Zhou

, Efficient Distributed Smith-Waterman Algorithm Based on Apache Spark, in 2017 IEEE 10th International Conference on Cloud Computing (CLOUD), pp. 608–615, Honolulu, CA, USA: IEEE, 2017.

31.

B.S.

, E

F.J.

and F

K.A.

, Integer prim-read solutions to a class of target defense problems, Operations Research 33 (1985), 726–745.

32.

B.D.

, L

H.M.

and A

L.D.

, Missile defense and intercept allocation by neuro-dynamic programming, IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans 30 (2000), 42–51.

33.

Dorigo

and Stützle

. Ant Colony Optimization. Cambridge, Massachusetts:, MIT Press; 2004.

34.

Hadoop

, HDFS Users Guide 2015. Available from: https://hadoop.apache.org/docs/stable/hadoop-project-dist/hadoop-hdfs/HdfsUserGuide.html.

v_s: Value of asset s	k_dsa: Probability of successful interception by one defending weapon of type d deployed to defend an asset s against an attacking weapon of type a (effectiveness)	n_sa: Number of attacking weapons of type a aimed at asset s (attack plan)
B_d: Number of defending weapons of type d	C_max: Maximum operating cost of weapons deployed	c_d: Cost of operating one defending weapon of type d
g_sa: Probability that a single attacking weapon of type a destroys the asset s when it can penetrate the defending weapons (damage probability)	M_d: Maximum available manpower to operate defending weapons of type d	m_d: Manpower required per defending weapon of type d
G_s: Ground area available at asset s	t_d: Ground area required by each defending weapon of type d

Runs	Optimum objective	relative deviation
1	0.596377	−0.1445%
2	0.595043	−0.3679%
3	0.594565	−0.4479%
4	0.594535	−0.4529%
5	0.594431	−0.4703%
6	0.594389	−0.4774%
7	0.594378	−0.4792%
8	0.594326	−0.4879%
9	0.594321	−0.4888%
10	0.594320	−0.4889%