Shape grammars and grammatical evolution for evolutionary design

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Michael O'Neill, Swafford, J.M., James McDermott, Jonathan Byrne, Anthony Brabazon, Shotton, E., McNally, C. & Hemberg, M.; (2009) Shape grammars and grammatical evolution for evolutionary design. Genetic and Evolutionary Computation Conference (GECCO) Montreal, Canada, , 10-JUL-09 - 12-JUL-09



We describe the first steps in the adoption of Shape Grammars with Grammatical Evolution for application in Evolutionary Design. Combining the concepts of Shape Grammars and Genetic Programming opens up the exciting possibility of truly generative design assist tools. In this initial study we provide some background on the adoption of grammar-based Genetic Programming for Evolutionary Design, describe Shape Grammars, and give a brief overview of Grammatical Evolution before detailing how Grammatical Evolution used Shape Grammars to successfully rediscover some benchmark target structures.

Extended Abstract


Used References

Lee Altenberg, The evolution of evolvability in genetic programming, Advances in genetic programming, MIT Press, Cambridge, MA, 1994

Ang, M.C., Chau, H.H., McKay, A., De Pennington, A. (2007). Combining Evolutionary Algorithms and Shape Grammars to Generate Branded Product Design. In Design Computing and Cognition '06 Part 7, pp.521--539. Springer.

Abimbola O. Asojo. (2001). Exploring algorithms as form determinants in design. In Proceedings international space syntax symposium, volume 3, Atlanta, USA.

Wolfgang Banzhaf, Genotype-Phenotype-Mapping and Neutral Variation - A Case Study in Genetic Programming, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.322-332, October 09-14, 1994

Peter J. Bentley, Evolutionary Design by Computers with CDrom, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999

Anthony Brabazon , Michael O'Neill, Biologically Inspired Algorithms for Financial Modelling (Natural Computing Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006

Ken Brown, Grammatical Design, IEEE Expert: Intelligent Systems and Their Applications, v.12 n.2, p.27-33, March 1997

Jonathan Cagan , Craig M. Vogel, Creating Breakthrough Products: Innovation from Product Planning to Program Approval, FT Press, 2002

Dempsey, I. (2007). Grammatical Evolution in Dynamic Environments. PhD Thesis. University College Dublin.

Ian Dempsey , Michael O'Neill , Anthony Brabazon, Foundations in Grammatical Evolution for Dynamic Environments, Springer Publishing Company, Incorporated, 2009

Frazer, J. (1995). An Evolutionary Architecture. Architectural Association, London.

Gero, J. S. (1994). Evolutionary Learning of Novel Grammars for Design Improvement. AIEDAM, 8(2):83-94.

Harper, R. and Blair, A. (2005). A structure preserving crossover in grammatical evolution, in Proceedings of the 2005 IEEE Congress on Evolutionary Computation, D. Corne, Z. Michalewicz, M. Dorigo, G. Eiben, D. Fogel, C. Fonseca, G. Greenwood, T. K. Chen, G. Raidl, A. Zalzala, S. Lucas, B. Paechter, J. Willies, J. J. M. Guervos, E. Eberbach, B. McKay, A. Channon, A. Tiwari, L. G. Volkert, D. Ashlock, and M. Schoenauer, Eds., vol. 3 Edinburgh, UK: IEEE Press, 2-5 Sep., pp. 2537--2544.

Erik Hemberg , Conor Gilligan , Michael O'Neill , Anthony Brabazon, A grammatical genetic programming approach to modularity in genetic algorithms, Proceedings of the 10th European conference on Genetic programming, April 11-13, 2007, Valencia, Spain

Hemberg, E., O'Neill, M., Brabazon, A. (2008). Grammatical Bias and Building Blocks in Meta-Grammar Grammatical Evolution. In Proceedings of the IEEE World Congress on Computational Intelligence, Hong Kong. IEEE Press.

Erik Hemberg , Michael O'Neill , Anthony Brabazon, Altering search rates of the meta and solution grammars in the mGGA, Proceedings of the 11th European conference on Genetic programming, March 26-28, 2008, Naples, Italy

Hemberg M., O'Reilly U-M. (2004) Extending Grammatical Evolution to Evolve Digital Surfaces with Genr8. In LNCS 3003 Proc. of the European Conference on Genetic Programming, pp. 299--308, Springer.

Hicklin, J. (1986). Application of the genetic algorithm to automatic program generation. MSc Thesis, University of Idaho, Moscow, ID.

Hornby G. S., Pollack J. B. (2001) The advantages of generative grammatical encodings for physical design. In Proc. of Congress on Evolutionary Computation, pp. 600--607, IEEE Press.

Robert E. Keller , Wolfgang Banzhaf, Genetic programming using genotype-phenotype mapping from linear genomes into linear phenotypes, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California

Knight, T. W. (1980). The generation of Hepplewhite-style chair back designs. Environment and Planning B, Vol.7, pp. 227--238.

Knight, T. W. (1993). Color Grammars: the Representation of Form and Color in Design Leonardo, Vol. 26, pp. 117--124.

Koning, H., Eizenberg, J. (1981). The language of the prairie: Frank Lloyd Wright's prairie houses, Environment and Planning B Vol. 8, pp. 295--323.

John R. Koza, Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers, Norwell, MA, 2003

