Predicting Convergence Time for Genetic Algorithms

It is difficult to predict a genetic algorithm's behavior on an arbitrary problem. Combining genetic algorithm theory with practice we use the average hamming distance as a syntactic metric to derive bounds on the time convergence of genetic algorithms. Analysis of a flat function provides worst case time complexity for static functions. Further, employing linearly computable runtime information, we provide bounds on the time beyond which progress is unlikely on arbitrary static functions. As a byproduct, this analysis also provides qualitative bounds by predicting average fitness. 1 Introduction A Genetic Algorithm (GA) is a randomized parallel search method modeled on natural selection (Holland 1975). GAs are being applied to a variety of problems and are becoming an important tool in machine learning and function optimization (Goldberg 1989). Their beauty lies in their ability to model the robustness, flexibility and graceful degradation of biological systems. Natural selection use..