This week I spent some time looking at my genetic algorithm code and seeing if there was anything I could improve. There was indeed quite a bit of bloat. A lot of overhead was spent storing data about each generation for the purpose of rendering a graph of the score over time when the solution is found. Each generation, every individual’s score was being calculated 3 times! I was able to optimize this process to where each individual’s score is only calculated a single time, and achieved a noticeable speedup of 3x or 4x. It’s not an order of magnitude or anything, but every second counts!
Running the new and improved genetic algorithm on a 15×15 grid a few times, a solution was found in under 300 seconds! The average time was about 500-600 seconds, and a few attempts didn’t finish (the algorithm falls into a local minima and has trouble getting out, something to look into). These times are much faster than before, taking minutes instead of hours to complete.
I also tried a new temperature function for the simulated annealing approach – a simple negative exponential function with time as the variable. The temperature at a given time is now equal to:
e^(-mult / time)
mult starts at a given value (such as 0.2), and then when the temperature reaches a critically low value (like 0.00001) mult is decreased and the annealing is restarted with the new value. In this way, the temperature decreases more slowly after each failed attempt, and more time is spent searching the solution space on each iteration.
The time to solve for this new function varies wildly based on the starting value of the mult variable. After testing on a 15×15 with a starting mult of 0.2, I can see that it was able to solve it in 450 seconds on the iteration that had a mult of 0.135. Running the simulation again with a starting mult of 0.135, a solution can be found in about 45 seconds – taking a single iteration of annealing. This existing knowledge of the optimal mult value enables extremely good performance, but finding that value of mult takes time and is different for each problem size. For larger grid sizes a smaller mult would be more optimal, while for smaller grid sizes a larger value would be better.
shoffing's blog 