Evolutionary Algorithms - Genetic Programming

So far we have discussed the use of evolutionary algorithms in the case where the solution could be encoded in a simple structure - a vector of some values - and all individuals had the same length of this vector. Today we will look at a few examples where the structure of the solution is more complex.

Genetic programming

Genetic programming is a technique that allows programs to be created automatically using evolutionary algorithms. Often only in the form of expressions. But it can be used (as we will see below) to design electronic circuits and similar complicated structures. There are many forms of genetic programming, depending on how the individual is encoded. We will look at a few of them. A very popular book on genetic programming is Field Guide to Genetic Programming (it is free to download).

Linear genetic programming

In linear genetic programming, an individual is written as a sequence of instructions that are then executed on some simulated computer. An example of a linear genetic program might be (from Wikipedia).

input/   # gets an input from user and saves it to register F
0/       # sets register I = 0
save/    # saves content of F into data vector D[I] (i.e. D[0] := F)
input/   # gets another input, saves to F
add/     # adds to F current data pointed to by I (i.e. F := F + D[0])
output/. # outputs result from F

The program is written in Slash/A, which uses two registers $F$ (for floats and input/output) and $I$ (for indexing into $D$) and an array of values $D$. On the language’s website you can see more complex programs written in it.

Operations on individuals in linear genetic programming are relatively simple. While not all individuals have the same length as before, it is still possible to do things like mutations that change an instruction for some other instruction, or we can cross individuals by combining parts from one program with parts from another program.

Cartesian genetic programming

In Cartesian genetic programming (Cartesian GP), an individual codes a program given on a grid $r \times l$, which has $r$ rows and $l$ layers (columns). The individual is then a vector of $r \times l$ genes, and each gene consists of two parts - the number (name) of the function it computes, and the indices to the previous layers from which it takes input. In the first layer, the indices point to an array of inputs. In addition, for each desired output an individual contains an index of the node where that output is evaluated in the individual.

In Cartesian genetic programming, typically only a mutation that changes a function, its inputs, or the output of the program is used.

Grammatical evolution

Grammatical evolution uses a formal notation of programming language syntax using a context-free grammar. An individual is then encoded as a sequence of numbers that determines which rule from the grammar should be used to rewrite the current first non-terminal. Since there can be multiple rules for each non-terminal, it does not depend directly on a particular value, but takes the rule that is computed from the value modulo the number of possibilities.

A problem in grammatical evolution is when an individual is too short and there are still some non-terminals left in the expression after processing it. Such an individual cannot then be evaluated. This is avoided by trying to generate longer individuals - so long that the individual doesn’t use some of its genes – this, however,doesn’t matter that much as when there are missing genes.

As operators, we can again use variants of the well-known $n$-point crossovers and mutations that randomly change some genes in the individual. Additionally, we can also use crossover, which picks a gene from each individual where a non-terminal starts to be processed and swaps it with a position in a second individual where the same non-terminal appears. In addition to this position, other genes that are involved in processing this non-terminal are also swapped. This crossover actually swaps entire subtrees between given individuals. The big advantage of this crossover is that it makes sense semantically, and, furthermore, if we have two valid parents, it will always produce a valid child.

Tree-based genetic programming

Tree-based genetic programming (more commonly referred to as genetic programming) represents an individual using a tree that contains functions (non-terminals) in the nodes and inputs or constants (terminals) in the leaves. The tree is then evaluated from the leaves to the root. The value of the root is then the output of the program.

Such a representation allows a variety of different reasonable genetic operators to be implemented, and it is typical for genetic programming to use a relatively large number of operators at once. Typical examples of operators are crossovers, which swap subtrees, or mutations, which change a terminal/non-terminal to some other terminal/non-terminal. Another mutation might then replace the subtree with a new, randomly generated, terminal.

In genetic programming, there is also the problem of how to create the initial population - one possibility is to generate random trees with some fixed depth (a terminal is always used at this given depth), or with a given number of non-terminals (the rest of the tree is again filled with terminals). Probably the most commonly used variant one is such that it uses the former approach for half of the population and the latter one for the rest (this approach is called ramped half-and-half).

There is also the question of how to deal with numerical constants in genetic programming. It is not quite possible to put all the numbers in the set of the terminals - there would be too many of them. Often only the basic constants (0, 1, 2, etc.) are given as terminals, and the program is assumed to compute the other values itself from them. Another option is to have special operators that change the values of the constants, similar to what is done in continuous optimization.

The basic genetic programming described above has a number of extensions. For example, programs often work with values of different types such as numbers or booleans. This is also possible in genetic programming, just by assigning the input and output types to each non-terminal. Operators must then be able to work with this. By adding types we get typed genetic programming.

Another extension is the so-called automatically defined functions, where we give the algorithm the possibility to create its own definitions of some non-terminals. It can then call these at different places in the program. Sometimes in automatically defined functions, the set of inputs, or possible non-terminals, is restricted to help the program with searching.

Evolution of classification rules

Another area where individuals with more complex encoding are used is machine learning and the evolution of classification rules. Here, individuals represent a set of rules that try to classify the given inputs. For example, if the input is a vector $n$ of numbers, then an individual can be a set of rules of the form $c_1, c_2, c_n \to k$, which means that if for every $i$ the condition $c_i$ holds for the $i$-th input then the object belongs to the class $k$. We need to somehow solve the situation where a given object satisfies all conditions for multiple rules. We can, for example, let the rules vote (i.e. assign the most frequent one as the predicted class), or we can decide according to the first rule satisfied (in such a case the order of the rules in the individual is important and we should probably have genetic operators that change it).

We have a variety of genetic operators that we can use for a given representation of an individual - again, crossover can be done relatively simply by combining rules from both parents. For mutations we can, for example, change the predicted class for a given rule, change the conditions on the left side of the rule (either for other conditions, or modify the constants in them if there are any). If the rules have different weights, we can change those as well.