Biases of Genetic Algorithms and Simulated Annealing
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?