Evolutionary Algorithms, Fitness Landscapes and Search

In March 1995, I finally finished my Ph.D. in computer science at the University of New Mexico working with Dr. Stephanie Forrest.

In the course of completing my degree, I was supervised by seven different people. To honor their brave efforts, I constructed an html shrine, the Ph.D. Supervisor page, to ensure that their names will never fade.

If you're really interested, you can read my thesis acknowledgments.

My dissertation is available here in PDF.

There are the following chapters:

Title, Abstract, Lists, Abbreviations etc. (25 pages).
Introduction (12 pages).
A Model of Landscapes (34 pages).
Crossover, Macromutation and Population-based Search (38 pages).
Reverse Hillclimbing (36 pages).
Evolutionary Algorithms and Heuristic Search (41 pages).
Related Work and Conclusions (19 pages).
Appendices and Bibliography (44 pages).

If you're lucky you may be able to get a hardcopy of the dissertation by contacting the Santa Fe Institute and requesting TR 95-05-048.

ABSTRACT

A new model of fitness landscapes suitable for the consideration of evolutionary and other search algorithms is developed and its consequences are investigated. Answers to the questions "What is a landscape?" "Are landscapes useful?" and "What makes a landscape difficult to search?" are provided. The model makes it possible to construct landscapes for algorithms that employ multiple operators, including operators that act on or produce multiple individuals. It also incorporates operator transition probabilities. The consequences of adopting the model include a "one operator, one landscape" view of algorithms that search with multiple operators.

An investigation into crossover landscapes and hillclimbing algorithms on them illustrates the dual role played by crossover in genetic algorithms. This leads to the "headless chicken" test for the usefulness of crossover to a given genetic algorithm and to serious questions about the usefulness of maintaining a population. A "reverse hillclimbing" algorithm is presented that allows the determination of details of the basin of attraction of points on a landscape. These details can be used to directly compare members of a class of hillclimbing algorithms and to accurately predict how long a particular hillclimber will take to discover a given point.

A connection between evolutionary algorithms and the heuristic search algorithms of Artificial Intelligence and Operations Research is established. One aspect of this correspondence is investigated in detail: the relationship between fitness functions and heuristic functions. By considering how closely fitness functions approximate the ideal for heuristic functions, a measure of search difficulty is obtained. This measure, fitness distance correlation, is a remarkably reliable indicator of problem difficulty for a genetic algorithm on many problems taken from the genetic algorithms literature, even though the measure incorporates no knowledge of the operation of a genetic algorithm. This leads to one answer to the question "What makes a problem hard (or easy) for a genetic algorithm?" The answer is perfectly in keeping with what has been well known in Artificial Intelligence for over thirty years.

Terry Jones (terry <AT> jon.es)