17×17 Research: Solving a 16×15 grid

This week I used the improved code from last week to solve a 16×15 grid with good success. I compared the performance of simulated annealing versus genetic algorithms at performing this task, running each 4 times:

16x15 completion time (in seconds)
Simulated Annealing: 11228, 1476, 3151, ---
Genetic Algorithm: 1702.5, 3291, 2589, 3641

From this small sample size of 4, ignoring outliers like the first simulated annealing test and the last (where the algorithm failed to finish in a reasonable time and I had to terminate it early to write this blog post), the two algorithms appear to have relatively similar performance. Perhaps a higher sample size will shed more light on how the two algorithms perform relative to each other, and both the algorithms could have their parameters optimized a bit more.

17×17 Research: Using a binary representation to achieve greater speeds

This week I fundamentally changed how my code works to store the colored grids. Before, grids would be stored in a 2D-array of ints, with each int representing the color of that cell. Now, grids are stored as a 2D-array of binary values – with each index [row][color] representing that particular color.

Previously:

[[0,1,3,2],
 [1,2,2,2],
 [0,0,1,3],
 [3,1,3,2]]

Now:

[[0b1000, 0b0100, 0b0001, 0b0010],
 [0b0000, 0b1000, 0b0111, 0b0000],
 [0b1100, 0b0010, 0b0000, 0b0001],
 [0b0000, 0b0100, 0b0001, 0b1010]]

I do this because it allows me to do a neat trick to speed up the score calculation: I can take two rows’ color values, perform a binary AND on them, count the number of bits in the resulting value as n, and then the number of rectangles between them is n * (n-1) / 2. This removes a for loop from my previous approach, and the process is now O(n^3) instead of O(n^4).

I performed some speed tests on the new code compared to the old, and here are the results:

For a 17×17 grid, the new score calculation algorithm is over 3x faster! This is a big improvement.

Time to Solve a 15×15 Grid: New vs. Old

This boxplot shows just how much faster the new score calculation is in practice. The plots were generated from datasets of 12 samples each.

17×17 Research: Optimizing the inner loop and testing another SA temperature function

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.

17×17 Research: Reaffirming the basics with the GA and a new temperature function for SA

This week I realized that a bit of my genetic algorithm is non-standard compared to how people usually implement one. The standard implementation is a bit simpler than the one I’ve been using, so I decided to refactor the code a bit to match the standard version (reading from Wikipedia and around the web) and see if it would help. The biggest difference between standard genetic algorithms and my code was that I was selecting a portion of a population to survive to the next generation, whereas that’s not something that’s done in the standard implementation. The standard implementation simply selects a portion of the population for breeding, then generates the entire next generation through crossover followed by mutation. I implemented roulette wheel selection to select the candidates for crossover, compared to my old selection functionality that just sorted the population by score and took the top 20%.

Testing seems to show that this more traditional implementation functions at best the same as my old code, if not worse. It takes the traditional implementation about 30 seconds to solve a 10×10 grid, which only takes about 1.5 seconds for my old code to solve. This is due to the fact that the traditional implementation has a much larger variance in the population. Perhaps I could optimize this traditional version with some parameter testing, that might be something to look into.

I also did some testing into different functions for the temperature in the simulated annealing approach. I came up with a little formula that kind of mimics the way blacksmiths do annealing in real life: they heat up the metal, let it cool, heat it up again to a slightly less heat than before, repeat. The formula is as follows, where dt represents the time elapsed since the start of the simulation in seconds.

temperature = (0.5 + 0.5 * cos(0.1 * dt)) * (0.5 + 0.5 * cos(0.005 * dt))

Here’s what that looks like on a graph (note x is scaled to 2000 seconds):

So it functions like a cosine wave inside another cosine wave. Because the function is cyclic, the test can be run indefinitely without worrying about the temperature getting to some unreasonable value. This seemed to perform fairly well, it solved a 15×15 in 470 seconds. I ran the old simulated annealing side-by-side and it took 2700 seconds to solve a 15×15, so definitely a big improvement. I’m not sure what you would call the constants in this equation (0.1 and 0.005), but it might be worth it to try and do some parameter optimization on them. Perhaps I’ll call them CYCLIC_RATE_MINOR and CYCLIC_RATE_MAJOR, respectively.

Research: 17×17 Genetic Algorithm Parameter Optimization Attempts

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.

Research: 17×17 Genetic Algorithm First Tests

This week, I jumped right in and implemented / started testing a genetic algorithm on the 17×17 challenge. I didn’t start with a 17×17 grid right away though, and instead focused on smaller, more manageable sizes first.

The algorithm uses the following parameters:

• 20 solutions per generation – i found this number worked better compared to the 10 sol/gen I used for the codon pair optimization last semester
• The top 30% of a previous generation is selected for breeding and will live on to the next generation
• From that 30%, 60% of the next generation is created through crossover (weighted by a random value between 0.2 – 0.8)
• The remaining 10% of the next generation is randomly generated for variety’s sake
• All solutions are then randomly mutated by a factor of 0.008, except for the top performing solution (preserving the best solution assures we don’t go backwards).

The algorithm was able to solve a 7×7 puzzle in 220 generations, 3.2 seconds:

3221022
3211031
1212210
0300212
2302313
2301010
2323131

The algorithm was able to solve everything up to a 14×14 within a reasonable amount of time (no more than several hours). I left the algorithm running for a very long period of time in an attempt to solve a 15×15 puzzle, but was not able to find a solution after 320993 seconds (89 hours). It was only able to find a partial solution of 5 rectangles:

221102031001332
010330101323212
110231321032032
101210012133323
032322123101230
321231203010310
311320230200101
212213000311033
230031220121123
303011102203231
033223310021311
003102113222003
130102232330112
220123033113201
322000311312120

I know that a solution exists for 15×15 because I was able to find it online. The algorithm still needs some work before it will be able to solve larger grids in a reasonably finite amount of time.

Despite this, I would say that this week has been a success. The algorithm is able to succeed at optimizing this problem, at least the smaller varieties. The next step is to optimize the algorithm, and then compare it to a simulated annealing approach.

Research: 17×17 Mutation and Crossover

This semester I’m working on solving the 17×17 problem with genetic algorithms. Last week, I started work on the Python script – implementing functions to generate random color grids (for the initial population) and score them based on the number of rectangles they have.

This week I added the mutate() and crossover() functions. The mutate() function takes as inputs a grid and a percentage amount. The function returns the input grid with a percentage of the cells randomized to different colors. The crossover() function takes as inputs two parent grids (a and b) and a weight amount. The function will randomly pick rows from both parents and create a child from them. The weight parameter determines which parent has the most influence – if weight < 0.5 then there will be more rows in the child from parent A, if weight > 0.5 then there will be more rows from parent B. So crossover(a, b, 0) == a, and likewise crossover(a, b, 1) == b.

Here’s the Python script so far: https://gist.github.com/shoffing/99b1b25a0ffaaa297c18

I made a little test for the two functions that simply generates two 17×17 grids with random colors, uses crossover() to combine them into a child grid, then uses mutate() on the child to mutate it by 25%. An example of the output:

Parent A:
10200012002311203
01110202121010003
21312111120021023
03033211310102111
12111330230013302
13131302131322230
11313011131033020
32122321112320212
13122101122230002
12003100333323011
12031001323231311
11120102131312333
22331102203130023
21021212301120130
33022200303120300
23233312013313032
10001223222033311
>> 277 rectangles


Parent B:
21112222010030102
30303130213333003
33210012122002131
23211032222030320
00312201123123230
32000130331203333
30303210202333222
02122231200332310
30230110232033010
20131031131233120
33312322102322321
20002123231111122
21220220313331210
20002010311332310
22323111210000013
21330330033012312
10313312003023032
>> 298 rectangles


Child:
21112222010030102
30303130213333003
21312111120021023
03033211310102111
12111330230013302
13131302131322230
30303210202333222
02122231200332310
13122101122230002
12003100333323011
33312322102322321
11120102131312333
21220220313331210
21021212301120130
22323111210000013
23233312013313032
10313312003023032
>> 286 rectangles


Child mutated 25%:
21112222031010102
30303130213333003
21332111120021303
00023231310112311
12011331230033302
13131002131222200
30203210202033020
32312231230332310
13122102122200003
12103101313323011
33112322100322332
12122102131312333
21220300113331010
22021212301122123
22323111210300013
23231312013213032
20313012003020032
>> 283 rectangles

Research: Dynamic Parameters

This week I attempted to improve the output of my algorithm by making some of the genetic parameters (selection ratio and mutation rate) dynamically change over the course of program execution.

For example, MUTATION_RATE can be set to start at 5% for generation 0, and interpolate towards a final mutation rate of 0.1% as the program approaches the maximum number of generations. This interpolation can be also be non-linear, providing different results. I tested the different functions for interpolation by running the program 5 times with each and recording the median score of the results. I express these interpolations as a function of x, the ratio of completed generations in the range 0 to 1. The results of this testing are below:

Constant (no dynamic parameters, no interpolation)

Median score: -264.21

Interpolation f(x) = x (Linear)

Median score: -331.91

Interpolation f(x) = x²

Median score: -308.29

Interpolation f(x) = x^0.5

Median score: -362.74

Interpolation f(x) = x^0.25

Median score: -392.43

It’s obvious from these results that making the parameters change dynamically like this is very effective. While an interpolation of x^0.25 provides the best results from this set of initial observations, I decided to use x^0.5 as the interpolation function for a test with a large number of populations because I worry that using an interpolation function as drastic as the 4th root of x with my algorithm might cause it to not spend enough time searching the solution space, instead falling into local minima too quickly. This negates one of the biggest benefits of using a genetic algorithm, its ability to search the entire solution space thoroughly.

I left my program to run overnight for 120K generations at 50 solutions per generation with parameters MUTATION_START, MUTATION_END, SELECTION_RATIO_START, and SELECTION_RATIO_END set to 0.03, 0.001, 0.2, 0.04 respectively and a interpolation function of x^0.5. The result is very good, much better than the results achieved even after a million generations of my algorithm without dynamic parameters:

120K Generations with Dynamic Parameters

Best solution: -456.725

While this score is much better than scores I have been able to achieve in the past, my algorithm still has yet to discover a solution with a score greater than that of the simulated annealing approach (-461.163).

Research: Trying to Diversify

This week I tried to figure out why my algorithm wasn’t able to find a good solution, even after a million generations. After skimming over some of the writing on genetic algorithms, I came to the conclusion that my new generation selection phase wasn’t diverse enough – possibly causing the algorithm to get stuck in local minimums. For each new generation I would keep the top 30% of the solutions from the previous with slight mutation, keeping the best solution completely unchanged, and fill the rest of the new generation with crossovers of those 30% or randomly generated new solutions. Keeping the top 30% each time is where I thought I could improve. The selection algorithm should have a small chance of not picking the same top solutions every time – hopefully increasing the diversity of the generations and widening the search area. I implemented tournament selection to accomplish this. Tournament selection breaks up the previous generation into random fixed-sized groups, and simply selects the best solution from each group.

I tested the algorithm overnight with 200k generations, and it is still not performing as well as I think it could. I know there exists a solution with a score of -460.6 as found by my professor with his simulated annealing approach, but my algorithm teetered around the -260 line with the best solution it found having a score of -276.4. For 5 hours of execution time, this is not optimal. Also, I turned off log scaling on the x-axis of the output graph because I thought it would make it more readable, but it appears to have had the opposite effect:

More work needs be done to see if I can squeeze better solutions out of the algorithm.

Research: Basic Code Profiling

This week I profiled my Python script in an attempt to find functions that could be optimized better. Following this simple tutorial, I ran cProfile on my code performing 100K generations and here are the results:

http://pastebin.com/raw.php?i=6dWakQAL

From this, I can see a few areas that might be able to be improved:

• A large amount of time is being spent in copy.deepcopy, as it’s used quite a bit throughout my code. Maybe I can find a better alternative.
• My calcScore() function is taking quite a bit of time. This is because it has to search the massive array of codon pair scores. I might be able to speed this up by using a different data structure to store the scores.