Selecting for evolvable representations

ABSTRACT

Evolutionary algorithms tend to produce solutions that are not evolvable: Although current fitness may be high, further search is impeded as the effects of mutation and crossover become increasingly detrimental. In nature, in addition to having high fitness, organisms have evolvable genomes: phenotypic variation resulting from random mutation is structured and robust. Evolvability is important because it allows the population to produce meaningful variation, leading to efficient search. However, because evolvability does not improve immediate fitness, it must be selected for indirectly. One way to establish such a selection pressure is to change the fitness function systematically. Under such conditions, evolvability emerges only if the representation allows manipulating how genotypic variation maps onto phenotypic variation and if such manipulations lead to detectable changes in fitness. This research forms a framework for understanding how fitness function and representation interact to produce evolvability. Ultimately evolvable encodings may lead to evolutionary algorithms that exhibit the structured complexity and robustness found in nature.

REFERENCES

• 1: Christoph Adami, Introduction to artificial life, Springer-Verlag New York, Inc., New York, NY, 1999
• 2: P. Bentley and S. Kumar. Three ways to grow designs: A comparison of embryogenies for an evolutionary design problem. In Proc. of the Genetic and Evolutionary Computation Conference, pages 35--43, Orlando, Florida, USA, 1999. Morgan Kaufmann.
• 3: Raffaele Calabretta , Stefano Nolfi , Domenico Parisi , Günter P. Wagner, Duplication of modules facilitates the evolution of functional specialization, Artificial Life, v.6 n.1, p.69-84, Dec. 1999 [doi>10.1162/106454600568320]
• 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: T. F. Hansen. Is modularity necessary for evolvability? Remarks on the relationship between pleiotropy and evolvability. BioSystems, 69:83--94, 2002.
• 6: G. S. Hornby. Functional scalability through generative representations: The evolution of table designs. Environment and Planning B: Planning and Design, 31(4):569--587, 2004.
• 7: G. S. Hornby and J. B. Pollack. The advantages of generative grammatical encodings for physical design. In Proc. of CEC 2001, 2001.
• 8: M. A. Huynen. Exploring phenotype space through neutral evolution. Journal of Molecular Evolution, 43:165--169, 1996.
• 9: N. Kashtan and U. Alon. Spontaneous evolution of modularity and network motifs. Proc. of the National Academy of Sciences, 102(39), 2005.
• 10: M. Kirschner and J. Gerhart. Evolvability. PNAS, 95:8420--8427, 1998.
• 11: Vladimír Kvasnička , Jiří Pospíchal, Emergence of modularity in genotype-phenotype mappings, Artificial Life, v.8 n.4, p.295-310, Fall 2002 [doi>10.1162/106454602321202390]
• 12: G. E. Liepins and M. D. Vose. Representational issues in genetic optimization. Journal of Experimental and Theoretical Artificial Intelligence, 2:101--115, 1990.
• 13: H. Lipson, J. Pollack, and N. Suh. On the origin of modular variation. Evolution, 56(8):1549--1556, 2002.
• 14: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]
• 15: R. A. Raff. The Shape of Life: Genes, development, and the Evolution of Animal Form. The University of Chicago Press, 1996.
• 16: Joseph Reisinger , Kenneth O. Stanley , Risto Miikkulainen, Towards an empirical measure of evolvability, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102315]
• 17: 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]
• 18: 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]
• 19: Adrian Thompson , Paul J. Layzell, Evolution of Robustness in an Electronics Design, Proceedings of the Third International Conference on Evolvable Systems: From Biology to Hardware, p.218-228, April 17-19, 2000
• 20: M. Toussaint. Compact representations as a search strategy: Compression EDA. Theoretical Computer Science, In press.
• 21: E. A. Variano, J. H. McCoy, and H. Lipson. Networks, dynamics and modularity. Physical Review Letters, 92(18), 2004.
• 22: G. Wagner and L. Altenberg. Complex adaptations and the evolution of evolvability. Evolution, 50(3):967--976, 1996.
• 23: Richard A. Watson , Jordan B. Pollack, Symbiotic Composition and Evolvability, Proceedings of the 6th European Conference on Advances in Artificial Life, p.480-490, September 10-14, 2001
• 24: D. Whitley, S. Rana, and R. Heckendorn. Representation Issues in Neighborhood Search and Evolutionary Algorithms, pages 39--58. John Wiley and Sons Ltd., 1997.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global 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, estimation-of-distribution, evolvability, genetic algorithms, indirect encodings, modularity, representations