View source

__FORCETOC__

Genetic Algorithms are biologically inspired programming techniques used to generate variations and approximate the solution to a problem by iterative selective breeding.  Genetic Algorithms have the advantage of finding novel solutions or variations for a specific situation without the programmer having to explicitly provide an analytic solution for the general case.  Like natural evolution, genetic algorithms yield increasingly optimized results by discarding poor adaptations, and breeding new generations from those successful adaptations selected by the environment.


== Biological Genetic Information ==

Biological genes can be thought of as linear sequences of 4 chemicals called nucleotides.  These cluster into groups of 3, called codons, which in turn cluster into genes. Genes in turn form a long strand of DNA, and a complete strand forms a chromosome. 

A gene's genotype refers to its specific chemical configuration, and when the gene is "expressed" it results in a phenotype, the trait which emerges as a result of the gene's influence.

Genetic variation across generations can happen in two ways.  First mutations occur when individual nucleotides spontaneously change, or groups of nucleotides change positions.  Second, recombination takes place when 2 strands of DNA crossover and exchange long strands of DNA.

Its worth noting that in a biological genetic system the "data" (the nucleotides) and the "computer" (the DNA and RNA machines that produce proteins) are composed of the same kind of "stuff"...chemicals. In a very real sense in DNA the software is also the hardware.
 

== Digital Genetic Information ==

In its classic form a genetic algorithm does not structure its data per se.  Rather it simply manipulates strings of bits.  At various points, however, that string of bits is interpreted by the software as the genotype for a set of possible phenotypes.

As a practical matter it is often more useful to treat information at a higher level of abstraction as genetic information.  For example, a gene which will be expressed as a color might be abstracted as 3 8 bit numbers representing an RGB color. Colors can also be coded in the form of HSV colors. Even in this simple example there are different ways to encode the genotype for a given set of phenotypes.

In both cases, however, the genes are treated as data by a computer, and there is no low level merger of software and hardware as is found in a biological system.

In addition genetic structures may be in a fixed length format, or it may be a variable length format made up of an arbitrary number of modules.

In both artistic and engineering applications, considerable effort is put into the design of the gene coding.
 

== Genetic Competition ==

The following cycle of genetic competition lies at the core of evolutionary computing:


{{SingleImage|imageWidthPlusTen=726|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/01.png|caption=Genetic Competition}}


* A number of individuals (chromosomes or sets of genes) are in the population (gene pool) and each has a fitness score.
* Based on the score for each individual some are selected for reproduction, some are deleted, and some are simply left alone.
** One option is to simply remove low scoring individuals, and then to randomly select from those remaining individuals for reproduction.
** Another option is to use the fitness score to calculate a probability the individual will be removed or selected for reproduction. This is preferred in more typical genetic algorithms to preserve diversity in the gene pool
** In some cases the upper n% of genes might be deemed immune from deletion. This can prevent the deletion of highly desireable chromosomes.
** It should be noted, however, that typical design systems have tended to keep very few individuals in the gene pool. Often only 2 or 3 hand selected chromosomes are retained, all the others are discarded, and the gene pool is refilled using the selected chromosomes
* The genes of the individuals selected for reproduction are used to generate genetic variations.
** Offspring of a single individual may have variations due to mutation.
*** For bit string formats mutations may be a function of individual random bit flips
*** For parametric formats mutations may be a function of uniform random numbers, or other statistical distributions such as Gaussian (Normal) random numbers
** Offspring of a single individual may have variations due to inversion. (This usually is only done with bit string genetic formats.)
** Offspring of two individuals may have variations due to recombination via crossover.
* The genetic variants are expressed producing the phenotypes of the individuals.
* The phenotype of each individual is subjected to a fitness function which yields a fitness score for each individual.
* Those individuals, or optionally only those that exceed a minimum fitness score, are added back into the population


== Minimum Requirements for an Evolutionary System ==

Even the most basic evolutionary system has these four components:

* A genotype representation
* A way to select genotypes based on their scores and then modify or recombine them for expression
* A way to express genotypes to create phenotypes
* A way to assign each genotype a fitness score based on an evaluation of the corresponding phenotype


== Methods for Providing Fitness Scores ==

In various industrial applications fitness can be automatically evaluated using objective measures.  For example, competing genetically based investment tools can be evaluated simply by comparing their rate of return on investment.  Automated fitness scores in the arts, sometime called Computational Aesthetic Evaluation, is an exceedingly difficult unsolved problem.  A viable alternative is for the artist himself to score phenotypical expressions creating an Interactive Evolutionary System.  However, with the artist "in the loop" the population size and the number of generations are both severely limited.

== Types of Genetic Representations ==

