Genetic Algorithms: From Hegemony to Chaos
Philippe Collard
Electronic mail address: pc@i3s.unice.fr
Manuel Clergue
Electronic mail address: clerguem@i3s.unice.fr
I3S Laboratory---CNRS, University of Nice-Sophia Antipolis,
2000 Rte des Lucioles,
Biot Sophia-Antipolis, F-06410, France
Abstract
Genetic algorithms are known to be convergent algorithms, with the final population tending to become homogeneous. In this paper we show that it is possible to exhibit complex dynamics for a genetic algorithm by slightly modifying the canonical algorithm. Indeed, adding a metalevel in the interpretation of the individuals, associated with a coupling between individuals, gives rise to periodic or chaotic behavior. The first part of the paper is dedicated to the presentation of the dual concept, together with an implementation of this concept: the dual genetic algorithm. Then a minimal model of the dynamical behavior of dual genetic algorithms is proposed and examined. This part emphasizes the fact that dual genetic algorithms converge toward heterogeneous populations. This feature allows us to claim that dual genetic algorithms should be efficient in problems where the conservation of the polymorphism of the population is critical. The second part of the paper presents how the introduction of a coupling between individuals in dual genetic algorithms leads to chaotic behaviors. Two routes towards chaos are observed: period doubling and quasiperiodic. We conclude with a discussion about the use of chaos in artificial evolving systems such as genetic algorithms.
