Design Tooling - Evolutionary Design

Design Tooling - Evolutionary Computation

	Return to front page


Information	Evolution and Biology Evolution drives the development of species in nature and is part of a very complex system of interaction between the elements the compounds that form out of the elements and the complex interactions on a chemical level that lead to the formation of the first living beings. A large part of evolution is the competition among entities in a more or less bounded environment. Competition creates selection and selection influences the proliferation of individuals who get to reproduce. Another core innovation that developed with evolution is the notion of phenotype and genotype which essentially means that the individual and its development is somewhat separated from the the plan that is followed in the growth of the individual. This refinement makes it possible to carry over very complex traits from generation to generation and allows evolutionary principles to affect whole populations rather then just individuals.


- Evolution!	- Homology		- DNA structure	- Chromosome

	Evolution and Computation Computational models have been developed inspired by and out of fascination for evolutionary principles. By no means though are the computational model representative of evolution in nature but serve as metaphors for developing models of computation to deal with the search of large solution spaces. Evolutionary algorithms are essentially guided search mechanisms that use sophisticated model to inform the direction and area of search within the design space. The design space or solution space is the result of all possible combinations of the design parameters of the problem at hand and usually is far too large to be searched exhaustively.


			- Genetic Algorithms	- Genetic Programming

	Evolution and Architecture John Frazer refers to evolutionary architecture in 1995 at the AA as follows: " Evolutionary architecture The exhibition charts the exploration of fundamental form-generating processes in architecture. It proposes the evolutionary model of nature as the generating process for architectural form, in an attempt to achieve in the built environment the symbiotic behaviour and metabolic balance that are characteristic of the natural environment. The profligate prototyping and awesome creative power of natural evolution are emulated by creating virtual architectural models which respond to changing environments. Successful developments are encouraged and evolved. Architecture is considered as a form of artificial life, subject, like the natural world, to principles of morphogenesis, genetic coding, replication and selection." link to the full text The use of GA as a form generator is very challenging, as the fitness criteria to test and evolve a form against can easily be too loose producing essentially random forms or to limiting which channels the results into the form that is described in the fitness function. As with any complex system the interactions and cross dependencies are very hard to foresee as the system grows large and requires a very fine balance of control and understanding of the system to be useful.The range of GA's goes from optimization to almost random form generation and is as much a design task as anything else. The use of a GA does not justify any result that comes out of it but should be viewed as a design as anything else produced. The authorship might be several steps removed from the artifact but the link is there.

Interpretation	The following examples demonstrate a range of simple and more complex examples based on GA's and related computational model to demonstrate the principles and challenges of this computational approach. They are by no means exhaustive and any search in the cited literature or additional source will turn up a large number of additional examples in many fields besides architecture, which only relatively recently applied the idea of GA's to design.




Implementation	Most of the examples here are based on an array of 1's and 0's for the representation of the genome. The array is initiated by filling it with random values of one or zero at the beginning of each generation. Each individual is represented by one genome and the number of genomes represent the population. Usually the size of the population stays constant. Each individual in a generation is tested according to the set fitness criteria. Usually it is a weighted score derived from how well the individual performs a certain task or how close it fits a given goal. The genome is also referred to the genotype. The genotype is used as the instruction to produce the phenotype. The phenotype is the entity that is being tested for fitness. After each generation the genomes are ranked based on the performance of their phenotype and a percentage of the most successful is reinserted into the next random generation after being subjected to cross over and point mutation. This cycle continues for usually several thousands if not hundred thousands cycles in order to see if any trend in the successful genotypes emerges.

Examples	Using Genetic Algorithms to Generate Developable Strips From Free formed Surfaces The environment for the GA model is the UV space of a NURBS surface. The UV space is the two dimensional representation of the three dimensional surface on a flat plane with width and length dimensions corresponding to the degrees of the surface. This gives the possibility to operate in a rectangular two dimensional environment which is easier to deal with and still maps perfectly onto the original three dimensional surface. One approach is to analyses the surface regarding curvature. After running the GA for a total of 1000 individuals for 200 generations using 1% probability of point mutation and 3 point crossover. A range of strips could be observed. The lower image shows the below the NURBS surface the environment is constructed from and in the upper part the strips mapped from UV space back onto the NURBS surface.


