Dynamic Properties of Minimal Algorithms for Coevolution

Enrique Pujals | Funes, Pablo

Keywords: Coevolution

One characteristic that differentiates coevolution from regular evolution is the existence of intransitivities (rock-scissors-paper). It is only recently that abstract models have begun to be used to study coevolution\emph{. Numbers Games} in particular, have been studied by several authors as minimal models of intransitivities. Here we carry out an analytical study of the dynamics of basic coevolutionary algorithms in the presence of intransitivities, focusing on two-dimensional numbers games. Rather than testing out different algorithms, we focus on using formal proofs. We show that depending on the nature of the problem, the coevolutionary hill-climber C(1+1) either makes progress with constant average speed or behaves as a random walk, wondering aimlessly. Also, depending on the space, optimal elements exist but are never reached. Larger populations make the analysis more difficult and do not bring qualitative changes into those dynamics, except on specific cases.

Anexos:

• rw3.pdf