Another significant challenge for evolutionary artists is the design of the genotype.  There are at least 4 types of genotype representation that can be differentiated based on the mechanisms they use.  Each has a different complexification capacity, i.e. some representations lead to more complexity than others.  

* '''''Fixed Parametric''''' - A genotype that uses a fixed number of parameters that map into phenotypical characteristics in a one-to-one manner. The complexification capacity of this system is highly constrained. 
**For example, consider a system for creating drawings of insects. There might be a gene for head size, another for body color, another for leg length, and so on. While such a system may draw a wide variety of insects it will never draw a spider because unless there is a “number of legs” gene all results will have six legs.
* '''''Extensible Parametric''''' - A slightly more complicated genotype that uses a variable number of parameters that map into phenotypical characteristics in a one-to-one manner. The complexification capacity of this system is still fairly constrained.  
**An extension of the previous example might allow an arbitrary number of genes for legs.  By allowing each gene to draw a single leg this system would be able to draw insects, spiders, and even centipedes and millipedes. But it would not be capable of drawing fish or birds because it lacks fin and wing genes. 
* '''''Direct Mechanical''''' - This type of genotype describes one or more machines that in turn construct the phenotype. The complexification capacity of this kind of system is potentially much greater than the previous two. 
**In our example this genetic system doesn’t describe a drawing, but rather describes a machine that can draw. Such a representation will, in theory, allow most anything to be drawn. In addition, during reproduction the genes themselves may mutate making the child different than the parent. For example, a machine that creates thin pencil lines may mutate into a machine that makes brushed ink marks. Such a system may seem to be of unlimited potential, i.e. unlimited complexification capacity. But such a system is only capable of a single layer of emergence. The machines immediately and directly draw the picture, and that is that.
* '''''Reproductive Mechanical''''' - Such a system is similar to the previous one, with the significant addition that within a single individual a machine may also create another machine, reproduce itself, or contribute to an emergent machine at a higher level of complexity and scale. This genetic representation offers the greatest complexification potential.
**And this is, in fact, the kind of genetic representation found in nature. There is an upwardly layered increase of complexity as DNA creates proteins, proteins organize to create organelles, organelles organize to create cells, cells organize to create organs, and so on.


== Practical Notes for Computer Artists ==

Nature has the advantage of very large populations, long time frames, and massively parallel execution.  For practical purposes a computer artist using methods inspired by evolution may want to keep in mind the following:
* Often using a genetic data representation is useful simply for generating random variations and as the basis of a sort of style database.
* Even without using any specific form of competition, a genetic data representation will allow the artist to selectively breed individuals to create variations which better approach an imagined ideal.  This would be similar to the way dog breeders might attempt to breed a champion.
* Along with variation operations the artist has to specify the rate of variation. For example, should mutations take place frequently, and perhaps multiple times in a single reproduced individual, or should it be a rare event?
* Chromosomes will take the form of data structures which assemble and allow for the variation of genes. These data structures may take a number of forms:
** The chromosome may be a bit-string, and then genes are extracted by matching against a template.
** The chromosome may be a data structure with a number of phenotype-specific parameters.
** The chromosome may be an extensible format. Such formats may include:
*** Programs which can be compiled and assembled.
*** Programs which can be interpreted by a virtual machine.
*** Mathematical formulae.
*** Instructions for modular construction

Chromosomes which use a fixed bit-string template or parametric representation are locked-in in terms of complexity. Their format defines an N-dimensional design space that will remain unchanged regardless of how the various individuals evolve. Extensible formats allow for complexification (a growth in complexity) as additional dimensions are added to the design space.

A fitness function for aesthetic choices is not something which is immediately obvious.  But a "fitness score" in an arts making context might include:
* Simply an intuitive judgment made by the artist.
* Interactive input provided by an audience.
* An evaluation based on design criteria such as scale, color, aspect ratio, degree of contrast, etc.
* A rule-based automated fitness function.


== Genetic Variation Operations ==

For bit-string genetic representations genetic variations are fairly straightforward.


{{SingleImage|imageWidthPlusTen=636|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/02.jpg|caption=Genetic Operations}}


For engineering solutions with structured (non-bitstring) genes the distribution of mutations may be non-uniform, e.g. Gaussian (or Normal). Some studies have shown such techniques provide faster more accurate solutions.


{{SingleImage|imageWidthPlusTen=610|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/03.jpg|caption=Comparision of mutation distributions}}

In addition the rate of mutation may be a genetic variable. This provides some relief in deciding what the mutation rate should be. The optimal mutation rate will then evolve. It's even possible that the mutation rate will self-adjust over time. Typically at the start the mutation rate should be higher (randomization) than it is later (when fine tuning). It's worth noting that some cases have been found in nature where the mutation rate increases in response to increased environmental pressure. This too could be simulated by calculating the mutation rate as a function of both genetics and environmental pressure.

