Evolutionary Theory

The process of creating Evolutionary Computer Graphics uses methods and algorithms that are defined in the biologically inspired field of Evolutionary Computation (EC).

The process of EC relates closely to a subfield of Artificial Intelligence (AI) called Machine Learning (ML), in which computer programs improve their performance through experience.

Some authors classify EC as a specific type of ML, while others relate the simularities as a cross-disciplinary exchange of methodology with different mindsets.

Specifically, EC techniques differ from standard ML methods in that they model a digital approximation of biological evolution. Instead of using formal logic, EC is typically used to optimize a solution through selective "guess-and-check" methods that don't necessarily learn from their mistakes or successes.

On the other hand, EC can be defined as the evolution of programs or algorithms designed for inductive learning. Furthermore, it is possible to use various techniques of EC to optimize existing solutions for ML.

Regardless of how they are classified, both processes are designed to automate the process of deriving a solution to a particular problem through iterative refinement.

Ultimately, however, a certain amount of domain knowledge is required for either method in order to properly formulate an algorithmic represention for the problem to be solved and develop operators to drive the decision making process to generate an approximation to the solution.

Formal modeling processes for representing a problem have been developed for ML and can be directly applied to EC since a similar modeling process must be performed.

This process is described in the following section with a particular emphasis on ML techniques. In later sections, these methods are adapted and discussed in the context of EC.

Evolutionary Computation

Evolutionary Computation is a category of methods which digitally simulate biological evolution. The various techniques that have been developed differ in the way that they model the evolutionary process and to what extent.

Each method of EC defines a more specific subdomain which tend to model evolution at successively more specific levels.

At the highest level, is the generic superclass of Genetic Programming (GP), followed closely by Evolutionary Algorithms (EA).

There are three main types of EAs, which include Evolutionary Programming (EP), Evolutionary Strategies (ES), and Genetic Algorithms (GA).

The following outline illustrates this heirarchy of EC and all of the afore-mentioned subfields, listed in ascending order of specificity.

A brief summary of each of these EC areas is presented in the following sections, followed by a brief summary of cellular biology and some common terms used in EC.

Genetic Programming

Genetic Programming (GP) can be defined as an ML system in which an initial population is represented as a set of computer programs that automatically improve through the evaluation of the data on which they are trained. (Benzhaf, 4) Genetic Programming This class of algorithms was first developed in 1992 by John R. Koza, and allows solutions to be represented that are of variable length. It primarily uses primarly sexual recombination (crossover) (95%) and mutation (5%) as its transformation operators.

The following distinguishing features identify GP from other ML systems.

It is interesting to note that this definition implies that GP can theoretically evolve any solution that any other ML system could possibly produce.

Evolutionary Algorithms

Evolutionary Algorithms (EA) are a general set of direct probablistic search and optimization algorithms based on a model of biological evolution used to perform EC (Back, vii).

As a result, there are a great number of EAs, but they all essentially model the learning process within a population of individuals. EAs typically retain certain information about their environment and most EAs are defined in the general subdomain of Evolutionary Strategies.

Evolutionary Programming

Evolutionary Programming (EP) is similar to GP in that it is an evolutionary optimization method, but differs in that it operates at the species level where a species is defined as a multi-individual class that shares a particular set of behavioral traits (Angeline, 6).

This evolutionary strategy was originally conceived by Lawrence J. Fogel in 1960, and places emphasis on the behavioral characteristics that form between generations rather than modeling a particular biological genetic operation.

There are no restrictions to the solution representation, although in practice, fixed length real valued strings tend to be used most often.

The primary operator is mutation, which is typically used to change links and states of finite state machines (FSM).

There are three fundamental steps to the basic EP algorithm, which are outlined in the table below.

Evolutionary Strategies

Evolutionary Strategies (ES) are a class of EAs which operate on individuals, and utilize mutation as their primary transformation operator. Representations are typically real valued (Angeline, 4). ES facilitates the adoption of learning processes, such that each individual can be assigned strategy parameters such as mutation rate and a particular recombination method. ES also embrace the notion of causality, where strong causes generate strong effects.

This deterministic process of selection results in better adapted individuals and closely models Charles Darwin's theory of Natural Selection.

The general form of an ES involves an initial population which can be transformed through random selection, mutation and mating, depending on certain strategies.

The first strategy called the plus strategy (+) selects individuals from the current generation and ignores the offspring, whereas the second strategy, the comma strategy (,) focuses entirely on the children and ignores the parents during the selection process (EC FAQ)

Genetic Algorithms

Genetic Algorithms (GA) were first introduced by John Holland in 1992 and operate on a genetic representation of an individual using biologically derived rules of sexual recombination and mutation. The representation is usually a fixed length binary string.

The fundamental steps to the basic GA are outlined in the table below.

The evolutionary model that is used by EC is a digital approximation of the biological evolutionary process, which is an incredibly complicated process in itself. As a result, a brief overview of cellular biology and genetic evolution is provided to aid in the understanding of the digital approximation used in Artificial Evolution AE.

Biological Evolution

In order for a species to evolve, there must exist a mechanism for individuals to reproduce and pass heredity from parents to offsping. This mechanism is genetics and for biological lifeforms, it is contained in a double-stranded helical structure called Deoxyribonucleic Acid (DNA).

This structure was discovered by Francis Crick and James Watson in 1962 and is composed of four specific nucleotide bases held together by a sugar molecule (deoxyribose) that forms the backbone of the polymer helix. These fundamental nucleotide bases are listed in the table below.

This DNA structure carries the genetic information of a cell and is located in a cell's nucleus in long thread-like packages called chromosomes. Each location on the DNA defines a gene which encodes a formula to build a specific protein molecule out of 20 possible amino acids. These genes are the fundamental transfer units of heredity (Back, 8)

During protein synthesis and cellular division, this genetic information is transferred via messenger ribonucleic acid (mRNA) from the nucleus of cell to the ribosomes which perform the protein synthesis. These amino acids are then transported via transfer ribonucleic acid (tRNA) to form protein chains.

Due to the extensive use of biological terms used in GA and GP some additional biological definitions are provided in the following table.

This examination of Biological Evolution and Evolutionary Computation can now be combined with the framework presented for Machine Learning to explore new avenues for creating complex digital imagery. The next section discusses some applications for creating evolutionary computer graphics.