The role of speciation in spatial coevolutionary function approximation

ABSTRACT

The role of space is more and more accepted as a way to dramatically improve the success of coevolutionary function approximation. The process behind this success however is not yet fully understood. It is suggested that spatiality causes a persistence in the population diversity over generations and a better targeting of weak points in the host-population by means of the parasite.

In this paper we will discuss the role of spatial pattern formation and speciation in coevolutonary function approximation and the influence on the success rate of coevolution.

We observe specific patterns of speciation in the problems as well in the problem solving-population (LISP functions). These patterns depend on a combination of the functions and the fitness criteria. The success of the spatial coevolutionary process can be understood from the speciation patterns: only if the problems speciate such that 'easy ones' are first evaluated, the coevolutionary process is successful.

REFERENCES

• 1: 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
• 2: Juillé, H., & Pollack, J. B. (1996). Co-evolving intertwined spirals. In L. Fogel, P. Angeline,& T. Baeck (Eds.), Evolutionary Programming V: Proceedings of the Fifth Annual Conference on Evolutionary Programming (pp. 461Â--467). Cambridge, MA: The MIT Press.
• 3: Pagie, L. & Hogeweg, P. (1997); Evolutionary consequences of coevolving targets. Evolutionary Computation 5(4):401--418.
• 4: Pagie, L. & Mitchell, M. (2002). A comparison of evolutionary and coevolutionary search. International Journal of Computational Intelligence and Applications, 2(1), 53--69.
• 5: Mitchell, M., Thomure, M. D. And Williams, N. L.(2006) The role of space in the Success of Coevolutionary Learning. Proceedings of ALIFE X - The Tenth International Conference on the Simulation and Synthesis of Living Systems, 2006.
• 6: Nathan Williams , Melanie Mitchell, Investigating the success of spatial coevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068096]
• 7: M. C. Boerlijst , P. Hogeweg, Spiral wave structure in pre-biotic evolution: hypercycles stable against parasites, Physica D, v.48 n.1, p.17-28, Feb. 1991 [doi>10.1016/0167-2789(91)90049-F]
• 8: Savill, N. J. (1997); Eco-evolutionary consequences of spatial pattern formation. Ph. D. thesis, Dep. Theor. Biol./Bioinformatics, Utrecht.
• 9: Susan L. Epstein, Toward an Ideal Trainer, Machine Learning, v.15 n.3, p.251-277, June 1994 [doi>10.1023/A:1022637925775]
• 10: Pagie, L. (1999); Coevolutionary dynamics: information integration, speciation, and red queen dynamics. In: Information integration in evolutionary processes, chap. 5. pp. 67--93.
• 11: Juillé, H. and Pollack, J. B. (1998). Coevolving the 'ideal' trainer: Application to the discovery of cellular automata rules. In Genetic Programming 1998: Proceedings of the Third Annual Conference, San Francisco, CA. Morgan Kaufmann.
• 12: Edwin D. De Jong , Jordan B. Pollack, Ideal Evaluation from Coevolution, Evolutionary Computation, v.12 n.2, p.159-192, June 2004 [doi>10.1162/106365604773955139]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.0 General

General Terms:
Theory

Keywords:
CA, coevolution, function optimization, spatial pattern formation, speciation