(In non-artistic optimization applications genetic algorithms often ramp down the frequency and size of mutations as the system converges on a solution. This is often referred to as "simulated annealing.")


== An Aside Regarding Bit String Genetic Representations ==

Often rather than using standard binary numbers to represent a continuous value an encoding called Gray Code is used. Gray Code will make bit mutations result, on the average, in fewer large changes and more frequent small changes. This is illustrated in the following example coding for the integers 0 through 15.


{{SingleImage|imageWidthPlusTen=455|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/04.png|caption=Gray Code}}


In both cases the mean degree of change is 3.75. In the case of binary codes there are as many transitions above the mean as below the mean. But in the case of gray codes 44 transitions are below the mean and 20 transitions are above the mean. Gray code provides a system where mutations result in a greater number of small changes, and a lesser number of large changes.


<span style="font-size:larger">Binary to Gray Code Conversion</span>

 1. Number the digits 1, 2, 3 … n
 2. Copy B[1] to G[1]
 3. For G[2], G[3] … G[n]
        G[i] = XOR(B[i], B[i-1])

 Example: convert 1011
 Binary             Gray
 <font color="red">1</font>011      COPY     <font color="red">1</font>
 <font color="red">10</font>11      XOR      1<font color="red">1</font>
 1<font color="red">01</font>1      XOR      11<font color="red">1</font>
 10<font color="red">11</font>      XOR      111<font color="red">0</font>

 Note: XOR is the eXclusive-OR function
 Inputs    Outputs
  0 0         0
  0 1         1
  1 0         1
  1 1         0


<span style="font-size:larger">Gray Code to Binary Conversion</span>

 1. Number the digits 1, 2, 3 … n
 2. Copy G[1] to B[1]
 3. For B[2], B[3] … B[n]
        B[i] = XOR(G[i], B[i-1])

 Example: Convert 0100
 Gray               Binary
 <font color="red">0</font>100      COPY     <font color="red">0</font>
 0<font color="red">1</font>00      XOR      0<font color="red">1</font>
 01<font color="red">0</font>0      XOR      01<font color="red">1</font>
 010<font color="red">0</font>      XOR      011<font color="red">1</font>




== Early Genetic Art - William Latham (with Stephen Todd and others) ==

William Latham began working using a genetic approach even before using computers.


{{SingleImage|imageWidthPlusTen=444|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/11.jpg|caption=Genetic Art Examples}}


{{SingleImage|imageWidthPlusTen=766|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/12.jpg|caption=Genetic Art Examples}}


Working with sculptural forms, Latham's genes are variable length assemblies of modules which are connected with various operations for contour, scale, and twist.


{{SingleImage|imageWidthPlusTen=719|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/13.jpg|caption=}}


Each gene can be considered a parameter which contributes a dimension to a gene space. The more alike two individuals genes are the closer together they are in gene space.


{{SingleImage|imageWidthPlusTen=766|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/14.jpg|caption=Genetic Art Examples}}


Using evolutionary methods, the artist applies an intuitive fitness function by manually evaluating phenotypes and assigning each a score. As a result the artist steers through the gene space towards an increasingly desirable result. As noted in the example above, attention must be paid to scaling so that the degree of variation is appropriate in each dimension. One approach is to normalize each parameter to values between 0 and 1, apply the variation method, and then re-map the parameter back into its native range.


{{SingleImage|imageWidthPlusTen=515|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/15.jpg|caption=Genetic Art Examples}}


The artist typically uses a selective breeding tool to navigate through the gene space. Latham sculpts forms in the sense that a farmer sculpts increasingly healthy crops by developing hybrid seed.


{{SingleImage|imageWidthPlusTen=739|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/16.jpg|caption=Genetic Art Examples}}


{{SingleImage|imageWidthPlusTen=545|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/17.jpg|caption=Genetic Art Examples}}


{{SingleImage|imageWidthPlusTen=620|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/18.jpg|caption=Genetic Art Examples}}


{{SingleImage|imageWidthPlusTen=759|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/19.jpg|caption=Genetic Art Examples}}


{{SingleImage|imageWidthPlusTen=752|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/20.jpg|caption=Genetic Art Examples}}


{{SingleImage|imageWidthPlusTen=759|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/21.jpg|caption=Genetic Art Examples}}


{{SingleImage|imageWidthPlusTen=488|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/22.jpg|caption=Genetic Art Examples}}



== Further Evolutionary Art Development by Karl Sims ==

<span style="font-size:larger">Image synthesis</span>

