Metaheuristics for Genetic Optimal Design

J. B. Dumont, MSc.

Centrale Graduate School, Lille, France.

Computer Science Laboratory, University of Lille, France.

e-mail: jean-baptiste.dumont@neuf.fr

Prof. J. Lefèvre, BEng, MSc, PhD.

Centrale Graduate School, Lille, France.

City University, London, UK.

e-mail: lefevreJ@libertysurf.fr

Abstract

Genetic Algorithm has already proved itself on several optimization problems. Since a few years, this heuristics has also been used in the design field, providing innovative, efficient and original results. Our work intends to exploit the potential of creative evolutionary system to produce 2D drawings.

This approach, known as evolutionary design, comes from the work of the zoologist Richard Dawkins about evolution. Dawkins wanted to illustrate in concrete terms the Principles of Darwin. He imagined a genotype describing simple shapes and a genetic algorithm to make them evolve. Because sometimes these drawings look like real living beings, they were called biomorphs.

The other approaches in this field tend to be, for most of them, either too constrained, restraining the creative potential of the algorithm, or too free, producing random and anarchic creation. Our MetaGOD (Metaheuristics for Genetic Optimal Design) system intends to provide a balance, similar to Dawkins’ Biomorph, between order and chaos.

MetaGOD is based on a dynamic tree-like structure able to describe drawings, which can be evolved by a genetic algorithm, using other heuristics like simulated annealing and advanced genetic programming. Each data structure in the computer matches with a drawing. The algorithm explores the different possible creations and makes them evolved to both a structural point of view and concerning the numeric attributes. This evolution is orientated by the expectation of the human creator who assesses each drawing every generation. In addition to original process for genetic crossover and mutation adapted to vectorial graphics, our approach is also based on other heuristics like simulated annealing and advanced genetic programming.

Introduction

In 1948, Turing suggested the possibility for a machine to give proof of a certain kind of intelligence. Nowadays, many programs are able to rival human brain thanks to AI techniques. Nevertheless, amongst all these algorithms, how many are able to demonstrate creativity? How many are able to produce an innovative and original result, at least comparable to human production?

Our work is focused on artificial creation of 2D vectorial drawing using the SVG (Scalable Vector Graphics) format. It is based on a genetic algorithm. In this approach, inspired of Darwin Principles, a population of individuals is evolving and multiplying according to a selective pressure. There, individuals are drawings and the selective pressure corresponds to the taste of a human creator.

First, a grammar has been set up. This grammar is able to describe a drawing. Then, a data structure has been implemented on a computer. This structure is handled by the genetic algorithm, which is able to produce genetically artistic creations and to make them evolve.

Creative Evolutionary Systems

This kind of process is defined as a creative evolutionary system. It is inspired of the research of Richard Dawkins. Dawkins was a zoologist who imagined a genotype description for simple forms and wrote a genetic algorithm to make them evolve in order to illustrate Darwin Laws. The amazing drawings, which were produced, looked like some living material observable in nature and were called Biomorphs. This breakthrough is the origin of creative evolutionary systems and evolutionary design.

Dawkins' Biomorphs

Dawkins has also proposed a generalization of Darwin Principles. These principles were initially applied to living world where information is materialized by DNA molecules. Then they inspired computer scientists who imagined Genetic Algorithm where information is materialized by the data in the computer. Dawkins postulates that Darwin Principles are applicable to any other field where variability, selectivity and heritability of information are verified and even if information is not truly materialized.

Through this principle, Dawkins focus on culture in main and especially on art:

• Variablity of information is verified judging from the existence of different cultures.

• Selectivity of information can be proved through noticing the fact that people usually choose which culture fit the best to them. For instance, there are some people who are more sensitive to a given fashion or cultural stream than others.

• There, heritability of information is also verified and is based on a special process of cultural replication observable through the mimetic interaction between the human beings.

Our approach was also targeted to enable an efficient balance between structured and methodic creation and free creation. The key point of our work is based on the data structure. Each kind of structuration has its pros and its cons. Rigid and steady structure enables efficient genetic algorithms owing to the proximity of the numerical optimization condition. However, it does not offer enough liberty to the process to produce innovative and original creations. Free structures can enable free creations, but mainly the results are often too anarchic to be adapted to a human solicitation.

MetaGOD

A drawing can be described through two sets of elements:

§ One set includes the n shapes which compose the drawing

§ The other one includes the k relations which exist between these n shapes

To a structural point of view, a drawing is a graph where the nodes are the n shapes and the edges are the k relations. MetaGOD system is a restriction of this approach to some sets of trees. This simplification enables easier way to go through the data and avoids the solving of the constraints problem represented in each cycle of the graph.

Implemented relations are:

§ Attachment

§ Containment

§ Disposition

