ACGA Algorithm of Solving Weapon - Target Assignment Problem

doi:10.4236/ojapps.2012.24B018

Paper Menu >>

Journal Menu >>

ACGA Algorithmof Solving Weapon - Target Assignment

Problem

Jiuyong Zhang1,2

1Mathematics Department,

Academy of Armed Forces Engineering,

Beijing, 100072, China

2School of Science, Beijing University of Civil Engineering

and Architecture, Beijing, 100044 , China

Chuanqing Xu2,3

2School of Science, Beijing University of Civil Engineering

and Architecture, Beijing, 100044 , China

3Mathematics Department, Hanshan Normal College

Chaozhou, 521041, China

Xiaojing Wang 2

2School of Science,

Beijing University of Civil Engineering and Architecture,

Beijing, 100044 , China

Dehui Yuan3

3Mathematics Department,

Hanshan Normal College

Chaozhou, 521041, China

Abstract—Weapon Target Assignment is not only an important issue to use firepower, but also an important operational

decision-making problem. As new intelligent algorithms,Genetic algorithm and ant colony algorithm are applied to solve

Weapons-Target Assignment Problem. This paper introduces the Weapon-Target Assignment (WTA) and the mathematical

model, and proposes ACGA algorithm which is the integration of genetic algorithm and ant colony algorithm then use ACGA

algorithm to solve the Weapon-Target Assignment Problem. Calculations show that: when ACGA algorithm is used to solve

Weapon – Target Assignment Problem, it has fast convergence and high accuracy.

Keywords- Weapon -Target Assignment; ant colony algorithm; genetic algorithm; integration





Introduction

In the modern military war, weapons-target assignment

is a very important problem. The timeliness of weapons-

target assignment and the quality of scheme directly

influence the effect of the combat. Therefore, people have

made a lot of algorithms to solve this problem: Firstly,

traditional algorithms, including implicit enumeration

method, the branch and bound method, cutting plane

method, the dynamic programming, etc; Secondly,

intelligent algorithms, such as simulated annealing

algorithm, neural network algorithm, genetic algorithm, ant

colony algorithm, etc; Thirdly, the algorithmwhich is

combined with two kinds of algorithms is used to solve the

problem [1].

2. Basic Concept and Mathematical

Model of WTA

The definition of WTA: according to the enemy’s ruing

probability, our defensive weapons’ kill probability and the

important degree of theresources, by some allocation

strategies, before the enemy's attacks, scientific distribute our

defensive weapons, to make the best hitting of enemy or the

best protection of our defense resources. If targets distributed

to weapons is one-time, this is called static distribution. In

actual combat, the situation is in the twinkling of an eye, the

actual results of the war and the expected effect can not

perfectly the same, in order to further improve the defense

quality, according to the real-time situation of the war, it is

necessary to more stagesto distribute weapons, this is called

dynamic allocation.

Weapons-target distribution (WTA) described as: In a

battle, there are m kinds of weapon platforms

WWW ,,, 21 ", existing n targets

TTT ,,,

,the value

of targets is n

VVV,,, 21 ",the weapon platform

㸦

mi ,,2,1 "

㸧has weapons

, Target

distributed weapons

at most, the probability of weapon

platforms i

Wdistribute to target

㸦

njmi ,,2,1,,,2,1 ""

㸧.

Different combat purposes have differentmathematical

models. There are kinds of standardsas following: (1) the

maximum probability or expect of defenders’ survival; (2)

the minimum probability or expect of enemy survival; (3) the

weighted sum of the first standard and the second standard,

namely on the one hand that to the maximumprobability or

expect of defenders’ survival, on the other hand to the

minimum probability or expect of enemy survival, the

mathematical model of this standards is complex.

The optimal allocation goal of this paper is the minimum

failure value of weapons hit all of the targets.

Open Journal of Applied Sciences

Supplement：2012 world Congress on Engineering and Technology

74 Cop

Suppose that

is the number of weapons platform

attacks target

