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