Cartesian Genetic Programming (CGP)

  • Members: Julian Miller, Steve Smith, David Halliday, Andy Tyrrell, Tim Clarke, Janet Clegg, Michael Lones, James Alfred Walker, Martin Trefzer, James Hilder, Tuze Kuyucu, Gul Muhammad Khan, Katharina Voelk
  • Website: http://www.cartesiangp.co.uk
  • Start Date: October 2003

CGP Overview

CGP was originally developed by Julian Miller and Peter Thomson for the purpose of evolving digital circuits. It represents a program as a directed graph (that for feed-forward functions is acyclic). The benefit of this type of representation is that it allows the implicit re-use of nodes, as a node can be connected to the output of any previous node in the graph, thereby allowing the repeated re-use of sub-graphs. This is an advantage over tree-based GP representations where identical sub-trees have to be constructed independently. The CGP technique shares some similarities with Riccardo Poli's Parallel Distributed GP, as the techniques were independently developed at the same time. Originally, CGP used a program topology defined by a rectangular grid of nodes with a user defined number of rows and columns. However, later work by Tina Yu and Julian Miller showed that it was more effective when the number of rows is chosen to be one.

In CGP, the genotype is a fixed length representation consisting of a list of integers which encode the function and connections of each node in the directed graph. However, CGP uses a genotype-phenotype mapping that does not require all of the nodes to be connected to each other, this results in the program (phenotype) being bounded but having variable length. Thus there may be genes that are entirely inactive, having no influence on the phenotype, and hence the fitness. Such inactive genes therefore have a neutral effect on genotype fitness. This phenomenon is often referred to as neutrality. The influence of neutrality in CGP has been investigated in detail by Julian Miller, Vesselin Vassilev, and Tina Yu, and has been shown to be extremely beneficial to the efficiency of evolutionary process on a range of test problems.

CGP Extensions

The following extensions to CGP have been developed by members of the Intelligent Systems Group:

  • Embedded and Modular CGP (James Walker and Julian Miller) allows the automatic acquisition, evolution and re-use of subroutines in CGP and has been shown to improve the performance of the technique on modular problems.
  • Multi-chromosome CGP (James Walker and Julian Miller) allows the decomposition of a large multiple output problem into a series of smaller single output problems. This has the affect of reducing the complexity of the problem and making it easier to solve.
  • Real-valued CGP (Janet Clegg, James Walker and Julian Miller) incorporates ideas from real-valued Genetic Algorithms with CGP. This introduces a real-valued genotype and an extra level of neutrality into the CGP representation, and also a crossover operator which appears to be beneficial to evolution.
  • Implicit-context CGP (Steve Smith and Michael Lones) introduces implicit context representation to CGP, a concept which was first developed in our work on the enzyme genetic programming system, and which enables positional independence and improved recombination.
  • Self-modifying CGP (Julian Miller and Simon Harding) is a developmental form of CGP which allows the phenotype to change over time using a series of iterative self-modification operations.

Applications of CGP

CGP and the extensions to CGP have also been applied to a number of applications within the Intelligent Systems Group.

 

Back to the Top