.the WTA model is:

)1(

,2,1,

)1(min





¦

mirx

njsx

qVE

iij

jij

ijj

WTA is NP problem in essence [2], there is no effective

algorithm for solving this problem.

3. Integration of ant colony algorithm

and genetic algorithm

A. Ant colony algorithm theory

Ant Colony Algorithm is presented by Italian scholars

such as Colorni[3]-[5], in the early 1990 s they simulated the

behavior of collective ants foraging in nature and proposed

the heuristic optimization algorithm based on the bionic

population. Firstly they used ACO success in solving the

famous Traveling salesman Problem (TSP). Below we use

TSP as an example to explain to the ant colony algorithm.

Suppose that C is the set of the cities which number is n, and

the ant number is m, not

),,2,1,( njid

is the

distance between city i and city j.

)(t

is the residual

pheromone strengthof the path which is between city i and

city j at time t, in order to simulate the real secretion of the

ants. In athletic process, the ant k(k = 1,2,Օ,m) determine its

transfer direction according to the amount of information on

various paths, and we use the taboo watch

),,2,1( nktabuk" to record the city which is the ant k

had passed through. In the search process, according to the

information and inspiration information of various paths, the

ant calculates the transition probability, so as to determine

the next city.

)(tp

means the probability of the ant k from

city i transfer to city j at time t, and its expression is:

)2(

)]([)]([

)(







else

allowedjif

alloweds

ikij

In formula (2):

}{

tabuCallowed 

means the next city which is

allowed ant k to choose;

is the information heuristic factor,

means the relative importance of track, it reflects therole of

information which is ants accumulate in athletic process. The

bigger the value, the more the ant inclines to choose the path

which is other ants had passed through, and the more

coordination between the ants;

is the expect stimulating

factor, means the relative importance of visibility, it reflects

the importance of the elicitation information in athletic

process, the bigger the value, the closer the transition

probability to greed rules;

)(t

is inspired function, its

expression as follows:

)(

㸦3㸧

In order to avoid too much residue information to

submerge residual heuristic information, when an ant walks

one step, or completes all of the cities (also known as a loop,

we must update residue information. This update imitate the

characteristics of human brain memory, when new

information into the brain continuously, the old information

stored in the brain with the passage of time decline, or even

forget. Therefore, the information in the path(i,j) at time

t+1,is adjusted following rules:

)()()1()1( ttt ijijij

WWUW

' 

㸦4㸧

' '

)()(

㸦5㸧

In formula (4) and (5),

means pheromone volatile

coefficient, so

1

notes pheromone residual factor. In

order to prevent the infinite accumulation of information, the

values of

for

)1,0[

;)(t

'means the pheromone

increment at path (i,j) in the cycle and

0)0( '

)(t

means the information of ant k

residue sin the path (i, j) in the cycle.

In the Ant-Cycle which is the most commonly used

model,

)6(

),(,

)(°



else

Lji

In formula (6), Q is pheromone strength which is

constant. It influences the algorithm convergence speed to a

certain extent.

means the total length of the paths which

is the ant k walked in the cycle. When all the ants travel all

the cities, we should global update the residual information.

And we only update the optimal path L in this cycle, for its

expres sion:

)7(

),(,

)(°



else

Lji

B. Integration of ant colony algorithm and genetic

algorithm

Compared with intelligent algorithms such as the genetic

algorithm, the chaos algorithm, particle swarm algorithm, the

main advantages of ant colony algorithm is that: (1) Strong

robustness. To modify slightly ant colony algorithm model,

itcan be applied to other problems; (2)Distributed

computing; (3) Combined with other methods easily. Of

course, it also has some defects: The algorithm is generally

need longer search time, and is prone to stagnation

phenomenon, when groups is in large scale, it is difficult to

find out a best path in a short time.

Genetic algorithm which is proposed by American

professor JohnHollnad in 1975, is a type of bionic

optimization algorithm. It uses population search

technology, gives a series of genetic operations on the

current population such as selection, crossover, mutation and

so on. Then produces a new generation of population and

Cop

gradually make the evolution close to the optimal solution. It

has rapid global search capabilityin a wide range. But when

it reaches a certain range, it will make a lot of redundancy

iteration. In a word, it has low efficiency for the exact

solution.

The idea of ant colony algorithm integrates with genetic

algorithm is: Firstly, we produce m optimal paths[7], the

paths stay information, others is unchanged. Then use ant

colony algorithm to complete the cycles, record the optimal

and near-optimal solution each cycle. For the cycle we give

crossover and mutation on optimal and near-optimal solution

to reach the new optimal solution. When we complete all the

cycles, we also get the global optimal solution.

4. The principle of ACGA algorithm

and the solution steps of the WTA

The ant colony algorithm had been used to solve WTA

problem[6]. The ACGA algorithm, which is proposed this

paper, is improved on the basis of the ant colony algorithm.

It brings random number and pheromone updating strategy

to expand the diversity of the initial solution. And brings

crossover operator and mutation operatorto enhance the

ability of looking for the global optimal solution and

accelerate the convergence speed.

This paper utilizes real number code, the length of code

is the number of targets, take 10 weapons hit 10 targets for

example: [1-4-5-6-2-3-9-10-8-7] means weapon 1 hit target 1,

weapon 2 hit target 5, weapon 3 hit target 6, weapon 4 hit

target 2, weapon 5 hit target 3, weapon 6 hit target 4,

weapon 7 hit target 10, weapon 8 hit target 9, weapon 9 hit

target 7, weapon 10 hit target 8.

C. Random number

When we calculate the transition probability

)(tpk

, we

bring the random number 0.1+0.8*rand (1),

)8(

)]([)]([

))1(8.01.0(

)(











else

allowedjif

rand

alloweds

ikij

here, ikikpt )(

So it increases the random selection and the diversity of

the solution, to avoid the algorithm reach the local optimal

early. And the algorithm is simple that can’t increase the

complexity of the algorithm.

D. Pheromone updating strategy

We use the pheromone diminishing strategy which is

mentioned in references[8][9] for the local pheromones

updating strategy.

)9(

),(,

2/min))(1(

))(1(











else

Ljiif

Maxn

MinMaxin

Max

qij



In it, Max means the maximum updating constant of the

pheromone; Min means the minimum updating constant of

the pheromone.

And the global pheromone updating strategy is

)10(min/)()1()1(Eqtt

ijijijij

WWUW

' 

As the new updating strategy, it can avoid the information in

the local optimal path much higher than others. It also

unlimited the further search space that the algorithm isn’t

prone to premature, stagnation phenomenon.

E. Crossover operator

We select randomly the same part of the optimal solution

and near-optimal solution

to crossover, and produce

two new solutions

New

and

New

, then we get the

optimal solution New from

New

and

New

.For

example, suppose that the optimal solution

˙[1-2-3-4-5-

6-9-8-7] and near-optimal solution

=[1-2-3-6-5-4-7-8-9],

the crossover part is from 4 to 6, that’s means we should

crossover the [4-5-6] in

with the [6-5-4] in 2

.We can

get

New

˙[1 -2 -3-6 -5-4 -9 -8-7] ,

New

˙[1 -2 -3-4 -5 -6-7 -8 -

9]. Then according to the values of E, we can get the optimal

solution New from

New

and

New

F. mutation operator

If the solution New meets the mutation probability, to get

the mutated solution Mu , we should select randomly the

mutation position and change it with the one in front of it.

Then we get the local optimal solution from New and Mu.

For example, New˙[1-2-3-6-5-4-9-8-7], the mutation

position is 3, then the mutated solution Mu˙[1-3-2-6 -5-4 -9 -

8-7]. According to the values of E, we can get the local

optimal solution.

G. Stepsof ACGA algorithm

The steps of ACGA algorithm to solve WTA are:

Step 1: Initialize parameters.

Step 2: Use genetic algorithm to produce solutions, leave

pheromone on the paths of the solutions, other paths

unchanged .

Step 3:Cycles

1mncnc

Step 4: m ants are placed in the weapon platform i,

according to the probability

, the ant k transfer to target j ,

until completes the traversal. In the traversal process,

according to the constraints of weapons and targets, we

should update the weapons and targets taboo list.

Step 5: According to formula (9), update the local

pheromone in the process.

Step 6 : From the m traversals, get the solution

and

near-optimal solution

76 Cop

Step 7 : Crossover

with

to get

New

and

New

get optimal solution New.

Step 8: According to the mutation

probability 01.0

p, mutate the solution New to get the

solution Mu. Compared with New and Mu, we get the local

optimal solution.

Step 9: According to formula (10), update the global

pheromone in the local optimal solution.

Step 10: If the number of cycles ncıNmax, end the

cycle and output the results, otherwise empty the tabu list

and jump to step 2.

5. Algorithm testing and analysis

In order to verify the validity of the ACGA algorithm,

take m = 14, n = 14 for example, the experimental data from

reference [10].

We use ant colony algorithm, genetic algorithm and

SAGA algorithm to simulate. Each algorithm runs 100 times,

we select 20 of the best solution as samples. The basic

settings are as follows:

,500max,150,7.0,5,1 NQ

UED

05.0,96.0 MinMax

Table 1 gives the optimal E(oE), average E(aE),

maximum times(maT), minimum times(miT), average

times(aT) when use the three algorithms to solve WTA

problem.

TABLE I. RESULTS OF THREE ALGORITHMS

oE aE maTmiTaT

AC 4.164.924442 179.6

GA 4.394.694789 223.8

ACGA 2.683.133079 224.3

From the table we can see that, the results of ASGA

algorithm is better than ant colony algorithm and genetic

algorithm, that’s means ASGA is superior to the other

algorithms. From the iterative times, the times of ant colony

algorithm arefewer than the other algorithms. That means

ant colony algorithm has convergence speed, but the

accuracy is not very high. In a word, the results show that

ASGA algorithm is superior to the other algorithms.

6. Conclusion

To solve WTA problem especially large-scale has

important theoretical significance and practical value. As

intelligent algorithms, ant colony algorithm and genetic

algorithm are applied to solve WTA problem. They have

different advantages, of course, also have shortcomings. This

paper has studied the integration of genetic algorithms and

ant colony algorithm, bring random number and pheromone

updating strategy to increase the diversity of the solutions;

bring crossover operator and mutation operator to expand the

search space. The improved algorithm of ACGA has strong

global search ability and fast convergence speed. The

simulatedexampleshows that this article is an effective

improved algorithm.

7. Acknowledgment

We would like to thank all the researchers who provided their

assistance. We are grateful to Professor Songgui Wang for

constructive criticisms on the manuscript.  Corresponding author:

yaoxcq@126.com,13810720446.Supportedby NSFC with

No.30800244, 60971075 and by the Natural Science Foundation of

Guangdong Province withNo.7008110

REFERENCES

[1] CAI Huai-ping,CHEN Ying-wu. The Development of

the Research on Weapon-Target Assignment (WTA)

problem[J].Fire Control and Command

Control,2006,31(12):13-15

[2] S.P.Lloyd,H.S.Witsenhause. Weapon allocation is NP-

Complete. Proceeding of the IEEE Summer Simulation

Conference. Reno, Nevada, 1986:1054~1058

[3] Colorni A,Dorigo M,Maniezzo V,et al.Distributed

optimization by ant colonies [A]. Proceedings of

European Conference onArtificialLife.Paris, 1991: 134-

142.

[4] Colorni A,Dorigo M,M aniezzo V.An investigation of

some properties of an ant algorithm.Proceedings Of

Parallel Problem Solving from Nature(PPSN). France:

Elsevier, 1992:509-520.

[5] Dorigo M,Maniezzo V,Colorni A.Ant system:

Optimization by a colony cooperating Agents[J].IEEE

Trans.on Systems,Man andCybernetics.Part

B:Cybernetics(S1083-4419),1996,26(1):29-41.

[6] GAO Shang,Ant Colony Algorithm for Weapon-target

Assignment problem[J]. Computer Engineering and

Applications,2003,78㸫79

[7] DING Jian-Li, CHEN Zeng-Qiang, and YUAN Zhu-

Zhi, On the Combination of Genetic Algorithm and Ant

Algorithm[J], Journal of Computer Research and

development, 2003,40(9): 1351-1354

[8] MA Xi-Jun,PAN Ruo-Yu,YANG Shan-Lin, Ant

Colony Algorithm Based on Pheromone Declining[J]

Journal of System Simulation,2006,18(11):3297-3300.

[9] YUANMei, LINGMing-xiang, ZENG Qing-shuang, An

AntColony Algorithm Based on Pheromone Declining

for Solving theWTA Problem[J], Computer

Simulation,2008,25(2);23-25

[10] CAO Qiying,HE Zhangbing.A Genetic Algorithm of

Solving WTA Problem[J].Control Theory and

Applications , 2001, 18(1): 76-79.

Cop