Acquiring evolvability through adaptive representations

ABSTRACT

Adaptive representations allow evolution to explore the space of phenotypes by choosing the most suitable set of genotypic parameters. Although such an approach is believed to be efficient on complex problems, few empirical studieshave been conducted in such domains. In this paper, three neural network representations, a direct encoding, a complexifying encoding, and an implicit encoding capable of adapting the genotype-phenotype mapping are compared on Nothello, a complex game playing domain from the AAAI General Game Playing Competition. Implicit encoding makes the search more efficient and uses several times fewer parameters. Random mutation leads to highly structured phenotypic variation that is acquired during the course of evolution rather than built into the representation itself. Thus, adaptive representations learn to become evolvable, and furthermore do so in a way that makes search efficient on difficult coevolutionary problems.

REFERENCES

• 1: A.-L. Barabasi and Z. N. Oltvai. Network biology: Understanding the cell's functional organization. Nature Reviews Genetics, 5:101--113, 2004.
• 2: P. J. 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, San Francisco, 1999. Kaufmann.
• 3: A. Bergman and M. L. Siegal. Evolutionary capacitance as a general feature of complex gene networks. Nature, 424:549--552, 2003.
• 4: J. Bongard, Evolving modular genetic regulatory networks, Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress, p.1872-1877, May 12-17, 2002
• 5: E. H. Davidson. Genomic Regulatory Systems. Academic Press, San Diego, 2001.
• 6: Edwin de Jong, The MaxSolve algorithm for coevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068091]
• 7: 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.
• 8: Sevan G. Ficici, Monotonic solution concepts in coevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068093]
• 9: M. R. Genesereth, N. Love, and B. Pell. General game playing: Overview of the aaai competition. AI Magazine, 26(2):62--72, 2005.
• 10: 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.
• 11: M. Kirschner and J. Gerhart. Evolvability. PNAS, 95:8420--8427, 1998.
• 12: D. E. Knuth and R. W. Moore. An analysis of alpha-beta pruning. Art. Intelligence, 6:293--326, 1975.
• 13: R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Shefer, and U. Alon. Superfamilies of evolved and designed networks. Science, 303(5663):1538--1542, March 2004.
• 14: R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: Simple building blocks of complex networks. Science, 298:824--827, 2002.
• 15: N. J. Radcliffe. Genetic set recombination and its application to neural network topology optimization. Neural computing and applications, 1(1):67--90, 1993.
• 16: R. A. Raff. The Shape of Life: Genes, development, and the Evolution of Animal Form. The University of Chicago Press, 1996.
• 17: 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.
• 18: Joseph Reisinger , Risto Miikkulainen, Selecting for evolvable representations, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144199]
• 19: Tom Smith , Phil Husbands , Paul Layzell , Michael O'Shea, Fitness landscapes and evolvability, Evolutionary Computation, v.10 n.1, p.1-34, Spring 2002 [doi>10.1162/106365602317301754]
• 20: 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]
• 21: K. O. Stanley and R. Miikkulainen. Competitive coevolution through evolutionary complexification. J. of Artificial Intel ligence Research, 21:63--100, 2004.
• 22: Marc Toussaint, Compact representations as a search strategy: compression EDAs, Theoretical Computer Science, v.361 n.1, p.57-71, 28 August 2006 [doi>10.1016/j.tcs.2006.04.005]
• 23: L. Van Valin. A new evolutionary law. Evolution Theory, 1:1--30, 1973.

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
          Subjects: Heuristic methods

General Terms:
Design, Experimentation, Performance

Keywords:
adaptive representations, coevolution, evolvability, genetic algorithms, indirect encodings, modularity, neural networks