Reverse Hillclimbing, Genetic Algorithms and the Busy Beaver Problem

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. <p> 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. <p> Finally, several other uses for reverse hillclimbing are discussed.