Karl Sims uses an old idea to create new art. In this SigGraph paper he describes how mathematical expressions can be treated as an assembly of genes. His paper can be found [http://www.karlsims.com/papers/siggraph91.html here.]

Basically the expression is parsed into a tree structure, and then subjected to mutations, or a form of crossover by substituting entire branches of the tree. An equivalent implementation can be done by using text oriented regular expression processing techniques. The resulting phenotype is an image computed pixel by pixel by evaluating each expression substituting the specific (x,y) coordinate.

Here is an illustration of the tree structure technique with the expressions added.


{{SingleImage|imageWidthPlusTen=636|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/23.jpg|caption=Illustration of the tree structure technique with the expressions added}}


As noted by Sims:

* For use in image synthesis each RGB color channel intensity can be calculated as a function of the (x,y) pixel location.
* Procedural textures can be created for 3D modeling by calculating for (x,y,z) voxels.
* Animations can be created by calculating each color channel as a function of (x,y,t) where t is time.
* Morph-like animated transitions can be achieved between two formula trees when they are similar with reference to the root node. (This looks significantly different than a tradtional cross-dissolve. Please see his paper above for details).
* Image processing or video processing can be done by calculating pixel values as a function of (x,y,i,t) where i is the value of the image channel and t is time.

Worth noting in this realm is the NEvAr system that automates the fitness function by using (more or less) the ratio of two complexity measures, compressibility via JPEG versus compressibility via fractal methods. A paper documenting NEvAr can be found [https://estudogeral.sib.uc.pt/bitstream/10316/7641/1/obra.pdf here.]

== Interactive Genetic Art Installation ==

In his famous [http://www.karlsims.com/galapagos/index.html Galapagos installation], Sims allows the audience to act as the evaluation function by simply "voting with their feet"...i.e. stepping up to the display that suit their fancy.

Sims is also well known for his [http://www.karlsims.com/evolved-virtual-creatures.html Evolved Virtual Creatures]. Using block like modules connected to actuators and neural networks, all in a virtual world with simulated physics, the genes fix the structure and then the resulting creature learns how to move based on a reward system providing feedback.

== More Examples ==

<span style="font-size:larger">Kenneth O. Stanley</span>

KStanley is not an artist, but his development of the NeuroEvolution of Augmenting Topologies (NEAT) method has been applied to image making by his students. It has also been applied to video games, the control of animation particle systems, and recently the evolutionary training of virtual dancers. The NEAT method evolves a neural network via complexification. I.e. the system starts with a very simple network and then slowly adds more nodes, connections, and weights as it gets closer and closer to the desired solution.

The student evolutionary art project is available as a web-based Java application [http://picbreeder.org/ here]. A website where you can download the video game developed using the NEAT method is available [http://nerogame.org/ here]. Stanley's Ph.D. dissertation which established the NEAT method is available [http://nn.cs.utexas.edu/downloads/papers/stanley.phd04.pdf here], and his web page is [http://www.cs.ucf.edu/~kstanley/ here]. This relatively recent work holds much promise to address the long standing challenge of effectively designing neural networks using evolutionary methods.


<span style="font-size:larger">Driessens & Verstappen</span>

Erwin Driessens and Maria Verstappen have created a number of generative works and some of these have used evolutionary techniques. [http://www.xs4all.nl/~notnot/breed/Breed.html Breed] creates virtual sculptures using genetic programming to manage the evolution of 3D cellular automata-like systems. The virtual sculptures are then rendered as physical objects using rapid prototyping technology. [http://www.xs4all.nl/~notnot/E-volverLUMC/E-volverLUMC.html E-volver] is presented as an interactive "image-breeding-machine. The resulting images have been used to create large prints and screensaver software. The resulting systems are being used in a larger installation called [http://www.xs4all.nl/~notnot/evolvedxxw/evolvedxxw.html E-volved Cultures XXW].


<span style="font-size:larger">Scott "Spot" Draves</span>

Artist/Programmer Scott Draves is the creator of [http://electricsheep.org/ Electric Sheep]. Electric Sheep uses a distributed network of over 60,000 computers that donate surplus computation cycles. This network renders frames of genetically-based animated fractal flames. Fractal flames are a particularly robust and complex family of fractals. Completed animations, called sheep, are then automatically downloaded and displayed on the computers in the network as screensavers. Users can rate the sheep, and those ratings are folded back into the system as fitness scores used to evolve the next generation of sheep.


== Additional Resources ==

* Matt Lewis - [http://accad.osu.edu/~mlewis/aed.html Evolutionary Design Links]
* Karl Sims - [http://www.karlsims.com/ Collected Works]
* Craig Reynolds - [http://www.red3d.com/cwr/evolve.html Evolutionary Computation Links]