Stephanie Forrest, Melanie Mitchell

Paper #: 91-05-024

In this paper we discuss a number of seemingly anomalous results reported by Tanese concerning the performance of the genetic algorithm (GA) on a subclass of Walsh polynomials. Tanese found that the GA optimized these functions poorly, that a partitioning of a single large population into a number of smaller independent populations seemed to improve performance, and that hillclimbing outperformed both the original and partitioned forms of the GA on optimizing these functions. We reexamine these results experimentally and theoretically, and propose and evaluate some explanations. In addition, we examine the question of what are reasonable and appropriate ways to measure the performance of genetic algorithms.