#### **6. Summarization**

The consideration of meta-heuristic is widly used in a lot of fields. Deffirent meta-heuristic algorithms are developed for solving deffirent problems, especially combinational optimiza‐ tion problems. In this chapter, we discussed a special case of MLLS problem. First, the general definition of MLLS problem was described. We shown its solution structure and explained its NP completeness. Second, we reviewed the meta-heuristic algorithms which have been use to solve the MLLS problem and pointed their merits and demerits. Based on the recognition, third, we investigated those implement techniques used in the meta-heuristic algorithms for solving the MLLS problems. And two criteria of distance and range were firstly defined to evaluate the effective of those techniques. We brifly discussed the mechanisms and character‐ istics of the techniques by using these two criteria, and provided simulation experiments to prove the correctness of the two criteria and to explain the performance and utility of them. This is one of our contributions. Fourth, we presented a succinct and easily implemented IVND algorithm and six implemental techniques for solving the MLLS problem. The IVND algorithm was evaluated by using 176 benchmark problems of different scales (small, medium and large) from literatures. The results on 96 small-sized benchmark problems showed the IVND algorithm of good optimality; it could find 100% optimal solutions in repeated 10 runs using a very low computing time(less than 1s for each problem). Experiments on other two sets of benchmark problems (40 medium-sized problems and 40 large-sized problems) showed it good efficiency and effectiveness on solving MLLS problem with product structure complex. For the medium-sized problems, the IVND can use 10 repeated runs to reach 40% of the 40 problems of their previous known best solutions and find another 20% of new best known solutions. By more repeated runs, our IVND algorithm actually had updated 30% (12 prob‐ lems) of the best known solutions, and computing efficiency was also very acceptable because the longest computing time for each problem was less than one minute. For the 40 large-sized problems, the IVND algorithm delivered even more exciting results on the quality of solution. Comparison of the best solutions achieved with the new method and those established by previous methods including HGA, MMAS, and PGA shows that the IVND algorithm with the six implemental techniques are till now among the best methods for solving MLLS problem with product structure complexity considered, not only because it is easier to be understood and implemented in practice, but more importantly, it also provides quite good solutions in very acceptable time.

## **Acknowledgements**

**P N Kmax Avg. Cost of 10 runs Comp. time of 10 runs (s)**

50 200 8 263,684 420

50 200 9 263,688 527

50 200 10 263,678 567

The consideration of meta-heuristic is widly used in a lot of fields. Deffirent meta-heuristic algorithms are developed for solving deffirent problems, especially combinational optimiza‐ tion problems. In this chapter, we discussed a special case of MLLS problem. First, the general definition of MLLS problem was described. We shown its solution structure and explained its NP completeness. Second, we reviewed the meta-heuristic algorithms which have been use to solve the MLLS problem and pointed their merits and demerits. Based on the recognition, third, we investigated those implement techniques used in the meta-heuristic algorithms for solving the MLLS problems. And two criteria of distance and range were firstly defined to evaluate the effective of those techniques. We brifly discussed the mechanisms and character‐ istics of the techniques by using these two criteria, and provided simulation experiments to prove the correctness of the two criteria and to explain the performance and utility of them. This is one of our contributions. Fourth, we presented a succinct and easily implemented IVND algorithm and six implemental techniques for solving the MLLS problem. The IVND algorithm was evaluated by using 176 benchmark problems of different scales (small, medium and large) from literatures. The results on 96 small-sized benchmark problems showed the IVND algorithm of good optimality; it could find 100% optimal solutions in repeated 10 runs using a very low computing time(less than 1s for each problem). Experiments on other two sets of benchmark problems (40 medium-sized problems and 40 large-sized problems) showed it good efficiency and effectiveness on solving MLLS problem with product structure complex. For the medium-sized problems, the IVND can use 10 repeated runs to reach 40% of the 40 problems of their previous known best solutions and find another 20% of new best known solutions. By more repeated runs, our IVND algorithm actually had updated 30% (12 prob‐ lems) of the best known solutions, and computing efficiency was also very acceptable because the longest computing time for each problem was less than one minute. For the 40 large-sized problems, the IVND algorithm delivered even more exciting results on the quality of solution. Comparison of the best solutions achieved with the new method and those established by previous methods including HGA, MMAS, and PGA shows that the IVND algorithm with the six implemental techniques are till now among the best methods for solving MLLS problem with product structure complexity considered, not only because it is easier to be understood and implemented in practice, but more importantly, it also provides quite good solutions in

**Table 9.** Experimental results of different parameters for medium-sized problem

104 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

**6. Summarization**

very acceptable time.

This work is supported by the Japan Society for the Promotion of Science (JSPS) under the grant No. 24510192.

## **Author details**

Ikou Kaku1\*, Yiyong Xiao2 and Yi Han3

\*Address all correspondence to<EMAIL_ADDRESS>
1 Department of Environmental and Information studies, Tokyo City University, Japan

2 School of Reliability and System Engineering, Beihang University, Beijing, China

3 College of Business Administration, Zhejiang University of Technology, Hangzhou, China

## **References**

[8] Dellaert, N, & Jeunet, J. (2000). Solving large unconstrained multilevel lot-sizing problems using a hybrid genetic algorithm, *International Journal of Production Re‐ search*, 38(5), 1083-1099.

[22] Pitakaso, R, Almeder, C, Doerner, K. F, & Hartlb, R. F. ant system for unconstrained multi-level lot-sizing problems, *Computer & Operations Research*, , 34, 2533-2552. [23] Raza, A. S, & Akgunduz, A. (2008). A comparative study of heuristic algorithms on Economic Lot Scheduling Problem, *Computers and Industrial Engineering.* 55(1),

A Comparative Study on Meta Heuristic Algorithms for Solving Multilevel Lot-Sizing Problems

http://dx.doi.org/10.5772/55279

107

[24] Steinberg, E, & Napier, H. A. (1980). Optimal multilevel lot sizing for requirements

[25] Tang, O. (2004). Simulated annealing in lot sizing problems, *International Journal of*

[26] Veral, E. A. and LaForge R. L., (1985). The performance of a simple incremental lotsizing rule in a multilevel inventory environment, *Decision Sciences*, , 16, 57-72. [27] Xiao, Y. Y, Kaku, I, Zhao, X. H, & Zhang, R. Q. (2011a). A variable neighborhood search based approach for uncapacitated multilevel lot-sizing problems, *Computers &*

[28] Xiao, Y. Y, Zhao, X. H, Kaku, I, & Zhang, R. Q. (2011b). A reduced variable neighbor‐ hood search algorithm for uncapacitated multilevel lot-sizing problems, *European*

[29] Xiao, Y. Y, Zhao, X. H, Kaku, I, & Zhang, R. Q. (2012). Neighborhood search techni‐ ques for solving uncapacitated multilevel lot-sizing problems, *Computers & Opera‐*

[30] Yelle, L. E. (1979). Materials requirements lot sizing: a multilevel approach, *Interna‐*

[31] Zhangwill, W. I. (1968). Minimum concave cost flows in certain network, *Management*

[32] Zhangwill, W. I. (1969). A backlogging model and a multi-echelon model of a dy‐ namic economic lot size production system-a network approach, *Management Sci‐*

planning systems, *Management Science*, 26(12), 1258-1271.

*Production Economics*, , 88, 173-181.

*Industrial Engineering*, , 60, 218-227.

