Evolutionary systems & genetic algorithms

From GenerativeArt

(Difference between revisions)
Jump to: navigation, search
(→Types of Genotype Representations)
Current revision (22:11, 9 September 2013) (view source)
(→Further Evolutionary Art Development by Karl Sims: Added a link to NEvAr)
 
-
{{SingleImage|imageWidthPlusTen=726|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/01.png|caption=Genetic Competition}}
+
{{SingleImage|imageWidthPlusTen=726|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/01.png|caption=Genetic Competition}}
* A way to select genotypes based on their scores and then modify or recombine them for expression
* 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 express genotypes to create phenotypes
-
* A way to assign each genotype a score based on an evaluation of the corresponding phenotype
+
* A way to assign each genotype a fitness score based on an evaluation of the corresponding phenotype
-
== Types of Genotype Representations ==
+
== 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.
-
There are at least 3 types of genotype representation that can be differentiated based on the mechanism used and the complexity of the resulting expression:
 
-
* A genotype can provide a fixed number of parameters
 
-
* A genotype can provide an extensible number of parameters
 
-
* A gentotype can provide construction machines of a fixed or extensible number
 
== Practical Notes for Computer Artists ==
== Practical Notes for Computer Artists ==
-
{{SingleImage|imageWidthPlusTen=636|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/02.jpg|caption=Genetic Operations}}
+
{{SingleImage|imageWidthPlusTen=636|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/02.jpg|caption=Genetic Operations}}
-
{{SingleImage|imageWidthPlusTen=610|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/03.jpg|caption=Comparision of mutation distributions}}
+
{{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 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.
-
{{SingleImage|imageWidthPlusTen=455|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/04.png|caption=Gray Code}}
+
{{SingleImage|imageWidthPlusTen=455|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/04.png|caption=Gray Code}}
  010<font color="red">0</font>      XOR      011<font color="red">1</font>
  010<font color="red">0</font>      XOR      011<font color="red">1</font>
-
 
-
== Example of Classic Genetic Programming for Problem Solving - Lawrence Fogel ==
 
-
 
-
Fogel is a graduate of NYU (B.S.E.E. 1948) and began the field of genetic programming in the mid-1960's. Genetic programming was used as a way to optimize solutions to problems with no exact or analytic solution.
 
-
 
-
 
-
<span style="font-size:larger;">The Traveling Salesman problem</span>
 
-
 
-
The goal of this classic optimization problem is to craft a path visiting each location once and only once in the shortest distance possible.
 
-
 
-
 
-
{{SingleImage|imageWidthPlusTen=592|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/07.png|caption=Traveling Salesman Problem}}
 
-
 
-
 
-
{{SingleImage|imageWidthPlusTen=729|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/08.jpg|caption=Routing Problems}}
 
-
 
-
 
-
{{SingleImage|imageWidthPlusTen=740|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/09.jpg|caption=Traveling Salesman Problem Visualized}}
 
-
 
-
 
-
{{SingleImage|imageWidthPlusTen=766|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/10.jpg|caption=Traveling Salesman Problem Visualized}}
 
-
{{SingleImage|imageWidthPlusTen=444|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/11.jpg|caption=Genetic Art Examples}}
+
{{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}}
+
{{SingleImage|imageWidthPlusTen=766|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/12.jpg|caption=Genetic Art Examples}}
-
{{SingleImage|imageWidthPlusTen=719|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/13.jpg|caption=}}
+
{{SingleImage|imageWidthPlusTen=719|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/13.jpg|caption=}}
-
{{SingleImage|imageWidthPlusTen=766|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/14.jpg|caption=Genetic Art Examples}}
+
{{SingleImage|imageWidthPlusTen=766|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/14.jpg|caption=Genetic Art Examples}}
-
{{SingleImage|imageWidthPlusTen=515|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/15.jpg|caption=Genetic Art Examples}}
+
{{SingleImage|imageWidthPlusTen=515|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/15.jpg|caption=Genetic Art Examples}}
-
{{SingleImage|imageWidthPlusTen=739|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/16.jpg|caption=Genetic Art Examples}}
+
{{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=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=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=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=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=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}}
+
{{SingleImage|imageWidthPlusTen=488|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/genetic/22.jpg|caption=Genetic Art Examples}}
<span style="font-size:larger">Image synthesis</span>
<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. Ashley Mills offers a simplified explaination of this method here.
+
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.
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.
-
{{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}}
+
{{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}}
* 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.
* 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 ==
== Interactive Genetic Art Installation ==
-
In his famous [http://www.genarts.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.
+
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.genarts.com/karl/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.
+
 +
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 ==
== More Examples ==
* Matt Lewis - [http://accad.osu.edu/~mlewis/aed.html Evolutionary Design Links]
* Matt Lewis - [http://accad.osu.edu/~mlewis/aed.html Evolutionary Design Links]
-
* Karl Sims - [http://accad.osu.edu/~mlewis/aed.html Evolutionary Computation for Art and Design Links]
+
* Karl Sims - [http://www.karlsims.com/ Collected Works]
* Craig Reynolds - [http://www.red3d.com/cwr/evolve.html Evolutionary Computation Links]
* Craig Reynolds - [http://www.red3d.com/cwr/evolve.html Evolutionary Computation Links]

Current revision

Retrieved from "http://philipgalanter.com/generative_art/wiki/index.php5?title=Evolutionary_systems_%26_genetic_algorithms"
Personal tools