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.