Part of Advances in Neural Information Processing Systems 6 (NIPS 1993)
Melanie Mitchell, John Holland, Stephanie Forrest
We analyze a simple hill-climbing algorithm (RMHC) that was pre(cid:173) viously shown to outperform a genetic algorithm (GA) on a simple "Royal Road" function. We then analyze an "idealized" genetic algorithm (IGA) that is significantly faster than RMHC and that gives a lower bound for GA speed. We identify the features of the IGA that give rise to this speedup, and discuss how these features can be incorporated into a real GA.