This past week, I ran several tests in attempts to find the perfect parameters for a genetic algorithm to solve the 17×17 challenge.
My process was fairly simple: I would pick a range and granularity of values for each of the seven parameters in my code, and then run the code over every combination of values in those ranges 4 times, then find the average time to completion for those parameters. I used Python’s multiprocessing support to run 4 instances simultaneously, and set timeouts (< 10 seconds) for each test so they wouldn’t run indefinitely. Using multiprocessing made the process 4X faster.
My first test was on a 7×7 grid. The parameter ranges turned out to be 81K tests. This took about 30-40 hours to complete. Unfortunately, I wasn’t able to draw much conclusion from this output data because I set the starting value of the mutation amount parameter higher than I should have, and the completion times were almost universally under 0.5 seconds so the performance range wasn’t as wide as I would’ve liked.
So I repeated the process with an 8×8 grid, this time with better choices for parameters. You can see the output (sorted by time to solution) here: https://gist.github.com/shoffing/01a43b2cc9b665f7357b
I took the top 100 parameter sets from the 8×8 output, and tried them with a 10×10 grid. What I found was surprising – the performance order on the 10×10 grid didn’t match up with the permanence order on the 8×8 grid at all. For example, the #1 performing parameter set from the 8×8 test was in the lower 10% on the 10×10 grid. From this I concluded that ideal parameters are very dependent on the size of the grid.
I performed another experiment following these test. I took one of the top performing parameter sets and put it up against a 15×15 grid (which I was unable to solve before). For some reason, I had a hunch that larger population sizes might work better for a larger grid. So I put that to the test – I ran the algorithm with 10, 20, 50, and 100 solutions per generation to see which (if any) would solve the 15×15 grid first. And, to my surprise, 100 solutions per generation was able to solve the problem in only a few hours time! For smaller grids, a smaller population size was the key to a faster solution. This does not seem to be the case for larger grid sizes. Here’s the solution I found for the 15×15 grid:
011233323011202 322102321321010 123031001302322 210312213303012 132330110231220 221200311000333 013323201120123 133202300213101 332221013112300 301031132220110 000203032131321 230010131322231 213121023230031 320123102013230 101110222133003
This is a big success, and one step closer to solving the 17×17.
shoffing's blog 