*tions Research*, 57((3)

*Scienc*e, , 14, 429-450.

*ence*, , 15, 506-527.

*Journal of Operational Research, 214*, 223-231.

*tional Journal of Production Research*, , 17, 223-232.

94-109.

[22] Pitakaso, R, Almeder, C, Doerner, K. F, & Hartlb, R. F. ant system for unconstrained multi-level lot-sizing problems, *Computer & Operations Research*, , 34, 2533-2552.

[8] Dellaert, N, & Jeunet, J. (2000). Solving large unconstrained multilevel lot-sizing problems using a hybrid genetic algorithm, *International Journal of Production Re‐*

[9] Dellaert, N, Jeunet, J, & Jonard, N. (2000). A genetic algorithm to solve the general multi-level lot-sizing problem with time-varying costs, *International Journal of Produc‐*

[10] Han, Y, Tang, J. F, Kaku, I, & Mu, L. F. (2009). Solving incapacitated multilevel lotsizing problem using a particle swarm optimization with flexible inertial weight,

[11] Han, Y, Kaku, I, Tang, J. F, Dellaert, N, Cai, J. H, Li, Y. L, & Zhou, G. G. (2011). A scatter search approach for uncapacitated multilevel lot-sizing problems, *Internation‐*

[12] Han, Y, Cai, J. H, Kaku, I, Lin, H. Z, & Guo, H. D. (2012a). A note on "a genetic algo‐ rithm for the preemptive and non-preemptive multi-mode resource-constrained

[13] Han, Y, Cai, J. H, Kaku, I, Li, Y. L, Chen, Y. Z, & Tang, J. F. (2012b). Evolutionary algorithms for solving unconstrained multilevel lot-sizing problem with series struc‐

[14] Hansen, P, & Mladenovic, N. (2001a). Variable neighborhood search: principles and

[15] Hansen, P, Mladenovic, N, & Perez, D. (2001b). Variable neighborhood decomposi‐

[16] Hansen, P, & Mladenovic, N. and Pe´rez J. A. M., (2008). Variable neighborhood

[17] Homberger, J. (2008). A parallel genetic algorithm for the multilevel unconstrained

[18] Hoos, H. H, & Thomas, S. (2005). Stochastic Local Search-Foundations and Applica‐

[19] Kaku, I, & Xu, C. H. (2006). A soft optimization approach for solving a complicated multilevel lot-sizing problem, *in Proc. 8th Conf. Industrial Management, ICIM'200638*

[20] Kaku, I, Li, Z. S, & Xu, C. H. (2010). Solving Large Multilevel Lot-Sizing Problems with a Simple Heuristic Algorithm Based on Segmentation, *International Journal of In‐*

[21] Mladenovic, N, & Hansen, P. (1997). Variable neighborhood search, *Computers & Op‐*

applications, *European Journal of Operational Research*, 130(3), 449-467.

search, *European Journal of Operational Research*, Editorial., 191, 593-595.

lot-sizing problem, *INFORMS Journal on Computing*, 20(1), 124-132

*novative Computing, Information and Control*, 6(3), 817-827.

*al Journal of Innovative Computing, Information and Control*, 7(7), 4833-4848.

project scheduling problem", *Applied Mechanics and Materials*, , 127, 527-530.

*Computers and Mathematics with Applications*, , 57, 1748-1755.

ture, *Journal of Shanghai Jiaotong University*, 17(1), 39-44.

tion search, *Journal of Heuristics*, , 7, 335-350.

tions, Morgan Kaufmann Publishers.

*erations Research*, , 24, 1097-1100.

*search*, 38(5), 1083-1099.

*tion Economics*, , 68, 241-257.

106 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

**Chapter 5**

**Provisional chapter**

**A Two-Step Optimisation Method for Dynamic**

**A Two-Step Optimisation Method for Dynamic**

The weapon target assignment (WTA) problem has been designed to match the Command & Control (C2) requirement in military context, of which the goal is to find an allocation plan enabling to treat a specific scenario in assigning available weapons to oncoming targets. The WTA always get into situation weapons defending an area or assets from an enemy aiming to destroy it. Because of the uniqueness of each situation, this problem must be solved in real-time and evolve accordingly to the aerial/ground situation. By the past, the WTA was solved by an operator taking all the decisions, but because of the complexity of the modern warfare, the resolution of the WTA in using the power of computation is inevitable to make possible the resolution in real time of very complex scenarii involving different type of targets. Nowadays, in most of the C2 this process is designed in order to be as a support for a human operator and in helping him in the decision making process. The operator will

The WTA arouses a great interest among the researcher community and many methods have been proposed to cope with this problem. Besides, the WTA has been proved to be NP-complete [1]. There are two families of WTA: the Static WTA (SWTA) and the Dynamic WTA (DWTA). In both of these problems, the optimality of one solution is based either on the minimisation of the target survival after the engagement or the maximisation of the survivability of the defended assets. The main feature of the SWTA stands in its single stage approach. It is considered that all the information about the situations are provided and the problem can be considered as a constrained resource assignment problem. In contrast, the DWTA is a multi-stage problem in which the result of each stage is assessed, then use to update the aerial situation for the upcoming stages. The DWTA can also be expressed as

> ©2012 Siarry et al., licensee InTech. This is an open access chapter distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. © 2013 Leboucher et al.; licensee InTech. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

© 2013 Leboucher et al., licensee InTech. This is a paper distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

**Weapon Target Assignment Problem**

**Weapon Target Assignment Problem**

Cédric Leboucher, Hyo-Sang Shin, Patrick Siarry, Rachid Chelouah,

Cédric Leboucher, Hyo-Sang Shin, Patrick Siarry,

Rachid Chelouah, Stéphane Le Ménec and

Additional information is available at the end of the chapter

Stéphane Le Ménec and Antonios Tsourdos

Additional information is available at the end of the chapter

give its final green light to proceed the intervention.

Antonios Tsourdos

10.5772/53606

**1. Introduction**

http://dx.doi.org/10.5772/53606

**Provisional chapter**

## **A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem**

Cédric Leboucher, Hyo-Sang Shin, Patrick Siarry, Rachid Chelouah, Stéphane Le Ménec and Antonios Tsourdos Cédric Leboucher, Hyo-Sang Shin, Patrick Siarry, Rachid Chelouah, Stéphane Le Ménec and Antonios Tsourdos Additional information is available at the end of the chapter

Additional information is available at the end of the chapter 10.5772/53606

http://dx.doi.org/10.5772/53606

## **1. Introduction**

The weapon target assignment (WTA) problem has been designed to match the Command & Control (C2) requirement in military context, of which the goal is to find an allocation plan enabling to treat a specific scenario in assigning available weapons to oncoming targets. The WTA always get into situation weapons defending an area or assets from an enemy aiming to destroy it. Because of the uniqueness of each situation, this problem must be solved in real-time and evolve accordingly to the aerial/ground situation. By the past, the WTA was solved by an operator taking all the decisions, but because of the complexity of the modern warfare, the resolution of the WTA in using the power of computation is inevitable to make possible the resolution in real time of very complex scenarii involving different type of targets. Nowadays, in most of the C2 this process is designed in order to be as a support for a human operator and in helping him in the decision making process. The operator will give its final green light to proceed the intervention.

The WTA arouses a great interest among the researcher community and many methods have been proposed to cope with this problem. Besides, the WTA has been proved to be NP-complete [1]. There are two families of WTA: the Static WTA (SWTA) and the Dynamic WTA (DWTA). In both of these problems, the optimality of one solution is based either on the minimisation of the target survival after the engagement or the maximisation of the survivability of the defended assets. The main feature of the SWTA stands in its single stage approach. It is considered that all the information about the situations are provided and the problem can be considered as a constrained resource assignment problem. In contrast, the DWTA is a multi-stage problem in which the result of each stage is assessed, then use to update the aerial situation for the upcoming stages. The DWTA can also be expressed as

©2012 Siarry et al., licensee InTech. This is an open access chapter distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. © 2013 Leboucher et al.; licensee InTech. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. © 2013 Leboucher et al., licensee InTech. This is a paper distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

a succession of SWTA, but the optimality of the final solution cannot be guaranteed since it comes to the same as in a greedy optimisation process. One other difference stands in the temporal dimension of the DWTA which does not exist in the SWTA. The weapons can intervene within a certain defined time because of physical, technical and operational constraints. In addition, any DWTA problem has to be solved in using real-time oriented method. By real-time it is assumed that the proposed method has to be fast enough to provide an engagement solution before the oncoming targets reached their goals. Most of the previous work on the WTA was focused on the resolution of the SWTA. Hosein and Athans was among the first to defined a cost function based on the assets [2]. This model was reused in [3] and [4]. Later, a second modelling has been proposed by Karasakal in [5], aiming to maximise the probability to suppress all the oncoming targets. One other variant of the WTA is to take into account a *threatening* value to each target according to its features and the importance of the protected assets. The research of Johansson and Falkman in [6] proposed a good overview of all the possible modelling, taking into account both of the developed models and enabling to take into consideration the value of the defended assets and the threatening index of the incoming target. Kwon *et al.* explored further this principle in assigning a value to the weapon in [7]. The main researches on the SWTA started around the 1950's. Most of the proposals to solve this problem was based on the classic optimisation processes: branch and bound algorithm appears in the survey conducted in 2006 by Cai *et al.* [8]. With the evolution of the new technologies, some more complex methods appeared in [9] in using the neural networks. The genetic algorithms are used in [4], [10] and [11] to solve the SWTA. Cullenbine is using the Tabu Search method in [12]. A different approach angle is used in [13]. In this former approach the WTA problem is treated as a resources management problem and the reactivity of the proposed approach, based on the Tabu Search, was able to deal with real-time requirement. Nowadays, this method is used in many military systems like Rapid Anti-Ship Missile-Integrated Defense System (RAIDS) [14] [13]. Whereas the SWTA had aroused the interest of the researchers first, lately the DWTA had attracted much more attention. The first DWTA was proposed by Hosein and Athans around 1990 [15]. In the proposed approach of Hosein and Athans, a sub-optimal solution was studied in order to determine a solution which was considered as "good enough" [15]. Later they developed exact methods to solve some simplified DWTA [16] [17]. The dynamic programming enables to solve the DWTA in [18], but under the assumption that all the engaged targets are destroyed. Despite its study to decrease the computational time, the problem was still treated in exponential complexity [18]. A more complex DWTA model is designed by Wu *et al.* in [19] where the temporal dimension is included under the form of firing time windows.

10.5772/53606

111

http://dx.doi.org/10.5772/53606

weapons to the targets, then the optimal firing sequence is obtained in using the results obtained from the first step. The optimal assignment is determined in using the graph theory, and more especially the Hungarian method in a bipartite graph. The used of this method in the first step is motivated by the optimality and the polynomial complexity of the method. Then, the computation of the firing sequence is optimised in using a particle swarm optimisation (PSO) process combined to the evolutionary game theory (EGT). This former

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

The performance index for the evaluation of the assignment is determined by three different criteria: the capacity to propose an early fire, the width of the firing time window and the minimisation of the overflying of the defended area by our own assets for security purpose. The quality of the firing sequence is obtained from the reactivity of the algorithm to treat the targets in the earliest possible way, the respect of the system constraints and the avoidance

The goal of this chapter is to develop an efficient method to solve a target based DWTA problem involving technical and operational constraints. A mission is considered as achieve only if no targets reach the defending area. The contribution of this paper includes the

• Design of a DWTA model taking into account target trajectories and operational and

• A two-step approach based on the graph theory, then a combined swarm intelligence and

• The targets are following a Bezier's curve trajectory in order to sow the confusion among

• The success of one fire is determined by the draw of one random number in [0, 1], then

The rest of this chapter is organised as follows: the second section describes the details of the studied DWTA, the third section introduces the background of Hungarian algorithm, particle swarm optimisation and evolutionary game theory. Then the fourth section details the proposed method before testing and analysing the obtained results by using a dedicated simulator designed for this DWTA problem. The chapter ends with the conclusion of this

The assignment problem arouses the interest of the researchers community for a while. The principle consists of finding a maximum weight matching in a weighted bipartite graph. It is more commonly formulated as: there are two distinct sets, one contain agents, the other one contain tasks. Note that each agent has his own ability to realise a job properly and this capability is represented by a quantitative value. The global objective to assign all the agents to the jobs can be achieved in one optimal way. The Hungarian method published by

evolutionary game method to solve the DWTA in an optimised fashion. • The reducing computational load in order to enable real-time applications.

method has been proved as efficient in general allocation resources problem [20].

of idle time when a firing is possible.

technical constraints on the weapons.

compared to a probability threshold of kill (PK).

**2. Background of the proposed approach**

**2.1. The Hungarian algorithm**

following aspects:

study.

the defending system.

The studied DWTA in this chapter slightly differs from the common defined DWTA in the literature. The proposed model has been designed to fit a specific requirement from industrial application. Whereas the classic problem is considering a multi-stage approach, the solved problem considers a continuous time where the targets are evolving in the space according to their own objectives and features. The targets trajectories are designed in using Bezier's curves defined by 4 control points which the last one is set to the centre of area that we are defending. The choice of this trajectory modelling has been done in order to add more diversity in the tested scenarii. The current situation is updated in real time, which means that the proposed algorithm must be as reactive as possible to cope with the oncoming targets. In order to solve the presented problem in the fastest and the most accurate way, a two-step optimisation method is proposed. The first step optimise the assignment of the weapons to the targets, then the optimal firing sequence is obtained in using the results obtained from the first step. The optimal assignment is determined in using the graph theory, and more especially the Hungarian method in a bipartite graph. The used of this method in the first step is motivated by the optimality and the polynomial complexity of the method. Then, the computation of the firing sequence is optimised in using a particle swarm optimisation (PSO) process combined to the evolutionary game theory (EGT). This former method has been proved as efficient in general allocation resources problem [20].

The performance index for the evaluation of the assignment is determined by three different criteria: the capacity to propose an early fire, the width of the firing time window and the minimisation of the overflying of the defended area by our own assets for security purpose. The quality of the firing sequence is obtained from the reactivity of the algorithm to treat the targets in the earliest possible way, the respect of the system constraints and the avoidance of idle time when a firing is possible.

The goal of this chapter is to develop an efficient method to solve a target based DWTA problem involving technical and operational constraints. A mission is considered as achieve only if no targets reach the defending area. The contribution of this paper includes the following aspects:

The rest of this chapter is organised as follows: the second section describes the details of the studied DWTA, the third section introduces the background of Hungarian algorithm, particle swarm optimisation and evolutionary game theory. Then the fourth section details the proposed method before testing and analysing the obtained results by using a dedicated simulator designed for this DWTA problem. The chapter ends with the conclusion of this study.

## **2. Background of the proposed approach**

## **2.1. The Hungarian algorithm**

2 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

included under the form of firing time windows.

a succession of SWTA, but the optimality of the final solution cannot be guaranteed since it comes to the same as in a greedy optimisation process. One other difference stands in the temporal dimension of the DWTA which does not exist in the SWTA. The weapons can intervene within a certain defined time because of physical, technical and operational constraints. In addition, any DWTA problem has to be solved in using real-time oriented method. By real-time it is assumed that the proposed method has to be fast enough to provide an engagement solution before the oncoming targets reached their goals. Most of the previous work on the WTA was focused on the resolution of the SWTA. Hosein and Athans was among the first to defined a cost function based on the assets [2]. This model was reused in [3] and [4]. Later, a second modelling has been proposed by Karasakal in [5], aiming to maximise the probability to suppress all the oncoming targets. One other variant of the WTA is to take into account a *threatening* value to each target according to its features and the importance of the protected assets. The research of Johansson and Falkman in [6] proposed a good overview of all the possible modelling, taking into account both of the developed models and enabling to take into consideration the value of the defended assets and the threatening index of the incoming target. Kwon *et al.* explored further this principle in assigning a value to the weapon in [7]. The main researches on the SWTA started around the 1950's. Most of the proposals to solve this problem was based on the classic optimisation processes: branch and bound algorithm appears in the survey conducted in 2006 by Cai *et al.* [8]. With the evolution of the new technologies, some more complex methods appeared in [9] in using the neural networks. The genetic algorithms are used in [4], [10] and [11] to solve the SWTA. Cullenbine is using the Tabu Search method in [12]. A different approach angle is used in [13]. In this former approach the WTA problem is treated as a resources management problem and the reactivity of the proposed approach, based on the Tabu Search, was able to deal with real-time requirement. Nowadays, this method is used in many military systems like Rapid Anti-Ship Missile-Integrated Defense System (RAIDS) [14] [13]. Whereas the SWTA had aroused the interest of the researchers first, lately the DWTA had attracted much more attention. The first DWTA was proposed by Hosein and Athans around 1990 [15]. In the proposed approach of Hosein and Athans, a sub-optimal solution was studied in order to determine a solution which was considered as "good enough" [15]. Later they developed exact methods to solve some simplified DWTA [16] [17]. The dynamic programming enables to solve the DWTA in [18], but under the assumption that all the engaged targets are destroyed. Despite its study to decrease the computational time, the problem was still treated in exponential complexity [18]. A more complex DWTA model is designed by Wu *et al.* in [19] where the temporal dimension is

The studied DWTA in this chapter slightly differs from the common defined DWTA in the literature. The proposed model has been designed to fit a specific requirement from industrial application. Whereas the classic problem is considering a multi-stage approach, the solved problem considers a continuous time where the targets are evolving in the space according to their own objectives and features. The targets trajectories are designed in using Bezier's curves defined by 4 control points which the last one is set to the centre of area that we are defending. The choice of this trajectory modelling has been done in order to add more diversity in the tested scenarii. The current situation is updated in real time, which means that the proposed algorithm must be as reactive as possible to cope with the oncoming targets. In order to solve the presented problem in the fastest and the most accurate way, a two-step optimisation method is proposed. The first step optimise the assignment of the

The assignment problem arouses the interest of the researchers community for a while. The principle consists of finding a maximum weight matching in a weighted bipartite graph. It is more commonly formulated as: there are two distinct sets, one contain agents, the other one contain tasks. Note that each agent has his own ability to realise a job properly and this capability is represented by a quantitative value. The global objective to assign all the agents to the jobs can be achieved in one optimal way. The Hungarian method published by Kuhn in 1955 is inspired by the work of two Hungarian researchers: Dénes Kõnig and Jenõ Egervàry [21]. This method has been proved as optimal and polynomial.

10.5772/53606

113

http://dx.doi.org/10.5772/53606

**2.3. The evolutionary game theory**

in the presence of the others.

*2.3.1. Evolutionary Stable Strategies*

distribution in the population is:

all *p* �= *p*∗,

strategy *q*.

*2.3.2. Replicator dynamics*

described using notations as follows. *ei* is the *i*

(probability distributions over the pure strategies *ei*).

*Aij* = *π*(*ei*,*ej*) is the *m* × *m* payoff matrix.

an individual using strategy *q* in this mixed population, be

for all *ε* > 0 "sufficiently small", for agents minimizing their fitness.

The evolutionary game theory appeared initially in a biologic context. The need to model the evolution phenomena led to the use of mathematical theory of the games to explain the strategic aspect of the evolution. Over the last few decades, the EGT has aroused interest of the economists, sociologists, social scientists, as well as the philosophers. Although the evolutionary game theory found its origin in biologic science, such an expansion to different fields can be explained by three facts. First of all, the notion of evolution has to be understood as the change of beliefs and norms over time. Secondly, the modelling of strategies change provides a social aspect which matches exactly the social system interactions. Finally, it was important to model dynamically the interactions within a population, which was one of the missing elements of the classic game theory. As in this former domain, the evolutionary game theory deals with the equilibrium which is a key point in both of the theories. Here the equilibrium point is called the evolutionary stable strategy. The principle of the EGT is not only based on the strategy performance obtained by itself, but also the performance obtained

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

An Evolutionary Stable Strategy (ESS) is a strategy such that, if all members of a population adopt it, then no mutant strategy could invade the population under the influence of natural selection. Assume we have a mixed population consisting of mostly *p*<sup>∗</sup> individuals (agents playing optimal strategy *p*∗) with a few individuals using strategy *p*. That is, the strategy

(1 − *ε*)*p*<sup>∗</sup> + *εp* where *ε* > 0 is the small frequency of *p* users in the population. Let the fitness, i.e. payoff of

*π*(*q*,(1 − *ε*)*p*<sup>∗</sup> + *εp*).

Then, an interpretation of Maynard Smith's requirement [25] for *p*<sup>∗</sup> to be an ESS is that, for

*π*(*p*,(1 − *ε*)*p*<sup>∗</sup> + *εp*) > *π*(*p*∗,(1 − *ε*)*p*<sup>∗</sup> + *εp*)

A common way to describe strategy interactions is using matrix games. Matrix games are

∆*<sup>m</sup>* ≡ {*p* = (*p*1, ..., *pm*) | *p*<sup>1</sup> + ... + *pm* = 1, 0 ≤ *pi* ≤ 1} is the set of mixed strategies

Then, *π*(*p*, *q*) = *p* · *Aq<sup>T</sup>* is the payoff of agents playing strategy *p* facing agents playing

*th* unit line vector for *i* = 1, ..., *m*.

 Then *G* = (*A*, *T*, *E*), where *E* denotes the set of the edges linking the set of Agents with the set of Tasks.  The function *P* : (*A* ∪ *T*) −→ **R** represents the potential if *p*(*i*) + *p*(*j*) ≤ *c*(*i*, *j*) for each *i* ∈ *A* and *j* ∈ *T*. The potential value is obtained in summing all the potential from the set *A* ∪ *T*: *p* = ∑*v*∈(*A*∪*T*) *p*(*v*). The Hungarian method enables to find the perfect matching and the potential equalising the cost and the value, which means that both of them are optimal.

## **2.2. The particle swarm optimisation**

Kennedy and Eberhart [22], the founders of the PSO method, was inspired by the behaviour of animals acting in society to achieve a goal. For example, the birds, the fishes, etc. can make up a very efficient collective intelligence in exchanging very basic information about the environment in which they are evolving. From this starting point, the authors have designed the PSO method to solve many optimisation problems over the last few decades. A swarm is composed of particles (representing a solution) flying on the solution space and communicating with the neighbourhood the quality of the current position.

The first step in PSO algorithm is to define the moving rules on the solution space for the particles. Let *X<sup>t</sup> <sup>i</sup>* = [*x<sup>t</sup> <sup>i</sup>*1, *<sup>x</sup><sup>t</sup> <sup>i</sup>*2,..., *<sup>x</sup><sup>t</sup> iD*, ], *<sup>x</sup><sup>t</sup> id* ∈ {0, 1} be a particle in a population of *P* particles and composed of *D* dimensions. The velocity of this particle is denoted as *Vt <sup>i</sup>* = [*v<sup>t</sup> <sup>i</sup>*1, *<sup>v</sup><sup>t</sup> <sup>i</sup>*2,..., *<sup>v</sup><sup>t</sup> iD*, ], *<sup>v</sup><sup>t</sup> id* <sup>∈</sup> **<sup>R</sup>**. Then, as in the PSO method described in [23], the next step is to define the best position for the particle *P<sup>t</sup> <sup>i</sup>* = [*p<sup>t</sup> <sup>i</sup>*1, *<sup>p</sup><sup>t</sup> <sup>i</sup>*2,..., *<sup>p</sup><sup>t</sup> iD*, ], *<sup>p</sup><sup>t</sup> id* <sup>∈</sup> **<sup>R</sup>** , and the best position *P<sup>t</sup> <sup>g</sup>* = [*p<sup>t</sup> <sup>g</sup>*1, *<sup>p</sup><sup>t</sup> <sup>g</sup>*2,..., *<sup>p</sup><sup>t</sup> gD*, ], *<sup>p</sup><sup>t</sup> gd* <sup>∈</sup> **<sup>R</sup>** of the entire population at the iteration *<sup>t</sup>*. The velocity of the particle *i* is adjusted in respect to the direction *d* with:

$$
\sigma\_{id}^{t+1} = \omega\_1 \upsilon\_{id}^t + \omega\_2(\mathbf{x}(t) - \mathbf{x}\_{ind}(t)) + \omega\_3(\mathbf{x}(t) - \mathbf{x}\_{global}(t)).
$$

The parameter *ω*<sup>1</sup> denotes the weight of the particle inertia. *ω*<sup>2</sup> is the coefficient associated to the individual coefficient. Then, *ω*<sup>3</sup> denotes the social coefficient. The final step of one PSO iteration is to update the position of the particles in using the following formula:

$$\mathbf{X}\_{i}^{t+1} = \mathbf{X}\_{i}^{t} + V\_{i}^{t}.$$

This process enables to find an optimal solution in repeating this process. In the classical version of the PSO [24], these coefficients are drawn randomly in order to maximise the exploration of the solution space by the particles. It can be a weakness when the computational time has to be the shortest possible. The studied method proposes to decrease this computational time in using the Evolutionary Game Theory (EGT) to determine the three coefficients *ω*1, *ω*<sup>2</sup> and *ω*3. Since the particles are "jumping" on the solution space, the creators wished to limit the jumped distance to a maximum length determined by the value of *Vmax* usually determined with respect to the solution space.

## **2.3. The evolutionary game theory**

4 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

which means that both of them are optimal.

**2.2. The particle swarm optimisation**

*<sup>i</sup>* = [*x<sup>t</sup>*

step is to define the best position for the particle *P<sup>t</sup>*

*iD*, ], *<sup>v</sup><sup>t</sup>*

*<sup>g</sup>*1, *<sup>p</sup><sup>t</sup>*

*<sup>i</sup>*1, *<sup>x</sup><sup>t</sup>*

*<sup>g</sup>*2,..., *<sup>p</sup><sup>t</sup>*

of *Vmax* usually determined with respect to the solution space.

the particles. Let *X<sup>t</sup>*

*<sup>i</sup>*1, *<sup>v</sup><sup>t</sup>*

best position *P<sup>t</sup>*

*<sup>i</sup>*2,..., *<sup>v</sup><sup>t</sup>*

*<sup>g</sup>* = [*p<sup>t</sup>*

*vt*+<sup>1</sup> *id* <sup>=</sup> *<sup>ω</sup>*1*v<sup>t</sup>*

*Vt <sup>i</sup>* = [*v<sup>t</sup>*

Egervàry [21]. This method has been proved as optimal and polynomial.

Kuhn in 1955 is inspired by the work of two Hungarian researchers: Dénes Kõnig and Jenõ

Let *G* be a complete bipartite graph composed, one hand by a set of |*A*| agents and one other hand by |*T*| tasks. Then *G* = (*A*, *T*, *E*), where *E* denotes the set of the edges linking the set of Agents with the set of Tasks.  The function *P* : (*A* ∪ *T*) −→ **R** represents the potential if *p*(*i*) + *p*(*j*) ≤ *c*(*i*, *j*) for each *i* ∈ *A* and *j* ∈ *T*. The potential value is obtained in summing all the potential from the set *A* ∪ *T*: *p* = ∑*v*∈(*A*∪*T*) *p*(*v*). The Hungarian method enables to find the perfect matching and the potential equalising the cost and the value,

Kennedy and Eberhart [22], the founders of the PSO method, was inspired by the behaviour of animals acting in society to achieve a goal. For example, the birds, the fishes, etc. can make up a very efficient collective intelligence in exchanging very basic information about the environment in which they are evolving. From this starting point, the authors have designed the PSO method to solve many optimisation problems over the last few decades. A swarm is composed of particles (representing a solution) flying on the solution space and

The first step in PSO algorithm is to define the moving rules on the solution space for

*P* particles and composed of *D* dimensions. The velocity of this particle is denoted as

The parameter *ω*<sup>1</sup> denotes the weight of the particle inertia. *ω*<sup>2</sup> is the coefficient associated to the individual coefficient. Then, *ω*<sup>3</sup> denotes the social coefficient. The final step of one PSO iteration is to update the position of the particles in using the following formula:

This process enables to find an optimal solution in repeating this process. In the classical version of the PSO [24], these coefficients are drawn randomly in order to maximise the exploration of the solution space by the particles. It can be a weakness when the computational time has to be the shortest possible. The studied method proposes to decrease this computational time in using the Evolutionary Game Theory (EGT) to determine the three coefficients *ω*1, *ω*<sup>2</sup> and *ω*3. Since the particles are "jumping" on the solution space, the creators wished to limit the jumped distance to a maximum length determined by the value

*Xt*+<sup>1</sup> *<sup>i</sup>* <sup>=</sup> *<sup>X</sup><sup>t</sup>*

*id* ∈ {0, 1} be a particle in a population of

*iD*, ], *<sup>p</sup><sup>t</sup>*

*id* <sup>∈</sup> **<sup>R</sup>** , and the

*<sup>i</sup>*2,..., *<sup>p</sup><sup>t</sup>*

*gd* <sup>∈</sup> **<sup>R</sup>** of the entire population at the iteration *<sup>t</sup>*. The

*id* <sup>∈</sup> **<sup>R</sup>**. Then, as in the PSO method described in [23], the next

*<sup>i</sup>*1, *<sup>p</sup><sup>t</sup>*

*<sup>i</sup>* = [*p<sup>t</sup>*

*id* <sup>+</sup> *<sup>ω</sup>*2(*x*(*t*) <sup>−</sup> *xind*(*t*)) + *<sup>ω</sup>*3(*x*(*t*) <sup>−</sup> *xglobal*(*t*)).

*<sup>i</sup>* <sup>+</sup> *<sup>V</sup><sup>t</sup> i* .

*iD*, ], *<sup>x</sup><sup>t</sup>*

communicating with the neighbourhood the quality of the current position.

*<sup>i</sup>*2,..., *<sup>x</sup><sup>t</sup>*

*gD*, ], *<sup>p</sup><sup>t</sup>*

velocity of the particle *i* is adjusted in respect to the direction *d* with:

The evolutionary game theory appeared initially in a biologic context. The need to model the evolution phenomena led to the use of mathematical theory of the games to explain the strategic aspect of the evolution. Over the last few decades, the EGT has aroused interest of the economists, sociologists, social scientists, as well as the philosophers. Although the evolutionary game theory found its origin in biologic science, such an expansion to different fields can be explained by three facts. First of all, the notion of evolution has to be understood as the change of beliefs and norms over time. Secondly, the modelling of strategies change provides a social aspect which matches exactly the social system interactions. Finally, it was important to model dynamically the interactions within a population, which was one of the missing elements of the classic game theory. As in this former domain, the evolutionary game theory deals with the equilibrium which is a key point in both of the theories. Here the equilibrium point is called the evolutionary stable strategy. The principle of the EGT is not only based on the strategy performance obtained by itself, but also the performance obtained in the presence of the others.

#### *2.3.1. Evolutionary Stable Strategies*

An Evolutionary Stable Strategy (ESS) is a strategy such that, if all members of a population adopt it, then no mutant strategy could invade the population under the influence of natural selection. Assume we have a mixed population consisting of mostly *p*<sup>∗</sup> individuals (agents playing optimal strategy *p*∗) with a few individuals using strategy *p*. That is, the strategy distribution in the population is:

$$(1 - \varepsilon)p^\* + \varepsilon p$$

where *ε* > 0 is the small frequency of *p* users in the population. Let the fitness, i.e. payoff of an individual using strategy *q* in this mixed population, be

$$
\pi(q,(1-\varepsilon)p^\* + \varepsilon p).
$$

Then, an interpretation of Maynard Smith's requirement [25] for *p*<sup>∗</sup> to be an ESS is that, for all *p* �= *p*∗,

$$
\pi(p,(1-\varepsilon)p^\* + \varepsilon p) > \pi(p^\*,(1-\varepsilon)p^\* + \varepsilon p),
$$

for all *ε* > 0 "sufficiently small", for agents minimizing their fitness.

#### *2.3.2. Replicator dynamics*

A common way to describe strategy interactions is using matrix games. Matrix games are described using notations as follows. *ei* is the *i th* unit line vector for *i* = 1, ..., *m*.

*Aij* = *π*(*ei*,*ej*) is the *m* × *m* payoff matrix.

∆*<sup>m</sup>* ≡ {*p* = (*p*1, ..., *pm*) | *p*<sup>1</sup> + ... + *pm* = 1, 0 ≤ *pi* ≤ 1} is the set of mixed strategies (probability distributions over the pure strategies *ei*).

Then, *π*(*p*, *q*) = *p* · *Aq<sup>T</sup>* is the payoff of agents playing strategy *p* facing agents playing strategy *q*.

Another interpretation is *π*(*p*, *q*) being the fitness of a large population of agents playing pure strategies (*p* describing the agent proportion in each behaviour inside a population) with respect to a large *q* population.

10.5772/53606

115

http://dx.doi.org/10.5772/53606

Where t denotes the simulation time and the *Wi*, *i* ∈ {1, 2, 3} and *Tj*, *j* ∈ {1, 2} represent the weapon *i* and the target *j*. The variable *FTi* denotes the Firing Time computed for the weapon *i*. The engagement plan evolves accordingly to the situation and depends on the current simulation time and on the aerial situation. In this application, the engagement plan is recomputed every *P* seconds in order to make up a very reactive engagement plan capable of dealing with the trickier cases in which the targets are constantly changing their

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

Since the complexity of the presented problem grows exponentially with the number of targets and weapons, to design an algorithm capable of handling the real-time computation, but taking into account very diversified performance indexes, the choice of two different steps was natural. Lloyd [1] proved that the DWTA is a NP-complete problem. Therefore, it is hard to find an exact optimisation method capable of solving the DWTA problem in an exact way within a reasonable time. The reasonable time implies a high frequency which can enable the real-time application of the optimisation method. Note that the system must be able to provide results in real-time in the DWTA problem since the engagement changes as the targets keep evolving in the aerial space during the computation. With these reasons, using a heuristic approach providing suboptimal solutions in real-time could be the best way to handle the DWTA problem. One other problem is to be able to quantify the quality of one proposed solution: the performance index of the assignment, and the firing sequence cannot be evaluated in using the same performance criterion. Whereas the assignment is evaluated from the system point of view, the firing sequence is evaluated from the weapons features. Dividing the problem into two parts could lead to the modification of the solution space and the optimum solution could be not the same as the optimal one if the entire solution space was considered. However regarding the real-time computation, and the heterogeneity of the considered criteria, dividing this problem into two steps makes sense in terms of reality and

applicability of the designed model, and in terms of quality of the found solution.

the initial number of weapons is greater than the number of oncoming targets.

with a target in the earliest possible date in order to avoid any risk.

In order to assign the targets to the available weapons, the Hungarian algorithm is used. The weapons and the targets are modelled as an asymmetric bipartite graph. The Figure 1 shows an example of possible assignment graph used. In the studied problem, it is assumed that

The quality of the proposed assignment is evaluated according to three different criteria: the capacity to propose an early fire, the width of the firing time window and the minimisation of the overflying of the defended area by our own assets for security purpose. These criteria

• the capability of the system to propose an early firing date, and then its ability to cope

• the width of the firing time windows represents the time that we have to cope with one target, then the larger is this firing time windows, the more time we have to propose one

**3.2. The choice of a two-step optimisation method**

**3.3. The weapon-target assignment**

respectively represent:

engagement solution,

trajectories.

The replicator equation (RE) is an Ordinary Differential Equation expressing the difference between the fitness of a strategy and the average fitness in the population. Lower payoffs (agents are minimizers) bring faster reproduction in accordance with Darwinian natural selection process.

$$\dot{p}\_i = -p\_i(e\_i \cdot A p^T - p \cdot A p^T)$$

RE for *i* = 1, ..., *m* describes the evolution of strategy frequencies *pi*. Moreover, for every initial strategy distribution *p*(0) ∈ *δm*, there is an unique solution *p*(*t*) ∈ *δ<sup>m</sup>* for all *t* ≥ 0 that satisfies the replicator equation. The replicator equation is the most widely used evolutionary dynamics. It was introduced for matrix games by Taylor and Jonker [26].

Note that this introducing to the EGT and the PSO comes from one of our previous study in [20].

## **3. The formulation of the DWTA: A target-based model**

A common approach to the DWTA problem based on the capabilities of the defence system to minimise the probability that a target can leak the proposed engagement plan. However, the problem dealt with in this study is slightly different from the classic DWTA. Whereas the classic DWTA is considering a multi-stage approach, the solved problem considers a continuous time where the targets are evolving in the space according to their own objectives and features. The proposed model has been designed to fit a specific requirement from industrial application, which explains this different approach.

The weapon system is defending an area from oncoming targets. This area is represented by a circle. All the weapons are disposed randomly within this range. In order to make the problem as general as possible, it is assumed that each weapon has its own velocity and own range. The targets are aiming the centre of the area to defend. The trajectories of the targets are designed by Bezier's curves in using 4 control points, all randomly drawn on the space, but the last point which is set to the centre of the area to defend. Thus, the problem presents a high diversity and can test the proposed method in the most of possible tricky cases. It is also assumed that the velocity of the targets and of the weapons are constant.

The assignment and the firing time sequence are computed in real-time in order to validate the reactivity of the studied algorithm. Which means that a timer is set at the beginning of the simulation, and the position of the targets evolves accordingly to this time.

#### **3.1. The engagement plan**

The engagement plan represents the solution space. An engagement plan is composed of one assignment weapon/target and completed by a date to fire. For example, if the following situation involves 3 weapons and 2 targets, a possible engagement plan *EP* could be:

$$EP(t) = \{ (\mathcal{W}\_1, T\_2, t + FT\_1); (\mathcal{W}\_3, T\_1, t + FT\_3) \}$$

Where t denotes the simulation time and the *Wi*, *i* ∈ {1, 2, 3} and *Tj*, *j* ∈ {1, 2} represent the weapon *i* and the target *j*. The variable *FTi* denotes the Firing Time computed for the weapon *i*. The engagement plan evolves accordingly to the situation and depends on the current simulation time and on the aerial situation. In this application, the engagement plan is recomputed every *P* seconds in order to make up a very reactive engagement plan capable of dealing with the trickier cases in which the targets are constantly changing their trajectories.

## **3.2. The choice of a two-step optimisation method**

6 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

with respect to a large *q* population.

selection process.

[20].

Another interpretation is *π*(*p*, *q*) being the fitness of a large population of agents playing pure strategies (*p* describing the agent proportion in each behaviour inside a population)

The replicator equation (RE) is an Ordinary Differential Equation expressing the difference between the fitness of a strategy and the average fitness in the population. Lower payoffs (agents are minimizers) bring faster reproduction in accordance with Darwinian natural

*p*˙*<sup>i</sup>* = −*pi*(*ei* · *Ap<sup>T</sup>* − *p* · *ApT*)

RE for *i* = 1, ..., *m* describes the evolution of strategy frequencies *pi*. Moreover, for every initial strategy distribution *p*(0) ∈ *δm*, there is an unique solution *p*(*t*) ∈ *δ<sup>m</sup>* for all *t* ≥ 0 that satisfies the replicator equation. The replicator equation is the most widely used evolutionary

Note that this introducing to the EGT and the PSO comes from one of our previous study in

A common approach to the DWTA problem based on the capabilities of the defence system to minimise the probability that a target can leak the proposed engagement plan. However, the problem dealt with in this study is slightly different from the classic DWTA. Whereas the classic DWTA is considering a multi-stage approach, the solved problem considers a continuous time where the targets are evolving in the space according to their own objectives and features. The proposed model has been designed to fit a specific requirement from

The weapon system is defending an area from oncoming targets. This area is represented by a circle. All the weapons are disposed randomly within this range. In order to make the problem as general as possible, it is assumed that each weapon has its own velocity and own range. The targets are aiming the centre of the area to defend. The trajectories of the targets are designed by Bezier's curves in using 4 control points, all randomly drawn on the space, but the last point which is set to the centre of the area to defend. Thus, the problem presents a high diversity and can test the proposed method in the most of possible tricky cases. It is

The assignment and the firing time sequence are computed in real-time in order to validate the reactivity of the studied algorithm. Which means that a timer is set at the beginning of

The engagement plan represents the solution space. An engagement plan is composed of one assignment weapon/target and completed by a date to fire. For example, if the following situation involves 3 weapons and 2 targets, a possible engagement plan *EP* could be:

*EP*(*t*) = {(*W*1, *T*2, *t* + *FT*1);(*W*3, *T*1, *t* + *FT*3)}

also assumed that the velocity of the targets and of the weapons are constant.

the simulation, and the position of the targets evolves accordingly to this time.

dynamics. It was introduced for matrix games by Taylor and Jonker [26].

**3. The formulation of the DWTA: A target-based model**

industrial application, which explains this different approach.

**3.1. The engagement plan**

Since the complexity of the presented problem grows exponentially with the number of targets and weapons, to design an algorithm capable of handling the real-time computation, but taking into account very diversified performance indexes, the choice of two different steps was natural. Lloyd [1] proved that the DWTA is a NP-complete problem. Therefore, it is hard to find an exact optimisation method capable of solving the DWTA problem in an exact way within a reasonable time. The reasonable time implies a high frequency which can enable the real-time application of the optimisation method. Note that the system must be able to provide results in real-time in the DWTA problem since the engagement changes as the targets keep evolving in the aerial space during the computation. With these reasons, using a heuristic approach providing suboptimal solutions in real-time could be the best way to handle the DWTA problem. One other problem is to be able to quantify the quality of one proposed solution: the performance index of the assignment, and the firing sequence cannot be evaluated in using the same performance criterion. Whereas the assignment is evaluated from the system point of view, the firing sequence is evaluated from the weapons features. Dividing the problem into two parts could lead to the modification of the solution space and the optimum solution could be not the same as the optimal one if the entire solution space was considered. However regarding the real-time computation, and the heterogeneity of the considered criteria, dividing this problem into two steps makes sense in terms of reality and applicability of the designed model, and in terms of quality of the found solution.

## **3.3. The weapon-target assignment**

In order to assign the targets to the available weapons, the Hungarian algorithm is used. The weapons and the targets are modelled as an asymmetric bipartite graph. The Figure 1 shows an example of possible assignment graph used. In the studied problem, it is assumed that the initial number of weapons is greater than the number of oncoming targets.

The quality of the proposed assignment is evaluated according to three different criteria: the capacity to propose an early fire, the width of the firing time window and the minimisation of the overflying of the defended area by our own assets for security purpose. These criteria respectively represent:

10.5772/53606

117

http://dx.doi.org/10.5772/53606

3, with

(*xt*, *yt*) position and the speed (*vtx* , *vty* ) of the target *t* (respectively (*xw*, *yw*) position and the speed (*vwx* , *vwy* ) of the weapon *w*) in the (*x*,*O*, *y*) plan. The entering point of the target *t* in the capture zone of the weapon *w* and the entering point of the defended area is computed in the same time as the *FTWw*/*<sup>t</sup>* and they are denoted by *Ptin* and *Ptout* . The initial position of

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

Let *W* be the set of the available weapons and *T* the set of the oncoming targets. If *A* represents the assignments linking the vertices *W* to the targets *T*. *G* = (*W*, *T*, *A*) denotes

The weight of each edge is computed from the linear combination of the three criteria: earliest possible fire, width of the firing time windows and minimising the overfly of the defended

*f*1(*Ew*/*t*) = *EFFw*/*t*,(*w* ∈ *W*),(*t* ∈ *T*)

*f*2(*Ew*/*t*) = *LFFw*/*<sup>t</sup>* − *EFFw*/*t*,(*w* ∈ *W*),(*t* ∈ *T*)

