The dynamics of genetic algorithms in interactive environments

We analyze the behavior of a simple genetic algorithm (GA) which is used to simulate the learning behavior of a population of interacting agents. Due to the fact that in this setup-contrary to traditional optimization setups-the fitness of a string depends on the current state of the population, existing theoretical results cannot be applied. We construct a Markov process which gives an exact representation of the behavior of GAs in such systems and show that for small mutation probabilities the limit distribution is concentrated near the uniform states. Further, we determine a system of difference equations whose solution orbits are a good approximation of the trajectory of the Markov process, at least for large populations. In fact, we prove that the maximal deviation of the two trajectories on any bounded time interval converges to zero in probability as the population size grows without bounds. Finally, we give some results concerning the local stability properties of the uniform states. (C) 1996 Academic Press Limited