Reverse Hillclimbing, Genetic Algorithms and the Busy Beaver Problem

Terry Jones and Gregory J. E. Rawlins

Working Papers from Santa Fe Institute

Abstract: This paper introduces a new analysis tool called {\it reverse hillclimbing}, and demonstrates how it can be used to evaluate the performance of a genetic algorithm. Using reverse hillclimbing, one can calculate the exact probability that hillclimbing will attain some point in a landscape. From this, the expected number of evaluations before the point is found by hillclimbing can be calculated. This figure can be compared to the average number of evaluations done by a genetic algorithm.

This procedure is illustrated using the {\it Busy Beaver problem}, an interesting problem of theoretical importance in its own right. At first sight, a genetic algorithm appears to perform very well on this landscape, after examining only a vanishingly small proportion of the space. Closer examination reveals that the number of evaluations it performs to discover an optimal solution compares poorly with even the simples form of hillclimbing.

Finally, several other uses for reverse hillclimbing are discussed.

Date: 1993-04
References: Add references at CitEc
Citations: View citations in EconPapers (2)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:93-04-024

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().