*EFFw*/*<sup>t</sup>* denotes the earliest feasible fire for the weapon *w* on the target *t*. The latest feasible

*f*3(*Ew*/*t*) = *d* (*Ptout* , *Pw*<sup>0</sup> )

Here the function *d*(*P*1, *P*2) represents the Euclidean distance function between the point *P*<sup>1</sup>

Then, the global weight of the assignment *Ew*/*<sup>t</sup>* is the linear combination of the three functions described above: *H*(*Ew*/*t*) = *α*<sup>1</sup> *f*1(*Ew*/*t*) + *α*<sup>2</sup> *f*2(*Ew*/*t*) + *α*<sup>3</sup> *f*3(*Ew*/*t*), where *H*(*Ew*/*t*) denotes the weighting function of the assignment *Ew*/*<sup>t</sup>* and (*α*1, *α*2, *α*3) ∈ [0, 1]

> *E*1/1 *E*2/1 *E*3/1 ... *E*|*W*|/1 *E*1/2 *E*2/2 *E*3/2 ... *E*|*W*|/2

*E*1/|*T*<sup>|</sup> *E*2/|*T*<sup>|</sup> *E*3/|*T*<sup>|</sup> ... *E*|*W*|/|*T*<sup>|</sup>

. ... .

. . The cost matrix used for the Hungarian algorithm has the following form:

. . . . . . . .

As mentioned, *EFFw*/*<sup>t</sup>* denotes the earliest feasible fire for the weapon *w* on the target *t*.

