Sponsor
This project was supported by the Santa Fe Institute's Adaptive Computation - Program and by grant B1992-46 from the Alfred P. Sloan Foundation.
Document Type
Working Paper
Publication Date
1993
Subjects
Genetic algorithms -- Mathematical models, Genetic programming (Computer science)
Abstract
In this paper we review some previously published experimental results in which a simple hillclimbing algorithm-Random Mutation Hill-Climbing (RMHC)-significantly outperforms a genetic algorithm on a simple "Royal Road" function. vVe present an analysis of RMHC followed by an analysis of an "idealized" genetic algorithm (IGA) that is in turn significantly faster than RMHC. We isolate the features of the IGA that allow for this speedup, and discuss how these features can be incorporated into a real GA and a fitness landscape, making the GA better approximate the IGA. We use these features to design a modified version of the previously published experiments, and give new experimental results comparing the GA and RMHC.
Persistent Identifier
http://archives.pdx.edu/ds/psu/12385
Citation Details
Mitchell, Melanie, John H. Holland, and Stephanie Forrest. "When will a genetic algorithm outperform hill climbing?" SGI Working Paper 1993-06-037 (1993)
Description
Santa Fe Institute Working Paper 1993-06-037. Subsequently published in Proceedings of the 5th International Conference on Genetic Algorithms, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©1993.