Finite Markov Chain Analysis of Genetic Algorithms with Niching
Jeffrey D. Horn · 1993
Finite, discrete-time Markov chain models of genetic algorithms have been used successfully in the past to understand the complex dynamics of a simple GA. Markov chains can exactly model the GA by accounting for all of the stochasticity introduced by various GA operators, such as initialization, selection, crossover, and mutation. Although such models quickly become unwieldy with increasing population size or genome length, they provide initial insights that guide our development of approximate, scalable models. In this study, we use Markov chains to analyze the stochastic effects of the "niching operator" of a niched GA. Specifically, we model the effect of fitness sharing on a single-locus genome. Without niching, our model is an absorbing Markov chain. With niching, we are dealing with a "quasi-ergodic" Markov chain. Rather than calculating expected times to absorption, we are interested in steady-state probabilities for positive recurrent states. Established techniques for analyzin...