the weapon *w* is denoted by *Pw*<sup>0</sup> = (*xw*<sup>0</sup> , *yw*<sup>0</sup> ).

*3.5.1. The assignment part: Hungarian algorithm*

area. These criteria are represented as follows:

fire for the weapon *w* on the target *t* is denoted by *LFFw*/*t*.

and the point *P*2. This criterion is shown in the Figure 2.

*H* =

the complete bipartite graph.

*α*<sup>1</sup> + *α*<sup>2</sup> + *α*<sup>3</sup> = 1.

**Figure 1.** Example of asymmetric bipartite graph with *w* weapons and *t* targets

• limiting the overfly in our own area enables to cope with security problem in case of material failure.

#### **3.4. The sequencing of the firing time**

As soon as the weapons are assigned to the targets, the sequencing of the firing is computed with respect to the weapons properties (range, velocity) and the firing time windows as well.

In order to evaluate the quality of the proposed solution, the performance index is based on the reactivity of the algorithm, the respect of the system constraints and the avoidance of idle time when a firing is possible.

The system is subject to some technical constraints as a required time between two firing times, which depends on the system. In the designed simulator this time is fixed to 3 seconds.

#### **3.5. Mathematical modelling**

This section describes the mathematical modelling of each step followed to achieve the DWTA. The first step is the assignment of the targets to the weapons, and then the sequencing of the firing time to complete in the best possible way the destroying of all the threatening targets. The weapon-target assignment is done by using the graph theory, especially the Hungarian algorithm. The second part is done by integrating two approaches: the PSO and the EGT to make up an efficient real-time oriented algorithm to solve the firing sequence problem.

In the following section, *FTWw*/*<sup>t</sup>* denotes the set of the firing time windows (time windows in which a weapon *w* can be fired with a given probability to reach the target *t*). *EFFw*/*<sup>t</sup>* denotes the earliest feasible fire for the weapon *w* on the target *t*. The latest feasible fire for the weapon *w* on the target *t* is denoted by *LFFw*/*t*. *Ew*/*<sup>t</sup>* represents the edge linking the weapon *w* with the target *t*. The average speed of the weapon *w* is denoted by *Sw*. *Rt* and *Rw* denote the state of the target *t* (respectively the weapon *w*). The states are composed of the (*xt*, *yt*) position and the speed (*vtx* , *vty* ) of the target *t* (respectively (*xw*, *yw*) position and the speed (*vwx* , *vwy* ) of the weapon *w*) in the (*x*,*O*, *y*) plan. The entering point of the target *t* in the capture zone of the weapon *w* and the entering point of the defended area is computed in the same time as the *FTWw*/*<sup>t</sup>* and they are denoted by *Ptin* and *Ptout* . The initial position of the weapon *w* is denoted by *Pw*<sup>0</sup> = (*xw*<sup>0</sup> , *yw*<sup>0</sup> ).

