Encoding in Robust Gene Expression Programming

I realized that I've never actually completely explained in this blog the decoding mechanism in my version on Gene Expression Programming- all my posts about it mention that I'm leaving out a bit of detail. So- here is goes.

We are given the set of terminal symbols and the set of operator symbols, which are problem specific and must be supplied by the user, as well as the number of genes per individual (the length). The individuals can then be generated as random bit vectors of size length*genesize where genesize is the minimum number of bits we can use to encode the symbols in the terminal and operator sets (plus one). We can find this by 1+log2(max(|terminals|, |operators|)). The plus one is because we need one extra bit per gene to determine if it will encode a terminal or operator.

Imagine we have a random individual. We decode first into the "raw symbol list" by splitting the bit vector into equal length chunks (the length is the result of the previous calculation) and decoding each chunk. Decoding a chunk is as follows: determine the type of the symbol by inspecting the first bit (0 for operator and 1 for terminal), and then turn the rest of the bits into a natural number in the usual binary encoding. This number is then used as the index in the set (or really, list) of symbols given by its type. In the case that the number is larger than the size of the list, we wrap around to the end, making it a circular list. In other words we take syms[n%len{syms)] if syms is the symbol list, n is the decoded value of the bits in the gene, and len gets the length of the provided list.

Having done this we have a list of symbols from the terminal and operator set, where the length is the given size of the individual. We must then turn this into an expression tree. While it is not necessary to actually build the tree, in principal we always can if we want. To do this we must do a reverse polish evaluation of the symbol list as an expression.

This evaluation starts with an empty stack, and evaluates each symbol in turn, updating the stack along the way. If a terminal is encountered then it is pushed onto the stack. If an operator is encountered, then the necessary number of arguments are popped off the stack (the arity of each operator is fixed and known ahead of time) and the result of the operator applied to the arguments is pushed as a result. If we are building a tree then the "result" is just a small tree with the root the operator and leaves the trees popped off the stack (which may be terminals or trees). In the case that the size of the stack is less than the number of required arguments the operator is simply skipped. This corrects for improperly defined trees, as there is no way for a partial tree to be constructed.

After each symbol has been evaluated the top of the stack is taken as the result, and this object (possible an expression tree) is the phenotype of the individual. This complex tree structure is much removed from the bit vector it started out as, but the process is really pretty painless. The resulting tree can be compiled or evaluated or inspected in some way to produce a fitness value for the individual.

Notice that it is possible for the stack to have many values at the end of evaluation which will be thrown out. These garbage expression may be more complex and interesting then the one chosen as the result, but it is not easy to know this in advance. It would be costly to evaluate each, and in common cases is is easy to see that the top of the stack will actually be very interesting.

Well, there it is, the full decoding process for RGEP. It might seem complex, but it is much nicer than some GEP mechanisms (IMHO) and has lots of advantages on several levels. I am not going to go into all the advantages of this encoding in this post, but suffice to say it is well motivated.

Lunch Assignment Problem

Last week someone I work with was assigned the task of setting up lunch groups for the interns in my program. This is something we do every week to meet new people, and it is intended that people eat with new and different people every week if possible. It should be clear that there may not be a solution after several weeks, but we can still find a solution with as small as possible a number of "collisions" (people eating together that have been assigned the same lunch group together in a previous week). Perhaps you can already see where I'm going with this?

This problem involves partitioning a set of people into n disjoint subsets with the minimal number of collisions. If each person is taken to be a node in an simple undirected graph then there is an edge between two people iff (if and only if) they have had lunch together before, and the edges can be weighted such that the weight is the number of times they have had lunch together. Alternatively each pair of people have a weight, which is simply 0 if they have never been in the same group. This provides a measure of the correctness of a solution, and therefore can be used as a fitness in an evolutionary algorithm!
I wrote a simple Random Mutation Hill Climber (RMHC) which we have been using the last two weeks to come up with our lunch assignments, and so far it has found perfect solutions. A RMHC simply mutates a randomly generated solution, and replaces the current solution with the mutated solution if the new one is better or equal to the previous one according to the fitness measure. The initial solution is generated by shuffling the list of people randomly and cutting the list into sublists of a fixed length. After that mutations occur by choosing two people and swapping the groups they are in.

I also tried a Genetic Algorithm for this problem, but it takes longer to run and seems to perform worse. Interestingly, next week it looks like the problem has gotten much harder in the sense that I doubt there is going to be a perfect solution. For this new instance of the problem the GA actually seems to work better! This is probably because the solution space has gotten much more complex and the RMHC, being merely a hill climber, has trouble exploring it even when run many times (so that many possible hills are climbed).

So! Evolutionary Algorithms tackling a very simple, real-life-style problem! Despite being a simple problem (simple to describe) the set of possible solutions is huge. It is infeasible to enumerate the solutions, and it doesn't seem to have an efficient deterministic solution, so it is the sort of problem that AI is often used to tackle. If anyone can classify this problem exactly I would be interested to hear about it- it doesn't remind me of anything off hand.

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!

Gene Expression Programming

Some papers on Gene Expression Programming that I found useful for my thesis (I am trying to get a paper on my variation of GEP called Robust Gene Expression Programming accepted at the Complex Adaptive Systems conference, and I will post a reference to that paper if it is accepted):

X. Li, C. Zhou, W. Xiao, and P.C. Nelson, “Prefix Gene Expression Programming”, in Late Breaking Paper at the Genetic and Evolutionary Computation Conference(GECCO- 8. References 2005), Washington, D.C., 2005.

