Philosophical Multicore

Sometimes controversial, sometimes fallacious, sometimes thought-provoking, and always fun.

Simulated Annealing vs. Genetic Algorithm

Posted by Michael Dickens on September 7, 2009

When I read about simulated annealing, I considered implementing it instead of a genetic algorithm. But I decided not to. Why? Simulated annealing relies on the assumption that the best layout is next to the second best layout, which is next to the third best layout, etc. But this is likely to be untrue. The second best keyboard probably looks nothing like the best keyboard. But genetic algorithms avoid this problem, through repetition. The “all star” round contains many very good layouts, so it is more likely to converge on the best layout.

But when I saw some results, I had to reconsider. Simulated annealing is seemingly much faster. But how can we get it to converge on the best possible layout? Could we do something like simulated annealing, but then repeat it and pool all the best layouts and evolve those using a genetic algorithm?

I ran some empirical tests, and it turns out that simulated annealing is indeed many times faster than a comparable genetic algorithm. Chris Johnson sent me some source code, and it turns out that it is indeed much faster.

Simulated annealing works sort of like a “smart” genetic algorithm with a pool size of only one. Instead of just making any old mutation, it looks for good mutations to make. This allows much faster convergence. But this strategy, as well as the genetic algorithm strategy, can sometimes skip over very good layouts, or even the best. I will explain in a later post, coming soon.

Advertisements

2 Responses to “Simulated Annealing vs. Genetic Algorithm”

  1. James said

    You said you ran empirical tests and found SA to be many times faster than GA. What kind of tests did you run? On what kind of hardware? I can think of many cases where GA would come to a faster solution than SA, especially if you are using multi-threads.

    • I tested my typing program (https://github.com/MTGandP/Typing) on my Macintosh with a 2.5 GHz dual-core processor. I think GA would be faster for some applications, but not for what I’m doing. The program is single-threaded for both GA and SA, but even if it weren’t, the SA algorithm is about 100 times faster, so multithreading would only help if you had a supercomputer.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: