April 23, 2012

# Visualising the Path of a Genetic Algorithm

The paths of 8 runs of a genetic algorithm optimising a multivariate normal mixture function. Three of the runs break out from a local maxima (presumably through mutation) to find the global solution. The circles are the starting points.

We quite regularly use genetic algorithms to optimise over the ad-hoc functions we develop when trying to solve problems in applied mathematics. However it’s a bit disconcerting to have your algorithm roam through a high dimensional solution space while not being able to picture what it’s doing or how close one solution is to another. With this in mind, and also just out of curiosity, I’ve tried to visualise the path of a genetic algorithm by using principal components analysis.

If you are not familiar with this extremely useful technique then there’s plenty of information online. To put it very very briefly PCA rotates the axes in whatever dimensional space you are working to find a solution where the first axis points in the direction of the greatest variation in your data, the second axis in the direction that captures the greatest part of the leftover variation and so on. The upshot is that if we take the first two axes we should get the best two dimensional view of the shape of our data.

So what I’ve done is run a genetic algorithm several times on the same function, recorded the paths of each run and then applied PCA to visualise these paths. To run the genetic algorithm I’ve used the excellent rgenoud package. The code below implements a function that I hope will be flexible enough to apply this process to any function that rgenoud can handle. You just need to specify the function, the number of parameters, the number of runs you want and a few other optional parameters.

I’ve tried it on a multivariate normal mixture function (above) and Colville’s function (below). I’d like to try some others when I’ve time and would love to see the results if anyone else would like to make use of it. I would recommend using the parallel option if you can as otherwise plotting many runs can take some time.

Eight runs eventually converge on the global minima of the Colville function. The circles are the starting points of the algorithm

If you enjoyed this then please check out more visualisation in Mark’s latest post.

Now here’s the code for the general function.

… and here is the code for the examples I’ve included.