Robust Gene Expression Programming as a Genetic Algorithm

I've posted before about the structure of Robust Gene Expression Programming (RGEP), but I wanted to go over the sense in which RGEP is a variation on the standard Genetic Algorithm (GA). Of course, it is closely related to Gene Expression Programming (GEP), Prefix Gene Expression Programming (PGEP), and Binary Gene Expression Programming (BGEP), and it takes inspiration from Genotype-Phenotype Mapping systems (GPM), but because of its simplicity it is closer to a simple GA than these other systems.

RGEP can be considered a bit vector encoded GA with point mutation, one and two point crossover, tournament selection, and a special "rotation" operator that does a left wrap around shift of its bit vector in multiples of the length of the encoding of a single symbol. Besides the rotation operator the main difference between RGEP and a GA is the expression mechanism.

Expression is very important in RGEP. It takes the bit vector and turns it into an expression tree, giving the genotype/phenotype distinction with the nice expressive structure of trees as the result and the simple and easy to manipulate structure of bit vectors as the encoding that we actually operate on with the genetic operators.

Expression takes several stages- first we group bits into fixed size chunks, the first bit of each group determines the type of symbol (operator or terminal) and the rest indexes into the list of that type of symbol. If the index is higher than the number of symbols, we wrap back around (so its an index modulus the size of the list). This new list of symbols is called the raw symbol list. Then we do a postfix evaluation of the raw symbol lists, and if any operator would cause a stack underflow we ignore it. This implicitly does a GPM-style editing of the symbol list and results in either some object whose fitness we evaluate, or builds a tree structure that we can use. Notice that we don't have to create the tree if we don't want to- it is okay to just do a postfix evaluation and create the object directly.

The nice thing about RGEP is that this is really it. Thats all! GEP is much more complex and I tried to make the most natural choice for each part so that it would be easy to code and easy to explain. The only thing missing in this post is some details about encoding. A Genetic Algorithm library should support this technique with very little work and we get to solve problems with nice tree structured solutions nearly for free if we have a good GA library!