Li, Andrew I-kang. (2002). Algorithmic Architecture in Twelfth-Century China: The Yingzao Fashi, pp. 141--150 in Nexus IV: Architecture and Mathematics, eds. Kim Williams and Jose Francisco Rodrigues, Fucecchio (Florence): Kim Williams Books.

Lindenmayer, A. (1968). Mathematical models for cellular interactions in development. Parts I and II. Journal of Theoretical Biology, Vol. 18, pp. 280--315.

Jon McCormack, Open Problems in Evolutionary Music and Art, Proceedings of the 3rd European conference on Applications of Evolutionary Computing, March 30-April 01, 2005, Lausanne, Switzerland

McDermott J., Griffith N., O'Neill M. (2007) Evolutionary GUIs for Sound Synthesis. In LNCS4448 Proc. EvoMUSART2007 The Fifth European Workshop on Evolutionary Music and Art Springer Giacobini et al. (Ed.'s), pp. 547--556, Valencia, Spain. Springer.

O'Neill, M. (2001). Automatic Programming in an Arbitrary Language: Evolving Programs in Grammatical Evolution. PhD thesis, University of Limerick, 2001.

O'Neill, M., Brabazon, A., (2008) Evolving a Logo Design using Lindenmayer Systems, Postscript and Grammatical Evolution, IEEE Congress on Evolutionary Computation 2008, Hong Kong, China.

Michael O'Neill , Anthony Brabazon, Grammatical Swarm: The generation of programs by social programming, Natural Computing: an international journal, v.5 n.4, p.443-462, November 2006

O'Neill, M., Brabazon, A. (2006). Grammatical Differential Evolution. In Proceedings of IC-AI, pp. 231--236. CSREA Press.

Michael O'Neill , Anthony Brabazon, mGGA: the meta-grammar genetic algorithm, Proceedings of the 8th European conference on Genetic Programming, March 30-April 01, 2005, Lausanne, Switzerland

O'Neill, M., Ryan, C. (2004). Grammatical Evolution by Grammatical Evolution: The Evolution of Grammar and Genetic Code. In LNCS 3003 Proceedings of the European Conference on Genetic Programming EuroGP 2004, pp. 138--149, Coimbra, Portugal. Springer.

Michael O'Neill , Conor Ryan, Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language, Kluwer Academic Publishers, Norwell, MA, 2003

M. O'Neill , C. Ryan, Grammatical evolution, IEEE Transactions on Evolutionary Computation, v.5 n.4, p.349-358, August 2001 [doi>10.1109/4235.942529]

Michael O'neill , Conor Ryan , Maarten Keijzer , Mike Cattolico, Crossover in Grammatical Evolution, Genetic Programming and Evolvable Machines, v.4 n.1, p.67-93, March 2003

O'Neill M., Hemberg E., Gilligan C., Bartley E., McDermott J., Brabazon A. (2008). GEVA - Grammatical Evolution in Java (v1.0). UCD School of Computer Science Technical Report UCD-CSI-2008-09. Available from

Michael O'Neill , Erik Hemberg , Conor Gilligan , Eliott Bartley , James McDermott , Anthony Brabazon, GEVA: grammatical evolution in Java, ACM SIGEVOlution, v.3 n.2, p.17-22, Summer 2008

Una-May O'Reilly , Martin Hemberg, Integrating generative growth and evolutionary computation for form exploration, Genetic Programming and Evolvable Machines, v.8 n.2, p.163-186, June 2007

Riccardo Poli , William B. Langdon , Nicholas Freitag McPhee, A Field Guide to Genetic Programming, Lulu Enterprises, UK Ltd, 2008

Conor Ryan , J. J. Collins , Michael O'Neill, Grammatical Evolution: Evolving Programs for an Arbitrary Language, Proceedings of the First European Workshop on Genetic Programming, p.83-96, April 14-15, 1998

Sass, L. (2006). Wood Frame Grammar: A generative system for digital fabrication. International Journal of Architectural Computing. 4(1):51--67.

Ratle, A., Sebag, M. (2000). Genetic Programming and Domain Knowledge: Beyond the Limitations of Grammar-Guided Machine Discovery. In LNCS 1917 Proceedings of Parallel Problem Solving from Nature PPSN VI, pp. 211--220. Springer.

Stiny, G. (1980). Introduction to shape and shape grammars. Environment and Planning B Vol.7, pp. 349--351.

Stiny, G. (1991) The Algebras of Design. Research in Engineering Design 2(3):171--181.

Stiny, G., Gips, J. (1972). Shape Grammars and the Generative Specification of Painting and Sculpture. In Proceedings of IFIP Congress71, pp. 1460--1465. North-Holland.

Stiny, G., Mitchell, W. J. (1978). The Palladian grammar, Environment and Planning B, Vol.5, pp. 5--18.

Takagi, Hideyuki. (2001). Interactive Evolutionary Computation: Fusion of the Capabilities of EC Optimization and Human Evaluation. Proceedings of the IEEE, Vol. 89, No,9, pp. 1275--1296.

Vogel, C. M., Cagan, J. and Boatwright, P. B. H. (2005). The Design of Things To Come. Prentice Hall.

Peter Alexander Whigham, Grammatical bias for evolutionary learning, University of New South Wales, New South Wales, Australia, 1996

Man Leung Wong , Kwong Sak Leung, Data Mining Using Grammar-Based Genetic Programming and Applications, Kluwer Academic Publishers, Norwell, MA, 2000


Full Text

intern file

Sonstige Links