Intelligent Systems Group, Department of Computer Science, University College London, Gower St., London WC1E 6BT, UK. Tel. 44 (0) 171 391 1329 Fax. 44 (0) 171 387 1397
E-mail: p.BENTLEY@cs.ucl.ac.uk www: http://www.cs.ucl.ac.uk/staff/p.bentley/
Abstract
This paper examines the four main types of Evolutionary Design by computers:. Evolutionary Design Optimisation, Evolutionary Art, Evolutionary Artificial Life Forms and Creative Evolutionary Design Definitions for all four areas are provided A review of current work in each of these areas is given,. with examples of the types of applications that have been tackled. The different properties and requirements of each are examined. Descriptions of typical representations and evolutionary algorithms are provided and examples of designs evolved using these techniques are shown. The paper then discusses how the boundaries of these areas are beginning to merge, resulting in four new 'overlapping' types of Evolutionary Design:. Integral Evolutionary Design, Artificial Life Based Evolutionary Design, Aesthetic Evolutionary AL and Aesthetic Evolutionary Design Finally, the last part of the paper discusses some common problems faced By Creators of Evolutionary Design Systems, INCLUDING: InterDepen DENT Elements in Designs, Epistasis, and constraint handling.
Keywords: Evolutionary Design, Creative Design, Optimisation, Computer Art, Artificial Life
INTRODUCTION
The use of Evolutionary Computation to generate designs has taken place in many different guises over the last ten or fifteen years. Designers have optimised selected parts of their designs using evolution, artists have used evolution to generate aesthetically pleasing forms, architects have evolved new building plans from scratch, computer scientists have evolved the morphologies and control systems of artificial life.However, work in these different application areas tends to be performed by researchers isolated within different fields, and whilst there is some cross-disciplinary communication, it seems that many work in ignorance of the highly related research performed by others in order to remedy this situation, this paper attempts to bring together the varied aspects of this type of research under a single heading:. Evolutionary Design.
Figure 1 Evolutionary Computation and Evolutionary Design Have The Their Roots In Computer Science and Evolutionary Biology.
Cross-disciplinary research is hardly new to Evolutionary Computation. Indeed, the entire field only exists because of the efforts of those such as Holland [24], Rechenberg [32] and Fogel [16] to merge the boundaries of Evolutionary Biology and Computer Science See Figure1.
Unfortunately, it does seem that the natural behaviour of many researchers is to entrench themselves within a single area, and then erect barriers around that area by trying to stress wider and wider distinctions -. Almost a form of intellectual territorialism This paper tries to encourage some Of these barriers to be removed, by Identifying The Common Elements of research offen considered as distinct and self.
Consequently, this paper proposes that the branch of research entitled 'Evolutionary Design' should encompass four distinct aspects: Evolutionary Design Optimisation, Creative Evolutionary Design, Evolutionary Art, and Evolutionary Artificial Life Forms.As is usually the case with any kind of classification system, the work of a few researchers does not fall neatly within one category, but may be included in two or more categories This paper also examines such work Particular attention is paid to the four 'overlapping' research areas, which this paper shall name..: Integral Evolutionary Design, Aesthetic Evolutionary Design, Artificial Life-based Evolutionary Design, and Aesthetic Evolutionary AL. Figure 2 shows all of these areas of research and how they relate to each other.
Figure 2 aspects of evolutionary design by computers
The following sections of this paper summarise the scope of research in each area and describe the aims and objectives that researchers in each area typically have, examining some key contributions to each of these fields of research. For each aspect of Evolutionary Design, examples of the representations, evolutionary algorithms and evolved solutions are outlined. Finally, some typical problems encountered by creators of Evolutionary Design systems are discussed, together with ways to overcome them.
2. Four aspects
2.1 Evolutionary Design Optimisation
The use of Evolutionary Computation to optimise existing designs was one of the first types of Evolutionary Design to be tackled. Over the last fifteen years, a huge variety of different engineering designs have been successfully optimised [3,19], from flywheels [15] TO Aircraft Geometries [25].
Although the exact approach used by developers of such systems varies, typically this type of Evolutionary Design can not be classed as generative or creative (see next section). Practitioners of Evolutionary Optimization usually begin the process with an existing design, and parameterise those parts of the design they feel need improvement. These parameters are then encoded as genes, the alleles (values) of which are then evolved by an evolutionary search algorithm. The designs are often judged by interfacing the system to analysis software, which is used to derive a fitness measure for each design. for example, Goodman [15] describes the optimisation of flywheels using genetic algorithms (GAs). Cross-sections of flywheels are parameterised (into a collection of height parameters) and evolved, see fig. 3 (top left) Evaluation of structure is Performed Using Multiple Finite Element Models [15]. AlternativeLely, Keane Has Minimianed The Structural Vibration of Design Such As AxialLi Vibra ting rods and satellite booms, using a GA to minimise fitness values returned by a Statistical Energy Analysis package [26] For more examples of Evolutionary Optimisation of Designs, see Gen and Cheng's recent book:. Genetic Algorithms and Engineering Design [19].
Phenotype representations for these design optimisation problems are application-specific, consisting of existing designs for that application, with the evolved parameter values simply inserted into the corresponding parameterised elements. Artificial embryologies (mapping or 'growth' stages from genotypes to phenotypes [14]) are often rudimentary or non-existent, simply because they are not necessary for such Evolutionary Design. Because of this, genotype representations may match phenotype representations closely, often with a one-to-one mapping between genes and parameters. Consequently, the addition or deletion of genes in genotypes, and parameters in phenotypes, is usually not performed by the evolutionary algorithm for Evolutionary Design Optimisation.When optimising designs, great emphasis is placed upon finding a solution as close to the global optimal as possible - perhaps more so than for Any Other Type of Evolutionary Design. OFTEN Designs That Are AREADY OF Good Quality Ar e to be improved, and it can be a challenge to improve them at all. Because of this motivation towards global optimality, researchers tend to concentrate on evolutionary search methods for reducing any tendencies towards convergence upon local optima. In addition, because the analysis software .
Numerous techniques have been tried to achieve these goals. To improve performance, sometimes multiple genetic representations are used in parallel [15]. Many complex types of genetic algorithm are used [19]. For example, Husbands [25] describes the use of a distributed GA and a distributed GA hybridized with gradient descent techniques to evolve the cross-section of optimal aircraft wingboxes. The research found that hybrid GAs outperformed many other search algorithms for this problem [25] .CLICK HERE fOR AN EXAMPLE oF EVOLUTIONARY OPTIMISATION
2.2 Creative Evolutionary Design
Calling anything generated by computer 'creative' is fraught with ambiguity and controversy, so this section will begin by attempting to define, for the purposes of Evolutionary Design, what 'creative' actually means.
Writing about this very subject in his paper 'Computers and Creative Design' [20], Gero makes the distinction between cognitive and social views, ie an individual can display creativity when designing, and a design can have characteristics which may be regarded as being creative . Gero concentrates on the former definition, and concludes that a computer is designing creatively when it explores the set of possible design state spaces in addition to exploring individual design spaces. in other words, Gero indicates that by evolving the number of decision variables in addition to evolving the values of those variables, a computer is being creative [20]. in a similar vein, Boden suggests in her book The Creative Mind [9], that creativity is only possible by going beyond the bounds of a representation, and by Finding a novel solimention which simply could NOTHAVE BEEN Defined by That Reresentation. Boden, HoWever, Does Not Feel That Computers Are Capable of Such Creativity [9]. Porther Definit ions for creative design include: having ability to generate 'surprising and innovative solutions', or' novel solutions that are qualitatively better than previous solutions' [21] However, for the purposes of this paper, Rosenman's description seems most apt:. 'the Lesser The Knowledge About EXISTING RELATIONSHIPS BETWEEN THE Requirements and The Form To Satisfy Those Requirements, The More A Design '[33].
Consequently, the main feature that all Creative Evolutionary Design systems have in common, is the ability to generate new forms starting from little or nothing (ie random initial populations), and be guided purely by functional performance criteria. In achieving this, such systems often do vary the number of decision variables during evolution [4,21,33]. They can often generate surprising and innovative solutions, or novel solutions qualitatively better than others [6,23]. Whether this means that these systems are really 'designing creatively ', or whether they simply generate' creative designs', will be left for the reader to decide.Research in the field of Creative Evolutionary Design is concerned with the preliminary stages of the design process. There are two main approaches. Both involve the use Of Evolutionary Computation To Generate Entirely New Designs from Scratch, However The Level At Which There Designs Are Reperesented is Different:
CONCEPTUAL EVOLUTIONARY Design - The Production of High-Level Conceptual Frameworks for Designs.
In this type of Evolutionary Design, the relationships and arrangements of high-level design concepts are evolved in an attempt to generate novel preliminary designs. A good example of this is the work of Pham, who describes his preliminary design system known as TRADES (TRAnsmission DESigner) [31]. TRADES uses a genetic algorithm to evolve the organisation of a set of conceptual building blocks (such as rack and pinion, worm gear, belt drive). When given the type of input (eg rotary motion) and the desired Output (EG Perpendicular Linear Motion), The System Generates A Suitable Concertual Transmission System To Convert The Input Into The Output.
In these systems, evolution is used to search through the possible networks of interconnected conceptual building blocks. The genotype and phenotype representations of these systems are often simple, with rudimentary embryologies, if any. Basic evolutionary algorithms are usually sufficient for this type of problem. there are always exceptions to every rule, however, and the work of Parmee provides such an exception. Parmee [29] describes the use of structured GA to evolve a large-scale hydropower system (this is intended to take place at the feasibility / bid stages of the design process, after the conceptual design stage). His advanced GA manipulates a design hierarchy of 'sites', 'dam types', 'tunnel lengths', 'modes of operation', etc., and allows appropriate elements to be Switch On or Off by Control Genes During Evolution [29] .Click Here for An Example of Conceptual Evolutionary Design
GENERATIVE EVOLUTIONARY DESIGN (Or Genetic Design) - The Generation of The Form of Designs Directly.
Using computers to generate the form of designs rather than a collection of pre-defined high-level concepts has the advantage of giving greater freedom to the computer. Typically such systems are free to evolve any form capable of being represented, and the evolution of such forms may well result in the emergence of implicit design concepts [6,23]. However, the difficulty of this type of Creative Evolutionary Design is severe, since it often involves the creation of dynamically specified representations and complex evaluation routines (see below).
Often involving just the preliminary stages of design, the emphasis for this type of Evolutionary Design is on the generation of novelty and originality, and not the production of globally optimal solutions. Representations of form vary tremendously, but they do all share certain features. For example, because the emphasis is on the generation of new forms, phenotype representations are typically quite general, capable of representing vast numbers of alternative morphologies (this is in contrast to representations for optimisation, which can only define variations of a single form). Representations range from direct spatial partitioning (eg voxels), which have one-to-one mappings between genes in genotypes and elements of phenotypes [2], to highly indirect representations which use shape grammars or cellular automata (CA) with some advanced embryologies to map Genotypes to Phenotypes [11,33]. for Example, Rosenman Describes the Use of a Ga To Evolve House Plans, Using A Design Gramma r of rules to define how polygons should be constructed out of edge vectors [33]. Coates uses genetic programming (GP) to evolve abstract architectural forms, with L-Systems forming the basis of the representation [11]. Schnier and Gero even attempt To Evolve New Higher-Level Representations Of Form, Suitable for Subsequent Evolution of House Plans in a specific architectural style [35].
Simple genetic algorithms are often sufficient for the design systems that employ simpler representations [2]. However, for Creative Evolutionary Design systems with advanced representations and corresponding embryologies (eg to 'grow' phenotypes from a set of shape-grammar rules defined in the genotypes ), more advanced GAs are essential. Typically, these GAs are used to evolve the larger structure of the representation (eg number and organisation of shape-rules) in addition to the detail (eg type and content of the individual rules). in other words, these GAs are capable of evolving designs which have representations of variable length - they explore new and different search spaces in addition to the parameter values within each space [7] GAs and GP are used to evolve these highly variable forms [4,. 11,33] Usually Beginning from Random, Simple Forms, And Gradually Improving The Structure and Detail of these Designs Until Some Functional criteria is met. The Objective of this Ty pe of research is not normally to use computers to generate a single global optimal solution, but rather to generate a number of 'creative' alternatives. The evaluation of designs can be more difficult, since most off-the-shelf analysis packages are limited to judging specific types of designs - when presented with some of the initially random forms generated by these systems, they simply generate errors Consequently, many of these systems rely on simplified custom-written evaluation routines, which can analyse everything presented to them, but perhaps. NOT Always with the desired account [4].
However, this is one of the most recent and exciting types of Evolutionary Design, and is already showing great potential in a number of application areas. Bentley [4,6,8] describes the evolution, from scratch, of a number of unusual and inventive designs for numerous applications, such as tables, heatsinks, optical prisms, aerodynamic and hydrodynamic forms, etc., see fig. 3 (top right). Pollack [17] demonstrates the use of a GA to evolve novel bridge and crane structures, which are subsequently built as LEGOTM models [17]. An application area currently receiving much media attention is 'Evolveable Hardware', where new logic circuits are evolved and evaluated in real silicon using FPGAs [23]. Already some surprising and novel electronic solutions have Been Found Using these Techniques [23]. Click Here for An Example of Generative Evolutionary DESIGN
2.3 Evolutionary ART
Evolutionary Art is perhaps the most commercially successful type of Evolutionary Design. Although academic research in this area is less common than in the other fields, there are perhaps more Evolutionary Art products available today than any other type of Evolutionary Design system.
All Evolutionary Art systems tend to resemble each other closely They all generate new forms or images from scratch (random initial populations) They all rely completely upon a human evaluator to set fitnesses for each member of the population -.. Normally based on aesthetic appeal. Population sizes are usually very small (often less than ten individuals), to allow them all to be quickly judged every generation. User-interfaces are often similar, with members of the current population shown on the screen in the form of a grid, allowing the user to rank them, or assign fitness scores by clicking on them with a mouse, see fig. 3, bottom left.The main differences between these systems lie in their phenotype representations. A large variety of alternative representations have been employed, from fractal equations (such as John Mount's 'Interactive Genetic Art', which was shown on-line at http: //robocop.modmath.cs.cmu.edu.8001/), to recursive grammar-rules using constructive solid geometry [40]. These representations are created with different intentions. For example, Dawkins' recursive tree-like structures were intended to resemble the recursive embryologies found in nature, in the hope that natural looking forms would emerge [13,14]. Todd and Latham's representation was based upon repeated elements such as spheres and tori, used to form 'horns' and 'ribs' out of which images are constructed [40]. Colour and texture can also be incorporated into these representations [14,40].
Perhaps surprisingly, many of the representations are evolved with fixed structures (eg Todd and Latham hand-designed the structures of forms, then evolved the detail within these structures [40]). Allowing evolution to vary structures (eg change the number of rules or primitive shapes), as is done in Creative Evolutionary Design, could possibly increase the creativity of such systems.One undesired side effect of many of these representations is that they generate pieces of art which have very distinct styles. Often the style of form generated using a particular representation is more identifiable than the style of the artist used to guide the evolution. This can cause problems if the artist wishes to take the credit for the piece. The cause of this 'style problem' is perhaps due to the initial preconceptions and Assumptions of the designer of the representation. by limiting the computer to a specific Type of Structure, OR A Specific Set of Primitive Shapes and constructure rules, IT WILL INEVITABLY Always Generate Forms With Many Common and Identifiable Elements.
Because evolution is guided by a human selector (ie the 'fitness function' is an artist), the evolutionary algorithm does not have to be complex. Evolution is used more as a continuous novelty generator, not as an optimiser. The artist is likely to score designs highly inconsistently as he / she changes his / her mind about desirable features during evolution, so the continuous generation of new forms based on the fittest from the previous generation is essential. Consequently, an important element of the evolutionary algorithms used is non- convergence. If the populations of forms were ever to lose diversity and converge onto Typically only mutation a single shape, the artist would be unable to explore any further forms. Because of this, most Evolutionary Art systems do not employ crossover within their evolutionary algorithms. IS Used, with all of their parents (and offly one). this mutation-driven evolution is Simil ar to the approach used in evolution strategies, which are known to be excellent for finding solutions to problems with continuously changing fitness functions [1] .Examples of such systems include Dawkins' biomorphs [13,14], Todd & Latham's Evolutionary Art [40 ], And SIMS 'Evolved Computer Graphics [37]. Today, Numerous Evolutionary Art Systems Are Available On-line (see http://www.netlink.co.uk/~snaffle/form/evolutio.html for an up-to -date list).
Click Here for an Example of Evolutionary Art
2.4 EVOLUTIONARY Artificial Life-Forms
Evolutionary Computation plays a significant role in many aspects of the new field of Computer Science known as Artificial Life (AL). Artificial 'brains', behaviour strategies, methods of communication, distributed problem solving and many other topics are commonly explored using genetic algorithms and other evolutionary search techniques [12] .Although all types of evolved AL could be described as aspects of Evolutionary Design, it is clear that certain topics within AL fall into the 'Evolutionary Design' category more comfortably than others. For the purposes of this paper , AL research that can be readily categorised as an aspect of Evolutionary Design will be defined as research which aims to evolve 'Artificial Life-Forms' Examples of Evolutionary AL-Forms include:. Lohn's Cellular Automata (CA) evolved to be capable of self -Replication [27], Harvey's Evolved Layout and Structure of Neurons [22], and The Evolved Plant-Like and Animal-Like Morphologies of Dawkins and SIMS [13, 14, 38, 39 ].
Motivations for the creation of Evolutionary AL-Forms are usually theoretical. The goals of such research are often to discover more about the mechanisms of natural evolution, to find explanations of forms observed in nature, or to exploit the solutions proven in nature by attempting to duplicate them. Often the evolved AL-forms show the enormous potentials of this type of Evolutionary Design, but as yet, practical applications are still scarce. Figure 3 (bottom right) shows some of Sims' evolved 'virtual creatures'.
Representations are typically specific to each system. For example, Lohn and Reggia [27] use CA 'rule tables' within the chromosomes of their GA. Sims [38,39] uses a hierarchical chromosome structure to define both' brain 'and' body '. Ventrella [41] combines ordered morphology and control parameters of his animats in a flat chromosome structure. Many of these representations are inspired by the genotype structure of natural organisms, and some researchers have attempted to evolve AL-forms with complex embryologies. Other ................. ..
Because research in this field is still very much at the 'blue-sky' stage, evolutionary techniques are often used as exploration tools, in a similar way to Evolutionary Art. These algorithms can be used to generate multiple solutions, incorporating niching, speciation, parasitism, competition, co-operation and other advanced methods [12]. Evaluation usually consists of analysing behaviour in simulated virtual worlds (although some researchers do test solutions using real robots [22]), and can be very time-consuming. To try to shorten evolution run-times, advanced methods are commonly used, eg steady-state GAs, parallel GAs, hybrid GAs [12]. Many systems that evolve AL-forms also use changing fitness functions, which necessitate the use of other specialised genetic search techniques (Harvey) [22]. Most systems evolve the forms from scratch (the initial population is random), however some occasionally seed initial populations with the fittest individuals from previous runs [39] .CLICK H ERE for An Example of Evolving Artificial Life Forms
Goodman's Evolutionary Optimisation of Flywheels Bentley's Creative Evolutionary Design Rowbottom's Evolutionary Art SIMS 'Evolved Artificial Life Forms
Figure 3 Examples of the Four Main Types of evolutionary design.
3. Combining Good ideas by Merging the Boundaries
Many researchers confine themselves to one of the four aspects of Evolutionary Design mentioned above, and seem loath to consider alternative approaches. However, more recently, some have begun to combine ideas from one or more of these areas in their work. This is leading to Four more (Still Very New and Relatively Unexplored) 'Overlapping' Areas of Research In evolutionary design .3.1 Integral Evolutionary Design
The evolution of engineering designs is becoming widespread today, with numerous academic engineering design centres exploring these ideas. Although most research seems to fall into either the Evolutionary Optimisation category, or the Creative Evolutionary Design category, some work does attempt to combine the two into unified , or Integrated Evolutionary design systems.
Parmee suggests that computers can be used within the entire design process, both the early conceptual design stages and the later, detailed design stages, by using a number of adaptive techniques. He discusses how the use of several different systems, each dedicated to a specific Stage of Design Could Be Used In Combination, Thus 'Integrating Adaptive Search At Every Stage of The Design Process' [29].
Alternatively, work performed by Bentley has investigated the use of a single Generic Evolutionary Design system, to perform the complete design process without making any distinction between the stages of design. It is 'generic' because it is capable of evolving designs for multiple different design That IT IS POSILELELY NEW DESIGNS from Scratch, And Optimise Them, Such That They Fulfil Specific Functional criteria [4, 6, 8].
With many optimisation systems beginning to be applied to more and more detailed parameterisations of designs, and many creative design systems beginning to be used to optimise the designs they generate, the field of Integral Evolutionary Design looks set to grow rapidly.3.2 Artificial Life Based Evolutionary DESIGN
Work in Artificial Life has generated forms of astonishing diversity and creativity, so some researchers are now using some of the techniques from AL in their Creative Evolutionary Design systems, in an attempt to improve the quality and originality of evolved engineering designs. For example, Parmee borrows distributed agent methods from AL to increase performance of search, in his 'Ant Colony' method, which he combines with evolutionary search [30]. Coates employs L-systems with GP to evolve new architectural forms [11].
Many other unexplored possibilities still exist in this area. For example, Bonabeau [10] describes an AL computer simulation of a swarm of artificial wasps, which build intricate three-dimensional nest architectures. One future avenue of research may be to evolve artificial wasps capable Of building new engineering designs Between.
3.3 AESTHETIC EVOLUTIONARY Artificial Life
The evolution of aesthetically pleasing AL was perhaps first performed by Dawkins, who hand-selected his artificial 'biomorphs' for reproduction in exactly the way artists select their forms using Evolutionary Art systems [13]. Ventrella has taken this one step further, and has evolved aesthetically pleasing animats which resemble animated stick-men. These are evolved for their ability to walk naturally in a virtual world, and also are guided by the aesthetic judgement of the user [41]. Alternatively, Lund [28] describes the use of neural networks which learn how to judge evolved pictures based on their aesthetics.Although to date there have been few applications to benefit from this area of research, the use of computers to evolve amusing or attractive animated characters may well be lucrative in the computer games industry , or for television advertisements.
3.4 AESTHETIC EVOLUTIONARY DESIGN
The evolution of aesthetic designs is an obvious area of research, which should perhaps receive more attention than it does. Few designs are purely functional, most are chosen partly because of their aesthetics, and some functionally outstanding designs are discarded purely because of their ugly appearance . Furuta [18] describes an approach in which bridge designs can be optimised using GAs, based on their appearance, using 'psychovectors' to quantify the aesthetic factors of the structures. Husbands [25] describes the evolution of 3D solid objects resembling propellers, USING a Superquadric Shape-Description Language and Guided by 'The Eye of The Beholder'.
4. Epistasis, Constraints, And Other Problems
There are a number of common problems encountered when attempting to perform Evolutionary Design using computers. As is usual when applying evolutionary computation to anything, there are issues related to the fitness functions, such as noisy functions, discontinuous functions, multimodal functions, and multiobjective functions [3,5,24]. There Are, However, Some More Specific Problems That Typically Arise More often with evolutionary design [34] .4.1 Epistatic representations
Epistasis means the 'degree of dependency' between multiple genes in a chromosome. A genetic representation with high epistasis may have many genes whose phenotypic effect relies to a large degree on the alleles of other genes. For example, a single shape-rule in a rule-based representation may have very different phenotypic effects, depending on which other shape-rules precede and succeed it. Conversely, a representation with low epistasis has few or no genes whose phenotypic effect relies on the alleles of other genes. For example, a SIMPLE VOXEL REPRESENTATION WHERE EVERY Gene Switches on or Off A Single Voxl in A Grid Has Zero Epistasis.
Experiments investigating whether epistasis should be high or low have so far been inconclusive [36]. However, a simple thought experiment may shed light on this dilemma. Consider a (fictional) representation which uses, say, ten genes to represent the entire form of designs, and the phenotypic effect of every gene is completely dependent on all of the other genes through some embryology process. With this (maximum) amount of epistasis, these ten genes effectively become elements of a single overall gene (just as the separate binary digits in an ordinary gene are completely dependent on their neighbours). So our ten-gene representation with complete epistasis could be considered as a single-gene representation. Consider what effect varying any part of that gene would have on the phenotype. with every part of THE Design Epistically Linked to Every Other Part, Any Attempt to Improve Just One Small Area Would Result In Changes To All of the rest of the design - MAKING EVOLUTION TO Accept Table Designs Very Difficult, if Not Impossible.
Alternatively, consider a representation with zero epistasis (eg a voxel representation using a 3D array). This requires no embryology, since every gene maps directly onto a specific area of the phenotype, and only that area of the phenotype. It should be clear that such a representation is well suited for evolution of small-scale detail, but evolution of large-scale characteristics becomes immensely difficult eg, the scaling of the entire form in one dimension, or the duplication or mirroring of an existing feature in the design. ( to duplicate or mirror an existing feature in the way segmentation or symmetry does, each new duplicate part would have to be re-evolved in entirety - highly unlikely to occur [8]) Having examined the two extreme cases, it should be clear that. Both Too Much Epistasis and Too Little Epistasis In a representation is undesirable. Consequently, IT Seem That An Ideal Representation for Evolutionary Design Should Have A 'Middling' Amount of Epistasis - Just A S Nature Seems To Use.
4.2 Constraints
Many design problems are heavily constrained, and dealing with these constraints within an evolutionary algorithm can be difficult. If the creator of the Evolutionary Design system does not take care, constraints can limit the effectiveness of evolutionary search by blocking off useful areas of the search space . Alternatively, if soft constraints are specified, there can be no guarantee that all the constraints will be satisfied there are eleven main ways in which a constraint can be implemented within an evolutionary system [42].:
C1: Legal SearchSpace Design Genotype Reperestation.
During the design of the evolutionary system, create a genotype representation that is only capable of representing legal solutions. Evolutionary search is then forced to consider only the space of legal solutions, where all constraints are satisfied. This method is frequently used, although designers who use it are often unaware that they are performing constraint handling of any kind For example, in GAs, if the range of a problem parameter must be between 0 and 255, most designers would automatically use a binary gene consisting of eight bits -. and this Genotype Reperestation Would The Ensure That The 0-255 Range Constraint Was Always Satisfied.c2: Legal SolutionSpace Design Phenotype Representation.
During the design of the evolutionary system, create a new phenotype representation, so that only legal phenotypes can be defined. All genotypes are then mapped onto these phenotypes, which by definition, must always satisfy the constraints. Often great care can go into the design . of suitable phenotypes for example, practitioners of floor-planning problems have two important constraints: room-spaces should not overlap, and no space should be left unaccounted for To ensure that the computer always evolves solutions that satisfy these constraints, designers of these. Systems Tend To Use Phenotype Reperestations Which Define The location of rooms indirectly, by defining the location and number of dividing walls [21].
C3: Legal Seed SEED with NON-Conflicting Solutions.
The initial population is seeded with solutions that do not conflict with the constraints and the crossover and mutation operators are designed so that they can not generate illegal solutions. This method has been used in GP to ensure that only type-correct programs are considered during evolution [ 42] The method ensures that all constraints are always satisfied, but may limit exploration by evolutionary search because of reduced initial diversity and limited genetic operations (It may also be impractical or impossible to generate the initial population of individuals -.. particularly if the whole Point of using evolutionary search Was to find solutions..
If a new individual conflicts with a constraint, correct the genes that are responsible for the conflict to make it satisfy that constraint. For algorithms such as GP which make no explicit distinction between genotypes and phenotypes, this method modifies the solution, and the modification is Inherited by its offspring.
This 'genetic engineering' approach ensures that all solutions will satisfy all constraints, but may damage epistatic genotypes, discarding the result of careful evolution over many generations. The design of the repair procedure may be a non-trivial task for some problems.
C5: Legal Map Correct ILLEGAL PHENOTYPES.
Map every genotype of an individual to a phenotype that satisfies the constraints using some form of simple embryology. This forces all solutions to satisfy all constraints, and also does not disrupt or constrain the genotypes in any way, allowing evolutionary search to continue unrestricted. For algorithms such as GP which make no distinction between genotypes and phenotypes, this method modifies the solution before fitness evaluation, but the modification is not inherited by its offspring.Using a mapping stage to generate legal phenotypes is a very common approach to perform simple constraint handling . In his book, Goldberg describes perhaps the simplest: mapping the range of a gene to a specified interval This permits constraints on parameter range and precision to be satisfied without the need to redesign the genotype representation and coding More recently mapping stages have become.. More Intricate and DeServing of the Term 'Artificial Embryology'. Research in GP Have Also Rep ORTED THATY USE OF An Explicit Genotype and Mapping Stage for Constraint Handling Can Increase Diversity In Population [42].
C6: Genotype Penalty Penalize Illegal Genotypes.
Identify alleles or gene fragments within genotypes that seem to increase the chances of a solution conflicting the constraints, and reduce the fitness of any individual containing these fragments of genetic code. Although the identification of 'bad genes' may discourage solutions from conflicting constraints, it will not guarantee that all solutions satisfy all constraints. in addition, with epistatic genotypes, this approach may result in the discouragement of other, epistatically linked, useful features within solutions. To date, research has investigated the automatic identification of 'good genes' during evolution to encourage the evolution of solutions with higher fitnesses [21] However, the author of this paper is unaware of any work which identifies 'bad genes' for constraint handling.C7:. PHENOTYPE PENALTY penalize illegal phenotypes.
When a phenotype conflicts a constraint, reduce its fitness (ideally in direct proportion to the number of constraints conflicted, and the degree to which they are conflicted). This 'soft constraint' discourages all phenotypes that conflict the constraints, but does not force evolutionary search to generate legal solutions. In effect, the use of a penalty value becomes an additional criteria to be considered by the evolutionary algorithm, and multiobjective techniques should be used to ensure that all criteria are considered separately (otherwise one or more criteria may dominate the Others [5]. This is one of the most of the maximinly used methodies for constraint handling in evolutionary algorithms.
C8: Legal Selection SELECT LEGAL PARENTS Only for Reproduction.
During reproduction, only select parent solutions which satisfy the constraints. This method should be used with a fitness-based replacement method to ensure that evolution is guided to evolve fit solutions in addition to legal solutions. However, the exclusion of potential parents discards potentially beneficial Getic Material and So May Be Harmful To Evolution. Only Two Recent Investigations Have Been Made On This Method [42] .c9: Legal Fertility Increase The No OFFSPRING for LEGAL PARENTS.
Having selected the parent genotypes (based on their fitnesses) this method allocates a larger fertility to parents which better satisfy the constraints. This method can be thought of as an implicit multiobjective method, allowing independent selection pressure to be exerted for high fitness and legal solutions . Being a 'soft constraint', there are no guarantees that all solutions will always satisfy the constraints. In addition, if legal parents are favoured excessively, it is possible that the diversity of the population could be reduced. To the author's knowledge, this IDEA HAS NOT BEEN Previously Used for constraint handling.
C10: Infanticide Stop Illegal Offspring from Being Born.
If a new solution conflicts a constraint, discard it, and try generating another solution using the same parents. This brute-force method, which is sometimes used in GAs [42], forces all solutions to satisfy the constraints, but may discard useful genetic Material. in Addition, for Heavily Constrained Problems, IT May Get Stuck In an endless, generating and discarding Illegal Solutions Forever, Given Two Parents That Can Only Have Illegal Offspring.
C11: Illegal Replacement Replace Illegal Solutions with legal offspring.
When replacing individuals with new offspring in the population, always replace the solutions that conflict constraints. (If all solutions satisfy the constraints, either replace randomly or replace the least fit.) This method should be used with a fitness-based selection method to ensure that evolution is guided to evolve fit solutions in addition to legal solutions. However, the replacement of potential parents discards potentially beneficial genetic material and so may be harmful to evolution.Work is in progress to investigate and compare these different techniques, both separately and in Combination [42].
4.3 Evolving Designs with Interdependent Elements
Opponents of Darwin's theory of natural section often give the example of the eye as a structure 'impossible to occur by evolution' They state that the eye consists of many interdependent parts:. The iris, the retina, the cornea, the lens, with each element relying on the correct functioning of all the other elements for the eye to work as a whole. Dawkins convincingly argues that there does exist a series of gradual evolutionary steps from no eye to eye, and that not only has the eye evolved, but it has evolved many times independently in different species [13]. However, although it is clear that such intricate designs have been evolved in nature, it is also clear that using evolutionary computation to generate designs with interdependent elements is a very difficult task.
For example, Bentley [6] describes (amongst other things) the evolution of a Penta-Prism. This design must bounce light twice using total internal reflection within its solid glass structure in order to reflect an image through 90 degrees whilst keeping the output image the right way up Although it is a single component, it does have two interdependent elements:.. the two reflective parts If either of these internally reflective sides are imprecisely oriented, or omitted, the design will not function correctly not only that, but. the first reflection must direct the light in a direction almost opposite to the final, desired direction: so a design without the second reflective part is actually worse than a design with no reflective parts at all [6] .Evolution 'prefers' to use as Few Elements As Possible, Slowly Building Up The Complexity of Designs [14]. However, if Care Is Not Taken The Design of The Reperestation and Operators, Evolution May Commit Approx imations of the desired design. In the example of the Penta-Prism, evolution normally began by evolving a simple right-angle prism (using a single reflection), which directed the light in the correct direction, but oriented the wrong way up. Having committed itself to this simple, but unsatisfactory type of solution, evolution was then unable to proceed to the more complex Penta-prism design. Perhaps because of limitations of the representation, the only way that evolution could be forced to abandon this unsatisfactory local optimum was BY PenAlising All Such Designs with a fitness constraint [6].
Such examples of Evolutionary Design [6] illustrate that design problems requiring solutions with many interdependent elements can have large numbers of local optima -. Some of which do not resemble the functionally correct designs at all Penalising all such unsatisfactory designs is not always a practical solution , so for design problems of this type, very careful consideration should be given to the creation of a representation and genetic operators that will always permit evolutionary paths from local optima to global optima.4.4 Evolving Structure and Detail
As described in previous sections, some types of Evolutionary Design allow evolution to explore the structure (eg number of parameters / rules / primitive shapes) of designs in addition to the detail (eg parameter values) of designs. In most representations, varying the structure of designs has considerably more impact on the fitness of these designs, compared to varying the detail. Because of this, evolution typically converges on suitable design structures long before converging on design details. Although this is not always a disadvantage (eg the skeletal structure of all mammals seems to permit sufficient diversity, as does the cell structure of plants), in some instances evolution may prematurely converge onto an inappropriate structure. If this happens, the evolution of detail around this structure may be insufficient to allow the production of an acceptable DESIGN.
There are two potential solutions to this problem. First, an improved representation capable of allowing changes in structure without disastrous fitness changes would allow structure and detail to converge simultaneously. This could be accomplished if the evolution of detail could directly affect the degree to which changes in structure affected fitnesses. For example, in nature, a superfluous bone will be gradually reduced in size by evolution (a change in design detail), whilst at the same time improving other aspects of the organism because of that change. This reduction continues until at some point the bone becomes sufficiently small and redundant that evolution can remove the entire bone (structure mutation), without decreasing the fitness of the organism.The second way to prevent premature convergence of structure is to reduce selection pressure once in a while, and Permit Less-Fit Designs to Propagate. Dawkins [14] Suggests That Certain Landmark Mutations in Structure Such As T he development of segmentation may have initially resulted in solutions with worse fitnesses. It seems likely that some of the more gross mutations are more likely to survive during 'good times' where food is plentiful, predators are scarce, and hence selection pressure low [14 ]. By Reducing Selection Pressure In Our Evolutionary Design Systems in A Similar Way, WE May Well Permit Changes in Structure To Occur At Later Stages of Evolution.
5. Conclusions
This paper has reviewed four highly related fields of research:. Evolutionary Design Optimisation, Evolutionary Art, Evolutionary Artificial Life-Forms and Creative Evolutionary Design In order to promote closer collaboration, it was proposed that the branch of research entitled Evolutionary Design should encompass these four distinct aspects. The different aims and techniques of each type of Evolutionary Design were then explored. For example, practitioners of Evolutionary Design Optimisation typically desire a single, global optimal design, in the minimum of time. in contrast, users of Evolutionary Art systems require . a never-ending, non-converging, supply of novel forms to explore, and judge for themselves Yet despite the differences between the approaches, researchers have now begun to combine these areas, forming four very new 'overlapping' types of Evolutionary Design: Integral Evolutionary Design, Artificial Life Based Evolutionary Design, AESTHETIC Evolutionary Al and AESTHETI c Evolutionary Design.The paper then briefly described some common problems faced by creators of Evolutionary Design Systems:. evolving designs with interdependent elements, evolving structure and detail, epistasis with representations, and constraint handling Some solutions were discussed to these problems, but research is ONGOING to Discover Conclusive Answers.
Interest in Evolutionary Design is expanding from academia into industry, with the media now beginning to report its successes. Although Evolutionary Design is still in its infancy, it shows great promise in becoming an invaluable type of computer software tool for designers, artists and biologists.
Acknowledgements
My thanks to Erik Goodman, Karl Sims, and Andrew Rowbottom for their permission to reproduce images of their evolved designs. Thanks also to Tina Yu and Sanjeev Kumar for providing stimulating discussions and helpful criticism.References
Bäck, T. 1996, Evolutionary Algorithms in Theory and practice. Oxford University Press, New York. Baron, P., Fisher, R. Mill, F. Sherlock, A. And Tuson, A. 1997. a Voxel-based Representation for the Evolutionary Shape Optimisation of a Simplified Beam:.. A Case-Study of a Problem-Centred Approach to Genetic Operator Design 2nd On-line World Conference on Soft Computing in Engineering Design and Manufacturing (WSC2) Bentley, PJ 1997. The Revolution of Evolution for Real-World Applications Emerging Technologies '97:... Theory and Application of Evolutionary Computation, 15th December, University College London Bentley, PJ & Wakefield, JP 1997. Generic Evolutionary Design Chawdhry, PK, Roy, R., & Pant , RK (eds) Soft Computing in Engineering Design and Manufacturing. Springer Verlag, Part 6, 289-298. Bentley, PJ & Wakefield, JP 1997. Finding Acceptable Solutions in the Pareto-Optimal Range using Multiobjective Genetic Algorithms. Chawdhry, PK, ROY, R., & PANT, RK (ED . S) Soft Computing in Engineering Design and Manufacturing Springer Verlag London Limited, Part 5, 231-240 Bentley, PJ & Wakefield, JP 1997. Conceptual Evolutionary Design by Genetic Algorithms Engineering Design and Automation Journal v3:.. 2, John Wiley & Sons, Inc, 119-131 Bentley, PJ & Wakefield, JP 1996. Generic Representation of Solid Geometry for Genetic Search Microcomputers in Civil Engineering 11:... 3, Blackwell Publishers, 153-161 Bentley, PJ & Wakefield, JP 1996. The Evolution of Solid Object Designs Using Genetic Algorithms. In Rayward-Smith, V. (ED) Modern Heuristic Search Methods. CH. 12, John Wiley & Sons Inc., 199-215. Boden, Ma, 1992. The Creative Mind: Myths &
Basic Books Pub. ISBN: 0465014518. Bonabeau, E., Theraulaz, G., ARPIN, E., SARDET, E. 1994. The Building Behaviour of Lattice Swarms. Brooks, R., And MAES, P. (EDS ) Artificial Live IV, Proc. of the 4th Int. Workshop on the Synthesis and Simulation of Living Systems, MIT Press, 307-312. Coates, P., 1997, Using Genetic Programming and L-Systems to explore 3D design worlds. CAADFutures '97, R. Junge (ED), Kluwer Academic Publishers, Munich. Cliff, C .; husbands, p .; meyer, j.; Wilson, SW (EDS) 1994. from animals to animats 3. Proceedings of the third International conference on simulation of adaptive behaviour, MIT Press. Dawkins, R. 1986. The Blind Watchmaker. Longman Scientific & Technical Pub. Dawkins, R. 1989. The Evolution of Evolvability. Artificial Life. The Proceedings of an Interdisciplinary Workshop on the Synthesis and Simulation of Living Systems, Vol. Vi, Langton, CG (Ed.), September, 1987, Los Alamos, New Mexico, Addison-Wesley Pub. Corp, PP.201-220. Eby, D., A verill, R., Gelfand, B., Punch, W., Mathews, O., & Goodman, E. 1997. An Injection Island GA for Flywheel Design Optimization. In 5th European Congress on Intelligent Techniques and Soft Computing EUFIT '97, . vol 1, pp 687-691 Fogel, LJ, 1963. Biotechnology:. Concepts and Applications Englewood Cliffs, NJ:... Prentice Hall Funes, P. & Pollack, J. 1997. Computer Evolution of Buildable Objects Brandeis University Computer Science Technical Report CS-97-191. Furuta, H., Maeda, K. &
Watanabe, W. 1995. Apllication of Genetic Algorithm to Aesthetic Design of Bridge Structures In Microcomputers in Civil Engineering v10:... 6 Blackwell Publishers, MA, USA, 415-421 Gen, M. and Cheng, R. 1997. Genetic Algorithms And Engineering Design, John Wiley & Sons, USA. Gero, JS 1996. Computers and Creative Design, In M.Tan and R.TEH (EDS), The Global Design Studio, National University of Singapore, PP. 11-19. Gero .., JS & Kazakov, V. 1996. An exploration-based evolutionary model of generative design process Microcomputers In Civil Engineering 11, 209-216 Harvey, I. 1997. Cognition is not Computation:. Evolution is not Optimisation In Artificial Neural Networks - ICANN97, PROC. OF 7th International Conference ON Artificial Neural 1997, Lausanne, Switzerland, Gerstner, W., Germond, A., Hasler, M, And Nicoud, JD (EDS). Springer-Verlag LNCS. 1327 PP. 685-690. Harvey, I. And Thompson, A. 1997. THROUGH The Labyrinth Evolution Finds A Way: a Slicon Ridge. Pro Ceedings of the 1st Int. conf. on evolveable systems: from biology to hardware (ICES96), HIGUCHI, T. AND IWATA, M. (EDS), Springer Ver; AG LNCS 1259, PP. 406-422. Holland, JH, 1975, Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor. Husbands, P., Jermy, G., McIlhagga, M., & Ives, R. 1996. Two Applications of Genetic Algorithms to Component Design. in Selected Papers from AISB Workshop on Evolutionary Computing. Fogarty, T. (ed.), Springer-Verlag, Lecture Notes in Computer Science, (pp. 50-61). Keane, A. 1994. Experiences with optimizers in structural design. in Proceedings of the conference on adaptive computing in engineering design and control '
94, ED. IC PARMEE, PLYMOUTH, PP. 14-27. Lohn, J. And Reggia, J. 1995. Discovery of self-replicating structures Using a gene setic algorithm. 1995 IEEE INT. Conf. On evolutionary computation (Icec '95 ), Vol 1, PERTH, WESTERN AUSTRALIA, PP. 678-683. Lund, H., Pagliarini, L., Miglino, O., 1995, Artistic Design With Ga and NN, Proc. of the 1st Nordic Workshop On Genetic Algorithms . and Their Applications (1NWGA), Uni Vaasa, Finland, xiii 417 pp 97-105 Parmee, I. 1996. Towards an optimal Engineering Design Process using Appropriate Adaptive Search Strategies Journal of Engineering Design, Vol 7:... 4, Carfax Pub. Parmee, I. 1996. The Development of a Dual-Agent Strategy For Efficient Search Across Whole System Engineering Design Hierarchies. 4th Int. Conf. on Parallel Problem Solving From Nature, Berlin, Germany, September 22-27. Pham, DT & YANG, Y., 1993. A Genetic Algorithm Based Preliminary Design System. Journal of Automobile Engineers V207: D2, 127-133. Rechenberg, I., 1973. EVOLUTION sstrategie: Optimierung Technisher Systeme nach Prinzipien der Biologischen Evolution Stuttgart:... Fromman-Holzboog Verlag Rosenman, M. 1997. The Generation of form Using an Evolutionary Approach Dasgupta, D. & Michalewicz (eds), Evolutionary Algorithms in Engineering Applications, Springer -Verlag Pub., 69-86. Roston, G. 1997. Hazards in Genetic Design Methodologies. Dasgupta, D. & Michalewicz (eds), Evolutionary Algorithms in Engineering Applications, Springer-Verlag Pub., 135-154. Schnier, T .......................................................................................
