AN EVALUATION OF LOCAL IMPROVEMENT OPERATORS FOR GENETIC ALGORITHMS

Genetic algorithms have demonstrated considerable success in providing good solutions to many NP-hard optimization problems. For such proble ms, exact algorithms that always find an optimal solution are only use ful for small toy problems, so heuristic algorithms such as the geneti c algorithm must be used in practice. In this paper, we apply the gene tic algorithm to the NP-hard problem of multiple fault diagnosis (MFD) . We compare a pure genetic algorithm with several variants that inclu de local improvement operators. These operators, which are often domai n-specific, are used to accelerate the genetic algorithm in converging on optimal solutions. Our empirical results indicate that by using th e appropriate local improvement operator, the genetic algorithm is abl e to find an optimal solution in all but a tiny fraction of the cases and at a speed orders of magnitude faster than exact algorithms.