#### *3.5.1. The assignment part: Hungarian algorithm*

8 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

**Figure 1.** Example of asymmetric bipartite graph with *w* weapons and *t* targets

**3.4. The sequencing of the firing time**

material failure.

time when a firing is possible.

**3.5. Mathematical modelling**

problem.

• limiting the overfly in our own area enables to cope with security problem in case of

As soon as the weapons are assigned to the targets, the sequencing of the firing is computed with respect to the weapons properties (range, velocity) and the firing time windows as well. In order to evaluate the quality of the proposed solution, the performance index is based on the reactivity of the algorithm, the respect of the system constraints and the avoidance of idle

The system is subject to some technical constraints as a required time between two firing times, which depends on the system. In the designed simulator this time is fixed to 3 seconds.

This section describes the mathematical modelling of each step followed to achieve the DWTA. The first step is the assignment of the targets to the weapons, and then the sequencing of the firing time to complete in the best possible way the destroying of all the threatening targets. The weapon-target assignment is done by using the graph theory, especially the Hungarian algorithm. The second part is done by integrating two approaches: the PSO and the EGT to make up an efficient real-time oriented algorithm to solve the firing sequence

In the following section, *FTWw*/*<sup>t</sup>* denotes the set of the firing time windows (time windows in which a weapon *w* can be fired with a given probability to reach the target *t*). *EFFw*/*<sup>t</sup>* denotes the earliest feasible fire for the weapon *w* on the target *t*. The latest feasible fire for the weapon *w* on the target *t* is denoted by *LFFw*/*t*. *Ew*/*<sup>t</sup>* represents the edge linking the weapon *w* with the target *t*. The average speed of the weapon *w* is denoted by *Sw*. *Rt* and *Rw* denote the state of the target *t* (respectively the weapon *w*). The states are composed of the Let *W* be the set of the available weapons and *T* the set of the oncoming targets. If *A* represents the assignments linking the vertices *W* to the targets *T*. *G* = (*W*, *T*, *A*) denotes the complete bipartite graph.

The weight of each edge is computed from the linear combination of the three criteria: earliest possible fire, width of the firing time windows and minimising the overfly of the defended area. These criteria are represented as follows:

$$f\_1(E\_{w/t}) = EFF\_{w/t} \ (w \in W) \ (t \in T)^\*$$

