Compositional Pattern Producing Networks: A Novel Abstraction of Development
Inhaltsverzeichnis
Reference
Stanley, Kenneth O.: Compositional Pattern Producing Networks: A Novel Abstraction of Development. Genetic Programming and Evolvable Machines 8(2), 131–162 (2007)
DOI
http://link.springer.com/article/10.1007%2Fs10710-007-9028-8
Abstract
Natural DNA can encode complexity on an enormous scale. Researchers are attempting to achieve the same representational efficiency in computers by implementing developmental encodings, i.e. encodings that map the genotype to the phenotype through a process of growth from a small starting point to a mature form. A major challenge in in this effort is to find the right level of abstraction of biological development to capture its essential properties without introducing unnecessary inefficiencies. In this paper, a novel abstraction of natural development, called Compositional Pattern Producing Networks (CPPNs), is proposed. Unlike currently accepted abstractions such as iterative rewrite systems and cellular growth simulations, CPPNs map to the phenotype without local interaction, that is, each individual component of the phenotype is determined independently of every other component. Results produced with CPPNs through interactive evolution of two-dimensional images show that such an encoding can nevertheless produce structural motifs often attributed to more conventional developmental abstractions, suggesting that local interaction may not be essential to the desirable properties of natural encoding in the way that is usually assumed.
Extended Abstract
Bibtex
Used References
Dellaert, F.: Toward a biologically defensible model of development. Master’s thesis, Case Western Reserve University, Clevekand, OH (1995)
Kandel, E.R., Schwartz, J.H., Jessell, T.M. (eds.) Principles of Neural Science. Elsevier, Amsterdam, 3rd edn (1991)
Zigmond, M.J., Bloom, F.E., Landis, S.C., Roberts, J.L., Squire, L.R. (eds.) Fundamental Neuroscience. Academic Press, London (1999)
Deloukas, P., Schuler, G.D., Gyapay, G., Beasley, E.M., et al.: A physical map of 30,000 human genes. Science 282, 744–746 (1998) http://dx.doi.org/10.1126/science.282.5389.744
Angeline, P.J.: Morphogenic evolutionary computations: Introduction, issues and examples. In: McDonnell, J.R., Reynolds, R.G., Fogel, D.B. (eds.) Evolutionary Programming IV: The Fourth Annual Conference on Evolutionary Programming, pp. 387–401. MIT Press, Cambridge (1995)
Bentley, P.J., Kumar, S.: The ways to grow designs: A comparison of embryogenies for an evolutionary design problem. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), pp. 35–43. Kaufmann, San Francisco (1999)
Hornby, G.S., Pollack, J.B.: Creating high-level components with a generative representation for body-brain evolution. Artif. Life 8, 223–246 (2002) http://dx.doi.org/10.1162/106454602320991837
Stanley, K.O., Miikkulainen, R.: A taxonomy for artificial embryogeny. Artif. Life 9, 93–130 (2003) http://dx.doi.org/10.1162/106454603322221487
Stanley, K.O., Bryant, B.D., Miikkulainen, R.: Real-time neuroevolution in the NERO video game. IEEE T. Evolut. Comput. Special Issue Evolut. Comput. Games 9, 653–668 (2005)
Stanley, K.O., Miikkulainen, R.: Evolving neural networks through augmenting topologies. Evolutionary Comput. 10, 99–127 (2002) http://dx.doi.org/10.1162/106365602320169811
Stanley, K.O., Miikkulainen, R.: Competitive coevolution through evolutionary complexification. J. Artif. Intell. Res. 21, 63–100 (2004)
Astor, J.S., Adami, C.: A developmental model for the evolution of artificial neural networks. Artif. Life 6, 189–218 (2000) http://dx.doi.org/10.1162/106454600568834
Boers, E.J.W., Kuiper, H.: Biological metaphors and the design of modular artificial neural networks. Master’s thesis, Departments of Computer Science and Experimental and Theoretical Psychology at Leiden University, The Netherlands (1992)
Bongard, J.C.: Evolving modular genetic regulatory networks. In: Proceedings of the 2002 Congress on Evolutionary Computation (2002)
Bongard, J.C., Pfeifer, R.: Repeated structure and dissociation of genotypic and phenotypic complexity in artificial ontogeny. In: Spector, L. et al. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference. Kaufmann, San Francisco, pp. 829–836 (2001)
Dellaert, F., Beer, R.D.: A developmental model for the evolution of complete autonomous agents. In: Maes, P., Mataric, M.J., Meyer, J.-A., Pollack, J., Wilson, S.W. (eds.) From Animals to Animats 4: Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior. MIT Press, Cambridge, MA (1996)
Eggenberger, P.: Evolving morphologies of simulated 3D organisms based on differential gene expression. In: Husbands, P., Harvey, I. (eds.) Proceedings of the Fourth European Conference on Artificial Life, pp. 205–213. MIT Press, Cambridge, MA (1997)
Federici, D.: Evolving a neurocontroller through a process of embryogeny. In: Schaal, S., Ijspeert, A.J., Billard, A., Vijayakumar, S., Hallam, J., Jean-Arcady (eds.) Proceedings of the Eighth International Conference on Simulation and Adaptive Behavior (SAB-2004), pp. 373–384. MIT Press, Cambridge, MA (2004a)
Federici, D.: Using embryonic stages to increase the evolvability of development. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004) Workshop Program. Springer-Verlag, Berlin (2004b)
Fleischer, K., Barr, A.H.: A simulation testbed for the study of multicellular development: The multiple mechanisms of morphogenesis. In: Langton, C.G. (ed.) Artificial Life III, pp. 389–416. Addison-Wesley, Reading (1993)
Gruau, F., Whitley, D., Pyeatt, L.: A comparison between cellular encoding and direct encoding for genetic neural networks. In: Koza, J.R., Goldberg, D.E., Fogel, D.B., Riolo, R.L., (eds.) Genetic Programming 1996: Proceedings of the First Annual Conference, pp. 81–89. Cambridge, MA: MIT Press (1996)
Hornby, G.S., Pollack, J.B.: The advantages of generative grammatical encodings for physical design. In: Proceedings of the 2002 Congress on Evolutionary Computation (2001a)
Hornby, G.S., Pollack, J.B.: Body-brain co-evolution using L-systems as a generative encoding. In: Spector, L. et al. (ed.) Proceedings of the Genetic and Evolutionary Computation Conference. Kaufmann, San Francisco (2001b)
Jakobi, N.: Harnessing morphogenesis. In: Proceedings of Information Processing in Cells and Tissues, pp. 29–41. University of Liverpool (1995)
Kaneko, K., Furusawa, C.: Emergence of multicellular organisms with dynamic differentiation and spatial pattern. Artif. Life 4, 79–93 (1998) http://dx.doi.org/10.1162/106454698568459
Kauffman, S.A.: The Origins of Order. Oxford University Press, New York (1993)
Kitano, H.: Designing neural networks using genetic algorithms with graph generation system. Complex Syst. 4, 461–476 (1990)
Komosinski, M., Rotaru-Varga, A.: Comparison of different genotype encodings for simulated 3D agents. Artif. Life 7, 395–418 (2001) http://dx.doi.org/10.1162/106454601317297022
Lindenmayer, A.: Mathematical models for cellular interaction in development parts I and II. J. Theor. Biol. 18, 280–299; 300–315 (1968) http://dx.doi.org/10.1016/0022-5193(68)90079-9
Lindenmayer, A.: Adding continuous components to L-systems. In: Rozenberg, G., Salomaa, A. (eds.) L Systems, Lecture Notes in Computer Science 15, pp. 53–68. Springer-Verlag, Heidelberg, Germany (1974)
Miller, J.F.: Evolving a self-repairing, self-regulating, French flag organism. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004). Springer Verlag, Berlin (2004)
Mjolsness, E., Sharp, D.H., Reinitz, J.: A connectionist model of development. J. Theor. Biol. 152, 429–453 (1991) http://dx.doi.org/10.1016/S0022-5193(05)80391-1
Nolfi, S., Parisi, D.: Growing neural networks. Technical Report PCIA-91- 15. Institute of Psychology, C.N.R., Rome (1991)
Prusinkiewicz, P., Lindenmayer, A.: The Algorithmic Beauty of Plants. Springer-Verlag, Heidelberg, Germany (1990)
Schnier, T.: Evolved representations and their use in computational creativity. PhD thesis, University of Sydney Department of Architectural and Design Science, Australia (1998)
Sims, K.: Evolving 3D morphology and behavior by competition. In: Brooks, R.A., Maes, P. (eds.) Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems (Artificial Life IV), pp. 28–39. MIT Press, Cambridge, MA (1994)
Turing, A.: The chemical basis of morphogenesis. Phil. T. Roy. Soc. B 237, 37–72 (1952)
Gilbert, C.D., Wiesel, T.N.: Receptive field dynamics in adult primary visual cortex. Nature 356, 150–152 (1992) http://dx.doi.org/10.1038/356150a0
Hubel, D.H., Wiesel, T.N.: Receptive fields and functional architecture in two nonstriate visual areas (18 and 19) of the cat. J. Neurophysiol. 28, 229–289 (1965)
Behravan, R., Bentley, P.J.: Exploring reaction-diffusion and pattern formation. In: Proceedings of the First Australian Conference on Artificial Life (ACAL 2003) (2003)
Cangelosi, A., Parisi, D., Nolfi, S.: Cell division and migration in a genotype for neural networks. Technical Report PCIA-93, Institute of Psychology, C.N.R. Rome (1993)
Belew, R.K., Kammeyer, T.E.: In: Forrest, S. (ed.) Proceedings of the Fifth International Conference on Genetic Algorithms. Kaufmann, San Francisco (1993)
Stanley, K.O., Reisinger, J., Miikkulainen, R.: Exploiting morphological conventions for genetic reuse. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004) Workshop Program. Springer Verlag, Berlin (2004)
Raff, R.A.: The Shape of Life: Genes, Development, and the Evolution of Animal Form. Chicago, The University of Chicago Press (1996)
Amores, A., Force, A., Yan, Y.-L., Joly, L., Amemiya, C., Fritz, A., Ho, R.K., Langeland, J., Prince, V., Wang, Y.-L., Westerfield, M., Ekker, M., Postlethwait, J.H.: Zebrafish HOX clusters and vertebrate genome evolution. Science 282, 1711–1784 (1998) http://dx.doi.org/10.1126/science.282.5394.1711
Darnell, J.E., Doolittle, W.F.: Speculations on the early course of evolution. Proc. Natl. Acad. Sci. USA 83, 1271–1275 (1986) http://dx.doi.org/10.1073/pnas.83.5.1271
Force, A., Lynch, M., Pickett, F.B., Amores, A., Lin Yan, Y., Postlethwait, J.: Preservation of duplicate genes by complementary, degenerative mutations. Genetics 151, 1531–1545 (1999)
Martin, A.P.: Increasing genomic complexity by gene duplication and the origin of vertebrates. Am. Nat. 154, 111–128 (1999) http://dx.doi.org/10.1086/303231
Watson, J.D., Hopkins, N.H., Roberts, J.W., Steitz, J.A., Weiner, A.M.: Molecular Biology of the Gene, 4th edn. The Benjamin Cummings Publishing Company, Inc, Menlo Park, CA (1987)
Altenberg, L.: Evolving better representations through selective genome growth. In: Proceedings of the IEEE World Congress on Computational Intelligence, pp. 182–187. IEEE Press, Piscataway, NJ (1994)
Carroll, S.B.: Homeotic genes and the evolution of arthropods and chordates. Nature 376, 479–485 (1995) http://dx.doi.org/10.1038/376479a0
Cybenko, G.: Approximation by superpositions of a sigmoidal function. Math. Control Signals Syst. 2, 303–314 (1989) http://dx.doi.org/10.1007/BF02551274
Meinhardt, H.: Models of Biological Pattern Formation. Academic Press, London (1982)
Curtis, D., Apfeld, J., Lehmann, R.: Nanos is an evolutionarily conserved organizer of anterior-posterior polarity. Development 121, 1899–1910 (1995)
Lall, S., Patel, N.: Conservation and divergence in molecular mechanisms of axis formation. Annu. Rev. Genet. 35, 407–447 (2001) http://dx.doi.org/10.1146/annurev.genet.35.102401.090832
Angeline, P.J., Saunders, G.M., Pollack, J.B.: An evolutionary algorithm that constructs recurrent neural networks. IEEE Trans. Neural Networks 5, 54–65 (1993) http://dx.doi.org/10.1109/72.265960
Opitz, D.W., Shavlik, J.W.: Connectionist theory refinement: Genetically searching the space of network topologies. J. Artif. Intell. Res. 6, 177–209 (1997)
Pujol, J.C.F., Poli, R.: Evolution of the topology and the weights of neural networks using genetic programming with a dual representation. Technical Report CSRP-97-7, School of Computer Science, The University of Birmingham, Birmingham B15 2TT, UK (1997)
Yao, X., Liu, Y.: Towards designing artificial neural networks by evolution. Appl. Math. Comput. 91, 83–90 (1996) http://dx.doi.org/10.1016/S0096-3003(97)10005-4
Zhang, B.-T., Muhlenbein, H.: Evolving optimal neural networks using genetic algorithms with Occam’s razor. Complex Syst. 7, 199–220 (1993)
Miller, J.F.P.T.: Cartesian genetic programming. In: Proceedings of the Third European Conference on Genetic Programming Published as Lecture Notes in Computer Science, vol. 1802, pp. 121–132 (2000)
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Slection. MIT Press, Cambridge, MA (1992)
Gomez, F., Miikkulainen, R.: Solving non-Markovian control tasks with neuroevolution. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence, pp. 1356–1361. Kaufmann, San Francisco (1999)
Saravanan, N., Fogel, D.B.: Evolving neural control systems. IEEE Expert 10, 23–27 (1995) http://dx.doi.org/10.1109/64.393139
Yao, X.: Evolving artificial neural networks. Proc. IEEE 87, 1423–1447 (1999) http://dx.doi.org/10.1109/5.784219
Radcliffe, N.J.L: Genetic set recombination and its application to neural network topology optimization. Neural Comput. Appl. 1, 67–90 (1993) http://dx.doi.org/10.1007/BF01411376
Roggen, D., Federici, D.: Multi-cellular development: Is there scalability and robustness to gain. In: Proceedings of the 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII), pp. 391–400 (2004)
Reisinger, J., Stanley, K.O., Miikkulainen, R.: Towards an empirical measure of evolvability. In: Genetic and Evolutionary Computation Conference (GECCO2005) Workshop Program, pp. 257–264. ACM Press, Washington, D.C. (2005)
Parmee, I.C.: Improving problem definition through interactive evolutionary computation. J. Artif. Intell. Eng. Design Analy. Manuf. Special Issue: Human-computer Interact. Eng. 16, 185–202 (2002)
Takagi, H.: Interactive evolutionary computation: Fusion of the capacities of EC optimization and human evaluation. Proc. IEEE 89, 1275–1296 (2001) http://dx.doi.org/10.1109/5.949485
Baluja, S., Pomerleau, D., Jochem, T.: Towards automated artificial evolution for computer-generated images. Connect. Sci. 6, 325–354 (1994)
Dawkins, R.: The evolution of evolvability. In: Langton, C.G. (ed.) Artificial Life, pp. 201–220. Addison-Wesley, Reading, MA (1989)
Greenfield, G.R.: Evolving expressions and art by choice. Leonard 33, 93–99 (2000) http://dx.doi.org/10.1162/0024094000552333
Lund, H.H., Pagliarini, L., Miglino, P.: Artistic design with GA and NN. In: Proceedings of the 1st Nordic Workshop on Genetic Algorithms and Their Applications (1NWGA), pp. 97–105 (1995)
McCormack, J.P.: Interactive evolution of L-system grammars for computer graphics modelling. In: Green, D.G., Bossomaier, T. (eds.) Complex Systems: From Biology to Computation, pp. 118–130. IOS Press, Amsterdam (1993)
Sims, K.: Artificial evolution for computer graphics. In: Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’91), pp. 319–328. ACM Press, New York, NY (1991)
Smith, J.R.: Designing biomorphs with an interactive genetic algorithm. In: Belew, R.K., Booker, L.B. (eds.) Proceedings of the 4th International Conference on Genetic Algorithms (ICGA-91), pp. 535–538. Morgan Kaufmann, San Mateo, CA (1991)
Todd, S., Latham, W.: Evolutionary Art and Computers. Academic Press, London (1992)
Dawkins, R.: The Blind Watchmaker. Longman, Essex, UK (1986)
Nishino, H., Takagi, H., Cho, S.-B., Utsumiya, K.: A 3D modeling system for creative design. In: 15th International Conference on Information Networking, pp. 479–486 (2001)
Todd, S., Latham, W.: The Mutation and Growth of Art by Computers, chapter 9, pp. 221–250. Morgan Kaufmann (1999)
Husbands, P., Germy, G., McIlhagga, M., Ives, R.: Two applications of genetic algorithms to component design. Evolutionary Computing. LNCS 1143, 50–61 (1996)
Andersen, T., Otter, C., Petschulat, C., Eoff, U., Menten, T., Davis, R., Crowley, B.: A biologically-derived approach to tissue modeling. In: Westwood, J. et al., (eds.) Technology and Informatics, pp. 15–21. IOS Press, Amsterdam (2005)
Miller, J.F.: Evolving developmental programs for adaptation, morphogenesis, and self-repair. In: Banzhaf, W., Christaller, T., Dittrich, P., Kim, J.T., Ziegler, J. (eds.) Advances in Artificial Life. 7th European Conference on Artificial Life, vol. 2801 of Lecture Notes in Artificial Intelligence, pp. 256–265. Springer, Dortmund, Germany (2003)
Links
Full Text
http://eplex.cs.ucf.edu/papers/stanley_gpem07.pdf
Sonstige Links
http://eplex.cs.ucf.edu/papers/stanley_aaaifs06.pdf Introduction to the theory behind Compositional Pattern Producing Networks (CPPNs)
