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.
ManneA.S., A Target-assignment problem, Operations Research6 (1958), 346–351.
2.
DayR.H., Allocating weapons to target complexes by means of nonlinear programming, Operation Research14 (1966), 992–1013.
3.
LloydS.P., WitsenhausenH.S., Weapons allocation is NP-complete, in Proceedings of IEEE Summer Conference on Simulation, pp. 1054–1058, Reno, Nevada, 1986.
4.
DenBroaderG.G., EllisonR.E. and EmerlingL., On optimum target assignments, Operation Research7 (1959), 322–326.
5.
OrlinD., Optimal weapons allocation against layered defenses, Naval Research Logistics34 (1987), 605–617.
6.
FriniA., GuitouniA. and BenaskeurA., Solving Dynamic Multi-Criteria Resource-Target Allocation Problem Under Uncertainty: A Comparison of Decomposition and Myopic Approaches, International Journal of Information Technology & Decision Making16 (2017), 1465–1496.
7.
DavisM.T., RobbinsM.J. and LundayB.J., Approximate dynamic programming for missile defense interceptor fire control, European Journal of Operational Research259 (2017), 873–886.
8.
XuH., XingQ. and TianZ., MOQPSO-D/S for Air and Missile Defense WTA Problem under Uncertainty, Mathematical Problems in Engineering2017 (2017), 1–13.
9.
ShalumovV. and ShimaT., Weapon– Target-Allocation Strategies in Multiagent Target– Missile– Defender Engagement, Journal of Guidance, Control, and Dynamics40 (2017), 2452–2464.
10.
RezendeM.D., De Lima BSLP and GuimarãesS, A Greedy Ant Colony System for Defensive Resource Assignment Problems, Applied Artificial Intelligence32 (2018), 138–152.
11.
KumH.C., Joy StewartC., RoseR.A. and DuncanD.F., Using big data for evidence based governance in child welfare, Children and Youth Services Review58 (2015), 127–136.
12.
KoprivaS., CalderwoodA., WeckoppS.C. and KoprivovaA., Plant sulfur and Big Data, Plant Science241 (2015), 1–10.
13.
HongI., MurrayA.T. and ReyS., Obstacle-avoiding shortest path derivation in a multicore computing environment, Computers, Environment and Urban Systems55 (2016), 1–10.
14.
FanC., XiaoF., MadsenH. and WangD., Temporal knowledge discovery in big BAS data for building energy management, Energy and Buildings109 (2015), 75–89.
15.
MarxV., Biology: The big challenges of big data, Nature498 (2013), 255–260.
16.
ChenH.C., ChiangR.H.L and StoreyV.C., Business Intelligence And Analytics: From Big Data To Big Impact, Mis Quarterly36 (2012), 1165–1188.
17.
JaiswalN.K., ShrotriP.K. and NagabhushanaB.S., Optimal weapon mix, deployment and allocation problems in multiple layer defence, American Journal of Mathematical and Management Sciences13 (1993), 53–82.
FangW. and ShiX., Swarm Intelligence Optimization Algorithms for Weapon Target Allocation Problem in Multilayer Defense Scenario, Mathematics in Practice & Theory43 (2013), 76–84.
20.
CaoM., FangW., 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.
OzdenS.G., SmithA.E. and GueK.R., Solving large batches of traveling salesman problems with parallel and distributed computing, Computers & Operations Research85 (2017), 87–96.
22.
ArchibaldB., MaierP., McCreeshC., StewartR. and TrinderP., Replicable parallel branch and bound search, Journal of Parallel and Distributed Computing113 (2018), 92–114.
23.
ChongdarakulW., SophatsathitP. and LursinsapC., Theoretical and heuristic aspects of heterogeneous system scheduling with constraints on client’s multiple I/O ports, Future Generation Computer Systems78 (2018), 901–919.
24.
JuarezF., EjarqueJ. and BadiaR.M., Dynamic energy-aware scheduling for parallel task-based application in cloud computing, Future Generation Computer Systems78 (2018), 257–271.
25.
SahniJ. and VidyarthiD.P., A Cost-Effective Deadline-Constrained Dynamic Scheduling Algorithm for Scientific Workflows in a Cloud Environment, IEEE Transactions on Cloud Computing6 (2018), 2–18.
26.
StützleT and HoosH.H., MAX-MIN Ant System, Future Generation Computer Systems16 (2000), 889–914.
27.
AbdelaliB., FangW., 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.
QiaoF., ZhangX., LiP., DingZ., JiaS. and WangH., A Parallel Approach for Frequent Subgraph Mining in a Single Large Graph Using Spark, Applied Sciences8 (2018), 230–248.
30.
XuB., LiC., ZhuangH., WangJ., WangQ., ZhouX., 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.
AB.S., EF.J. and FK.A., Integer prim-read solutions to a class of target defense problems, Operations Research33 (1985), 726–745.
32.
PB.D., LH.M. and AL.D., Missile defense and intercept allocation by neuro-dynamic programming, IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans30 (2000), 42–51.
33.
DorigoM. and StützleT.. Ant Colony Optimization. Cambridge, Massachusetts:, MIT Press; 2004.
