Genetic search: analysis using fitness moments

Abstract

Genetic algorithms (GAs) are efficient and robust search methods that are being employed in a plethora of applications with extremely large search spaces. The directed search mechanism employed in GAs performs a simultaneous and balanced exploration of new regions in the search space and exploitation of already-discovered regions. This paper introduces the notion of fitness moments for analyzing the working of GAs. We show that the fitness moments in any generation may be predicted from those of the initial population. Since a knowledge of the fitness moments allows us to estimate the fitness distribution of strings, this approach provides for a method of characterizing the dynamics of GAs. In particular, the average fitness and fitness variance of the population in any generation may be predicted. We introduce the technique of fitness-based disruption of solutions for improving the performance of GAs. Using fitness moments, we demonstrate the advantages of using fitness-based disruption. We also present experimental results comparing the performance of a standard GA and two other GAs (the controlled disruption GA and the adaptive GA) that incorporate the principle of fitness-based disruption. The experimental evidence clearly demonstrates the power of fitness-based disruption