The Exact Schema Theorem
Cyclic and Chaotic Behavior in Genetic Algorithms
Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
Laboratory of Computational Intelligence
Institute for Microtechnologies
Bucharest, PO Box 38-160, 72225 Romania
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.