Evolutionary systems & genetic algorithms

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

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}}

{{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.

* A number of individuals (chromosomes or sets of genes) are in the population (gene pool) and each has a fitness score.

* Those individuals, or optionally only those that exceed a minimum fitness score, are added back into the population

* Those individuals, or optionally only those that exceed a minimum fitness score, are added back into the population

Even the most basic evolutionary system has these four components:

Even the most basic evolutionary system has these four components:

* 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 score based on an evaluation of the corresponding phenotype

== Types of Genotype Representations ==

== Types of Genotype Representations ==

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

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}}

{{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.

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.

(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.")

(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 ==

== 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.

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}}

{{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.

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>

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

  1. Number the digits 1, 2, 3 … n

  1. Number the digits 1, 2, 3 … n

  2. Copy B[1] to G[1]

  2. Copy B[1] to G[1]

   1 0        1

   1 0        1

   1 1        0

   1 1        0

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

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

  1. Number the digits 1, 2, 3 … n

  1. Number the digits 1, 2, 3 … n

  2. Copy G[1] to B[1]

  2. Copy G[1] to B[1]

  01<font color="red">0</font>0      XOR      01<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>

  010<font color="red">0</font>      XOR      011<font color="red">1</font>

== Example of Classic Genetic Programming for Problem Solving - Lawrence Fogel ==

== Example of Classic Genetic Programming for Problem Solving - Lawrence Fogel ==

{{SingleImage|imageWidthPlusTen=766|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/genetic/10.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}}

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

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

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

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=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}}

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

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=}}

{{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.

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}}

{{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.

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}}

{{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.

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=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}}

== Further Evolutionary Art Development by Karl Sims ==

== Further Evolutionary Art Development by Karl Sims ==

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

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}}

{{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:

As noted by Sims:

* 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).

* 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.

* 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.

== Interactive Genetic Art Installation ==

== Interactive Genetic Art Installation ==