Cyclic and chaotic behavior in genetic algorithms
Alden H. Wright, Alexandru Agapie · 2001
This paper demonstrates dynamical system models of genetic algorithms that exhibit cycling and chaotic behavior. The genetic algorithm is a binary-representation genetic algorithm with truncation selection and a density-dependent mutation. The density dependent mutation has a separate mutation rate for each bit position which is a function of the level of convergence at that bit position. Density-dependent mutation is a very plausible method to maintain diversity in the genetic algorithm. Further, the introduction of chaos can potentially be used as a source of diversity in a genetic algorithm. The cycling/chaotic behavior is most easily seen in a 1-bit genetic algorithm, but it also occurs in genetic algorithms over longer strings, and with and without crossover. Dynamical system models of genetic algorithms model the expected behavior or the algorithm, or the behavior in the limit as the population size goes to infinity. These models are useful because they can show behavior of a genetic algorithm that can be masked by the stochastic effects of running a genetic algorithm with a finite population. The most extensive development of dynamical systems models has been done by Michael Vose and coworkers. (See [Vose and Liepins, 1991], [Vose and Wright, 1994] and [Vose, 1999] for examples.) They have developed an elegant theory of simple genetic algorithms based on random heuristic search. Heuristic search theory is based on the idea of a heuristic map G, which is a map from a population space to itself. The map G includes all of the dynamics of the simple genetic algorithm. The map defines a discrete-time dynamical system which we call the infinite population model. The simple genetic algorithm heuristic G is called focused if G is continuously differentiable and if the sequence