Evolutionary design using grammatical evolution and shape grammars: Designing a shelter

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Michael O’Neill, James McDermott, John Mark Swafford, Jonathan Byrne, Erik Hemberg, Elizabeth Shotton, Ciaran McNally, Anthony Brabazon, and Martin Hemberg: Evolutionary design using grammatical evolution and shape grammars: Designing a shelter. International Journal of Design Engineering, 2011.



A new evolutionary design tool is presented, which uses shape grammars and a grammar-based form of evolutionary computa- tion, grammatical evolution (GE). Shape grammars allow the user to specify possible forms, and GE allows forms to be iteratively selected, recombined and mutated: this is shown to be a powerful combination of techniques. The potential of GE and Shape Grammars for Evolutionary Design is examined by attempting to design a single-person shelter to be evaluated by collaborators from the University College Dublin school of Architecture, Landscape, and Engineering. The team was able to successfully generate conceptual shelter designs based on scrutiny from the collaborators. A number of avenues for future work are highlighted arising from the case study.

Extended Abstract


Used References

Aoki, K. and Takagi, H. (1996). Interactive GA-based design support system for lighting design in 3-D computer graphics. Trans. of IEICE, 81:1601–1608.

Banzhaf, W. (1994). Genotype-phenotype-mapping and neutral variation—a case study in genetic programming. In Proceedings of Parallel Problem Solving from Nature III, volume LNCS 866, pages 322–332. Springer.

Banzhaf, W. (1997). Interactive evolution. In Back, T., Fogel, D. B., and Michalewicz, Z., editors, Handbook of Evolutionary Computation, chapter C2.9, pages 1–6. IOP Publishing Ltd. and Oxford University Press.

Bentley, P. J. (2000). Exploring component-based representations—the secret of creativity by evolution? In Parmee, I. C., editor, Proceedings of the Fourth International Conference on Adaptive Computing in Design and Manufacture (ACDM 2000), pages 161–172, University of Plymouth.

Bentley, P. J. and O’Reilly, U.-M. (2001). Ten steps to make a perfect creative evolutionary design system. In GECCO 2001 Workshop on Non-Routine Design with Evolutionary Systems.

Biles, J. (1994). GenJam: A genetic algorithm for generating jazz solos. In Proceed- ings of the International Computer Music Conference, pages 131–131. INTER- NATIONAL COMPUTER MUSIC ASSOCIATION.

Brabazon, A. and O’Neill, M. (2006). Biologically Inspired Algorithms for Financial Modelling. Springer.

Byrne, J., O’Neill, M., McDermott, J., and Brabazon, A. (2009). Structural and nodal mutation in grammatical evolution. In Proceedings of the GECCO-2009 Workshop on Non-routine Design with Evolutionary Systems.

Cagan, J. and Vogel, C. M. (2001). Creating Breakthrough Products: Innovation from Product Planning to Program Approval. Prentice Hall.

Dahlstedt, P. (2009). On the role of temporary storage in interactive evolution. In Giacobini, M. et al., editors, Applications of Evolutionary Computing: EvoWork- shops 2004, number 5484 in LNCS, pages 478–487. Springer-Verlag.

Dawkins, R. (1986). The Blind Watchmaker. Longman Scientific and Technical, Harlow, England.

Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multi-objective genetic algorithm: Nsga-ii. IEEE Transaction on Evolutionary Computation, 6(2):181–197.

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

Dempsey, I., O’Neill, M., and Brabazon, A. (2009). Foundations in Grammatical Evolution for Dynamic Environments. Springer.

Dorris, N., Carnahan, B., Orsini, L., and Kuntz, L. (2004). Interactive evolution- ary design of anthropomorphic symbols. In CEC2004: Proceedings of the 2004 Congress on Evolutionary Computation, volume 1.

Foreign Office Architects (2009). Foreign Office Architects. URL http://www.f-o-a.net. Accessed 13 May, 2009.

Funes, P. and Pollack, J. (1997). Computer evolution of buildable objects. In Husbands, P. and Inman Harvey, E., editors, Proceedings of the Fourth European Conference on Artificial Life, pages 358–367.