Axel Kilian 2002	- diagram	- pdf of final paper in 6.837


	Box Search Algorithm A GA is used to generate boxes of a certain volume given a choice of x y z dimensions. The target values are weighted against each other which allows putting different emphasis on the values according to user preference. It is an example to illustrate a very simple case of multiple targets expressed through a weighted fitness function.


Axel Kilian 2004	- The interpreter	- source in processing	- the population	- the top ten


	A Growth example In the growth example the genome contains information that is being interpreted as the branching pattern during the growth of the tree. As an evaluation function the overall volume of the tree is measured against a target value. In addition volume of material


Axel Kilian 2004	- The interpreter	- source in processing	- the population	- the top ten


	Tower Optimization Algorithm In this example a GA is used to generate tower variations based on the 6 control variables. A possible fitness criteria is volume, surface area and height. In the applet the towers are simply sorted by volume for now.


Axel Kilian 2004	- The interpreter	- source in processing	- the population	- the top ten


	Mesh Thickening The mesh-thickening GA was part of an exploration in evolutionary computation for design purposes. Specifically it was developed for Mark Goulthorpe's Banside Towertop project. The algorithm attempted to create thickness / shell a three dimensional mesh object and satisfy the over-constrained condition of not increasing the number of vertices (more than double) and offset in parallel the faces of the original mesh by a constant amount.


Stylianos Dritsas 2004	Instructions


	Minimum Volume Bounding Box The purpose of this genetic algorithm is to calculate the minimum volume bounding box around an arbitrary collection of points in space. It was developed for fabrication purposes and more specifically for preparing parts for CNC-milling. Generating bounding boxes around the three dimensional parts of the design is part of the manufacturing process; minimizing the volume of the blocks is directly related to the waste of material and total cost of production. Using a genetic algorithm in this case was a decision made because of the complexity in implementing an analytic method for calculating the bounding boxes.


Stylianos Dritsas 2004


	Evolution of "ants" using finite state automata Based on the paper "Genesys/Tracker system by David Jefferson et al from UCLA an evolutionary system to evolve ants to search for trails of food in a grid environment was programmed. The ants behavior is specified by a finite state automata of in this case 16 possible states and a lookup table that specifies the next state and next action based on whether food was encountered in the environment or not. Over several generations the successful traits in the FSA should emerge in the ant population. The biggest difference to the examples above is that the evolution is not acting on the geometry of an object but is applied to the FSA of the ant and therefor evolves its actions and interaction with the environment. Every ant is then inserted and tested in the grid environment and receives a score based on how well it did in finding food.
Axel Kilian 2003

- one possible 16 state FSA	- another 16 state FSA	- Part of the ant environment	- the generation statistics


Bibliography	Bentley, P. J. (1999), "Evolutionary Design by Computers", San Francisco, California, Morgan Kaufman Publishers. Darwin, C. (1964), "On the Origin of Species, A Facsimile of the First Edition", with an Introduction by Ernst Mayr, Cambridge, Massachusetts, Harvard University Press. Frazer J. (1995) exhibition catalog for an exhibition titles "evolutionary architecture" at the AA link Goldberg, D. E. (1985), "Genetic algorithms and rules learning in dynamic control systems", Proceedings of the First International Conference on Genetic Algorithms and Their Applications : July 24-26, 1985 at the Carnegie-Mellon University, Pittsburg, PA / Hillsdale, N.J. : Lawrence Erlbaum Associates. 1988 Goldberg, D. E. (1989), "Genetic Algorithms in Search, Optimization, and Machine Learning", Reading, Mass. Addison-Wesley Pub. Co. Holland, J. H. (1975), "Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence", Ann Arbor, University of Michigan Press. Sims, K. (1994) "Evolving Virtual Creatures", Proceedings of SIGGRAPH 94, Computer Graphics Proceedings, Annual Conference Series, Andrew Glassner editor, ACM SIGGRAPH, pp 15-22 Sims, K. (1994) "Evolving 3D morphology and behavior by competition". Artificial Life IV: Proceedings of the Fourth International Workshop on the synthesis and simulation of living systems, Brooks, R and Maes, P (eds.), Cambridge, MA: MIT Press.


	Return to front page