Evolutionary Solver: Mutations

March 5, 2011

This is the sixth post in a series on Evolutionary Solvers.

All the mechanisms we have discussed so far (Selection, Coupling and Coalescence) are designed to improve the quality of solutions on a generation by generation basis. However all of them have a tendency to reduce the bio-diversity in a population. The only mechanism which can introduce diversity is mutation. Several types of mutation are available in the Galapagos core, though the nature of the implementation in Grasshopper at the moment restricts the possible mutation to only Point mutations.

Before we get to mutations though, I’d like to talk briefly about Genome Graphs. A popular way to display multi-dimensional points on a two-dimensional medium is to draw them as a series of lines that connect different values on a set of vertical bars. Each bar represents a single dimension. This way we can quite easily display not just points with any number of dimensions, but even points with a different number of dimensions in the same graph:

Here for example we have a genome consisting of 5 genes. This genome is thus a point in the 5-dimensional space that delineates this particular species. When G0 is drawn at ⅓, it means that the value is one-third between the minimum and maximum allowed limits. The benefit of this graph is that it becomes quite easy to spot sub-species in a population, as well as lone individuals. When we apply mutations to a genome, we should see a change in the graph, as every unique genome has a unique graph.

The above modification shows a Point Mutation, where a single gene value is changed. This is currently the only mutation type that is possible in Galapagos. We could also swap two adjacent gene values, in which case we get an Inversion Mutation:

Inversion mutations are only useful when subsequent genes have a very specific relationship. It tends to drastically modify a genome and thus in most cases also drastically modify fitness. This is almost always a detrimental operation.

Two examples of mutations that cannot be used on a species which requires a fixed number of genes are Addition and Deletion mutations. At present Galapagos only works on fixed-size genomes, but this this is not a logical or practical limitation and probably will be overcome in future releases.