Philosophical Multicore

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

Biases of Genetic Algorithms and Simulated Annealing

Posted by Michael Dickens on September 7, 2009

Both genetic algorithms and simulated annealing have a serious problem: they get stuck. There are some possible layouts which could be very good, but which the algorithm will never get to since it requires getting past a certain hurdle. So how can this be solved?

1. Let a layout live and mutate for a while before you kill it. The problem with this is one of memory. You’re going to need some really huge arrays to hold all of those layouts.

2. Make one or a few keys inactive. This was inspired by a bug which led to some interesting results. The idea here is that you make a particular letter cost nothing, and run the algorithm as normal. If this letter was acting as a “wall” preventing the algorithm from getting to a good layout, the wall will be taken down. Then, after a few iterations, insert the letter again. I tried this out, and it had minimal effect. On the other hand, it didn’t slow the program down by much, either.\

3. Make one or a few scoring criteria inactive. This could more effectively break down potential walls than #2. This is tricky to implement reliably, though. If you rotate through the scoring criteria, making each one inactive in turn, then the definition of “best” changes every generation and so the program never comes to a stopping point. If you remove each criterion for a few generations but only one time, then you don’t know if it is adequately hurdle-skipping. And then there’s the added problem that the actual fitness will be reduced, and that has to be balanced somehow.

Are there any other methods that could actually work?

Advertisements

2 Responses to “Biases of Genetic Algorithms and Simulated Annealing”

  1. phynnboi said

    One idea I had early on for the simulated annealing-type algorithm was this: Go ahead and let it find its “best” layout using individual swaps. When no individual swap improves the layout, try to make an improvement by making two swaps at once (easy enough by making improveLayout() recursive). If that doesn’t work, try three swaps at once. Etc. You can go to however many swaps at a time you want, although three swaps is already pushing the limits of my patience :). Obviously, that’s not perfect, but it can at least give you a little added security about your layout–no one can come along with the same scoring criteria and improve the layout merely with three or four swaps.

    I also tried a variation on #3 where I started by optimizing for one criterion. Then I took that layout, added a criterion, and optimized for those two criteria. Eventually, I’d added all the criteria. It didn’t help.

    Personally, I came to the conclusion that it isn’t worth worrying too much about. There’s a pretty limited number of places you can reasonably put E, T, A, and O, for instance, or Q and Z. So, I don’t think the fitness surface is particularly deceptive. In my experience, a few runs of the SA algorithm generally turn up the best algorithm it’s ever going to; you can let it run all night and come back and it won’t have found anything better. At that point, I’m willing to concede that the resultant layout is really, really good. I can’t prove it’s optimal, but the chances of anyone else finding a better layout using the same fitness function are very low, and that’s about all you can ask for with probabilistic algorithms such as these.

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: