maze

Genetic Algorithms

A few weeks ago I had the opportunity to participate in a webinar put on by the Society of Actuaries about Genetic Algorithms in actuarial problems. It was a quite enlightening presentation especially for myself as I had no prior experience with Genetic Algorithms.

For those who aren’t familiar, genetic algorithms attempt to solve problems using a “survival of the fittest” type approach. We’re really focusing on problems that have a large solution space. How the algorithm works, is that a number of random solutions are generated and then ranked or scored based on how well they solve the problem. The top solutions are then used to generate another set of solutions (known as a generation). We can also then incorporate some mutations to introduce an element of further┬árandomness┬áthat may unveil an even more optimal solution.

I’ve uploaded a small sample of how they work. In this sample, a genetic algorithm was used to solve a small maze. Now given that a maze has only one optimal solution, the algorithm doesn’t work the best. Also, I’ve modified how mutations are made to the maze direction string. What was happening is that the mutations were all having a negative effect on the outcome of the maze. Now a mutation is made up of a move, and it’s opposite. This results in more exploring and allows mutations to have a more positive effect on the overall solution.

As can be seen in this maze example, that the algorithm may find a solution but human judgement may be needed to determine an optimal solution. You can play around with the sample at the bottom link.

Maze-genetics

 

50