Shape Grammars and Grammatical Evolution for Evolutionary Design
Inhaltsverzeichnis
Reference
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
DOI
Abstract
We describe the first steps in the adoption of Shape Gram- mars with Grammatical Evolution for application in Evo- lutionary Design. Combining the concepts of Shape Gram- mars and Genetic Programming opens up the exciting pos- sibility of truly generative design assist tools. In this ini- tial study we provide some background on the adoption of grammar-based Genetic Programming for Evolutionary De- sign, 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
Bibtex
Used References
[1] Altenberg, L. (1994). Evolution of Evolvability in Genetic Programming. In Advances in Genetic Programming, Chapter 3, pp.47-74. MIT Press.
[2] 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.
[3] Abimbola O. Asojo. (2001). Exploring algorithms as form determinants in design. In Proceedings international space syntax symposium, volume 3, Atlanta, USA.
[4] Banzhaf, W. (1994). Genotype-phenotype-mapping and neutral variation- A case study in genetic programming, in Lecture Notes in Computer Science 866, Parallel Problem Solving from Nature III, pp. 322-332. Springer.
[5] Bentley, P. (Ed). (1999). Evolutionary Design by Computers. Morgan Kaufmann.
[6] Brabazon, Anthony and O’Neill, Michael (2006), Biologically Inspired Algorithms for financial Modelling, Springer.
[7] Brown, K. (1997) Grammatical Design. IEEE Expert, March-April, pp. 27-33.
[8] Cagan, J., Vogel, C.M. (2001). Creating Breakthrough Products: Innovation from Product Planning to Program Approval. Prentice Hall.
[9] Dempsey, I. (2007). Grammatical Evolution in Dynamic Environments. PhD Thesis. University College Dublin.
[10] Dempsey, I., O’Neill, M., Brabazon, A. (2009). Foundations in Grammatical Evolution for Dynamic Environments. Springer. 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.
Hemberg, E., Gilligan, C., O’Neill, M., Brabazon, A. (2007). A Grammatical Genetic Programming Approach to Modularity in Genetic Algorithms. In LNCS 4445 Proceedings of EuroGP Tenth European Conference on Genetic Programming. Valencia, Spain, pp.1-11. Springer.
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.
Hemberg, E., O’Neill, M., Brabazon, A. (2008). Altering Search Rates of the Meta and Solution Grammars in the mGGA. In LNCS 4971 Proceedings of EuroGP 2008, Naples, Italy, pp.362-373. Springer.
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.
Keller, R.E. 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, J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, Eds. Stanford University, CA, USA: MIT Press, 28–31 Jul., pp. 116–122.
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 WrightOs Environment and Planning B Vol. 8, pp.295-323.
Koza, John R., Keane, Martin A., Streeter, Matthew J., Mydlowec, William, Yu, Jessen, and Lanza, Guido. (2003). Genetic Programming IV. Routine Human-Competitive Machine Intelligence. Boston, MA: Kluwer Academic Publishers.
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.
McCormack, J., (2005) Open Problems in Evolutionary Music and Art, LNCS 3449 Applications of Evolutionary Computation, Proc. Of EvoMUSART 2005, pp.428-436. Lausanne, Switzerland. Springer.
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.
O’Neill, M., Brabazon, A. (2006). Grammatical Swarm: The generation of programs by social programming. Natural Computing, Vol.5, No.4, pp.443-462.
O’Neill, M., Brabazon, A. (2006). Grammatical Differential Evolution. In Proceedings of IC-AI, pp.231-236. CSREA Press.
O’Neill, M., Brabazon, A. (2005). mGGA: The meta-Grammar Genetic Algorithm. In LNCS 3447, Proceedings of the European Conference on Genetic Programming EuroGP 2005, pp.311-320, Lausanne, Switzerland. Springer.
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.
O’Neill, M., Ryan, C. (2003). Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Kluwer Academic Publishers.
O’Neill, M., Ryan, C. (2001). Grammatical Evolution, IEEE Trans. Evolutionary Computation. 2001.
[37] O’Neill, M., Ryan, C., Keijzer M., Cattolico M. (2003). Crossover in Grammatical Evolution. Genetic Programming and Evolvable Machines, Vol. 4 No. 1. Kluwer Academic Publishers, 2003.
[38] 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 http://ncra.ucd.ie/geva/.
[39] O’Neill M., Hemberg E., Gilligan C., Bartley E., McDermott J., Brabazon A. (2009). GEVA: Grammatical Evolution in Java. SIGEVOlution, 3(2):17-22.
[40] O’Reilly, U-M., Hemberg M. (2007). Integrating generative growth and evolutionary computation for form exploration. Genetic Programming and Evolvable Machines, Vol. 8, No. 2, pp.163-186. Springer.
[41] Poli R., McPhee N.F., Langdon W.B. (2008). A Field Guide to Genetic Programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk.
[42] Ryan, C., Collins, J.J., O’Neill, M. (1998). Grammatical Evolution: Evolving Programs for an Arbitrary Language. Proc. of the First European Workshop on GP, 83-95, Springer-Verlag.
[43] Sass, L. (2006). Wood Frame Grammar: A generative system for digital fabrication. International Journal of Architectural Computing. 4(1):51-67.
[44] 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.
[45] Stiny, G. (1980). Introduction to shape and shape grammars. Environment and Planning B Vol.7, pp. 349-351.
[46] Stiny, G. (1991) The Algebras of Design. Research in Engineering Design 2(3):171-181.
[47] 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.
[48] Stiny, G., Mitchell, W.J. (1978). The Palladian grammar, Environment and Planning B, Vol.5, pp. 5-18.
[49] 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.
[50] Vogel, C. M., Cagan, J. and Boatwright, P.B.H. (2005). The Design of Things To Come. Prentice Hall.
[51] Whigham, P.A. (1996). Grammatical Bias for Evolutionary Learning. PhD Thesis, University of New South Wales, Australian Defence Force Academy, Canberra, Australia.
[52] Wong, M.L., Leung, K.S. (2000). Data Mining Using Grammar Based Genetic Programming and Applications. Kluwer Academic Publishers.
Links
Full Text
http://ncra.ucd.ie/papers/GECCO2009Shapes.pdf
