string- and permutation-coded genetic algorithms for the static weapon-target assignment problem
In the Weapon-Target Assignment Problem, m enemy targets are inbound, each with a value V j representing the damage it may do. The defense has n weapons, and the probability that weapon i will kill target j is p ij . 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 target 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 solution. In comparisons on fifteen randomly-generated problem instances, all the algorithms significantly reduced the hypothetical strikes' values, but the greedy heuristic was both effective and fast, while the seeded permutation-coded GA returned the best results. The times that all the GAs require grow quickly with problem size.
permutations weapon-target assignment problem maximum marginal return representations coding