Julian Miller, one of the creator. of Cartesian Genetic Programming (CGP) has sadly passed away. It is my privilege to pay homage to this unknown genius of our generation. So, it is worth exploring CGP and how it differs from current AI techniques.

In 2019, Julian published a detailed review of the technique referred as Cartesian genetic programming: its status and future. The paper provides a complete review of CGP and his close collaborators and other members of the community. I am quite happy Iterative CGP was covered in details, in this paper. It was an important part of my PhD thesis.

What is Genetic Programming?

Genetic Programming (GP) is a family of techniques that evolves programs. The concept of programs can be a digital circuit, some mathematical expressions, or some computer programs expressed as some low-level or high-level statements. GP was invented by John Koza, a PhD student of John Holland. John Koza let’s a computer program changing the order of operations in a program to solve a solution. His ideas was to represent suitable computer programs as the pick of a mountain, but the bogs and valley would be the programs that unsuitably find a solution to a problem. That idea is often expressed as fitness landscape.

Often the first program is randomly generated and solve the problem in an effective manner. However, other candidate programs are randomly generated. They are assessed for their effectiveness. If the latter improves, then the better performant candidate program earn the right to reproduce and its parents die. Otherwise, it dies itself. I know it is tough….

Is it like the natural evolution?

Darwinism is one evolution theory, based on natural selection and selection of the fittest. The natural environment in which individuals interact with dictates the genes the most suitable for survival. Consequently, suitable features increases the changes of compete, survive and reproduce.

The evolution of programs is similar. Each candidate program is considered an individual with some features encoded in some genes. These genes can be crossed over to produce a new individuals using the genes from two parents. Genes can be mutated to providing smaller changes. The candidate programs fitness are assessed against a set of criteria. The most criteria met, the higher quality is a candidate program; its survival probability increases too. The fitness evaluation acts as the natural environment. It is defined by the user of GP; it often evaluate the order of instructions against some solution to problem. These solutions provide a mean to numerically represent their quality. Often we minimise candidates program fitness values. So the lowest value found, the better. We are moving towards a good method of finding the solution of a problem.

The method of assessing the quality of a solution can bring bias to the candidate program. Our human bias towards suitable problem solutions to form an environment can lead to a lack of generalisation on unseen instances. Our human bias can also provide limited operations that may also limit the program search space. So, we need to keep an open mind and validate our choices against our own bias and definition of suitable solutions.

How are the programs represented?

We need some data structure to hold these programs. So, we GP often relies on tree. However, CGP relies on graphs, especially directed graphs, where acyclic graphs represent a sequence of instructions. Cyclic graphs can represent iterations and evolve them without any internal stopping criterion.

The representation below shows some inputs and outputs. A candidate program is read from right to left to define the sequence of instructions. Then each instruction is interpreted against an operator. If you are implementing such mapping, an interpreter OOP pattern becomes useful, for example.

At that stage, I can still hear Julian saying, only the active nodes are identified. The connection between the nodes are random and randomly altered. So, some nodes may not be part of path that is connected to an output. The image below shows the evolution of iterations, with the formation of cycle. However, nodes 4 and 5 are redundant. So they are inactive. They can become active again, in other candidate program.

How different is GP to other type of AI?

GP is quite different than what we consider a form of AI. The diagram below illustrates that symbolism is used to find a methods to solve a problem. We automate the design of steps to find solutions to well-defined problems. Machine learning and Bayes techniques make predictions based on a set of data. GP uses probabilistic models to simulate the natural evolution to stochastically find methods to solve problems. These are two areas of AI. However, GP can evolve neural networks and therefore can be used to improve their performance too.

Let’s conclude

I have attempted to bring some clarity how CGP and GP works. They are complex methods to solve some problems. Their users have often some good mathematical skills and understanding of stochastic methodologies. Julian would encourage anyone to have a go, learn, and improve CGP. Just try and join us.

These techniques may require some high performance computing facilities, otherwise, its users need to wait quite a long time to find some solutions. However, simple problems can be played with such as the mimicry problem and other toy problems. It helps to learn about genetic algorithms before deepening your understanding of any GP techniques.

An implementation can be found in https://github.com/patRyserWelch8/CartesianGeneticProgramming. Feel free to clone and reference to any publications.