1. How to translate GEP Chromosomes
2. How to evaluate the performance
3. How to read the ETs? (old executables)

Gene expression programming uses two types of representation: a linear (chromosome) and a ramified representation (expression tree - ET). For the sake of simplicity, the solutions evolved by GEP are shown in the linear representation, but these chromosomes are easily translated into ETs or conventional mathematical expressions.

Karva Notation was developed specifically for GEP (Ferreira, C., 2001. Gene Expression Programming: a New Adaptive Algorithm for Solving Problems. Complex Systems, Vol. 13, issue 2: 87-129. pdf) and consists of a universal way of representing any ET or mathematical expression.

GEP chromosomes consist of one or more Karva expressions (K-expressions), and they are very easy to interpret. For example, the gene:

0123456
+/*abcd

can be represented as a diagram or expression tree (ET):

The translation of the gene into the ET is straightforward: The first element in the gene (position 0) corresponds to the root of the ET; then, below that function, are attached as many nodes as there are arguments to that function (two in this case); then these nodes are filled with the next elements in the gene (positions 1 and 2)... The process is repeated until a line composed only of terminals is formed (the third line in this case).

More formally, the gene and ET above are expressed by the equation:

y = a/b+c*d

Usually the genes evolved by GEP are more complex than the gene presented above. Consider the following gene:

01234567890123456
Q/a*+b-cbabaccbac

where Q represents the square root function. This gene has an head of length 8 and therefore its length is 8*2+1=17. Its translation is done exactly as in the previous example, obtaining:

Note that, in this case, not all the elements in the gene were used to construct the ET, as the translation ends when a line consisting of only terminals is formed.

Furthermore, GEP chromosomes are usually multigenic, and each gene codifies for a sub-ET. The sub-ETs are posttranslationally linked by a particular function such as addition or multiplication.

For example, the three-genic chromosome below (the zero position indicates the beginning of each gene):

012345678012345678012345678
*aQ+abbaa/Q*/aababa*+Qaabba

encodes the following sub-ETs:

Depending on the linking function, the sub-ETs are linked by addition or multiplication. If the linking function were addition, then the following ET would be obtained:

- Linking Function

Note that it is easy to translate the above ET into a simple K-expression:

01234567890123456
++a*/aQQ*+/aaabba

To evaluate the performance I use the average number of fitness-functions evaluations (F_z) needed to find a correct program with a certain probability (z). The number of independent runs (R_z) required to find a correct solution by generation i with a probability of 0.99 is calculated by the formula [1]:

Rz=	log(1-z)
	---------
	log(1-Ps)

where P_s is the probability of success.

Bibliography:
1. Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press.

(This how-to refers only to the non-historical executables)
The ETs are very easy to interpret, for example, the ET:

+ / * abab

can be read exactly like a GP parse tree:

The only thing you must know is how many arguments has each function: below each function you attach as many nodes as there are arguments to that function, and then you just fill in the nodes with the symbols that appear in the ET. Mathematically, the ET above corresponds to:

a/b+a*b