GENETIC SEARCH - ANALYSIS USING FITNESS MOMENTS

Genetic Algorithms are efficient and robust search methods that are be ing employed in a plethora of applications with extremely large search spaces. The directed search mechanism employed in Genetic Algorithms performs a simultaneous and balanced, exploration of new regions in th e search space and exploitation of already discovered regions. This pa per introduces the notion of fitness moments for analyzing the working of Genetic Algorithms (GAs). We show that the fitness moments in any generation may be predicted from those of the initial population. Sinc e a knowledge of the fitness moments allows us to estimate the fitness distribution of strings, this approach provides for a method of chara cterizing the dynamics of GAs. In particular the average fitness and f itness variance of the population in any generation may be predicted. We introduce the technique of fitness-based disruption of solutions fo r improving the performance of GAs. Using fitness moments, we demonstr ate the advantages of using fitness-based disruption. We also present experimental results comparing the performance of a standard GA and GA s (CDGA and AGA) that incorporate the principle of fitness-based disru ption. The experimental evidence clearly demonstrates the power of fit ness based disruption.