Cartesian Genetic Programming

Genetic Programming (GP)

Genetic Programming is concerned with the automatic evolution (as in Darwinian evolution) of computational structures (such as mathematical equations, computer programs, digital circuits, etc.). The best known figure in this field is
John Koza.
The form of GP pioneered by John Koza used a tree representation of computer programs. This was inspired by the artificial intelligence computer language, LISP.

Cartesian Genetic Programming (CGP)

CGP is a highly efficient and flexible form of Genetic Programming that encodes a graph representation of a computer program.
It was invented by Julian Miller in 1999 and was developed from a representation of electronic circuits devised by Julian Miller and Peter Thomson developed a few years earlier.

CGP represents computational structures (mathematical equations, circuits, computer programs etc) as a string of integers. These integers, known as genes determine the functions of nodes in the graph, the connections between nodes, the connections to inputs and the locations in the graph where outputs are taken from.

Using a graph representation is very flexible as many computational structures can be represented as graphs. A good example of this is artificial neural networks (ANNs). These can be easily encoded in CGP. Recent published results of Khan and Miller and Turner and Miller(see the publications linked from this site) show that using CGP to encode and evolve ANNs (CGPANNs) is highly efficient and very competitive with other methods of evolving ANNs. Here is a ten-slide introduction to CGP.
Chapters 1 and 2 of Julian Miller's edited book are available from the link below: chapter1-and-2-CGP-book.pdf

What can CGP be used for?

Machine Learning, Neural Networks, Artificial Intelligence, Data Mining, Financial prediction, Function optimization, Classification, Electronic circuit design, medical diagnostics, evolutionary art and music,..., the list is endless.

Understanding the advantages of CGP

CGP typically finds good solutions very efficiently in few evaluations. Although it uses many generations, it also uses extremely small populations, typically 5, where one is the best one from the previous generation.

In all comparisons CGPs performance has been shown to be highly competitive with other GP methods.

CGP is extremely efficient to decode. It takes one pass though the graph to find which nodes are required. So running data through the graph is very fast as it only visits nodes are are used.
In addition, CGP genotypes tend to decode into phenotypes that are a small fraction of the genotype size. This means solutions found are naturally very small and no parsimony pressure is required.

CGP does not bloat like other forms of GP.

CGP is easy to implement and indeed has been implemented in various languages (see Resources)

CGP, unlike some other forms of GP can easily implement multiple output functions. This allows it to solve such problem as circuits problems, implement neural networks and other graph-based computational systems.

Frankly, there is no reason not to try CGP.

How to choose CGP parameters if you are a non-specialist

Choose one row and a quite large number of columns ( at least 100, but maybe 1000).

If the package you are using has levels-back, make it equal to the number of columns.

Use a 1+4 evolutionary strategy. So, population size is 5 and each generation is formed from the parent (best candidate from previous generation) and four mutated versions of the parent (offspring).

This means that only four new fitness evaluations are required in each generation. Note by checking nodes used, you can find out if any offspring have phenotypes identical to parents. If so, set their fitness to be the parents (and do not increment the evaluation counter)

Either only mutate one active gene, or stop mutating when an active gene has been mutated (single). If you want to choose a mutation rate or probability of gene mutation then choose it so that only a few genes are actually mutated to create an offspring from a parent.

Brian Goldman and Bill Punch wrote a very interesting paper of various mutation mechanisms in CGP and found single to be very good.
Analysis of Cartesian Genetic Programming's Evolutionary Mechanisms

Do not use crossover.

Choose how many fitness evaluations you want to do and let your program determine the number of generations.

Only process used nodes when decoding CGP (Most software implementations do this).

To learn more

Buy the CGP book edited by Julian Miller (cheapest at amazon).
Cartesian Genetic Programming
Download a tutorial by Julian Miller and Simon Harding - note that more recent tutorials are always available from Julian Miller' publication page (go to People tab)
GECCO 2012 Tutorial on CGP.

News highlights

Cartesian Genetic Programmng is now available in Julia

Dennis Wilson has created a github repository of his implementation of CGP in Julia. Dennis also has a paper applying CGP to playing Atari games. He will present the work at GECCO 2018 in Japan in July.

You can read about this work at the archive version of the paper. CGP finds some amazingly simple human-readable strategies for attaing very high scores on Atari games!!

Tutorial on Cartesian Genetic Programming

Julian Miller is giving a tutorial on Cartesian Genetic Programming at the PPSN conference (in September in Coimbra, Portugal)

He is also co-organizing a workshop at PPSN together with Dennis Wilson and Sylvain Cussat-Blanc on developmental ANNS. These are Artificial Neural Networks that have been created using analogues to the way biological development produces brains.

What is Julian working on?

Julian Miller is currently working on evolving CGP programs that build a brain that can solve multiple problem. One can extract multiple GOF ANNs from the brain which solve various problems. He has so far applied this to solving multiple classification problems and will present this work in at the PPSN conference (see above). He has a couple of book chapters on this subject coming out in 2019.

Machine Intelligence Ltd.

Simon Harding's company Machine Intelligence Ltd exploits the power of CGP for automatic visual defect detection, and process control and optimization. Here is a interesting video showing how software detects faults in a metallic surface.