MetaGOD prototype is able to use any kind of usual shapes (line, circle, rectangle...), but in its most recent version, the system has been focused on Bezier curves.

The grammar is defined through the different relation between shapes is able to describe most of usual drawing.

MetaGOD grammar is able to describe most of usual drawings

Concerning the data structure, the basic object is composed by the shape and by the relation with its ancestor. It is an object to Oriented Object Programmation point of view. This basic object owns properties (size of the shape, kind of relation...) and methods. Amongst these methods, one is the program which generates the corresponding graphics for this entity. To a graphic point of view, a drawing is a structured set of arranged shapes. To a data point of view, it is just a tree-like structure of programs. To produce the drawing, MetaGOD go through the data and for each shape composing the drawing and executes the display method. This program produces the SVG formated code corresponding to the graphics of the shape. Adobe SVG viewer, which displays the whole drawing, then interprets this code. Thus, the genetic part of MetaGOD, which make the drawings evolve, is based on the manipulation of tree-structured programs sets.

Genetic Operators

To make MetaGOD able to evolve drawings, several adapted genetic operators were imagined. As usual genetic algorithms, MetaGOD employs mutation and crossover processes to modify the data. Mutation consists in the modification, more or less randomly, of one parameter from the drawing. There are mainly two operators for the mutation process for the basic object of the structure: one works on the parameters related to the shape and the other works on the parameters related to the relation to its ancestor. Crossover consists in sharing information between two drawings. There are mainly two operators for the crossover process. One is local: two shapes share information concerning their outlines. The other operator is global: two drawings share information concerning their shapes. In the first case, the two crossed shapes give birth to two children which have one portion of their outlines coming from the first parent and the other portion come from the second parent. Global crossover is actually a process to cross two drawings. The two children have a part of their shape and their arrangement coming from one parent and the other part coming from the second parent.

Global and local crossover

Hybridizing of heuristics

In addition to the evolutionary based techniques implemented, MetaGOD system is also based on the use of other heuristics, well known from computer scientists: simulated annealing and advanced genetic programming.

MetaGOD: an original combination of heuristics

As a general principle, for the computer scientist, a simulated annealing process implies to define an external temperature in order to set the intensity of the internal process. In local search for instance, the temperature sets the amplitude for the neighborhood of exploration around the current point. In other cases, the temperature is also able to influence the amplitude of the changes required to switch from one solution to another one. There, MetaGOD system uses two independent temperatures. Concerning the mutation operator, the first temperature conditions the probability for one parameter to be modified. The second one is required when a change is decided and influences the maximal amplitude for the modification of one parameter. The program goes through each tree sets of the drawing, entity by entity, parameter by parameter, and applies this process. Concerning the crossover operator, only the second temperature is useful. It influences the ratio of exchanged information during the reproductive process (outline for local crossover and depth of switched sub-trees for global crossover).

Advanced Genetic Programming consists for the user in the possibility to fix the fittest shapes of a drawing. In other words, when MetaGOD draws a shape that suit to his taste, the user can say: “this shape is nice enough for me, let stop its evolution”. Genetic Programming works on two levels: On the one hand, it enables the user to influence the genetic part of MetaGOD by fixing a suitable shape; on the other hand, it has also an impact on the functioning of the simulated annealing. Indeed, fixing a shape amounts to saying "this shape is isolated from the external temperatures" or "its temperature is set to the absolute zero". The interaction between GP and SA is not limited to the only aspect of the shape itself. GP influences also the evolution of the edge of the structure, that is to say the relation between the shapes. Actually, when the user evaluates a set of shapes, the shapes are not the only purpose of the evaluation: the disposition of the shape is another aspect of the appreciation of the drawing. Thus, when the user choose to fix two shapes which are linked by a given relation, it seems normal to fix the relation too, in order to avoid an untimely evolution of the whole set. Considering a given relation, if only one shape is fixed and the other one remains free, then the evolution of the relation remains possible, but the maximal amplitude of any modifications on the edge is reduced by an half. In other words and to simplify, the temperature of one edge corresponds to the average of the temperature of the two shapes linked by this relation.

The influence of simulated annealing and genetic programming on the data structure

Results

To maintain an efficient aesthetic coherency, the functioning of MetaGOD system has been restricted to Bezier curves. Thanks to this simplification, every shape has the same type: each shape is then a list of points. Nevertheless, this does not restrain the creative potential of our algorithm because these curves are sufficient to describe every usual shape.

Let us point out the fact that another heuristics has been used: the collision avoidance, aimed at avoiding undesirable overlapping of one shape over another.

Influence of the use of collision avoidance

User interface is presented like this:

User interface

On the upper part of the interface, there is the menu of the possible actions. On the principal part, there are the different drawings and four radiobuttons for the evaluation. On the lower part, there are the two temperatures that are adjustable by the user.