Gero, J. S., Louis, S. J., and Kundu, S. (1994). Evolutionary learning of novel grammars for design improvement. AIEDAM, 8:83–94.

Harper, R. and Blair, A. (2005). A structure preserving crossover in grammatical evolution. In Proceedings of the 2005 IEEE Congress on Evolutionary Computa- tion, volume Volume 3, pages 2537–2544. IEEE Press.

Hemberg, E., Gilligan, C., O’Neill, M., and Brabazon, A. (2007a). A grammatical genetic programming approach to modularity in genetic algorithms. In Ebner, M. et al., editors, EuroGP 2007: Proceedings of the 10th European Conference on Genetic Programming, number 4445 in LNCS, Valencia, Spain. Springer.

Hemberg, E., O’Neill, M., and Brabazon, A. (2008). Grammatical bias and building blocks in meta-grammar grammatical evolution. In In Proceedings of the IEEE World Congress on Computational Intelligence, pages 3775–3782, Hong Kong. IEEE Press.

Hemberg, M. and O’Reilly, U.-M. (2004). Extending grammatical evolution to evolve digital surfaces with Genr8. In Keijzer, M., O’Reilly, U.-M., Lucas, S. M., Costa, E., and Soule, T., editors, Genetic Programming 7th European Conference, EuroGP 2004, Proceedings, volume 3003 of LNCS, pages 299–308, Coimbra, Por- tugal. Springer-Verlag.

Hemberg, M., O’Reilly, U.-M., Menges, A., Jonas, K., da Costa Goncalves, M., and Fuchs, S. (2007b). Genr8: Architect’s experience using an emergent design tool. In Machado, P. and Romero, J., editors, The Art of Artificial Evolution. Springer-Verlag, Berlin.

Hicklin, J. (1986). Application of the genetic algorithm to automatic program generation. Master’s thesis, University of Idaho, Moscow, ID.

Hornby, G. S. (2005). Measuring, enabling and comparing modularity, regularity and hierarchy in evolutionary design. In Proceedings of GECCO ’05.

Keller, R. and Banzhaf, W. (1996). Genetic programming using genotype- phenotype mapping from linear genomes into linear phenotypes. In Genetic Programming 1996: Proceedings of the First Annual Conference, pages 116–122, Stanford University, CA, USA. MIT Press.

Kicinger, R., Arciszewski, T., and Jong, K. D. (2005). Evolutionary computation and structural design: A survey of the state-of-the-art. Computers and Struc- tures, 83(23-24):1943 – 1978.

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

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

Mayall, K. and Hall, G. B. (2005). Landscape grammar 1: spatial grammar theory and landscape planning. Environment and Planning B: Planning and Design, 32:895–920.

Mayall, K. and Hall, G. B. (2007). Landscape grammar 2: implementation. Envi- ronment and Planning B: Planning and Design, 34:28–49.

McDermott, J. (2008). Evolutionary Computation Applied to the Control of Sound Synthesis. PhD thesis, University of Limerick.

McKay, R. I. B., Nguyen, X. H., Whigham, P. A., and Shan, Y. (2005). Grammars in genetic programming: A brief review. In Kang, L., Cai, Z., and Yan, Y., editors, Progress in Intelligence Computation and Intelligence: Proceedings of the International Symposium on Intelligence, Computation and Applications, pages 3–18, Wuhan, PRC. China University of Geosciences Press.

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

O’Neill, M. and Brabazon, A. (2005). mGGA: The meta-grammar genetic algo- rithm. In Proceedings of the European Conference on Genetic Programming Eu- roGP 2005, volume LNCS 3447, pages 311–320, Lausanne, Switzerland. Springer.

O’Neill, M. and Brabazon, A. (2006a). Grammatical differential evolution. In Proceedings of IC-AI, pages 231–236. CSREA Press.

O’Neill, M. and Brabazon, A. (2006b). Grammatical swarm: The generation of programs by social programming. Natural Computing, 5(4):443–462.

O’Neill, M. and Brabazon, A. (2008). Evolving a logo design using Lindenmayer systems, Postscript and grammatical evolution. In IEEE Congress on Evolution- ary Computation 2008, pages 3788–3794, Hong Kong, China. IEEE Press.

