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.
shoffing's blog 