#
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)