As mentioned, *EFFw*/*<sup>t</sup>* denotes the earliest feasible fire for the weapon *w* on the target *t*.

$$f\_2(E\_{w/t}) = LFF\_{w/t} - EFF\_{w/t'} (w \in W)\_t (t \in T)$$

*EFFw*/*<sup>t</sup>* denotes the earliest feasible fire for the weapon *w* on the target *t*. The latest feasible fire for the weapon *w* on the target *t* is denoted by *LFFw*/*t*.

$$f\_{\mathfrak{Z}}(E\_{w/t}) = d\left(P\_{t\_{out}}, P\_{w\_0}\right)$$

Here the function *d*(*P*1, *P*2) represents the Euclidean distance function between the point *P*<sup>1</sup> and the point *P*2. This criterion is shown in the Figure 2.

Then, the global weight of the assignment *Ew*/*<sup>t</sup>* is the linear combination of the three functions described above: *H*(*Ew*/*t*) = *α*<sup>1</sup> *f*1(*Ew*/*t*) + *α*<sup>2</sup> *f*2(*Ew*/*t*) + *α*<sup>3</sup> *f*3(*Ew*/*t*), where *H*(*Ew*/*t*) denotes the weighting function of the assignment *Ew*/*<sup>t</sup>* and (*α*1, *α*2, *α*3) ∈ [0, 1] 3, with *α*<sup>1</sup> + *α*<sup>2</sup> + *α*<sup>3</sup> = 1.

The cost matrix used for the Hungarian algorithm has the following form:

$$H = \begin{pmatrix} E\_{1/1} & E\_{2/1} & E\_{3/1} & \dots & E\_{|W|/1} \\ E\_{1/2} & E\_{2/2} & E\_{3/2} & \dots & E\_{|W|/2} \\ \vdots & \vdots & \vdots & \dots & \vdots \\ E\_{1/|T|} & E\_{2/|T|} & E\_{3/|T|} & \dots & E\_{|W|/|T|} \end{pmatrix}$$

10.5772/53606

119

http://dx.doi.org/10.5772/53606

*f*4(*FS*) =

Where, *FT* denotes the firing time of the weapon assigned to the target *t*.

*f*5(*FS*) =

*f*6(*FS*) =

value in order to avoid infeasible solution.

weapon *i*, otherwise *ci* = 0.

available weapons.

current particle.

is obtained as:

with the EGT.

**4. The proposed method**

**4.1. A two step-method**

*T* ∑ *t*=1 *FTt*

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

The second criterion evaluates the feasibility of the proposed solution to respect the short time delay due to the system constraints. This criterion is based on the presence of constraint violations. When any of the constraints is violated, the proposed solution takes the maximum

> *W* ∑ *w*=1

The vector Conflict = [*ci*], *i* = {1, . . . , |*W*|} with *ci* = 1 if there is a constraint violation by the

The third and last criterion is based on the idle time of the system. This criterion enables to avoid the inactivity of the system if there are possible fires by the current time. In the best case, this value should be reduced to the time constraint multiplied by the number of

> *W*−1 ∑ *w*=1

Note that the *FS* vector is sorted before computing this performance index function to the

When all the criteria are computed, the global performance of the proposed firing sequence

*<sup>F</sup>*(*FS*) = (*f*4(*FS*) + <sup>1</sup>). *<sup>f</sup>*6(*FS*) if *<sup>f</sup>*5(*FS*) = <sup>0</sup>

The proposed method is based on the consecutive use of the Hungarian algorithm to solve the assignment problem before determining the fire sequencing using the PSO combined

As described on the Flowchart 3, the two-step process computes first the optimal assignment of the targets to the weapons, then in a second time the optimal firing sequence is determined.

Conflict(*w*)

(*FSw*<sup>+</sup><sup>1</sup> − *FSw*)

+∞ if *f*5(*FS*) �= 0

**Figure 2.** Representation of the overflying criterion. The used value is the Euclidean distance between the entering point of the target in the area to defend and the initial position of the weapon.

#### *3.5.2. The firing time sequencing: EGPSO*

As described in the section 2.2, the EGPSO process is based on the combination of the PSO algorithm combined to the EGT in order to increase the convergence speed [27]. In this section, *FS* = [*FTi*], *i* = {1, . . . , *w*} denotes a firing sequence for the *w* selected weapons from the previous assignment and *FTi* represents the firing time of the weapon *i* (*i* ≤ |*W*|). In the proposed model, *FS* represents one particle composed by the set of the firing times for each weapon. Since the solution space is composed by the firing time windows, it can be very heterogeneous in terms of length along each dimension. In order to avoid an unequal exploration of the solution space, the normalisation over the solution space is operated. Thus, the solution space is reduced to a [0, 1] <sup>|</sup>*W*<sup>|</sup> hypercube and enables a homogeneous exploring by the particles.

In order to evaluate the performance of a proposed solution, the global performance index is based on the reactivity of the algorithm, the respect of the system constraints and the avoidance of idle time when a firing is possible. The global cost function is obtained in multiplying each criterion. The multiplication is selected to consider evenly all the criteria. Thus, if one criterion is not respected by the proposed engagement plan, the cost function will decrease accordingly to the unsatisfied criterion.

The first performance index based on the time delay enables to quantify the reactivity of the system in summing the firing times. The function *f*<sup>1</sup> enables to express this criterion.

$$f\_4(FS) = \sum\_{t=1}^{T} FT\_t$$

Where, *FT* denotes the firing time of the weapon assigned to the target *t*.

The second criterion evaluates the feasibility of the proposed solution to respect the short time delay due to the system constraints. This criterion is based on the presence of constraint violations. When any of the constraints is violated, the proposed solution takes the maximum value in order to avoid infeasible solution.

$$f\_{\mathbb{S}}(FS) = \sum\_{w=1}^{W} \text{Conflict}(w).$$

The vector Conflict = [*ci*], *i* = {1, . . . , |*W*|} with *ci* = 1 if there is a constraint violation by the weapon *i*, otherwise *ci* = 0.

The third and last criterion is based on the idle time of the system. This criterion enables to avoid the inactivity of the system if there are possible fires by the current time. In the best case, this value should be reduced to the time constraint multiplied by the number of available weapons.

$$f\_6(FS) = \sum\_{w=1}^{W-1} (FS\_{w+1} - FS\_w)^2$$

Note that the *FS* vector is sorted before computing this performance index function to the current particle.

When all the criteria are computed, the global performance of the proposed firing sequence is obtained as:

$$F(FS) = \begin{cases} (f\_4(FS) + 1).f\_6(FS) \text{ if } f\_5(FS) = 0\\ +\infty & \text{if } f\_5(FS) \neq 0 \end{cases}$$

## **4. The proposed method**

10 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

the target in the area to defend and the initial position of the weapon.

*3.5.2. The firing time sequencing: EGPSO*

the solution space is reduced to a [0, 1]

will decrease accordingly to the unsatisfied criterion.

by the particles.

**Figure 2.** Representation of the overflying criterion. The used value is the Euclidean distance between the entering point of

As described in the section 2.2, the EGPSO process is based on the combination of the PSO algorithm combined to the EGT in order to increase the convergence speed [27]. In this section, *FS* = [*FTi*], *i* = {1, . . . , *w*} denotes a firing sequence for the *w* selected weapons from the previous assignment and *FTi* represents the firing time of the weapon *i* (*i* ≤ |*W*|). In the proposed model, *FS* represents one particle composed by the set of the firing times for each weapon. Since the solution space is composed by the firing time windows, it can be very heterogeneous in terms of length along each dimension. In order to avoid an unequal exploration of the solution space, the normalisation over the solution space is operated. Thus,

In order to evaluate the performance of a proposed solution, the global performance index is based on the reactivity of the algorithm, the respect of the system constraints and the avoidance of idle time when a firing is possible. The global cost function is obtained in multiplying each criterion. The multiplication is selected to consider evenly all the criteria. Thus, if one criterion is not respected by the proposed engagement plan, the cost function

The first performance index based on the time delay enables to quantify the reactivity of the system in summing the firing times. The function *f*<sup>1</sup> enables to express this criterion.

<sup>|</sup>*W*<sup>|</sup> hypercube and enables a homogeneous exploring

The proposed method is based on the consecutive use of the Hungarian algorithm to solve the assignment problem before determining the fire sequencing using the PSO combined with the EGT.

#### **4.1. A two step-method**

As described on the Flowchart 3, the two-step process computes first the optimal assignment of the targets to the weapons, then in a second time the optimal firing sequence is determined.

10.5772/53606

121

http://dx.doi.org/10.5772/53606

matrix is composed by the mean fitness of the particles composing each swarm. Let *S* be the

After one iteration using each strategy successively, the payoff matrix consists of the mean

2

*π*(*s*3) + *π*(*s*2)

The coefficients *π*(*si*), *i* ∈ {1, 2, 3} are the mean value of the swarm after using the pure strategy *si*. The evolutionary game process used to converge to the evolutionary stable strategy is the *replicator dynamic* described in [20]. As soon as the population is stabilised, the proposed algorithm stop running the replicator dynamic. This ESS gives the stable strategy rate, generally composed by a mix of the strategies *s*1, *s*2, and *s*3. Then, the final step uses

The principle of the method is described on the Flowchart 4 and by the following process

(a) Random selection of particles following the classical PSO process (exploration) and

(b) Classic iteration of the PSO in using only one strategy for each swarm (inertial,

(c) Computation of the payoff matrix in computing the mean value of the swarm in using

the particles following the EGPSO (increase computational speed).

(d) Find the evolutionary stable strategy depending on the payoff matrix (e) Classic iteration of the PSO using the previously found coefficients

<sup>2</sup> *<sup>π</sup>*(*s*2) *<sup>π</sup>*(*s*2) + *<sup>π</sup>*(*s*3)

<sup>2</sup> *<sup>π</sup>*(*s*3)

*π*(*s*1) + *π*(*s*3) 2

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

2

*<sup>π</sup>*(*s*1) *<sup>π</sup>*(*s*1) + *<sup>π</sup>*(*s*2)

set of the available strategies *si*, *i* ∈ {1, 2, 3} which are as follows:

*π*(*s*2) + *π*(*s*1)

*π*(*s*3) + *π*(*s*1) 2

*s*1: Use of the pure strategy *inertia s*2: Use of the pure strategy *individual s*3: Use of the pure strategy *social*

value of the swarm. *A* denotes this payoff matrix:

these rates as coefficients in the PSO algorithm.

2. For a maximum number of iterations

(f) Check if the swarm is stabilised

• If YES, restart the swarm like at the step 1 • If NOT, keep running the algorithm

In the presented simulation, the PSO parameters are defined as:

individual, social)

3. Obtain the optimal solution

the strategies

1. Initialisation of the swarm in position and velocity

step by step:

Π =

**Figure 3.** Representation of the two-step method to solve the DWTA.

## **4.2. The Hungarian algorithm**

The assignment of the targets to the weapons is realised in using the Hungarian algorithm [21]. The section 3.5.1 states all the required details enabling to understand the principles of the used method. Since in real scenarii the number of targets is only rarely the same as the number of weapons, the Hungarian algorithm designed for asymmetric bipartite graphs is used. The following parameters are used to determine the best assignment: the cost matrix has a |*T*|×|*W*| form in order to assign all the targets and the coefficients of this cost matrix are determined in using the equations described in 3.5.1.

#### **4.3. The integration of the particle swarm optimisation with the evolutionary game theory**

There are two main steps in this approach, the first one is the movement of the swarm in using only, first the inertia, then only the individual component, then only the social component. From the obtained results of the movement of the three swarms, the payoff matrix is composed by the mean fitness of the particles composing each swarm. Let *S* be the set of the available strategies *si*, *i* ∈ {1, 2, 3} which are as follows:

*s*1: Use of the pure strategy *inertia*

12 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

**Figure 3.** Representation of the two-step method to solve the DWTA.

are determined in using the equations described in 3.5.1.

The assignment of the targets to the weapons is realised in using the Hungarian algorithm [21]. The section 3.5.1 states all the required details enabling to understand the principles of the used method. Since in real scenarii the number of targets is only rarely the same as the number of weapons, the Hungarian algorithm designed for asymmetric bipartite graphs is used. The following parameters are used to determine the best assignment: the cost matrix has a |*T*|×|*W*| form in order to assign all the targets and the coefficients of this cost matrix

**4.3. The integration of the particle swarm optimisation with the evolutionary**

There are two main steps in this approach, the first one is the movement of the swarm in using only, first the inertia, then only the individual component, then only the social component. From the obtained results of the movement of the three swarms, the payoff

**4.2. The Hungarian algorithm**

**game theory**

After one iteration using each strategy successively, the payoff matrix consists of the mean value of the swarm. *A* denotes this payoff matrix:

$$
\Pi = \begin{pmatrix}
\pi(s\_1) & \frac{\pi(s\_1) + \pi(s\_2)}{2} & \frac{\pi(s\_1) + \pi(s\_3)}{2} \\
\frac{\pi(s\_2) + \pi(s\_1)}{2} & \pi(s\_2) & \frac{\pi(s\_2) + \pi(s\_3)}{2} \\
\frac{\pi(s\_3) + \pi(s\_1)}{2} & \frac{\pi(s\_3) + \pi(s\_2)}{2} & \pi(s\_3)
\end{pmatrix}
$$

The coefficients *π*(*si*), *i* ∈ {1, 2, 3} are the mean value of the swarm after using the pure strategy *si*. The evolutionary game process used to converge to the evolutionary stable strategy is the *replicator dynamic* described in [20]. As soon as the population is stabilised, the proposed algorithm stop running the replicator dynamic. This ESS gives the stable strategy rate, generally composed by a mix of the strategies *s*1, *s*2, and *s*3. Then, the final step uses these rates as coefficients in the PSO algorithm.

The principle of the method is described on the Flowchart 4 and by the following process step by step:

	- (a) Random selection of particles following the classical PSO process (exploration) and the particles following the EGPSO (increase computational speed).
	- (b) Classic iteration of the PSO in using only one strategy for each swarm (inertial, individual, social)
	- (c) Computation of the payoff matrix in computing the mean value of the swarm in using the strategies
	- (d) Find the evolutionary stable strategy depending on the payoff matrix
	- (e) Classic iteration of the PSO using the previously found coefficients
	- (f) Check if the swarm is stabilised
		- If YES, restart the swarm like at the step 1
		- If NOT, keep running the algorithm

In the presented simulation, the PSO parameters are defined as:

10.5772/53606

123

http://dx.doi.org/10.5772/53606

• 50 particles are used to explore the solution space.

is considered as

**5. Results and comments**

missing fire for example).

