On hopeful monsters, neutral networks and junk code in evolving L-systems

ABSTRACT

This paper investigates L-system evolution through experiments with a simulation platform of virtual plants. The conducted simulations vary the occurrence probability of terminal versus non-terminal symbols and study its impact on the evolutionary performance of the system. The results reveal a variant of the exploration-exploitation dilemma. A closer look at individual runs allows to discover a range of emergent evolutionary dynamics. In particular, the activation and improvement of previously dormant production rules leads to variation in the fixation rate of mutations. The corresponding fitness leaps suggest that L-system evolution derives much of its creative power from the mobilization of randomly drifting non-addressed rules. The observed patterns are related to the phenomena of positive and negative selection, neutral mutations and junk DNA in the natural genome.

REFERENCES

• 1: R Bian and J Hanan and N Chiba, Statistical data directed evolution of L-system models for botanical trees, Proceedings of FSPM04, Montpellier, France, 253--256, 2004.
• 2: S Bornhofen and C Lattaud, Evolutionary Design of Virtual Plants, Proceedings of CGVR, Las Vegas, USA, 28--34, 2006.
• 3: S Bornhofen and C Lattaud, Life History Evolution of Virtual Plants: Trading off between Growth and Reproduction, Proceedings of PPSN IX, Reykjavik, Iceland, 808--817, 2006.
• 4: S Bornhofen and C Lattaud, Evolution of Virtual Plants Interacting with their Environment, Proceedings of VRIC, Laval, France, 172--176, 2007.
• 5: L E. DaCosta and J A. Landry, Generating grammatical plant models with genetic algorithms, Proceedings of the Int. Conf. on Adaptive and Natural Computing Algorithms. Coimbra, Portugal, 230--234, 2005.
• 6: Bruce Damer , Karen Marcelo , Frank Revi, Nerve Garden: A Public Terrarium in Cyberspace, Proceedings of the First International Conference on Virtual Worlds, p.177-185, July 01-03, 1998
• 7: R Dawkins, The Selfish Gene, Oxford University Press, Oxford, 1976.
• 8: R Dawkins, The Blind Watchmaker, WW Norton, New York, 1986.
• 9: J Doebley and A Stec and C Gustus, Teosinte branched1 and the origin of maize: evidence for epistasis and the evolution of dominance, Genetics, 141, 333--346, 1995.
• 10: Marc Ebner , Adrian Grigore , Alexander Heffner , Jürgen Albert, Coevolution Produces an Arms Race among Virtual Plants, Proceedings of the 5th European Conference on Genetic Programming, p.316-325, April 03-05, 2002
• 11: G Escuela and G Ochoa and N Krasnogor, Evolving L-Systems to Capture Protein Structure Native Conformations, LNCS, 3447, 73--83, 2005.
• 12: A Fick, Über Diffusion, Ann. Phys. (Leipzig), 170, 59--86, 1855.
• 13: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 14: R Goldschmidt, The Material Basis of Evolution, Yale University Press, 1940.
• 15: S J. Gould, The Return of Hopeful Monsters, Natural History, 86, 6, 23--30, 1977.
• 16: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 17: G S. Hornby and J B. Pollack, Body-brain co-evolution using L-systems as a generative encoding, Proceedings of GECCO, San Francisco, USA, 868--875, 2001.
• 18: G S. Hornby and J B. Pollack, The Advantages of Generative Grammatical Encodings for Physical Design, Proceedings of CEC, Seoul, Korea, 600--607, 2001.
• 19: S G. Inge-Vechtomov, A possible role of translation ambiguity in gene evolution, Molecular Biology, 36, 2, 202--208, 2002.
• 20: Christian Jacob, Genetic L-System Programming, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.334-343, October 09-14, 1994
• 21: Christian Jacob, Evolution Programs Evolved, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.42-51, September 22-26, 1996
• 22: C Jacob, Evolving evolution programs: Genetic programming and L-systems, Proceedings of the 1st Annual Conference on Genetic Programming, Cambridge, MA, 107--115, 1996.
• 23: M Kimura, The Neutral Theory of Molecular Evolution, Cambridge Univ. Press, Cambridge, 1983.
• 24: Gabriella Kókai , Zoltán Tóth , Róbert Ványi, Modelling Blood Vessels of the Eye with Parametric L-Systems Using Evolutionary Algorithms, Proceedings of the Joint European Conference on Artificial Intelligence in Medicine and Medical Decision Making, p.433-442, June 01, 1999
• 25: A Lindenmayer, Mathematical models for cellular interaction in development, I and II. Journal of Theoretical Biology, 18, 280--315, 1968.
• 26: K J. Mock, Wildwood: The evolution of L--system plants for virtual environments, Proceedings of ICEC, Anchorage, Alaska, 476--480, 1998.
• 27: ODE website: http://www.ode.org (April, 2008)
• 28: Gabriela Ochoa, On Genetic Algorithms and Lindenmayer Systems, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.335-344, September 27-30, 1998
• 29: OGRE website: http://www.ogre3d.org (April, 2008)
• 30: S Ohno, Evolution by Gene Duplication, Springer-Verlag, Berlin-Heidelberg-New-York, 1970.
• 31: S Ohno, So much "junk" DNA in our genome, Brookhaven Symposia in Biology, 23, 366--370, 1972.
• 32: P. Prusinkiewicz , Aristid Lindenmayer, The algorithmic beauty of plants, Springer-Verlag New York, Inc., New York, NY, 1990
• 33: K Shinozaki and K Yoda and K Hozumi and T Kiro, A quantitative analysis of plant form -- the pipe model theory, I. basic analysis., Jpn. J. Ecol., 14, 97--105, 1964.
• 34: R Sievanen and E Nikinmaa and P Nygren and H Ozier-Lafontaine and J Perttunen and H Hakula, Components of functional-structural tree models, Annals of Forest Sciences, 57, 399--412, 2000.
• 35: Alvy Ray Smith, Plants, fractals, and formal languages, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.1-10, July 1984
• 36: 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]
• 37: D Steinberg and S Sikora and C Lattaud and C Fournier and B Andrieu, Plant growth simulation in virtual worlds: towards online artificial ecosystems, Proceedings of the First Workshop on Artificial Life Integration in Virtual Environment, Lausanne, Switzerland, 84--89, 1999.
• 38: J H. M. Thornley, A balanced quantitative model for root:shoot ratios in vegetative plants, Annals of Botany, 36, 431--441, 1972.
• 39: J Zhang, Evolution by gene duplication: an update, Trends in Ecology and Evolution, 18, 6, 292--298, 2003.
• 40: Tina Yu , Julian F. Miller, Neutrality and the Evolvability of Boolean Function Landscape, Proceedings of the 4th European Conference on Genetic Programming, p.204-217, April 18-20, 2001
• 41: Franz Rothlauf , David E. Goldberg, Redundant representations in evolutionary computation, Evolutionary Computation, v.11 n.4, p.381-415, Winter 2003 [doi>10.1162/106365603322519288]
• 42: W Fontana, The Topology of the Possible, Understanding Change: Models, Methodologies and Metaphors, A Wimmer and R Kössler, Palgrave Macmillan, Basingstoke, 2006.
• 43: M Toussaint, Demonstrating the evolution of complex genetic representations: An evolution of artificial plants, Proceedings of GECCO, Chicago, USA, 86--97, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
L-systems, artificial evolution, artificial life, neutral networks, virtual plants