String- and Permutation-Coded Genetic Algorithms for the Static Weapon-Target Assignment Problem

In the Weapon-Target Assignment Problem, m enemy tar-gets are inbound, each with a value Vj representing the dam-age it may do. The defense has n weapons, and the prob-ability that weapon i will kill target j is pij. The problem is to assign the weapons to targets so as to reduce as much as possible the total expected value of the targets. A greedy heuristic for this problem repeatedly assigns a weapon to a target to maximally degrade the target's value. Two genetic algorithms encode candidate assignments as strings of tar-get labels indexed by weapon labels and as permutations of weapon labels decoded by a greedy algorithm, respectively. Both GAs can be seeded with the greedy heuristic's solu-tion. In comparisons on fteen randomly-generated problem instances, all the algorithms signicantly reduced the hypo-thetical strikes ' values, but the greedy heuristic was both eective and fast, while the seeded permutation-coded GA returned the best results. The times that all the GAs require grow quickly with problem size. c ACM, 2009. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The denitive version was published in Proceedings of the Genetic and Evolutionary Computatio