Square of 50000 m by 50000 m

on the centre of the space.

16 Weapons vs. 12 Targets. **Condition of engagement success:**

operating a successful shot is 75%.

**The aerial space:**

**Weapons**

**Targets**

(0, 0).

**The initial conditions:**

• The maximum distance travelled by one particle in one iteration is limited to 1/10 along each dimension. Notice that since the solution space has been normalised, the maximum

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

• In order to be able to be competitive in real-time, the exit criterion is a defined time of

In order to enable a quick convergence to the optimal vector rate of the PSO coefficients, the EGT process is launched in using as payoff matrix Π described in the section 4.3. The replicator equation is computed over 500 hundred generations, and then the obtained result

In this section, the efficiency of the proposed approach is analysed. After running 100 times a simulation, the number of experiences that the mission is successfully achieved is compared to the number of times it fails. Then, in a second time the evolution of the assignment is studied in analysing the target motions and the proposed engagement plan. The study ends with the analysis of the human operator point of view in order to determine if the proposed algorithm can be reliable and stable for the operator. By stable, it is assumed that the operator can have a global overview of the next engagement to execute in advance, and that this plan won't change if there are no major changes in the aerial situation (suppressed enemy or

velocity enables an homogeneous exploration of the solution space.

In the presented simulator, the used parameters are set up as follows:

The speed is randomly drawn between 50 m/s and 900 m/s.

The initial position is within a radius of 3000 m around the central objective

The range of each weapon is randomly drawn between 10000 meters and 15000 meters.

The initial position is set up between 30000 m and 50000 m from the main objective located

The trajectories that the targets are following are modelled in using a Bezier curve defined by 4 control points. The last control point is automatically set as the centre of the space

The success of an engagement one weapon on one target is determined in drawing one random number. If this number is greater than a determined value, then the shoot is considered as a success. Otherwise, it is considered that the target avoids the weapon. In this simulator this value is arbitrary fixed to 0.25, which means that the probability of

2500 ms, after that the best found solution is considered as the optimal one.

**Figure 4.** Details on the method designed to mix EGT and PSO.

In order to enable a quick convergence to the optimal vector rate of the PSO coefficients, the EGT process is launched in using as payoff matrix Π described in the section 4.3. The replicator equation is computed over 500 hundred generations, and then the obtained result is considered as

## **5. Results and comments**

In this section, the efficiency of the proposed approach is analysed. After running 100 times a simulation, the number of experiences that the mission is successfully achieved is compared to the number of times it fails. Then, in a second time the evolution of the assignment is studied in analysing the target motions and the proposed engagement plan. The study ends with the analysis of the human operator point of view in order to determine if the proposed algorithm can be reliable and stable for the operator. By stable, it is assumed that the operator can have a global overview of the next engagement to execute in advance, and that this plan won't change if there are no major changes in the aerial situation (suppressed enemy or missing fire for example).

In the presented simulator, the used parameters are set up as follows:

#### **The aerial space:**

Square of 50000 m by 50000 m

#### **Weapons**

14 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

**Figure 4.** Details on the method designed to mix EGT and PSO.

The initial position is within a radius of 3000 m around the central objective The range of each weapon is randomly drawn between 10000 meters and 15000 meters.

#### **Targets**

The initial position is set up between 30000 m and 50000 m from the main objective located on the centre of the space.

The trajectories that the targets are following are modelled in using a Bezier curve defined by 4 control points. The last control point is automatically set as the centre of the space (0, 0).

The speed is randomly drawn between 50 m/s and 900 m/s.

#### **The initial conditions:**

16 Weapons vs. 12 Targets.

#### **Condition of engagement success:**

The success of an engagement one weapon on one target is determined in drawing one random number. If this number is greater than a determined value, then the shoot is considered as a success. Otherwise, it is considered that the target avoids the weapon. In this simulator this value is arbitrary fixed to 0.25, which means that the probability of operating a successful shot is 75%.

10.5772/53606

125

http://dx.doi.org/10.5772/53606

**Figure 6.** The upper graph illustrates the variation in the assignment process over the time. The regularity of the proposed assignment can be noticed, especially as long as the aerial situation does not change (no target are suppressed). The black vertical lines highlight these phases. The lower graph shows the evolution of the proposed firing time to engage the target over

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

been killed, then it denotes a change in the aerial situation. During the different highlighted phases, the assignment presents some interesting features as the regularity over the time when the aerial situation keep being similar. The lower graph on the Figure 6 represents the evolution of the firing time for each target over the time. The vertical lines have the same meaning as the upper graph and denotes a change in the aerial situation like, for example, a suppressed enemy or an unsuccessful fire. This second graph highlights the continuity of the proposed firing sequence over the time. It is shown that the operator can not only approve the firing sequence in executing the firing, but the operator can follow the entire scenario and can anticipate the upcoming events. The Figure 7 focuses on the real time aspect in focusing only on the operator point of view. Indeed this Figure represents a zoom on the 25 last seconds before firing the weapons. The horizontal dash line illustrates a time limit of 5

**Figure 7.** This graph represents a zoom on the final instruction of the operator to execute the firing of the weapon as soon as

the proposed firing time is within 5 seconds of the current time. This limit is illustrated by the horizontal dash line.

seconds from which the operator can execute the firing.

the time.

**Figure 5.** Representation of a possible initialisation of trajectory and weapon position. The triangle marker represents the initial position of the target. The dot line is the trajectory that the target will follow to reach its goal. The continuous line represents the area that we are defending and the cross marker surrounded by a dot line denote the defending weapon and its capture zone.

The Figure 5 shows a possible initialisation of a scenario. Note that if the trajectory is a priori known by the target, the defending side has no information at all but the final point of the target and its current position.

The analysis of the evolution of the assignment of the weapons to the oncoming targets clearly shows stability over the simulation time as long as there are no major change in the scenario. A major change in the scenario can be qualified by the suppression of one enemy which leads to the reconsideration of the entire scenario. Otherwise, the proposed method clearly shows a good stability over the simulation time which is required in the presented case. Considering the presence of a human operator having the final decision making and using this method as a help in the decision making process, it is important for the proposed engagement to be continuous over the time when the aerial situation does not vary dramatically. The upper graph of the Figure 6 displays the assignment of the target *t* over the number of iterations. The vertical lines identify the instants when a target has

16 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

**Figure 5.** Representation of a possible initialisation of trajectory and weapon position. The triangle marker represents the initial position of the target. The dot line is the trajectory that the target will follow to reach its goal. The continuous line represents the area that we are defending and the cross marker surrounded by a dot line denote the defending weapon and its capture

The Figure 5 shows a possible initialisation of a scenario. Note that if the trajectory is a priori known by the target, the defending side has no information at all but the final point of the

The analysis of the evolution of the assignment of the weapons to the oncoming targets clearly shows stability over the simulation time as long as there are no major change in the scenario. A major change in the scenario can be qualified by the suppression of one enemy which leads to the reconsideration of the entire scenario. Otherwise, the proposed method clearly shows a good stability over the simulation time which is required in the presented case. Considering the presence of a human operator having the final decision making and using this method as a help in the decision making process, it is important for the proposed engagement to be continuous over the time when the aerial situation does not vary dramatically. The upper graph of the Figure 6 displays the assignment of the target *t* over the number of iterations. The vertical lines identify the instants when a target has

zone.

target and its current position.

**Figure 6.** The upper graph illustrates the variation in the assignment process over the time. The regularity of the proposed assignment can be noticed, especially as long as the aerial situation does not change (no target are suppressed). The black vertical lines highlight these phases. The lower graph shows the evolution of the proposed firing time to engage the target over the time.

been killed, then it denotes a change in the aerial situation. During the different highlighted phases, the assignment presents some interesting features as the regularity over the time when the aerial situation keep being similar. The lower graph on the Figure 6 represents the evolution of the firing time for each target over the time. The vertical lines have the same meaning as the upper graph and denotes a change in the aerial situation like, for example, a suppressed enemy or an unsuccessful fire. This second graph highlights the continuity of the proposed firing sequence over the time. It is shown that the operator can not only approve the firing sequence in executing the firing, but the operator can follow the entire scenario and can anticipate the upcoming events. The Figure 7 focuses on the real time aspect in focusing only on the operator point of view. Indeed this Figure represents a zoom on the 25 last seconds before firing the weapons. The horizontal dash line illustrates a time limit of 5 seconds from which the operator can execute the firing.

**Figure 7.** This graph represents a zoom on the final instruction of the operator to execute the firing of the weapon as soon as the proposed firing time is within 5 seconds of the current time. This limit is illustrated by the horizontal dash line.

In order to test the efficiency of the proposed method over different scenario, the designed experience has been launched 100 times and the final result archived. The pie diagram 8 shows the number of times that the proposed method achieved its goal versus the number of time it fails. The analysis of this result shows that the proposed algorithm successfully achieved its mission in 96% of the cases. If we look into details the causes of these failures, we can notice that 3 of the 4 failures was due to the lack of available weapons. Which means that the method does not achieved its goal because of the probability. Indeed, with PK threshold fixed to *PK* = 0.90 and 16 available weapons versus 12 targets, we have an estimate failure rate of approximatively 2 %. This last result comes from the binomial distribution, where the probability of getting exactly *T* success in *W* trials is given by:

