Reverse Hillclimbing, Genetic Algorithms and the Busy Beaver Problem

Terry Jones
Santa Fe Institute
1399 Hyde Park Road
Santa Fe, NM 87501, USA
terry@santafe.edu

and

Gregory J. E. Rawlins
Department of Computer Science,
Indiana University,
215 Lindley Hall,
Bloomington, IN 47405, USA.
rawlins@cs.indiana.edu

Abstract

This paper introduces a new analysis tool called {\em 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 {\em 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 simplest form of hillclimbing.

Finally, several other uses for reverse hillclimbing are discussed.

Terry Jones (terry <AT> jon.es)