Stephanie Forrest, John Holland, Melanie Mitchell

Paper #: 91-10-046

Genetic algorithms (GAs) play a major role in many artificial-life systems, but there is often little detailed understanding of why the GA performs as it does, and little theoretical basis on which to characterize the types of fitness landscapes that lead to successful GA performance. In this paper we propose a strategy for addressing these issues. Our strategy consists of defining a set of “features” of fitness landscapes that are particularly relevant to the GA, and experimentally studying how various configurations of these features affect the GA's performance along a number of dimensions. In this paper we informally describe an initial set of proposed feature classes, describe in detail one such class (“Royal Road'' functions), and present some initial experimental results concerning the role of crossover and “building blocks” on landscapes constructed from features of this class.

PDF