O’Neill, M. and Brabazon, A. (2009). Recent patents in genetic programming. Recent Patents on Computer Science, 2(1):43–49.

O’Neill, M., Hemberg, E., Bartley, E., McDermott, J., and Brabazon, A. (2008). GEVA: Grammatical evolution in java. SIGEVOlution, 3(2):17–22. O’Neill, M. and Ryan, C. (2001). Grammatical evolution. IEEE Transactions on Evolutionary Computation, 5(4):349–358.

O’Neill, M. and Ryan, C. (2003). Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Kluwer Academic Publishers.

O’Neill, M. and Ryan, C. (2004). Grammatical evolution by grammatical evolution: The evolution of grammar and genetic code. In Proceedings of the European Conference on Genetic Programming, pages 139–148. Springer.

O’Neill, M., Ryan, C., Keijzer, M., and Cattolico, M. (2003). Crossover in gram- matical evolution. Genetic Programming and Evolvable Machines, 4(1).

O’Reilly, U.-M. and Hemberg, M. (2007). Integrating generative growth and evolu- tionary computation for form exploration. Genetic Programming and Evolvable Machines, 8(2):163–186.

O’Reilly, U.-M. and Ramachandran, G. (1998). A preliminary investigation of evolution as a form design strategy. In Adami, C., Belew, R. K., Kitano, H., and Taylor, C. E., editors, Proceedings of the Sixth International Conference on Artificial Life, pages 443–447, University of California, Los Angeles. MIT Press.

Parmee, I. and Bonham, C. (2000). Towards the support of innovative concep- tual design through interactive designer/evolutionary computing strategies. AI EDAM, 14(01):3–16.

Poli, R., McPhee, N., and Langdon, W. (2008). A Field Guide to Genetic Programming. Published via http://lulu.com and freely available at http: //www.gp-field-guide.org.uk.

Purshouse, R. and Fleming, P. (2007). On the evolutionary optimization of many conflicting objectives. IEEE Trans. Evolutionary Computation, 11(6):770–784.

Ratle, A. and Sebag, M. (2000). Genetic programming and domain knowledge: Beyond the limitations of grammar-guided machine discovery. In Proceedings of Parallel Problem Solving from Nature PPSN VI, volume LNCS 1917, pages 211–220. Springer.

Reddin, J., McDermott, J., and O’Neill, M. (2009). Elevated pitch: Automated grammatical evolution of short compositions. In Giacobini, M. et al., editors, Applications of Evolutionary Computing: EvoWorkshops 2004, number 5484 in LNCS, pages 579–584. Springer-Verlag.

Ryan, C., Collins, J. J., and O’Neill, M. (1998). Grammatical evolution: Evolving programs for an arbitrary language. In Banzhaf, W., Poli, R., Schoenauer, M., and Fogarty, T. C., editors, Proceedings of the First European Workshop on Genetic Programming, volume 1391, pages 83–95, Paris. Springer-Verlag.

Sims, K. (1991). Artificial evolution for computer graphics. In SIGGRAPH ’91: Proceedings of the 18th annual conference on computer graphics and interactive techniques, pages 319–328, New York, NY, USA. ACM.

Stichting Blender Foundation (2009). Blender 3D. http://www.blender.org/. Last viewed 11 May 2009.

Stiny, G. (1980). Introduction to shape and shape grammars. Environment and Planning B, 7:343–351.

Takagi, H. (2001). Interactive evolutionary computation: Fusion of the capabilities of EC optimization and human evaluation. Proc. of the IEEE, 89(9):1275–1296.

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

Whigham, P. (1996). Grammatical Bias for Evolutionary Learning. PhD thesis, University of New South Wales, Australian Defence Force Academy, Canberra, Australia.

Wong, M. and Leung, K. (2000). Data Mining Using Grammar Based Genetic Programming and Applications. Kluwer Academic Publishers.

Wonka, P., Wimmer, M., Sillion, F., and Ribarsky, W. (2003). Instant architecture. ACM Trans. Graph., 22(3):669–677.


Full Text


intern file

Sonstige Links