Interactive Evolutionary Computation by Duplication and Diversification of L-Systems
Inhaltsverzeichnis
Reference
Thomas Burt: Interactive Evolutionary Computation by Duplication and Diversification of L-Systems. PhD Thesis, THE UNIVERSITY OF CALGARY, 2013.
DOI
Abstract
Evolutionary processes are responsible for the wide variety of organic forms seen in the natural world. Digital simulations inspired by these processes can be used to create diverse models for computer imagery purposes. In the case of interactive evolutionary computation (IEC), a modeler affects the resulting forms by guiding evolutionary processes. This guidance can be achieved using very simple interfaces, thus putting IEC in the hands of a broad class of users. In our work we focus on the application of IEC to plant modeling. The individual plants are generated using L-systems. Evolution of L-systems is particularly appealing due to analo- gies that can be drawn between genetic code and L-system productions. Several attempts to evolve L-system-based models have been devised in the past by different authors using the standard operations of genetic algorithms — mutations and crossover — to modify the productions. We have improved on these results by considering a different set of operations — duplication and diversification — as the basis of L-system evolution instead. These oper- ations reflect the widely accepted theory of evolution of genetic material, according to which gene duplication is the first step in smooth transitions from less complex to more complex phenotypes via gradual diversification of redundant genetic material. This thesis investi- ages how this general principle can be adapted to the evolution of L-systems, presents an interactive modeling system based on the resulting theory, and illustrates the results using numerous visual examples.
Extended Abstract
Bibtex
Used References
[1] H. Abelson and A. Disessa. Turtle Geometry: The Computer as a Medium for Exploring Mathematics. The MIT Press, 1980. isbn: 9780262510370.
[2] A. V. Aho and M. J. Corasick. “Efficient string matching: an aid to bibliographic search”. In: Commun. ACM 18.6 (June 1975), pp. 333–340. doi: 10.1145/360825. 360855.
[3] M. Aono and T. Kunii. “Botanical Tree Image Generation”. In: IEEE Comput. Graph. Appl. 4.5 (May 1984), pp. 10–34. doi: 10.1109/MCG.1984.276141.
[4] N. Barricelli. “Numerical testing of evolution theories”. In: Acta Biotheoretica 16 (1 1962), pp. 69–98. doi: 10.1007/BF01556771.
[5] N. Barricelli. “Numerical testing of evolution theories”. In: Acta Biotheoretica 16 (3 1963), pp. 99–126. doi: 10.1007/BF01556602.
[6] K. Blossfeldt, G. Bataille, and G. Mattenklott. Art Forms in Nature: The Complete Edition. Schirmer Art Books, 1999.
[7] S. de Bodt, S. Maere, and Y. Van de Peer. “Genome duplication and the origin of angiosperms”. In: Trends in Ecology & Evolution 20.11 (2005), pp. 591–597.
[8] S. Bornhofen and C. Lattaud. “Evolution of virtual plants interacting with their envi- ronment”. In: Proceedings of VRIC. Laval, France (2007), pp. 172–176.
[9] S. Bornhofen and C. Lattaud. “On hopeful monsters, neutral networks and junk code in evolving L-systems”. In: Proceedings of the 10th annual conference on Genetic and evolutionary computation. ACM. 2008, pp. 193–200.
[10] S. Bornhofen and C. Lattaud. “Competition and evolution in virtual plant communi- ties: a new modeling approach”. In: Natural Computing 8.2 (2009), pp. 349–385.
[11] F. Boudon et al. “L-Py: an L-System simulation framework for modeling plant devel- opment based on a dynamic language”. In: Frontiers in Plant Science 3.76 (2012). doi: 10.3389/fpls.2012.00076.
[12] P. J. Bowler. Evolution: the history of an idea. University of California Press, 1984. isbn: 0-520-04880-6.
[13] C. Bridges. “Salivary chromosome maps”. In: Journal of Heredity 26.2 (1935), pp. 60– 64.
[14] C. Bridges. “The Bar “gene” A duplication”. In: Science 83.2148 (1936), p. 210.
[15] S. Carroll, J. Grenier, and S. Weatherbee. From DNA to diversity: molecular genetics and the evolution of animal design. Wiley-Blackwell, 2005.
[16] S. B. Carroll. “Evolution at Two Levels: On Genes and Form”. In: PLoS Biol 3.7 (July 2005), e245. doi: 10.1371/journal.pbio.0030245.
[17] J. Clune and H. Lipson. “Evolving 3D objects with a generative encoding inspired by developmental biology”. In: SIGEVOlution 5.4 (Nov. 2011), pp. 2–12. doi: 10.1145/ 2078245.2078246.
[18] S. Conway Morris. “The predictability of evolution: glimpses into a post-Darwinian world”. English. In: Naturwissenschaften 96.11 (2009), pp. 1313–1337. doi: 10.1007/ s00114-009-0607-9.
[19] R. Curry. On the Evolution of Parametric L-systems. Tech. rep. University Of Calgary, Jan. 1999. url: http://hdl.handle.net/1880/46565. http://dspace.ucalgary.ca/jspui/bitstream/1880/46565/2/1999-644-07.pdf
[20] C. Darwin. On the Origin of Species by Means of Natural Selection or the Preservation of Favoured Races in the Struggle for Life. 2nd ed. Digital transcription of the edition London 1860. Project Gutenberg, 2007. url: http://www.gutenberg.org/files/22764/22764-h/22764-h.htm.
[21] R. Dawkins. The Selfish Gene. Popular Science. Oxford University Press, 1986.
[22] J. Dawson and R. Lucas. The nature of plants: habitats, challenges, and adaptations. Csiro Publishing, 2005.
[23] K. Druse. Natural Companions: The Garden Lover’s Guide to Plant Combinations. Stewart, Tabori & Chang, 2012.
[24] L. Fogel, A. Owens, and M. Walsh. “Intelligent decision-making through a simulation of evolution”. In: SIMULATION 5.4 (1965), pp. 267–279.
[25] J. Hanan. “Parametric L-systems and Their Application To the Modelling and Visu- alization of Plants”. PhD thesis. University of Calgary, 1992.
[26] J. H. Holland. Adaptation in natural and artificial systems. Ann Arbor, MI, USA: University of Michigan Press, 1975. isbn: 0-472-08460-7.
[27] H. Honda. “Description of the form of trees by the parameters of the tree-like body: Effects of the branching angle and the branch length on the shape of the tree-like body”. In: Journal of theoretical biology 31.2 (1971), pp. 331–338.
[28] H. Innan and F. Kondrashov. “The evolution of gene duplications: classifying and distinguishing between models”. In: Nature Reviews Genetics 11.2 (2010), pp. 97–108.
[29] C. Jacob. “Evolving evolution programs: Genetic programming and L-systems”. In: Proceedings of the first annual conference on genetic programming. MIT Press. 1996, pp. 107–115.
[30] C. Jacob. “Principia Evolvica: simulierte Evolution mit Mathematica”. In: (1997).
[31] C. Jacob. “Evolution of developmental programs”. In: Illustrating evolutionary compu- tation with Mathematica. Morgan Kaufmann, 2001. Chap. 9-11.
[32] R. Karwowski and P. Prusinkiewicz. “The L-system-based plant-modeling environ- ment L-studio 4.0”. In: Proceedings of the 4th International Workshop on Functional– Structural Plant Models. 2004, pp. 403–405.
[33] J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems). 1st ed. A Bradford Book, Dec. 1992. isbn: 0262111705.
[34] J. R. Koza. “Gene duplication to enable genetic programming to concurrently evolve both the architecture and work-performing steps of a computer program”. In: Pro- ceedings of the 14th international joint conference on Artificial intelligence - Volume 1. IJCAI’95. Montreal, Quebec, Canada: Morgan Kaufmann Publishers Inc., 1995, pp. 734–740. isbn: 1-55860-363-8, 978-1-558-60363-9.
[35] Y. Kuwada. “Meiosis in the pollen mother cells of Zea Mays L”. In: Bot. Mag 25 (1911), p. 163.
[36] A. Lindenmayer. “Mathematical models for cellular interactions in development II. Simple and branching filaments with two-sided inputs”. In: Journal of Theoretical Bi- ology 18.3 (1968), pp. 300 –315. doi: 10.1016/0022-5193(68)90080-5.
[37] C. v. Linnaeus. Sytema Naturae or [Three kingdoms of nature systematically proposed by means of classes, orders, genera, and species]. Lugduni Batavorum [Leiden, the Netherlands], 1735, p. 13. doi: 10.5962/bhl.title.877.
[38] J. McCormack. “Interactive evolution of L-system grammars for computer graphics modelling”. In: Complex Systems: from biology to computation (1993), pp. 118–130.
[39] J. McCormack. “Aesthetic evolution of L-systems revisited”. In: Applications of Evo- lutionary Computing (2004), pp. 477–488.
[40] J. McCormack. “Evolutionary L-systems”. In: Design by Evolution (2008), pp. 169–196.
[41] M. Mitchell. An introduction to genetic algorithms. 1999.
[42] T. Morgan et al. The Mechanism of Mendelian Heredity. Holt, 1915. url: http : //archive.org/details/mechanismofmende00morgiala.
[43] G. Nelson. “Sonomorphs: An application of genetic algorithms to the growth and devel- opment of musical organisms”. In: Proceedings of the Fourth Biennial Art & Technology Symposium. Vol. 155. 1993.
[44] K. J. Niklas and V. Kerchner. “Mechanical and Photosynthetic Constraints on the Evolution of Plant Shape”. English. In: Paleobiology 10.1 (1984), pp. 79–101. url: http://www.jstor.org/stable/2400502.
[45] G. Ochoa. “On genetic algorithms and Lindenmayer systems”. In: Parallel Problem Solving from Nature PPSN V (1998), pp. 335–344.
[46] S. Ohno. Evolution by gene duplication. London: George Alien & Unwin Ltd. Berlin, Heidelberg and New York: Springer-Verlag., 1970.
[47] P. Prusinkiewicz. “Graphical applications of l-systems”. In: In Proceedings of Graphics Interface ’86 — Vision Interface ’86. 1986, pp. 247–253.
[48] P. Prusinkiewicz and A. Lindenmayer. The Algorithmic Beauty of Plants. New York, NY, USA: Springer-Verlag New York, Inc., 1990. isbn: 0-387-97297-8.
[49] I. Rechenberg. “Evolutionsstrategie–Optimierung technisher Systeme nach Prinzipien der biologischen Evolution”. In: (1973).
[50] I. Rechenberg. “Case studies in evolutionary experimentation and computation”. In: Computer Methods in Applied Mechanics and Engineering 186.24 (2000), pp. 125 –140. doi: 10.1016/S0045-7825(99)00381-3.
[51] K. Sims. “Artificial evolution for computer graphics”. In: SIGGRAPH Comput. Graph. 25 (4 July 1991), pp. 319–328. doi: 10.1145/127719.122752.
[52] K. Stanley and R. Miikkulainen. “A taxonomy for artificial embryogeny”. In: Artificial Life 9.2 (2003), pp. 93–130.
[53] A. Sturtevant. “The effects of unequal crossing over at the Bar locus in Drosophila”. In: Genetics 10.2 (1925), p. 117.
[54] H. Takagi. “Interactive evolutionary computation: Fusion of the capabilities of EC optimization and human evaluation”. In: Proceedings of the IEEE 89.9 (2001), pp. 1275– 1296.
[55] J. Taylor and J. Raes. “Duplication and divergence: the evolution of new genes and old ideas”. In: Annu. Rev. Genet. 38 (2004), pp. 615–643.
[56] D. Thompson. On growth and form: The complete revised edition. Dover, New York, 1992.
[57] S. Ulam. “On Some Mathermatical Problems Connected with Patterns of Growth of Figures”. In: Mathematical Problems in the Biological Sciences. Ed. by R. E. Bellman. Vol. 14. Proceedings of Symposia in Applied Mathematics, 1962, pp. 215 –224. isbn: 0-8218-1314-5.
[58] J. Yu. “Evolutionary Design of 2d Frcatals and 3D Plant Structures for Computer Graphics”. MA thesis. University of Calgary, 2004.
[59] J. Zhang. “Evolution by gene duplication: an update”. In: Trends in Ecology & Evolu- tion 18.6 (2003), pp. 292–298.
Links
Full Text
http://algorithmicbotany.org/papers/tburt.th2013.pdf
