Graph grammars for evolutionary 3D design

author = "James McDermott",

title = "Graph grammars for evolutionary {3D} design",

journal = "Genetic Programming and Evolvable Machines",

year = "2013",

volume = "14",

number = "3",

pages = "369--393",

month = sep,

note = "Special issue on biologically inspired music, sound, art and design",

keywords = "genetic algorithms, genetic programming, Grammatical evolution, Graph grammars, 3D design, Indirect representations",

ISSN = "1389-2576",

DOI = "

doi:10.1007/s10710-013-9190-0",

size = "25 pages",

abstract = "A new interactive evolutionary 3D design system is presented. The representation is based on graph grammars, a fascinating and powerful formalism in which nodes and edges are iteratively rewritten by rules analogous to those of context-free grammars and shape grammars. The nodes of the resulting derived graph are labelled with Euclidean coordinates: therefore the graph fully represents a 3D beam design. Results from user-guided runs are presented, demonstrating the flexibility of the representation. Comparison with results using an alternative graph representation demonstrates that the graph grammar search space is more rich in organised designs. A set of numerical features are defined over designs. They are shown to be effective in distinguishing between the designs produced by the two representations, and between designs labelled by users as good or bad. The features allow the definition of a non-interactive fitness function in terms of proximity to target feature vectors. In non-interactive experiments with this fitness function, the graph grammar representation out-performs the alternative graph representation, and evolution out-performs random search.",

notes = "This paper is an expanded and improved version of Graph Grammars as a Representation for Interactive Evolutionary 3D Design, presented at EvoMUSART, Malaga, Spain, 2012, \cite{McDermott:2012:EvoMUSART}",