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.

Things Haskell Has Taught Me Or Helped Me Learn About

Monads, functors, categories, limits, the Yoneda Lemma, domain theory, denotational semantics, abstract algebra, the theory of combinatorial species, type theory, the lambda calculi, intuitionistic logic, referential transparency, natural transformations, comonads, currying/partial application, lazyness/eagerness, strictness/non-strictness, and adjunctions.

And much more, but thats all I can think of at the moment. I don't completely understand all of these things (actually I'm not sure I would really say I understand any of them). The important thing is that Haskell has taught me about math, logic and computer science. Also, knowing Haskell has given me a way of understanding new material in math. What a cool language.

Negation in Computer Science

Negation in Computer Science is a funny thing.

There are several important semirings in CS, which miss out on being rings simply because there is no negation. Some examples include the theory of combinatorial species (which describes datastructures), the Kleene Algebra describing regular expressions aka regular grammars aka finite state machines, and both Boolean and Heyting lattices. The last two have a lot of applications- obviously Boolean algebra is important in CS. Heyting lattices are a generalization of Boolean lattices which have some implication structure not necessarily satisfying the usual a -> b = -a\/b. Negation in this context is defined as -a = a -> _|_, so "not a" is the same as "a implies bottom". These are important in denotational semantics and Domain theory.

Negation is also interesting in constructive mathematics, where there is no double negation elimination. Double negation is something like "potentially false" apparently.

The translation of statements from classical logic into intuisionistic logic by double negation corresponds to a translation into CPS (continuation passing style) which is pretty amazing. This only occurs when the _|_ type is replaced with some other type, giving the type of continuations (a -> r) -> r, which is related to the Yoneda Lemma in a way that I am having trouble understanding.

Double negation also has something to say about the concept of proof irrelevance. A term of a type is a proof of the proposition that its type corresponds to. On the other hand, which the actual term is important from a computational perceptive (as it is an algorithm) it is irrelevant from a proof perspective because we are interested in the existence of a proof, not its particulars. The double negation actually removes the computational content from a proof in a very interesting way. In (a -> _|_) -> _|_, if "a" is inhabited then (a -> _|_) is not, as there is no function from an inhabited set to an empty one. If (a -> _|_) is equal to _|_ then (_|_ -> _|_) is inhabited, as there is one function from the empty set to the empty set. This means that the type (a -> _|_) -> _|_, proves a if true, but has lost the particular term that proves a, losing the computational context. I wonder if this is related to the difference between Prop and Set in Coq when doing program extraction to other languages..

There is probably more to say, but for now thats all I can think of.

Visualization of Diversity in a Cellular Genetic Algorithm

A Cellular Genetic Algorithm (CGA) is a regular GA with additional structure on the population. While the normal populations in a GA are a multi-set (a set that can have repeated elements) in a CGA they are some other data structure. Often this is either a list or a torus (a grid whose edges meet). This imposes a restriction on crossover where individuals can only cross with others near them. It also affects selection, where an individual can only be replaced by individuals around them.

On of the neat things about CGAs is that they can have interesting behavior with diversity. It is possible for some sections of the structure (lets consider a grid, as that will be interesting later on in this post) to converge to different solutions then other areas. This means that in the center of some collection of cells (holding individuals) there will be very little change, as mutations will be weed out (mostly) and crossover will not affect equal individuals. On the other hand, at the edges between to converged groups, selection will cause one group to dominate other other, or a stable edge may appear. Crossover across this edge will cross the traits that make each group highly fit, and may produce very very fit individuals. This is the coolest thing about this technique. This may also occur in an Island Genetic Algorithm, incidentally.

The other thing I want to introduce before getting into the point of this post is the solution space. This really is a space, as for any two points (encoding of solutions) a distance measure may be taken. If the encoding is simple bit vectors, then the distance is the hamming distance (the number of bits that differ between the individuals). This distance does not necessarily correspond to the difference between their fitnesses. This gives another dimension to the solution space, which we may imagine as a landscape where the solutions are x, y coordinates and the z value is the fitness of those points. The landscape may be very complex.

Another measure we can make is the "diversity" of the individual. We can take the pair-wise hamming distance between the individual and the individuals "near" to it. In a multi-set population an individual is "near" all individuals in the population's topology. In a CGA this is not the case, and diversity is measured only by the individuals in cells of a certain distance away in the topology (lets say distance 1, so a cell in a grid has 8 neighbors).

The idea of this post is that we can equate the diversity measure of the individuals and an individual's fitness. This means that we are almost certain to have many different groups converging to different bit vectors. Then we can imagine the grid of fitness values of the individuals, which will tell us not their genetic material but just how much they differ from their neighbors. This is were the visualization comes in.

If we assign some range of colors to the values from 0 to the maximum diversity measure (neighbors*individual length), probably with blue or white around 0 and red around the highest diversity. Then we could make images out of the population's fitness values throughout the run of the CGA and see the interaction at the edges of the groups. Probably the groups will quickly form and one group will take over the others, but really I don't know what would happen. I do know it would look really neat.