Raisanen and Whitaker compare four different genetic algorithms (GAs) for solving the antenna placement problem. The problem of where to place a series of antennae for a wireless network (in this particular case, a cellular network) is a nondeterministic polynomial time hard (NP-hard) optimization problem, with the optimization criteria being maximal service coverage and lowest financial cost (the fewer antennae needed, the less expensive the network).
Many techniques exist for generating approximate solutions for NP-hard problems. An objective function generates some measure of the performance of a candidate solution. For example, the objective function for solving the traveling salesperson problem (TSP) would be the total length of a candidate route. An objective function for antenna placement would be some measure of how well the set of antennae placements cover a particular region and how costly the solution is. It is possible that there are multiple objective functions that are optimized simultaneously.
Recently, GAs have been of particular interest for approximating hard combinatorial problems. A genetic algorithm begins with a set of candidate solutions to a problem, and then selects better solutions based on the objective functions. The GA then generates a new population of candidate solutions using some form of recombination.
Each GA in this study has been previously published, has different fitness selection criteria, and has a different method for recombining candidate solutions. The comparison considers not only the performance between the solutions based on the objective functions, but also how quickly each GA generates a solution. As might be expected, the authors find that there is a tradeoff between the speed in which a GA converges to a solution and the quality of the solution. Two of the GAs generate solutions that are very similar, but converge to a solution more slowly than a third GA, which generates worse solutions but is faster. The fourth GA in the comparison generates very poor solutions, but executes very quickly.
This paper is well written, and presents a nice application of GAs, as well as a methodology for comparing GAs.