Several scenarios were considered depending on the size of the shapes, on the kind of structuration for the drawings, on the reproductive process, or on the use of advanced genetic programming.

Experimental results

The main difference between these two paintings comes from the use of different reproductive process. On picture a), the reproductive process used was sexual. There, the shapes seem to be quite more original than on picture b) (asexual process). There are, at least, two explanations for these divergences. On the one hand, the crossover process seems to introduce noise in the drawing, which is then filtered by the user. This noise, oriented by the taste of the human creator, contributes to the creativity of the global system. On the other hand, for the user the design of the drawings is radically different depending on the chosen configuration. In the first case, the user has to work on several drawing at the same time. Thus, he is less concentrated and by extent, creation happens more randomly. While in the second case, he can focus on his creation and consequently his creation is less extravagant.

When MetaGOD and a human artist work together:

Artificial creation meets human interpretation

Conclusion

Our work provides an evolutionary method combined with advanced heuristics of algorithmics, applied to the design of 2D drawings. This system is based on an efficient data structure which enables free creation, is hierarchic enough to avoid anarchic creation, and can be handled by a genetic algorithm.

The genetic part of the algorithm is a true spring of creativity. The assessment given by the user for each drawing, every generation, is analog to the fitness function from usual genetic algorithm and orientates the creative potential of the program. Simulated annealing and advanced genetic programming provide an easier integration of the taste of the human creator.

References

[1] P.J. Bentley, "Evolutionary Design by Computers", Ed. Morgan Kaufman, 1999.

[2] P.J. Bentley, "Creative Evolutionary Systems", Ed. Morgan Kaufman, 2002.

[3] P.J. Bentley, "The Revolution of Evolution for Real-World Applications", in Emerging Technologies '97: Theory and Application of Evolutionary Computation, University College London, 1997.

[4] P.J. Bentley, "Aspects of Evolutionary Design by Computers", in Proceedings of the 3rd On-line World Conference on Soft Computing in Engineering Design and Manufacturing (WSC3), 1998.

[5] J.A. Biles, "Life with GenJam: Interacting with a Musical IGA", in Proceedings of The IEEE International Conference on Systems, Man, and Cybernetics, 1999.

[6] R. Dawkins, "The Blind Watchmaker", Longman Harlow, 1986.

[7] J. David Eisenberg, "SVG Essential", Ed. O'Reilly, 2003.

[8] M.J. French, "Invention and Evolution: Design in Nature and Engineering", 2nd Edition Cambridge University Press, 1994

[9] L.J. Fogel & al., "Artificial Intelligence through Simulated Evolution", 1966

[10] R. Girard, "Celui par qui le scandale arrive", ed. Desclée de Brouwer, 2001.

[11] D.E. Goldberg, "Genetic Algorithms as a Computational Theory of Conceptual Design", in Proceedings of Applications of A.I. in Engineering, 1991

[12] J. Koza, "Genetic Programming: on the Programming of Computers by Means of Natural Selection",1992.

[13] J. Lefèvre, "L'Algorithmique Evolutive, une aide à la création de dessins innovants", 2004.

[14] M. Lewis, "Aesthetic Evolutionary Design with Data Flow Networks", PhD Thesis, Ohio State University, 2000.

[15] D.S. Linden and E.E. Altshuler, "Evolving Wire Antennas using Genetic Algorithms", in First NASA/DoD Workshop on Evolvable Hardware, Pasadena, July 1999.

[16] K. McAlpine, E. R. Miranda, and S.Hoggar, "Composing Music with Algorithms: A Case Study", in Computer Music Journal, 1999.

[17] A.Moroni, J. Manzolli, F. Von Zuben, "Composing with interactive Genetic Algorithm", 2000.

[18] S. Rooke, "Aesthetic Selection: The Evolutionary Art of Steven Rooke", in IEEE Computer Graphics and Applications, 1996.

[19] T. Schnier, J.S. Gero, "From Mondrian to Frank Lloyd Wright:Transforming Evolving Representations, in 3rd International Conference on Adaptive Computing in Design and Manufacture, 1998.

[20] K. Sims, "Evolving 3D Morphology and Behavior by Competition, in Proceedings of Artificial Life IV, MIT Press 1994.

[21] H. Takagi, "Interactive Evolutionary Computation: Fusion of the Capabilities of EC Optimization and Human Evaluation", in Proceedings of The IEEE International Conference on Systems, Man, and Cybernetics, 2001.

[22] S.Todd and W.Latham, "Evolutionary Art and Computers", Academic Press, London, 1992.

[23] A.M. Turing, "Computing Machinery and Intelligence", Oxford University Press, 1950.

[24] M. Whitelaw, "Breeding Aesthetic Objects: Art and Artificial Evolution", in Symposium on Creative Evolutionary Systems, part of AISB99, Edinburgh, April 1999.