Xin Li, Chi Zhou, Weimin Xiao, and Peter C. Nelson. "Direct Evolution of Hierarchical Solutions with Self-Emergent Substructures." In Proceedings of the 4th International Conference on Machine Learning and Applications (ICMLA'05), pp. 337-342. Dec 15-17, 2005. Los Angeles, CA, USA.

Xin Li. "Self-Emergence of Structures in Gene Expression Programming." In
AAAI/SIGART Doctoral Consortium 2005. July 9-10, 2005. Pittsburgh, Pennsylvania, USA

Xin Li, Chi Zhou, Peter C. Nelson, and Thomas M. Tirpak. "Investigation of Constant Creation Techniques in the Context of Gene Expression Programming." In Late Breaking Paper at Genetic and Evolutionary Computation Conference (GECCO-2004). June 26-30, 2004. Seattle, Washington, USA

Ferreira, C. Gene Expression Programming: a New Adaptive Algorithm for Solving Problems. Complex Systems, 13, 2 (2001)

Ferreira, C. Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence. Angra do Heroismo, Portugal, 2002.

J. G. Moreno-Torres, X. Llorfla, and D. E. Goldberg. Binary representation in gene expression programming: Towards a better scalability. Technical report, Illinois Genetic Algorithms Lab (IlliGAL) at UIUC, 2009.

Banzhaf, W., Genotype-Phenotype-Mapping and Neutral Variation – A Case Study in Genetic Programming. In Y. Davidor, H.-P. Schwefel, and R. Männer, eds., Parallel Problem Solving from Nature III, Lecture Notes in Computer Science, 866: 322-332, Springer-Verlag, 1994.

R. E. Keller and W. Banzhaf, “Genetic Programming Using Genotype-phenotype Mapping from Linear Genomes into Linear Phenotypes”, in J. R. Koza, D. E., Goldberg, D. B. Fogel, J. R. Koza, W. Banzhaf, K. Chellapilla, M. Dorigo, D. B.Fogel, and R. L. Riolo, eds., Genetic Programming 1996

My favorite of these is the Prefix Gene Expression Programming paper- PGEP is (imho) a much cleaner and easy to use system then the original GEP and I think that it should be used for the basis of future extensions to GEP (I definitely based RGEP on PGEP (and on BGEP) not GEP).

Notice the papers on Genotype-Phenotype Mapping Systems- they are the basis of GEP, Grammatical evolution, Binary Genetic Programming, Developmental Genetic Programming, Cartesian Genetic Programming, and probably many other systems.

Learning Genetic Algorithms, encodings

We have got all the basics of GAs down so far. We have an encoding (a representation of solutions- often as bit vectors) a mutation a crossover and a selection. Often this is enough, but if we want to use this technique for a particular problem we have to determine how to encode solutions to the problem as a linear structure. There are a series of problems that may arise here, the main one being that the easiest encoding may be too "loose" in the sense that it may be able to express invalid individuals.

A common example is in the traveling salesman problem (TSP) where we want a tour of a set of cities such that we visit each city once and only once. If this is represented as a list of cities then it is hard to enforce the constraints. Even starting out with only valid tours a single point mutation will almost certainly result in a tour that visits a city twice and one city zero times.

So what do we do about it? We have talked about editing as a way to ensure each individual is valid, and for the case of expression trees I believe that editing (it done simply and easily as in RGEP) is a very nice choice.

Other possibilities include modifying the fitness function such that invalid individuals take a fitness hit often proportional to some measure of how invalid they are. This may work in some cases, but in other there is no meaning for invalid individuals and we would have to turn them into valid ones (which is basically editing). Another possibility is to modify the operators to create problem specific mutations and crossovers (or sometimes adding different operators or removing ones that don't seem to work- often crossover is the casualty here). For the traveling salesman example we could replace point mutation by an inversion operator that inverts the path between two indices. We could also add a swap operator that just swaps the cities in two indices. Crossover is a bit difficult to modify here, but it has been done in several ways. This turns a general GA into a problem specific algorithm that may perform very well for some small (but possibly interesting) set of problems.

Another possibility is to come up with some clever encoding that cannot even express invalid individuals. This is very difficult in general as we are (very) often concerned with a subset of some obvious set of solutions like the valid tours in the set of all paths for the TSP. An example of such an encoding would be a (even length) list of numbers where each pair of number in the list (the first and the second, the third and the fourth, etc) are a swap of some fixed ordering of the cities. This cannot express an invalid individual as all swaps preserve validity and we can use the regular genetic operators we know so well. The only problem is that a level of indirection can have consequences that are hard to predict and reason about. For example a small change from point mutation on this list may have a large change on the resulting tour, so point mutation is more disruptive then we might expect it to be.

Another problem with encoding is that it may not be obvious that the problem can even be expressed as a vector of symbols. In Gene Expression Programming (GEP) and Linear Genetic Programming the linear representation allows us to do a GA style algorithm (especially with Robust Gene Expression Programming) on a tree structure, but there algorithm also specialize their operators to work with the resulting expressions. For other problems we may have to be very indirect or clever just to create an appropriate encoding, and we may have to simplify the problem or exclude certain possibilities. If we are laying out a factory, how do we determine where each component goes without duplicates (which may or may not be allowed)? If solving sudoku, maybe the linear encoding of reading the board off row by row is not the best because there is a lack of locality (squares nearby in the game board are not necessarily nearby in the representation) which makes crossover less helpful and more disruptive. Perhaps we need an inversion operator that only inverts with respective to crossover but not with respect to expression into a sudoku board (an interesting possibility usually done with a type of inversion operator which evolves the encoding along with the solutions).

So, we have seen some possible difficulties with encodings in a Genetic Algorithm. I would like to post some about my musing about the natural of GAs and evolutionary algorithms in general, as I have an interest in generalizing and making them more rigorous.

Algebraic Signatures and GEP

I've been thinking about what structure describes the expressions evolved by evolutionary algorithms like GP and GEP for a while, and it looks like algebraic signatures fit the requirements very well. Certainly we can describe a grammar and say we are evolving words in the language generated by the grammar, but that isn't really satisfying (to me). In this post I'm going to go over them again (I describe them in a previous post as well) and show that they are a very natural structure to describe the expressions evolved by genetic programs.

So, what is a signature? A signature consists of a set of types (possibly generated by a grammar) as well as a collection of function symbols and relation symbols. The function and relation symbols each have an arity (the number of arguments they take (although for now we are thinking of this as a purely syntactic system)) as well as an ordering, which says which arguments are of what type. If the arity for a function symbol is 0 than it is a constant, which allows us to specify elements of a type (a constant that has a type is an element of that type).

A signature together with a set of axioms gives a theory. This allows us to describe some theory in math (the theory of Groups, the theory of Monoids, the theory of Categories, etc) as a mathematical object. The models of the theory (the mathematical objects that embody the elements and rules of the theory) are the actual groups, monoid, categories, etc.

If a signature has only relation symbol it will give a relational theory, and if it has only functional symbols it will give an algebraic theory, which is what we are concerned with in this post. If the terms generated from the types and the function symbols can have abstractions then the theory is functional (in the terminology used in "Categories for Types").

If we take an algebraic theory with one type than the terms consist of fixed arity functional taking all arguments of one type and returning something of the same type. This fulfill the closure property for GEP (all function involve only one type). If the axioms are also provided we might be able to automate the evaluation of the expressions by reductions given by the axioms. This would mean that using GEP (or more specifically RGEP) would involve specifying the theory that we are interested in, and perhaps an interpretation of the theory in order to map the resulting expression to an object (which we can then determine the fitness of).

More generally, in Genetic Programming we may have multiple types and more complex functions, but it seems like algebraic theories will cover them. I would love if this allowed a more systematic treatment of what goes on with Genetic Programming, as I find that AI can be a little ad hoc at times compared to my other interests in category theory, type theory, and functional programming.

Learning Genetic Algorithms, Robust Gene Expression Programming

My thesis is on a new form of Gene Expression Programming that I've named Robust Gene Expression Programming (RGEP). It is designed to be simpler and more robust than its closest relatives, without losing generality or performance. In this post I'm just going to describe each part of RGEP without a complete explanation.

RGEP consists of the following stages: a single initialization step, followed by n generations consisting of gene expression, evaluation, selection, point mutation, rotation, one point crossover, and two point crossover.

The population consists of bit vectors of some fixed length. Initializing them is easy- they are completely random. All individuals are valid, so there is no need to do any checking while creating individuals.

Gene expression consists of splitting the bit vectors (which are symbol lists where the symbols can only be 1 or 0) into fixed size groups called codons. Each codon is expressed into a symbol, forming the raw symbol lists. This can then be edited/expressed into a tree using the postfix notation from the last post. The resulting tree can then have its fitness determined.

Selection is a simple tournament selection with 2 individuals per tournament and elitism.

Point mutation is just like in a GA.

Rotation rotates an individual just like a wrap around shift in a register. The rotation point must be a multiple of the codon size so that the rotation occur on codons, not bits. This prevents rotation from being terribly disruptive.

One point crossover is just like in a GA, and two point crossover is just like one point crossover except we chose two random points and exchange with respect to both.

So- that was a very short description missing details on the decoding process. I may go into much more detail on this in later posts, as well as other topics in GAs and Evolutionary Algorithms.

Learning Genetic Algorithms, editing

Editing of a symbol list takes valid individuals (individuals whose genetic material encodes a tree) to themselves, so it makes no changes, and invalid individuals to an individual that encodes a tree, hopefully the "closest" such individual. We can add extra symbols, delete symbols, or change symbols, or any combination of those three. In Binary Genetic Programming, the original Genotype Phenotype Mapping system, the editing stage was very complex. In the systems that followed that line of research the editing only got more complex as they were intended to investigate the idea of developing an individual using the genetic material as a template. The editing that I will explain is must easier and is novel in the field (not that it is all that clever, but it works well). The downside is that it only works on the more algebraic expressions that GEP evolves rather then the more general ones in other Genotype Phenotype Mapping systems. On the other hand, its very nice compared to other techniques in the GEP literature, and it suggests a really cool addition to GEP systems that I hope to get into at some point involving stack operators.

Okay, so lets get to editing! Starting with the expression +1-2*3 lets see if we can create an expression that is pretty close but valid. The tree it expresses to is:

            +
           / \
          1   -
             / \
            2   *
               / \
              3   _

Where the _ symbol is an argument that is missing for *. Notice how we filled out the tree btw, depth first. This is prefix notation. A very close valid individual would be:

            +
           / \
          1   -
             / \
            2   3

We could do this by "floating" the 3 up to the -, but it is easier to do this if we don't actually create the tree. So! Postfix notation!

Starting with an empty stack, written [], and the expression +1-2*3, lets evaluate the expression in the usual postfix way. First lets reverse the expression, 3*2-1+, and evaluate the expression symbol by symbol. Any terminal is simply pushing onto the stack, so first 3 is pushed- the expression is *2-1+ and the stack is [3]. The * will try to pop enough arguments off the stack (2) and multiply them, pushing the result on the stack. If the stack had been [3, 2] and the next symbol * the stack would become [6] or [(2*3)] assuming the top of the stack is the rightmost item in the list. Since there is not enough arguments on the stack when the stack was [3] the * is ignored. Then the expression is 2-1+ and the stack is [3]. Then we get -1+ [3, 2], then 1+ and [(2-3)] or [-1] then + and [-1, 1] then an empty expression and the stack [0].

Notice that the only thing that differs from this evaluation and the prefix one is that the * is ignored, which was the goal we set out to perform. This mechanism will always remove operators that do not have enough arguments, and it will make very few operators and make no other changes to the expression. It can also be done while evaluating the individual, so we don't even need to create the expression tree at all. This is very cool.

One of the nicest things about this notation and editing is that the subexpression in the tree (the tree starting from any node and taking all of that nodes children and childrens children, etc) are close to each other in the symbol lists. This means that symbols close to each other in the genetic material are close in the expression tree, and symbols that are part of a subexpression are never distanced by symbols of a different subtree. This is not the case in the original notation, Karva notation, which fills out its trees breadth first. The postfix notation allows us to gain this locality property as well as remove operators that will be a problem in the expression tree. This could be called postfix evaluation ignoring operators that cause a stack underflow.

We have gotten to material that is introduced in my thesis in this post. Perhaps I will post about the other parts of RGEP, and maybe about the algorithm as a whole. The editing stage is the only really novel thing besides some details of the binary encoding and the meaning of the genetic operators. Everything else in RGEP from the literature on Genetic Algorithms, Genetic Programming, Genotype Phenotype Mapping Systems, and Gene Expression Programming.

Learning Genetic Algorithms, Gene Expression Programming

So, this series of posts is pretty poorly named. I should have titled it Learning Evolutionary Algorithms, as I'm about to get into Gene Expression Programming (GEP), which is a couple of steps removed from Genetic Algorithms in terms of subfields. In another sense GEP is closer to a GA then Genetic Programming as it uses a linear encoding (symbol lists again).

The original GEP is very complex, and I will not go over the whole thing. Instead I just want to introduce some ideas and operators, and show how they fit together. I think that Prefix Gene Expression Programming is a much nicer algorithm then the original, so that is the one I will describe in the most detail.

Remember expression trees from last post? Instead of evolving trees directly, in GEP (and Genotype-Phenotype Mapping systems in general) we evolve symbol lists which contain the terminal and the operators. This can be exactly like a GA, but often has extra genetic operators beyond Point Mutation and One Point Crossover. It is a distinguishing factor of GEP that it has many different operators, while some of its cousins have only Point Mutation. When we want to measure the fitness of an individual we have to turn it into a tree and determine the fitness of the tree.

I want to make a quick point about fitness before talking about this translation between the list of symbols (the genotype) and the tree (the phenotype). Fitness can be determined in any way that is appropriate for the problem, but a good way of measuring it for many problems is this: we have a list input/output pairs, and the fitness of a function (assuming the individual encodes a function or can be described by one) called f is the sum of the error the function makes on the output given the input it is paired with. For example if an individual's tree encodes the function f(x) = x*2 + 1 then if we had some data [(1, 2), (4, 2), (10, 3)] (a list of pairs, the first the input, the second the expected output of an ideal function) we would get |f(1)-2| +
|f(4)-2| + |f(10)-3| which is the sum of the differences between each input and output. I'm using |expr| as the absolute value of the expr between the pipes "|". If we get 0 as the fitness then the individual's encoded function, f, made no errors and was a perfect solution. While we may not have such a simple interpretation of the individual as a function from x to y, so we just have (x, y) pairs, it will very often be some pairing of inputs of some form to outputs of some form and a way of determining how well an individual's outputs match the ideal outputs.

So, decoding a symbol list into an expression tree. We can choose any notation we want- infix, prefix, postfix, or anything else. This can be very complex in general, we could be evolving expressions in a programming language for example, but I am mostly interested in this more restricted case where we are interested in expressions combining terminals with operators (its very algebraic, which I might post about sometime). For this purpose the choices of in/pre/postfix notation are the well known ones. The other option is Karva notation, which is not very nice (IMHO).

If we want our individuals to be symbol lists in some notation, we would like that they always can be turned into a tree. This is not a problem for an expression like +1-23 which is 1+(2-3) in infix notation, but what about +1-2*? This expression does not encode a tree as the operator * does not have two arguments (it has 0 arguments). We can do many things in this case, but the two options I want to look at are: we can forbid such messy individuals, or we can allow them and, when we want them to flower into trees (we get very attached to our individuals sometimes and want them to succeed even if they are not valid expressions), we can make changes to the genetic material in order to make a tree without changing the actual individual. Imagine that we made a copy of the individual, edited it to make it valid, and then turned it into a tree to determine its fitness.

The first option is taken by Prefix Gene Expression Programming, as well as the original GEP. In the original algorithm the symbol lists had two parts- operators could only appear in the beginning of the individual and so they would always have enough terminals after them to have a valid tree. In PGEP genetic operators that caused invalid individuals, like a point mutation from +1*32 to +1*/2, are undone when they happen. This means that the operators must know what a valid individual looks like to make sure they don't cause any problems.

The other possibility is what is common in other Genotype-Phenotype Mapping systems, which are any system where the linear list of symbols becomes a more complex object before evaluating its fitness (a tree, graph, whatever). It is called editing, and the original such systems had some complex editing as they wanted to evolve programs in programming language like C.

In the next post I will go over the symbol list idea more, the editing stage that I used in my thesis, and the expression of the linear encoding into an expression tree.

Learning Genetic Algorithms, Genetic Programming

The symbol lists of Genetic Algorithms are lots of fun. We can encode all sorts of things if we are clever enough. It is generally considered a good idea to use the most natural structure to encode a problem, if possible. If we are optimizing the parameters to a real-valued function then we should try to use a real-valued encoding (a vector of doubles, for example). But what if the problem has some more complex structure?

There are some very interesting problems that are most easily described by trees structures. Just so we are on the same page here I will describe the concept of a tree (a binary tree aka 2-ary tree for simplicity). A tree is either empty, or it is a node with 2 subtrees, called its children.
Here is an awesome ascii-art tree with the nodes as * and the \ and / connecting each node to its children.

            *
           / \
          *   *
         / \
        *   *
            /
            *

In general these trees may have anything labeling their nodes, not just * symbols. If the internal nodes (the ones with children) are functions like +, -, *, or / and the leaves (the nodes with no children) we may have something interesting. A function like f(x) = x*2 + 1 would look like:

           +
          / \ 
         *   1
        / \
       x   2

This can be written in the infix notation as x*2 + 1, in prefix notation as +*x21, and in postfix notation as 12x*+, all of which completely and unambiguously define the tree above (assuming we know the number of arguments each operator symbol (+ and *) requires).

If we want to evolve functions like this, or many other things (programs can be described this way using formal grammars and abstract syntax trees), we may want to evolve them directly. This means creating random trees, making sure each function has enough arguments and each leaf has a terminal (a constant or variable or something with no arguments to fill).

A technique called Genetic Programming does exactly this. This gives it a great deal of expressiveness- trees are complex, interesting, and general things. An example of how cool this is- imagine a robot that knows some things about its current situation (location, facing, direction of something good or bad, speed, etc) and needs some controlling program. We can use an expression tree with many variables, not just "x" as in our example, and functions that act on the variables. It may be tricky to get this function to really do anything interesting, but it is not all that hard. The cool thing would be that we can evolve functions for controlling robots like this.

Another cool possibility is to evolve a function to fit some set of data. We can then use the function to describe the data- it tells us something about the data we might not know and it can be used to extrapolate and interpolate. The fitness for a tree is the sum of the error it makes on each data point when used as a function.

Just like a GA, we generate random structures to start the algorithm out. Then we must do something like mutation and crossover. Unfortunately trees are more complex than vectors, and the biological metaphor stops making much sense. This is one problem with the more complex trees structures, and we will see in a later post how the algorithms I am most interested in deal with this by using a symbol vector to encode a tree. Mutation here means choosing a random node and replacing it with a randomly generated tree, which deletes the node and any of its children. Crossover of two trees means choosing random nodes (one in each tree) and replacing them with each other (swapping the subtrees underneath them as well).

This is all well and good (actually its pretty great- GP is really good at a lot of things), but there are some problems beyond the complexity of the operators (there are normally more restrictions that are added then what I described). One interesting problem is called bloat- the trees will tend to grow uncontrollably with no associated increase in their fitness. The interesting thing is that not only is this possible, but if the tree is able to do this it will be in its best interest to do so, and so it will start to grow uncontrollably.

An advantage of the more complex structure is we can enforce all sorts of extra constraints to encode more interesting problems. We can add operators with different types or use recursions or iteration or some memory space or lots of things.

All I wanted to do in this post is get a little bit into GP and show how trees can be evolved. Mostly this is just buildup to Gene Expression Programming, but it is important to understand trees and how they might be useful.

Purely Functional Genetic Algorithms

In this post I want to go over an idea I had about a month ago about the representation of a population in a Genetic Algorithm (or really any evolutionary algorithm) where the population is represented by a function. I got this idea from a library called pan which represents images as functions from a coordinate to a color (although it is really more general than just that). A population of a Genetic Algorithm can be considered a function from a pair of integers (the first integer specifies which individual and the second the location in that individual) to a bit (assuming for simplicity that we are concerned with bit vectors). Alternatively, we could represent the population as a function that, given an integer specifying the individual, returns a function that defines that individual and which, given an integer, returns its value at that location.

Each of the genetic operators has to be reinterpreted using this representation. We can't change the population directly, as it has no mutable structure (real functions have no internal state), but we can wrap it up in other functions that enact changes. Let go through the three main operators- mutation, crossover, and selection.

Mutation requires that some small number of bits are flipped. These bits can be represented by a set of integer pairs specifying not the bits values, but rather their location. There value is not important in the representation. If we make such a set of random pairs, we can create a function that takes as an argument a function representing a population, and returns a function representing the new population. This new function will use the old function to get the value of a particular location, but if the coordinate requested is also in the set of mutated coordinates then it will flip the result before returning it. This means that we use the old population's values, but wrap the function up in case we need to change its specific locations.

Crossover can be represented by a list of triples. The first two numbers are the crossed pair, and the third in the triple is the cut point between the two individuals. Of course, some individuals will not be crossed at all, and their cut points will be 0. Again, the actual genetic material of the individuals does not matter, only the place that the cut point occurs. This list of triples can be used to wrap up the function representing the population, such that to get a particular coordinate one has to check the respective triple and cut point, and get the value from the previous population. If the requested value is before the cut, we get it from the first individual, and if it is after the cut point then we get it from the second individual.

Selection is particularly easy to represent. Each selected individual- regardless of the selection mechanism- gets its index recorded in a list as long as the population. This list is like a switch board- when an index is requested, the index from the previous population is returned based on the value in this list. So to get the first individual in the new population, we return the individual in the previous population whose index is recorded in the first position of this list. If we don't want to make the choose of the actual individual, as we will see at the end of the post, we can just use tournament selection and record the tournaments, deciding the winners when we have the individuals. Something similar is possible with roulette wheel where we record value from 0 to 1 and use them as the spins for the wheel.

With all the genetic operators represented this way, we simply have to create a population function and wrap it up in higher order functions again and again to perform a run of the algorithm. This turns out not be be terribly fast in my trials, as after a couple of operators there are a large number of bit flips, checks, and indirections necessary to get the value of a location. I've tried several things to make it faster, but at least the naive implementation does not appear to scale well. It is still an interesting idea, however. If the population where somehow very sparse it might even save space, as you only have to record changes, not all the actual bits. In fact, if the population started out completely uniform- for example all bits are set to 0- such as before the initialization step, then the population could be represented by a very concise function- the constantly 0 function. This requires a fixed constant amount of memory, which might be a huge win in some cases.

Unfortunately I have not been able to get this idea to be any better then the usual way of doing a GA. The only thing that it has lead to is an idea about investigating the effect of the initial population on the resulting population. If all the generations where generated as I've described (and not necessarily stored wrapped up in a function, but rather just as the data structures) then a run could be performed many times. If we generate some population, and then run the same GA many times with the same mutations, crossovers, and selections, then we could flip each bit one at a time and see how it effects the resulting population. This would tell us if some bits where more important then others. The coolest thing would be a "heat map" were each bit in the original population is replaced with a color based on how many bits in the final population it effected. This would be really cool to look at, if nothing else.

Learning Genetic Algorithms, the max problem

One of the nicest things about Genetic Algorithms is how general they are- notice that the operators we looked at in the last post did not make any reference to the problem they where involved with solving (except fitness evaluation, but that can easily be replaced with whatever we want). The main thing we have to think about when solving a new problem with a GA is how to encode solutions to the problem.

One problem we might want to use a GA to solve is the "best" series of choices. For example, we may have many compiler flags, purchase choices, forks in the road, or any other type of yes/no decision to make. We can certainly do more then just yes and no, but for simplicity lets consider the situation where we must make 6 choices. To make it even simpler, it will turn out in our example that to get the best answer, we should always choose yes. The maximum fitness is 6 and the perfect individual will get this fitness by choosing "yes" for each choice.

So how do we write down random symbols that encode a series of 6 choices? Like so- 001010, 111000, 101010, 001011. This will be our population- each individual will chose "yes" for the indices that it has a 1 in, and "no" in the indices that it has a 0 in. Since we want the individuals to always choose yes, the fitness function will just count the number of 1s in the individual.

Remember the first step is determining fitness- f(001010)=2, f(111000)=3, f(101010)=3, f(001011)=3. Now lets let selection choose a new population- 111000, 111000, 111000, 001011. The way this is actually done is by creating something like a pie chart, where each individual gets a slice proportional to how high its fitness is. A little spinner is spun 4 times, in this case, and the individual that it lands on gets copied into our new population. This is called Roulette Wheel selection.

I want to mention that there are other selection methods. One, called Tournament Selection, just holds a series of tournaments to determine who gets copied into the new population. Each tournament consists of a random selection of individuals from the population (normally 2) and the competition is just selecting the individual with the higher fitness most of the time, and randomly choosing a less fit individual as the winner some of the time (normally 75% of the time the better individual wins). An individual might participate in many tournaments, or it might not be chosen for any tournaments at all.

Now lets do some mutation- 111000, 111000, 111000, 001011 becomes 111000, 111000, 111100, 001011.

And Crossover, pairing individuals up randomly- (111000, 111100), (111000, 001011). Lets say both pairs are chosen for crossover, as the rate of crossover is normally set pretty high (70% or so). The first pair gets the space between the third and fourth index as the cut point, and the second the space between the fifth and sixth. (111|000, 111|100), (11100|0, 00101|1), where the "|" is the cut point, becomes 111100, 111000, 111001, 001010.

We are going to go for more than one generation in this example, so lets start from the beginning- f(111100)=4, f(111000)=3, f(111001)=4, f(001010)=2. Notice that not all that much progress has been made and we certainly don't have a perfect solution (which would be 111111). Well, lets keep going- selection gets us 111001, 111001, 111001, 111001. It looks like one individual has taken over the population- we say the population has converged.

This population has no diversity, which is a very bad thing. Diversity is vital in a GA to get good solutions and partial solutions to create good results. Now we have to let mutation randomly mutate the 4th and 5th digits from 0s to 1s in order to discover the best individual. This is one of the contributions of mutation to a GA- it will introduce new genetic material into a population that no longer has the diversity to find good solutions through crossover.

I won't go through the details of the rest of the run- imagine that mutation takes several more generations to mutation those last couple of indices to 1s, and we find that the resulting population is all individuals that look like 111111. Maybe a 011111 is thrown in there too- mutation can decrease fitness just as easily as increase it.

This problem- finding an individuals of all ones- is called the MAX problem for GAs. There are many standard problems for different techniques that try to isolate properties of the problem solver (GA in this case) so that variations of the basic methods can show is they do better than others in the aspects that these problems try to showcase.

I sneakily introduced the "yes or no" encoding as 1s and 0s to introduce the most common encoding for individuals in a GA- a binary string aka bit vector aka {0, 1}* aka base two numeral.

I think next time we will move on to Genetic Programming on our long road to RGEP. Good times ahead!

Learning Genetic Algorithms, cont

In this post I will introduce the biological metaphor of Genetic Algorithms, and try to develop a simple example problem. We will see how to encode solutions for this example problem and motivate the parts of a GA.

The sample problem will be trying to find a value, x, for the function f(x) = x^2- the function that takes a single input number, lets say a positive whole number, and returns its square. We want to know what input number between 0 and 1000 (exclusive, so 0-999 inclusive) will get us the highest number as a result. The solution space is the numbers from 0 to 999. It will be convenient to write all numbers with 3 digits, so 0 is written as 000 and 23 as 023, etc.

The answer is obviously 999. If this partially random search of the solution space is to be "intelligent" it should arrive at the same conclusion that we have come to.

Now that we have a problem to solve (the max output of f(x)=x^2), a solution space (the numbers 0-999), and a way of writing down possible solutions as a list of symbols (000-999, which is all possible three symbol words using the numbers 0-9), we are ready for the biological metaphor. The story is that the list of symbols is sort of like the genetic material for an organism. The number that it corresponds could be considered its phenotype- so 023 is the genetic material that gives rise to the number 23 as the phenotype. The fitness of the individual is the result of putting its phenotype (its "body") into the fitness function (here its our squaring function). The result of squaring its phenotype tells us how well it solved our problem because we are looking for the highest output of the function f.

This is a nice little relation between the components of the problem and the situation in nature, but there are still parts missing. In nature we may expect there to be many individuals- in a GA we have many lists of symbols, not just one. Also we expect that fitness isn't just a number- fitness should affect the survival of the individual. It is not enough for fitness to affect survival, as there must also be some sort of variation between generations (which implies some way of creating children). This situation gives us the inspiration for the rest of the system.

Lets outline the situation using these new facts- there is a population of lists of symbols which will be random, our example population will be 900, 002, 299, and 432; there is some selection of good solutions that kills off some bad solutions, there is some random variation corresponding to mutation in natural genetics, and there is some mechanism for creating child, a crossover similar to crossover in natural genetics. We hope that good solutions will be copied many times during selection, that mutation will improve solutions and not make them worse, and the crossover will take two goodish solutions and create really good ones by combining the parts of the solutions that made them good into an individual with the traits to be great.

Starting with the population of randomly generated individuals 900, 002, 219, and 432 we should turn them into their phenotype-900 becomes 900, 002 becomes 2, 219 becomes 219, and 432 becomes 432. Now we can put them into our fitness function so f(900)=81000, f(2)=4, f(219)=47961, f(432)=186624. Clearly 900 is a good (but not perfect solution), and 432 is pretty good too. Now lets select some of the good ones, allowing them to be selected many times so the new population may have several individuals that look exactly the same. I won't go into example how to do this in this post, but lets say we end up selecting a new population from the old (think of the individuals as reproducing) and we get 900, 900, 219, and 432. The 219 wasn't as good as 900 or 432, but the "best" individual doesn't always live in nature and the "worst" doesn't always fail to reproduce.

Now lets do some mutation. This means that we take our new population (900, 900, 219, 432) and just randomly change some digits to random numbers. After mutation the population may look like this: (900, 900, 299, 132) which changed exactly two digits in different numbers. It looks like the 432 that got mutated into 132 got much worse, but that happens sometimes. The 219 that was mutated into 299 certainly got better, which is nice.

We are almost to the end of the first generation! Now we just to crossover. This means that we pair up each individual, and sometimes the "happy couple" crosses their genetic material, and sometimes (again, randomly) they don't. Lets say they are paired like this: (900, 299) and (132, 900). Lets assume only the first pair (900, 299) chose, or was chosen, to be crossed. Now we must chose a (random) place in the genetic material to do the cross, so lets chose between the first and second digit. This splits the individuals into the pieces (9, 00) and (2, 99). We take the first part of the first individual (9) and the second part of the second individual (99) and put them together getting 999, and the first part of the second individual (2) and the second part of the first individual (00) which combine to 200. The new population is 999, 200, 132, and 900.

This might have all seemed pretty random and not very intelligent at all- the only thing that wasn't *completely* random was selection. Mutation and crossover could create terrible mutants that perform nowhere near as well as the originals just as it could possibly create good solutions. So why did we do this at all? Well, for one thing, in practice we would repeat the selection, mutation, and crossover many times on a much larger population so there would certainly be some chance or getting a perfect solution.

The other thing to notice is the first individual in the new population- its the perfect solution 999! It looks like we started with a small random population that didn't contain a perfect individual and randomly ended up with the correct solution! Its almost as if I had this in mind from the very beginning!

The most vital thing to notice here- really the point of this whole post- is that the original population didn't contain a perfect individual, and none of selection, mutation, or crossover by itself created the perfect solution. Selection ensured that the individual 900, which is a pretty good solution, appeared in the population more than once. Mutation introduced a pattern that was not in the original population (the 99 in 299, which we would write as #99 with # as a "don't care" symbol, which says that we are interested in the last two digits being 9s, and we don't care what the first digit is in this pattern). Crossover took two patterns that helped the fitness of the individuals they were in (#99 and 9## are the patterns that combined) and this produced the individual 999, which has both useful patterns.

This is the basic Genetic Algorithm. The three operations performed many times is the canonical example of an Evolutionary Algorithm and is considered the primal form of Genetic Algorithms. The problems can be much more complicated and useful, the genetic material can have many different symbols and different digits may be constrained to different values. The genetic material may be many numbers, like 934202 could be two inputs to a function f(x, y) = x*y where x=932 and y=202 in the example individual.

Hopefully Genetic Algorithms aren't so mysterious now, and we can move on to more interesting material. The basic Genetic Algorithm is surprisingly similar to my own work- Robust Gene Expression Programming- but we will have to introduce many new concepts to get there from here.

Learning Genetic Algorithms

I plan on posting more about the lambda calculus, perhaps showing its connection to the always amazing functional programming paradigm. For now, though, I want to also start a series on my other favorite topic in computer science- Genetic Algorithms and the related methods Genetic Programming and Gene Expression Programming (which is the subject of my thesis).

To understand Genetic Algorithms we need a little bit of background. One important part of the field of Artificial Intelligence is methods for solving certain types of very difficult problems. It is not that these problems are difficult to describe, or even that we don't know what good solutions look like, but rather that there are so many possible solutions it is difficult to find the best solution (or even a pretty good solution).

This doesn't at first seem like its related to intelligence at all. The connection is that while tradition methods rely on complex math, AI techniques for problem solving rely on partially random but directed searches through the solution space. A solution space is the "space" or the set of possible solutions. In the case of a function of two variables, for example, it would really look like a space as it could be visualized as a landscape with hills where there are good solutions and valleys of poor solutions (or the reverse, it depends on if we are looking for the smallest or largest value of the function). The way the search is directed makes it seem intelligent in a way- it should be designed to spend more time looking at solutions similar to ones that its seen that are good while still searching as much of the solution space as possible.

These methods will often try to mimic a natural phenomenon that appear intelligent. This can be the swarming behavior of insects, the neurons of the brain, or, in our case, the force of natural selection. The important thing isn't actually to study intelligence (obviously selection is not really intelligent) but rather to study selection as a guiding force that produces complex structures that are adapted to their environment. We will start out much simpler than this at first, though.

The simplest method of this type would be to construct a random solution and see if it is any good. We could generate many random solutions and just remember which was the best. For example, imagine we wanted to find the input value for some function, f(x), for which it returns the largest result, and we are interested in values only between 0 and 10. We may know what the function f looks like, but we might not- it might be a "black box" that we put values into and get values out. If we generated 100 random numbers between 0 and 10, perhaps one would be very good, perhaps not. Maybe one time we try and we get a very good result and the next time we get a much worse. There is no guarantees and no consistency, but on the other hand this is a very simple method.

A slightly better approach is this- generate a random number as before, but then try to increase it by a little bit and see if that gets a better result. Then try to decrease it a little bit, and see if that is better than increasing. If we keep trying to increase or decrease, and we move which point we are at depending on which direction (increasing or deceasing) is better, than we will often get better values than if we just generated number randomly. The problem, however, is that we are just climbing to the closest good point- if it would be good to go down a little bit in value to find a place were the result is better than the current than this method will not be able to solve the problem. This method is called hill climbing as it is like climbing the nearest hill in the solution space (the closest maximum value).

There are many problems that have the right characteristics for this type of search- as long as the solutions can be written down in some nice form (like as a number, a list of numbers, a list of symbols, etc), we can measure how well a solution solves the problem, and there are many possible solutions (to many to try them all). Often solutions that are similar in their representation (in terms of numbers, solutions that are close to each other on the number line) perform similarly as solutions to the problem. Unfortunately this can mean that there are many groups of good solutions and it is hard to find the best solutions among them. In general it is difficult to know anything at all about the solution space. What we want is a method for search any type of solution space that does not make any assumptions about how the solutions are spaced, or anything else about the problem.

In the next post we will look at encoding solutions as lists and introduce the biological metaphor that guides the field of Genetic Algorithms.

Binary Decision Trees

I posted before about decision tree induction in GEP. Unfortunately there is not much data to compare GEP's ability to do DTs as the original author made some changes to GEP to do her experiments that I don't want to do to RGEP. Instead I'm trying to replicate results from a GA called GATree, which is pretty much a Genetic Programming technique, where the authors create Binary Decision Trees.
Binary Decision Trees (BDTs) are like normal decision trees in that each internal node is a decision and each leaf is one of the possible classes for the decision variable. The difference is that the internal nodes always have two children (hence the name). Rather than choosing the sub-child corresponding to the value of the attribute associated with the node, the node is associated with a single possible value for a single attribute. These values can be names or ranges. The left sub-child is taken if the current piece of data being decided on has the given value for the given attribute and the right sub-child is taken if not.
It is very easy to model this situation in Haskell. Here is the algebraic data type for the trees:
data BDT a = Leaf a | Node a (BDT a) (BDT a) deriving (Show, Eq, Functor, Foldable, Traversable)

and the evaluator:

evaltree _ (Leaf a) = a
evaltree attrs (Node a l r) = evaltree attrs $ if a `elem` attrs then l else r

Where attrs is a list of values of type a. The result is a value of type a that the tree has giving as the class of the list of as. Notice that all nodes and leafs hold the name type- since we are doing only nominal attributes even ranges of integers can be described by a string, which is what I'm actually using.
You have to use the following pragma to get all those beautiful derives:
{-# LANGUAGE DeriveTraversable, DeriveFoldable, DeriveFunctor #-}

The last important bit here is the ability to get the number of training cases correctly classified:

evalcases tree = sum . map (\(cas, expected) -> fromEnum $ evaltree cas tree == expected)

In case this is confusing, notice that it is in point free style- it evaluates to a function that expects a list of training cases which are pairs of attribute lists and their correct class. The fromEnum just turns a boolean value into an Int.

I'm also going to look into using functions as binary classifiers to test the results in the GEP book a little and see if I can include them in my thesis.

Awesome Images

Robust Gene Expression Programming is an evolutionary algorithm using bit vectors to encode expression trees. I was playing around with the idea of a linear population where individuals can only cross with those next to them, which has been done in Genetic Algorithms with interesting results, when I realized something really neat- a bit vector population in a linear order viewed as a picture would be a box of black and white pixels where useful schemata would float around the population from where they originated, and it might be possible to view this if the population where made into a picture.

Since I don't really want to look into variations of RGEP at the moment, I just recorded the normal unordered population every 50 generations and made a picture out of it. Here is a population at generation 500 trying to learn f(x) = 3*(x+1)^3 + 2*(x+1)^2 + x + 1:

I reversed the image so the front is the part of the individual that is interesting, since we are technically using postfix notation and the back is what is most likely to effect the fitness. I was concerned about the lack of convergence here- I expected much more uniformity. To see what the effect of Tournament Selection was against Roulette Wheel, I did a run using Roulette Wheel, and after only 50 generation we have:

So the population converged almost immediately. This is really interesting- the selection mechanisms have a much bigger effect on the diversity than I realized. I really like Tournament Selection and it performs very nicely, but it really seems like they take different strategies, exploration vs exploitation. Strange how the front part converged and the rest didn't though.

Hurray for data visualization! Now to figure out what it means for RGEP.

Decision Tree Induction

To show that GEP can be used to solve many types of problems its inventor, Candida Ferreira, presents many different tasks from symbolic regression, design of neural networks, block stacking, traveling salesman, and many others. Some of them require significant modification of the original algorithm but other problems can be solved by carefully chosen operators and terminals.

One problem that is fairly simple to set up with GEP is the creation of decision trees. These are what they sound like- tree structures that can make decisions. They consist of nodes each of which corresponds to an attribute, and for some given value of that attribute the node will return the value of the correct subtree corresponding to that value. This means that we can fill in the attribute values and ask the tree to give us an answer, and one of its leaves will ultimately be selected as the result.

To do this in GEP, or in my case RGEP, we just make the attributes into operators with n children where n is the number of values the attribute can have, and we have one terminal for each value of the decision variable. I'm only doing a simple example case, and Ferreira adds some additional complexity when creating decision trees with continuous valued attributes.

Since I'm only doing a proof of concept for my thesis, I am only going to try a simple example about whether or not to play tennis based on the weather. I have already written some very very basic code to create decision trees- I considered more complex schemes, but since this is a very minor part of my thesis I ended up adding the ability to create operators and terminals as well as a fitness evaluator for decision trees in 5 lines of code. Pretty simple!

Designing Multiplexers!

One problem used to test methods in AI is the multiplexer problem. It has been used as an example to test the ability of different methods such as decision trees, genetic programming, neural networks, and gene expression programming to correctly classify inputs. The idea is that for some k > 0 we want to design a multiplexer with k address lines and 2^k data lines, and we want the multiplexer's output to be the data line selected by the address lines. The way this has been done with GP and GEP is to have these methods evolve a boolean expression with all k+2^k variables, one for each input, whose result should match the correct data line input.

The fitness in this case can just be how many test cases the function/multiplexer works correctly for. In John Koza's work he used how many it misclassified instead, and then produced a scaling function to normalize the fitness' and make sure they could be used in roulette wheel selection. I'm going the simpler route and just finding how many cases (and you do try every possible case for every individual every generation) each solution gets correct. I am free to minimize or maximize with RGEP, and scaling would have absolutely no effect since the scaling function will be either isotone or antitone- either way tournament selection will only compare ordering not size.

I'm going to try this problem as a test for RGEP to show that it can evolve more then just functions, which is what most of my tests are doing. I plan on trying different size multiplexers, probably 3, 7, and 11 sized because that is what Koza tried in one of his works on GP. I want to also try doing decision tree evolution in RGEP for some variety, and it would be pretty simple to evolve a decision tree for this problem. I think it might even be easier then the boolean function approach as a completely correct tree could be very short.

I will try to post about decision trees when I get that far.

Functional Programming in Evolutionary Algorithms

FP and EAs are two of my main interests in computer science, so naturally I want to see how they can be combined. Genetic programming has a special connection to functional programming in that early genetic programs were lisp expressions. This of course makes sense- the abstract syntax tree is the subject of evolution in this case and lisp is a natural language for this as you program the syntax tree directly.
There are other connections however- many of the important additions to GP have come from functional programming. There have been variations taking imperative constructs as well, but that is not the subject of this post. Some examples are polymorphism, recursion, and the addition of a type system. Some GPs even evolve lambda expressions.
Logic programming has also been applied to GP to evolve statement from a "logic grammar".
Along with the type systems that have been used in GP literature, there has been work allowing a GP to evolve higher order functions.
The use of functions like fold and map is called implicit recursion in GP and gives a nice way to allow recursive structures without the need to evolve higher order functions directly, or add recursive semantics and check for termination, etc.

I would like some day to look into other functional programming techniques in the context of EAs. For example, laziness opens up some possible optimizations. Tournament selection does not necessarily check every individual's fitness (they can be skipped if they are not chosen for any tournaments). In this case we must either add a lazy evaluation strategy, or use a lazy language or one that includes some way of specifying laziness. This has been investigated before, but the language used was Java.
One thing that I thing would be really neat would be using categorical concepts (category theory is another favorite topic of mine, especially where it interacts with functional programming). For example- could we make a monadic GP? A comonadic GP? So far I haven't been able to come up with a reasonable problem to test this out on, but it seems interesting.

Tournament and Roulette Wheel Selection

There are many selection mechanisms available in GA literature, but the two most common seem to be roulette wheel and tournament selection. Roulette wheel involves (conceptually) creating a pie chart where the fitness value of each individual gives the size of the slice of the pie that that individual is assigned to. To create a new population, we can imagine a little arrow spinning around the middle of the chart, and the part of the chart it lands on is the individual that should be selected. Performing this computation n times for a population of n individuals yields a new population. In Heal, my Haskell Evolutionary Algorithm Library, roulette selection is implemented like this:
roulette :: (Linear p) => p (a, Double) -> EAMonad (p a) e
roulette pop = do
let sumfit = F.sum $ fmap snd pop
ds <- Tr.forM pop $ const (nextDouble sumfit)
return $ fmap (select pop) ds
select v !d | empty v = error $ "No selection, fitness remaining: " ++ show d
| remaining <= 0.00001 = i
| otherwise = select (rest v) remaining where
(i, f) = first v
remaining = d - f
where L is the qualified name of Data.Foldable, Tr is the qualified name of Data.Traversable, and Linear is a type class of finite linear structures (so the user can user whatever structure they like- I'm using the Seq sequence structure from Data.Sequence). EAMonad is basically the Random monad with some extra statefulness. Its second type argument e is the environment of the evolutionary algorithm, but in understanding the code one can safely ignore this.

Tournament selection on the other hand consists of small tournaments. To selection a single individual for the new population, we must selection k (normally k = 2. In fact, some definitions of tournaments selection describe it as having tournaments that are always size 2) and we have them compete against each other. The competition consists of choosing the more fitness individual (if k is greater than 2, chose the most fit) some percentage p (normally p = 75%) of the time, and the less fit otherwise. For k>2 this is slightly more complex, but basically the less fit the smaller chance of selection, and for the most part k=2, p=75%. Interestingly the fitness for tournament selection does not necessarily have to be a real number greater than 0 as with some other selection mechanisms, it just has to be of a type with a total order. In Heal, tournament selection is implemented like this:
tournament :: (Linear p, Ord b) => p (a, b) -> EAMonad (p a) e
tournament pop = do
pop' <- Tr.forM pop $ const $ selectPlayers pop >>= compete
return pop'
selectPlayers p = do
i <- nextInt $ count p
i' <- nextInt $ count p
return $ (index p i, index p i')
compete (a, a') = do
b <- test 0.75
return $ fst $ maxBy snd a a'
maxBy f a a' = if f a > f a' then a else a'
Notice the weaker condition on the second part of the pair, (the first part is the individual, the second the fitness) it is simply an Ord instance. Count gives the size of the linear structure (meaning that the structures should be finite) and index allows you to index into the structure. While roulette wheel is used in the original GEP, tournament selection is more common in GP literature, and apparently in GA literature as well. I personally prefer tournament selection and I've chosen it for RGEP.