Investigating the success of spatial coevolution

ABSTRACT

We investigate the results of coevolution of spatially distributed populations. In particular, we describe work in which a simple function approximation problem is used to compare different spatial evolutionary methods. Our work shows that, on this problem, spatial coevolution is dramatically more successful than any other spatial evolutionary scheme we tested. Our results support two hypotheses about the source of spatial coevolution's superior performance: (1) spatial coevolution allows population diversity to persist over many generations; and (2) spatial coevolution produces training examples ("parasites") that specifically target weaknesses in models ("hosts"). The precise mechanisms by which the combination of spatial embedding and coevolution produces these results are still not well understood.

REFERENCES

• 1: John Cartlidge , Seth Bullock, Combating Coevolutionary Disengagement by Reducing Parasite Virulence, Evolutionary Computation, v.12 n.2, p.193-222, June 2004 [doi>10.1162/106365604773955148]
• 2: W. Daniel Hillis, Co-evolving parasites improve simulated evolution as an optimization procedure, Physica D, v.42 n.1-3, p.228-234, June 1990
• 3: Hugues Juillé , Jordan B. Pollack, Coevolutionary Learning: A Case Study, Proceedings of the Fifteenth International Conference on Machine Learning, p.251-259, July 24-27, 1998
• 4: John R. Koza, Genetic programming: a paradigm for genetically breeding populations of computer programs to solve problems, Stanford University, Stanford, CA, 1990
• 5: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 6: Pagie, L. & Hogeweg, P. (1997); Evolutionary consequences of coevolving targets. Evolutionary Computation 5(4):401--418.
• 7: Pagie, L. & Mitchell, M. (2002). A comparison of evolutionary and coevolutionary search. International Journal of Computational Intelligence and Applications, 2(1), 53--69.
• 8: Christopher Darrell Rosin, Coevolutionary search among adversaries, University of California at San Diego, La Jolla, CA, 1997
• 9: Christopher D. Rosin , Richard K. Belew, Methods for Competitive Co-Evolution: Finding Opponents Worth Beating, Proceedings of the 6th International Conference on Genetic Algorithms, p.373-381, July 15-19, 1995
• 10: Watson, R.A. and Pollack, J.B. (2001). Coevolutionary Dynamics in a Minimal Substrate. In Spector, L. et al. (Eds), Proceedings of the 2001 Genetic and Evolutionary Computation Conference, pp. 702--709 San Mateo, CA: Morgan Kaufmann.
• 11: Werfel, J., Mitchell, M., and Crutchfield, J. P. (2000). Resource sharing and coevolution in evolving cellular automata. IEEE Transactions on Evolutionary Computation, 4(4), 388--393

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms

Keywords:
coevolution, genetic programming, resource sharing, spatial evolution