10.5772/53606

127

http://dx.doi.org/10.5772/53606

results have shown the efficiency of the proposed two-step approach in various cases. The proposed algorithm achieves its objective in 96% for the given scenarii which include random simulation parameters selected for the generality of the senarii. Note that from a probability study on this application, with the chosen simulation parameters, 2% of the scenarii was expected to be failed simply because of the associated probability laws based on a Binomial

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

Cédric Leboucher1,<sup>⋆</sup>, Hyo-Sang Shin2, Patrick Siarry3, Rachid Chelouah4,

<sup>⋆</sup> Address all correspondence to<EMAIL_ADDRESS>
3 Université Paris-Est Créteil (UPEC), LISSI (EA 3956), Créteil, France

2 Cranfield University, School of Engineering, College Road, Cranfield, Bedford, UK

[1] S. P. Lloyd and H. S. Witsenhausen. Weapon allocation is np-complete. In *Proceeding IEEE Summer Simulation Conference*, page 1054 âA ¸S 1058, Reno (USA), 1986. ˘

[2] P. A. Hosein and M. Athans. Preferential defense strategies. part i: The static case. Technical report, MIT Laboratory for Information and Decision Systems with partial

[3] S. Bisht. Hybrid genetic-simulated annealing algorithm for optimal weapon allocation

[4] A. Malhotra and R. K. Jain. Genetic algorithm for optimal weapon allocation in

[5] O. Karasakal. Air defense missile-target allocation models for a naval task group.

[6] F. Johansson and G. Falkman. Sward: System for weapon allocation research & development. *13th Conference on Information Fusion (FUSION)*, 1:1–7, July 2010.

[7] O. Kwon, K. Lee, D. Kang, and S. Park. A branch-and-price algorithm for a targeting

[8] H. Cai, J. Liu, Y. Chen, and H.Wang. Survey of the research on dynamic weapon-target

inmultilayer defence scenario. *Defence Sci. J.*, 54(3):395 – 405, 2004.

multilayer defence scenario. *Defence Sci. J.*, 51(3):285 – 293, 2001.

assignment problem. *J. Syst. Eng. Electron.*, 17(3):559 – 565, 2006.

[9] E. Wacholder. A neural network-based optimization algorithm for the static weapon-target assignment problem. *ORSA J. Comput.*, 1(4):232 – 246, 1989.

1 MBDA France, 1 av. Reaumur, Le Plessis Robinson, France

4 L@ris, EISTI, Avenue du Parc, Cergy-Pontoise, France

Stéphane Le Ménec<sup>1</sup> and Antonios Tsourdos<sup>2</sup>

support, Cambridge (USA), 1990.

*Comput. Oper. Res.*, 35:1759 – 1770, 2008.

problem. *Naval Res. Log.*, 54:732 – 741, 2007.

distribution.

**Author details**

**References**

$$P(T; W, PK) = \frac{W!}{T!(W - T)!} PK^T (1 - PK)^{W - T}$$

Thus, to solve this issue, two possible ways could be explored: first, the increasing of available weapons; second, using more accurate weapons. Although both of the proposed solutions can cope with this issue, it leads to increase the cost of the mission. Controlling this probability enables to optimise the used deployment to protect our area.

**Figure 8.** This bar diagram illustrates the number of time that the simulation is a success versus the number of time that it fails.

## **6. Conclusion**

In this chapter, a two-step optimisation method for the DWTA was proposed. Based on the successive use of the Hungarian algorithm, and a PSO combined with the EGT, the proposed algorithm shows reliable results in terms of performance and real-time computation. The proposed method is verified using one simulator designed to create random scenarii and to follow the normal evolution of the battlefield in real-time. The initialised scenario was composed of 16 weapons versus 12 targets. The stability of the assignment and the continuity of the firing sequence was analysed over the launch of 100 simulations. Regarding the probability of successfully achieved the mission, a short study about the binomial distribution has been done and could be helpful in the mission planning process to determine the optimal number of available weapons before the mission. The simulation results have shown the efficiency of the proposed two-step approach in various cases. The proposed algorithm achieves its objective in 96% for the given scenarii which include random simulation parameters selected for the generality of the senarii. Note that from a probability study on this application, with the chosen simulation parameters, 2% of the scenarii was expected to be failed simply because of the associated probability laws based on a Binomial distribution.

## **Author details**

18 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

probability of getting exactly *T* success in *W* trials is given by:

**6. Conclusion**

*<sup>P</sup>*(*T*; *<sup>W</sup>*, *PK*) = *<sup>W</sup>*!

this probability enables to optimise the used deployment to protect our area.

In order to test the efficiency of the proposed method over different scenario, the designed experience has been launched 100 times and the final result archived. The pie diagram 8 shows the number of times that the proposed method achieved its goal versus the number of time it fails. The analysis of this result shows that the proposed algorithm successfully achieved its mission in 96% of the cases. If we look into details the causes of these failures, we can notice that 3 of the 4 failures was due to the lack of available weapons. Which means that the method does not achieved its goal because of the probability. Indeed, with PK threshold fixed to *PK* = 0.90 and 16 available weapons versus 12 targets, we have an estimate failure rate of approximatively 2 %. This last result comes from the binomial distribution, where the

*T*!(*W* − *T*)!

Thus, to solve this issue, two possible ways could be explored: first, the increasing of available weapons; second, using more accurate weapons. Although both of the proposed solutions can cope with this issue, it leads to increase the cost of the mission. Controlling

**Figure 8.** This bar diagram illustrates the number of time that the simulation is a success versus the number of time that it fails.

In this chapter, a two-step optimisation method for the DWTA was proposed. Based on the successive use of the Hungarian algorithm, and a PSO combined with the EGT, the proposed algorithm shows reliable results in terms of performance and real-time computation. The proposed method is verified using one simulator designed to create random scenarii and to follow the normal evolution of the battlefield in real-time. The initialised scenario was composed of 16 weapons versus 12 targets. The stability of the assignment and the continuity of the firing sequence was analysed over the launch of 100 simulations. Regarding the probability of successfully achieved the mission, a short study about the binomial distribution has been done and could be helpful in the mission planning process to determine the optimal number of available weapons before the mission. The simulation

*PKT*(<sup>1</sup> − *PK*)

*W*−*T*

Cédric Leboucher1,<sup>⋆</sup>, Hyo-Sang Shin2, Patrick Siarry3, Rachid Chelouah4, Stéphane Le Ménec<sup>1</sup> and Antonios Tsourdos<sup>2</sup>

<sup>⋆</sup> Address all correspondence to<EMAIL_ADDRESS>
1 MBDA France, 1 av. Reaumur, Le Plessis Robinson, France

2 Cranfield University, School of Engineering, College Road, Cranfield, Bedford, UK

3 Université Paris-Est Créteil (UPEC), LISSI (EA 3956), Créteil, France

4 L@ris, EISTI, Avenue du Parc, Cergy-Pontoise, France

## **References**

[10] K. E. Grant. Optimal resource allocation using genetic algorithms. Technical report, Naval Research Laboratory, Washington (USA), 1993.

10.5772/53606

129

http://dx.doi.org/10.5772/53606

[23] M. Clerc. Discrete particle swarm optimization, illustred by the travelling salesman

algorithm. In *The 1997 IEEE International Conference on Systems, Man, and Cybernetics*,

A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem

[25] J. Maynard-Smith. *Evolution and the theory of games*. Cambridge University Press, 1982.

[27] C. Leboucher, R. Chelouah, P. Siarry, and S. Le Ménec. A swarm intelligence method combined to evolutionary game theory applied to ressources allocation problem. In

problem. *New Optimization Techniques in Engineering*, 1:219–239, 2004.

[26] P. Taylor and Jonker L. Evolutionary stable strategies and game dynamics.

*International Conference on Swarm Intelligence*, Cergy (France), June 2011.

volume 5, pages 4104–4108, Orlando (USA), October 1997.

*Mathematical Bioscience*, 40:145–156, 1978.

[24] J. Kennedy and R.C. Eberhart. A discrete binary version of the particle swarm

[23] M. Clerc. Discrete particle swarm optimization, illustred by the travelling salesman problem. *New Optimization Techniques in Engineering*, 1:219–239, 2004.

20 Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

Naval Research Laboratory, Washington (USA), 1993.

*Autom.*, pages 3401 – 3405, Dalian (China), 2006.

Way, WPAFB, OH, 2000.

support, Cambridge (USA), 1990.

Systemswith partial support, 1990.

*Logistics Quarterly*, 2:83 – 97, 1955.

662, 2010.

2008.

[10] K. E. Grant. Optimal resource allocation using genetic algorithms. Technical report,

[11] H. Lu, H. Zhang, X. Zhang, and R. Han. An improved genetic algorithm for target assignment optimization of naval fleet air defense. In *6th World Cong. Intell. Contr.*

[13] D. Blodgett, M. Gendreau, F. Guertin, and J. Y. Potvin. A tabu search heuristic for

[14] B. Xin, J. Chen, J. Zhang, L. Dou, and Z. Peng. Efficient decision makings for dynamic weapon-target assignment by virtual permutation and tabu search heuristics. *IEEE transaction on systems, man, and cybernetics - Part C: Application and reviews*, 40(6):649 –

[15] P. A. Hosein and M. Athans. Preferential defense strategies. part ii: The dynamic case. Technical report, MIT Laboratory for Information and Decision Systems with partial

problems with vulnerable c2 nodes. Technical report, MIT Laboratory for Information

[16] P. A. Hosein, J. T. Walton, and M. Athans. Dynamic weapon-target assignment

[17] P. A. Hosein and M. Athans. Some analytical results for the dynamic weapon-target allocation problem. Technical report, MIT Laboratory for Information and Decision

[18] T. Sikanen. Solving weapon target assignment problem with dynamic programming. Technical report, Mat-2.4108 Independent research projects in applied mathematics,

[20] C. Leboucher, R. Chelouah, P. Siarry, and S. Le Ménec. A swarm intelligence method combined to evolutionary game theory applied to the resources allocation problem.

[21] H.W. Kuhn. The hungarian method for the assignment problem. *Naval Research*

[22] J. Kennedy and R. C. Eberhart. Particle swarm optimization. In *Proceedings of IEEE*

*International Conference on Neural Networks*, pages 1942 – 1948, Piscataway (USA), 1995.

weapon-target allocation problem with decreasing weapons and targets. In *IEEE Congr.*

and Decision Systems with partial support, Cambridge (USA), 1988.

[19] L. Wu, C. Xing, F. Lu, and P. Jia. An anytime algorithm applied to dynamic

*International Journal of Swarm Intelligence Research*, 3(2):20 – 38, 2012.

*Evol. Comput.*, pages 3755 – 3759, Hong Kong (China), 2008.

resource management in naval warfare. *J. Heur.*, 9:145 – 169, 2003.

[12] A. C. Cullenbine. A taboo search approach to the weapon assignment model. Master's thesis, Department of Operational Sciences, Air Force Institute of Technology, Hobson

## *Edited by Javier Del Ser*

This book aims at attracting the interest of researchers and practitioners around the applicability of meta-heuristic algorithms to practical scenarios arising from different knowledge disciplines. Emphasis is placed on evolutionary algorithms and swarm intelligence as computational means to efficiently balance the tradeoff between optimality of the produced solutions and the complexity derived from their estimation. In summary, this book serves as a good start point for early-stage investigators in the initial steps of their research on meta-heuristics, grounded on both a thorough literature review and the practical orientation of its contents.

Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

Recent Advances on

Meta-Heuristics and Their

Application to Real Scenarios

*Edited by Javier Del Ser*

Photo by scyther5 / iStock