Genetic Algorithms for Fun and Calculating Profit
While we here at Torchbox usually spend our days creating interfaces and writing business logic, occasionally a challenge comes along that requires something different.
Recently we've been doing some work on the Indie Screenings code, changing their pricing calculations so they have more flexibility as they expand into new countries. Unfortunately, changing the calculations meant we rendered all of the current price factors useless, and the quotes were coming out completely wrong - we needed a new set of price factors.
Faced with manually tweaking around fifty inter-dependent values for hours on end, or the chance to use evolutionary computing, we of course chose the latter. I spent an hour tinkering with PyGene, and wrote a genetic algorithm to evolve some new price factors.
For those unfamiliar with genetic algorithms, it's essentially a guided random mutation process, which uses a "fitness function" to determine how well each solution is doing. In our case, we chose to use the mean squared relative error between every possible combination of the price factors, old and new.
The genetic algorithm will take its 'population' of 10 sets of factors, mutate some, crossbreed (i.e. take some factors from one, some from another, and mix them) good sets of factors, and then pick the best resulting ten, and then repeat the process. We got through around 4000 generations of factors overall, but we could have kept going - the longer you run a GA, the better the result, although usually you get smaller and smaller improvements.
It took only a few hours for those generations to run, and we now have some factors that are appreciably close to producing the same results as before - time saved for both us and the client.
We haven't quite got to self-evolving websites yet, but I'm sure that's just around the corner.
Image from http://www.flickr.com/photos/good-karma/453011538/
