Morphogenesis of Spatial Configurations

Building upon the work on Evolutionary Computation, this research investigates generative rule systems for the conceptual design of spatial configurations. The aim of this research is the development of a “creative” evolutionary system. Creativity in this context refers to the ability of such an evolutionary system to elaborate solutions that over generations improve performance through evolving the body plan (the structural topology). Another important aspect that enables creativity is the interaction with the user (the designer) who, together with well-defined design criteria that are evaluated through computation (e.g. structural stability), collaborate with the system to steer the evolution.

The design methodology developed through this research is based on a combination of Genetic Programming (GP) and Lindenmayer Systems (L-Systems). GP can be considered as a generalization of Genetic Algorithms (GA). The main difference is that in GP the genotype has a component-based structure in the form of a data tree replacing the sequential string of binary numbers used in GA. The data tree contains the rules that define the developmental process. This means that the body plan is not predetermined; the definition of the body plan is a result of evolution. A data tree can be visualized as comprising root, branches and leaves. A joint between two branches can be thought of as a node that contains information. A node can be either an “operand” or an “operator”. An operand is an argument for the function performed by the operator. At the very end of the tree, there can be only operands (also called terminals). The nodes that lie on lower level branches, can be both operands and operators. Following the tree hierarchy, one can unfold from the tree leaves to its root expressing the phenotype that is encoded in it. Each node can contain different data types, a recursive procedure, a subroutine process, etc.

L-Systems are employed to simulate a morphogenesis process. L-Systems are based on rewriting rules whereby characters in a string are replaced by other symbols. The string that initiates the rewriting procedure is called axiom, while the rules that specify which character of the axiom should be replaced with other symbols are called production rules. The symbols are interpreted graphically in a 3D environment. For example, in this work the character “F” is “move forward” and place a building block (a cube); “+” and “-“ are yaw left and right, respectively, by 45° around the Z-axis; “£” and “$” are roll left and right, respectively, by 45° around the X-axis, etc. A new block can be generated only from existing blocks (except for the very first seed block). Following the biological analogy, a building block can be thought of as a cell in an organism, the process by which all the blocks are put together is the growth of the individual. To form the genotype of a candidate solution, axiom and production rules are first randomly generated and a string of symbols is created using rewriting. Bracketed expressions are employed for parsing the string into a data tree. When an open branch character “[” is encountered a new branch is created. When a close branch character “]” is met, the header goes back to the node position that contains the corresponding open branch character.

Candidate solutions are evaluated through different design criteria. A simplified structural analysis has been implemented to evaluate the stability of each configuration as it grows. The building blocks are connected through joints located along the edges and at the vertices. Blocks and joints are assigned predefined mechanical properties including tensile, shear and flexural strength. Gravity load is applied as a vector field that acts on each block. Since new blocks can be generated only from existing blocks, it is possible to simulate a development process similar to the growth of trees and bones. When a new layer of building blocks is formed, the temporary substructure is analyzed. If a failure occurs at any stage of the development process, the genotype of the configuration under development will not be passed on to subsequent generations. A multi-objective fitness function is implemented to couple structural stability with other objectives depending on the type of configuration to be evolved. For example, bridge-like configurations emerge when the objective function rewards solutions that develop a long span lying orthogonally to the Z-axis. Likewise, tall configurations emerge when the fitness score is proportionate to the height of the candidate solution. Another important criterion is a measure of “accessibility” that is computed by evaluating the topology of the neighborhood of each building block. Face-to-face connections are assigned the highest score followed by edge-to-edge and vertex-to-vertex connections. A block that shares a face with one of its neighbors, is assigned a higher score because it is more accessible from it than it would be from another neighbor sharing an edge of a vertex with it. The fitness score determined through this analysis is a measure of the connectedness of the spatial configuration as a whole. Co-evolution has been investigated by letting two initially separate individuals interact. The interaction involves cooperation to improve performance under the defined design criteria. If during development the co-evolved solutions happen to share commons spaces, their genotypes are merged to create a unique individual. In some cases, it has been observed that two non-stable separate structures have merged to support each other to achieve structural stability.

Starting from the initial generation, which is randomly generated, new individuals are created through cross-over and mutation. When cross-over is performed, a data tree node of one solution is swapped with another node from another solution, hence, replacing an entire branch. Mutation is implemented by deleting or adding new branches as well as by changing the operand or operator of a single node. When using Genetic Programming, solutions between successive generations can be significantly different due to the effect of genetic operators (crossover and mutation). This can lead to the loss of good solutions. For this reason, a selection operator based on elitism has been adopted. In contrast to selection proportionate to fitness, elitism works by passing a certain number of best-performing solutions to subsequent generations. These solutions remain unaltered until better performing individuals will be obtained. Selection is also operated through human interaction. The user periodically evaluates a set of best-performing solutions and selects a subset to be passed to subsequent generations.

The combination of L-systems with Genetic Programming as well as the implementation of user interaction has led to the emergence of a system that generates solutions of increasing complexity over generations. In contrast to previous work on Evolutionary Computation, the solution domain comprises not only variables (operand) but also a set of functions (operator) that operate on the variables. The outcome of this research has met the intended aim of developing a creative evolutionary system. Although the search space is inherently discontinuous, because the solution body plan is evolved, there is positive feedback between solutions produced by the evolutionary system and selection through evaluation of the design criteria and user interaction. Working with the evolutionary system has been occasionally surprising as non-intuitive yet high-performance solutions have been produced.