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.