The Exact Schema Theorem

Cyclic and Chaotic Behavior in Genetic Algorithms

Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
wright@cs.umt.edu
(406) 243-4790
http://www.cs.umt.edu/u/wright/wright.htm

Alexandru Agapie
Laboratory of Computational Intelligence 
Institute for Microtechnologies
Bucharest, PO Box 38-160, 72225 Romania
agapie@imt.pub.ro


Abstract

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.