Towards an empirical measure of evolvability

ABSTRACT

Genetic representations that do not employ a one-to-one mapping of genotype to phenotype are known as indirect encodings, and can be much more efficient than direct encodings for complex problems. Increasing a representation's capacity to facilitate effective search, i.e. its evolvability, has long been a goal of Evolutionary Computation. However, currently no benchmarks exist to measure evolvability. One reason is that it is difficult to decouple a representation's capacity to evolve under any fitness function, i.e. the latent evolvability, and its performance on a specific benchmark. Towards this goal, a method is proposed in this paper that measures the representation's ability to extract invariant properties from a changing fitness function. The test is applied to three distinct representations and it is able to distinguish all three. Ultimately, this test can serve as the foundation for performing controlled experiments determining what factors contribute to evolvability.

REFERENCES

• 1: A.-L. Barabási and Z. N. Oltvai. Network biology: Understanding the cell's functional organization. Nature Reviews Genetics, 5:101--113, 2004.
• 2: A. Bergman and M. L. Siegal. Evolutionary capacitance as a general feature of complex gene networks. Nature, 424:549--552, 2003.
• 3: J. C. Bongard. Evolving modular genetic regulatory networks. In Proc. of CEC 2002, pages 1872--1877. IEEE Press, 2002.
• 4: Marc Ebner , Mark Shackleton , Rob Shipman, How neutral networks influence evolvability, Complexity, v.7 n.2, p.19-33, November/December 2001 [doi>10.1002/cplx.10021]
• 5: P. Eggenberger. Evolving morphologies of simulated 3d organisms based on differential gene expression. Proc. of the 4th European Conf. on Artificial Life, pages 205--213, 1997.
• 6: W. Fontana. Modeling 'evo-devo' with rna. BioEssays, 24:1164--1177, 2002.
• 7: Faustino Gomez , Risto Mikkulainen, Incremental evolution of complex general behavior, Adaptive Behavior, v.5 n.3-4, p.317-342, Winter/Spring 1997 [doi>10.1177/105971239700500305]
• 8: T. F. Hansen. Is modularity necessary for evolvability? remarks on the relationship between pleiotropy and evolvability. BioSystems, 69:83--94, 2002.
• 9: J. Hermisson and G. Wagner. The population genetic theory of hidden variance and genetic robustness. Genetics, 168:2271--2284, 2004.
• 10: P. Hogeweg. Evolving mechanisms of morphogenesis: On the interplay between differential adhesion and cell differentiation. Jour. of Theo. Bio., 203:317--333, 2000.
• 11: H. Lipson, J. Pollack, and N. Suh. On the origin of modular variation. Evolution, 56(8):1549--1556, 2002.
• 12: J. Maynard-Smith, R. Burian, S. Kauffman, P. Alberch, J. Campbell, B. Goodwin, R. Lande, D. Raup, and L. Wolpert. Developmental constraints and evolution. The Quarterly Review of Biology, 60(3):265--287, 1985.
• 13: R. A. Raff. The Shape of Life: Genes, development, and the Evolution of Animal Form. The University of Chicago Press, 1996.
• 14: R. A. Raff and B. J. Sly. Modularity and dissociation in the evolution of gene expression territories in development. Evolution and Development, 2(2):102--113, 2000.
• 15: I. Rechenberg. Evolutionsstrategie '94. Friedrich Frommann Verlag, 1994.
• 16: J. Smith and T. Fogarty. Operator and parameter adaption in genetic algorithms. Soft Computing, 1:81--87, 1997.
• 17: B. M. R. Stadler, P. F. Stadler, G. Wagner, and W. Fontana. The topology of the possible: Formal spaces underlying patterns of evolutionary change. Journal of Theoretical Biology, 213:241--274, 2001.
• 18: Kenneth O. Stanley , Risto Miikkulainen, Evolving neural networks through augmenting topologies, Evolutionary Computation, v.10 n.2, p.99-127, Summer 2002 [doi>10.1162/106365602320169811]
• 19: Kenneth O. Stanley , Risto Miikkulainen, A Taxonomy for artificial embryogeny, Artificial Life, v.9 n.2, p.93-130, Spring 2003 [doi>10.1162/106454603322221487]
• 20: C. H. Waddington. Canalization of development and the inheritance of acquired characters. Nature, 150:563, 1942.
• 21: G. Wagner and L. Altenberg. Complex adaptations and the evolution of evolvability. Evolution, 50(3):967--976, 1996.
• 22: C.-H. Yuh and E. H. Davidson. Modular cis-regulatory organization of endo16, a gut-specific gene of the sea urchin embryo. Development, 122:1069--1082, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

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

General Terms:
Experimentation, Measurement, Performance

Keywords:
development, evolvability, genetic algorithms, genetic regulatory networks, indirect encodings, representations