Automatic Structure Generation using Genetic Programming and Fractal Geometry
Inhaltsverzeichnis
Reference
Steven Bergen: Automatic Structure Generation using Genetic Programming and Fractal Geometry. Master Thesis Brock University, Ontario (2011)
DOI
Abstract
Three dimensional model design is a well-known and studied field, with numerous real-world applications. However, the manual construction of these models can often be time-consuming to the average user, despite the advantages offered through computational advances. This thesis presents an approach to the design of 3D structures using evolutionary computation and L-systems, which involves the automated production of such designs using a strict set of fitness functions. These functions focus on the geometric properties of the models produced, as well as their quantifiable aesthetic value - a topic which has not been widely investigated with respect to 3D models. New extensions to existing aesthetic measures are discussed and implemented in the presented system in order to produce designs which are visually pleasing. The system itself facilitates the construction of models requiring minimal user initialization and no user-based feedback throughout the evolutionary cycle. The genetic programming evolved models are shown to satisfy multiple criteria, conveying a relationship between their assigned aesthetic value and their perceived aesthetic value. Exploration into the applicability and effectiveness of a multi-objective approach to the problem is also presented, with a focus on both performance and visual results. Although subjective, these results offer insight into future applications and study in the field of computational aesthetics and automated structure design.
Extended Abstract
Bibtex
Used References
[1] A3D. Archive 3d. In http://archive3d.net/.
[2] Christian Beck. Generalized information and entropy measures in physics, 2009.
[3] P. Bentley and D. Corne. Creative evolutionary systems. Evolutionary Computation Series. Morgan Kaufmann, 2002.
[4] Peter J. Bentley and Jonathan P. Wakefield. Finding acceptable solutions in the pareto-optimal range using multiobjective genetic algorithms. In P. K. Chawdhry, R. Roy, and R. K. Pant, editors, Soft Computing in Engineering Design and Manufacturing, pages 231–240. Springer- Verlag, January 1998.
[5] S. R. Bergen. Evolving stylized images using a user-interactive genetic algorithm. In Rothlauf [50], pages 2745–2752.
[6] S. R. Bergen and B.J. Ross. Evolutionary art using summed multi-objective ranks. In O’Reilly U.-M. Riolo R. and McConaghy T., editors, Genetic Programming Theory and Practice VIII, pages 227–244. Springer, 2010.
[7] G. D. Birkhoff. Aesthetic Measure. Harvard University Press, 1933.
[8] C. Coia. A Genetic Approach to the Grammatical Creation of External Building Architecture. MSc Thesis, Department of Computer Science, Brock University, 2011.
[9] Helen Couclelis. Cities and complexity: Understanding cities with cellular automata, agent- based models, and fractals - michael batty. Papers in Regional Science, 85(3):471–473, 2006.
[10] R. Flack. Evolution of Architectural Floor Plans. MSc Thesis, Department of Computer Science, Brock University, 2011.
[11] Jaime Garces-perez, Dale A. Schoenefeld, and Roger L. Wainwright. Solving facility layout problems using genetic programming. In Stanford University, pages 28–31. MIT Press, 1996.
[12] D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison- Wesley Professional, 1 edition, January 1989.
[13] G. Gunlu and H.S. Bilge. Symmetry analysis for 2d images by using dct coefficients. ICSCCW, pages 1–4, 2009.
[14] H. Jurgens H. Peitgen and D. Saupe. Chaos and fractals, new frontiers of science. 1993.
[15] E. Den Heijer and A. E. Eiben. Comparing aesthetic measures for evolutionary art, 2010.
[16] Martin Hemberg and Una-May O’Reilly. GENR8 - using grammatical evolution in A surface design tool. In Alwyn M. Barry, editor, GECCO 2002: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference, pages 120–123, New York, 8 July 2002. AAAI.
[17] Brian Henderson-Sellers and David Cooper. Has classical music a fractal nature? - a reanalysis. Computers and the Humanities, 27(4):277–284, 1993.
[18] G. Hornby. Evolving L-systems to generate virtual creatures. Computers & Graphics, 25(6):1041–1048, December 2001.
[19] Gregory S. Hornby. Measuring complexity by measuring structure and organization. In 2007 IEEE Congress on Evolutionary Computation, pages 2017–2024. IEEE Press, 2007.
[20] K. J. Hsu and A. J. Hsu. Fractal Geometry of Music. Proceedings of the National Academy of Science, 87:938–941, February 1990.
[21] Christian Jacob. Illustrating evolutionary computation with Mathematica. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001.
[22] Christian Jacob, Aristid Lindenmayer, and Grzegorz Rozenberg. Genetic l-system program- ming. In Parallel Problem Solving from Nature III, Lecture Notes in Computer Science, pages 334–343. Springer-Verlag, 1994.
[23] Yannick Joye. Fractal architecture could be good for you. Nexus Network Journal, 9:311–320, 2007.
[24] Michael Kazhdan, Bernard Chazelle, David Dobkin, Thomas Funkhouser, and Szymon Rusinkiewicz. A reflective symmetry descriptor for 3d models, 2004.
[25] Rafal Kicinger, Tomasz Arciszewski, and Kenneth De Jong. Evolutionary computation and structural design: A survey of the state-of-the-art. Comput. Struct., 83:1943–1978, September 2005.
[26] John R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.
[27] Matthew Lewis. Evolutionary visual art and design. In Juan Romero and Penousal Machado, editors, The Art of Artificial Evolution, Natural Computing Series, pages 3–37. Springer Berlin Heidelberg, 2008.
[28] Ming Li and Paul Vitanyi. An introduction to kolmogorov complexity and its applications: Preface to the first edition, 1997.
[29] Markus Lipp, Peter Wonka, and Michael Wimmer. Interactive visual editing of grammars for procedural architecture. In ACM SIGGRAPH 2008 papers, SIGGRAPH ’08, pages 102:1– 102:10, New York, NY, USA, 2008. ACM.
[30] H. Lipson and W. Cochran. The determination of crystal structures - 3rd revised and enlarged ed. Cornell University Press, 1966.
[31] William E. Lorensen and Harvey E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. SIGGRAPH Comput. Graph., 21:163–169, August 1987.
[32] S. Luke. ECJ - a java-based evolutionary computation research system. In http://cs.gmu.edu/ eclab/projects/ecj/.
[33] Penousal Machado and Amlcar Cardoso. Computing aesthetics. In Proceedings of the Brazilian Symposium on Artificial Intelligence, SBIA98, pages 219–229. Springer-Verlag, 1998.
[34] Edoardo Milotti. 1/f noise: a pedagogical review. arxiv preprint, physics/0204033, April 2002.
[35] C. Neufeld, B. J. Ross, and W. Ralph. The evolution of artistic filters. In Juan Romero and Penousal Machado, editors, The Art of Artificial Evolution, Natural Computing Series, pages 335–356. Springer Berlin Heidelberg, 2008.
[36] R.A. Novelline and L.F. Squire. Squire’s fundamentals of radiology. Squire’s Fundamentals of Radiology. Harvard University Press, 2004.
[37] Michael O’Neill, John Mark Swafford, James McDermott, Jonathan Byrne, Anthony Brabazon, Elizabeth Shotton, Ciaran McNally, and Martin Hemberg. Shape grammars and grammatical evolution for evolutionary design. In GECCO, pages 1035–1042, 2009.
[38] M. Ostwald. Fractal architecture: Late twentieth-century connections between architecture and fractal geometry. Nexus Network Journal, 3(1):73–83, 2001.
[39] Mine Ozkar and George Stiny. Shape grammars. In ACM SIGGRAPH 2009 Courses, SIG- GRAPH ’09, pages 22:1–22:176, New York, NY, USA, 2009. ACM.
[40] Wenjun Pang and K. Hui. Interactive evolutionary 3d fractal modeling. The Visual Computer, 26:1467–1483, 2010. 10.1007/s00371-010-0500-8.
[41] Yoav I. H. Parish and Pascal M ̈ uller. Procedural modeling of cities. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, SIGGRAPH ’01, pages 301–308, New York, NY, USA, 2001. ACM.
[42] Riccardo Poli and William B. Langdon. Genetic programming theory I & II. In Genetic and Evolutionary Computation Conference, pages 3015–3056, 2009.
[43] Riccardo Poli, William B. Langdon, and Nicholas Freitag McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).
[44] P. Prusinkiewicz and J. Hanan. Lindenmayer Systems, Fractals, and Plants. Lecture Notes in Biomathematics, 75, 1989.
[45] Przemyslaw Prusinkiewicz and Aristid Lindenmayer. The algorithmic beauty of plants. Springer- Verlag New York, Inc., New York, NY, USA, 1996.
[46] W. Ralph. Painting the Bell Curve: The Occurrence of the Normal Distribution in Fine Art. In preparation, 2006.
[47] Jaume Rigau, Miquel Feixas, and Mateu Sbert. Conceptualizing birkhoff’s aesthetic measure using shannon entropy and kolmogorov complexity. pages 105–112, 2007.
[48] M. A. Rosenman. The generation of form using an evolutionary approach. Artificial, pages 643–662, 1996.
[49] Brian J. Ross, William Ralph, and Hai Zong. Evolutionary image synthesis using a model of aesthetics. In Gary G. Yen, Lipo Wang, Piero Bonissone, and Simon M. Lucas, editors, Proceed- ings of the 2006 IEEE Congress on Evolutionary Computation, pages 3832–3839, Vancouver, 6-21 July 2006. IEEE Press.
[50] Franz Rothlauf, editor. Genetic and Evolutionary Computation Conference, GECCO 2009, Proceedings, Montreal, Qu ́ebec, Canada, July 8-12, 2009, Companion Material. ACM, 2009.
[51] N. Sala. Fractal models in architecture: A case of study. In Proceedings International Conference on Mathematics for Living, pages 266–272, 2000.
[52] R. Scruton. The aesthetics of architecture. University paperbacks. Methuen, 1979.
[53] K. Sims. Artificial evolution for computer graphics. Computer Graphics, pages 319–328, 1991.BIBLIOGRAPHY 110
[54] Karl Sims. Evolving virtual creatures. In Proceedings of the 21st annual conference on Computer graphics and interactive techniques, SIGGRAPH ’94, pages 15–22, New York, NY, USA, 1994. ACM.
[55] B. Spehar, C. W. G. Clifford, B. R. Newell, and R. P. Taylor. Universal aesthetic of fractals. Computers and Graphics, 27:813–820, 2003.
[56] P. Steadman. The Evolution of Designs: Biological Analogy in Architecture and the Applied Arts - revised edition. Routledge, London and New York, 2008.
[57] Kostas Terzidis. Algorithmic Architecture, volume 1. Architectural Press, 2006.
[58] S. Todd and W. Latham. Evolutionary art and computers. Academic Press, 1992.
[59] M.F. Triola. Essentials of Statistics: International Edition. Pearson Education, Limited, 2010.
[60] Peter von Buelow. Genetically Engineered Architecture - Design Exploration with Evolutionary Computation. VDM Verlag, Saarbrucken, Germany, 2007.
[61] Richard F. Voss and John Clarke. 1/f noise from systems in thermal equilibrium. Phys. Rev. Lett., 36:42–45, Jan 1976.
[62] Dennis D. Wackerly, William Mendenhall III, and Richard L. Scheaffer. Mathematical Statistics with Applications. Duxbury Advanced Series, sixth edition edition, 2002.
[63] Paul Walsh and Prasad Gade. The use of an aesthetic measure for the evolution of fractal landscapes. In IEEE Congress on Evolutionary Computation, pages 1613–1619. IEEE, 2011.
[64] M. Sei Watanabe. Induction Design: A Method for Evolutionary Design. Birkhauser, Basel, Switzerland, 2002.
Links
Full Text
https://dr.library.brocku.ca/bitstream/handle/10464/3916/Brock_Bergen_Raphael_2011.pdf?sequence=2 https://dr.library.brocku.ca/handle/10464/3916
Sonstige Links
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.228.7562
