Index of /pub/terry/phd

      Name                    Last modified       Size  Description


[DIR] Parent Directory        28-Aug-1995 14:33      -  
[   ] part00.ps.gz            30-May-1995 19:13    36k  
[   ] part01.ps.gz            30-May-1995 19:13    33k  
[   ] part02.ps.gz            30-May-1995 19:13    90k  
[   ] part03.ps.gz            30-May-1995 19:13   126k  
[   ] part04.ps.gz            30-May-1995 19:13    76k  
[   ] part05.ps.gz            30-May-1995 19:13   633k  
[   ] part06.ps.gz            30-May-1995 19:13    43k  
[   ] part07.ps.gz            30-May-1995 19:13    87k  
[   ] phd.ps.gz               30-May-1995 19:13   986k  


This directory contains compressed postscript files of my dissertation.

The entire dissertation is in phd.ps.gz.  If you are on UNIX, you may
want to print this using "lpr -s phd.ps" which will cause the printer
software to make a symbolic link to the file rather than copying it
(if you use -s you cannot remove phd.ps until the printing is done).
If this is too big for you to transfer or print, there are also 8 smaller
files part00.ps.gz to part07.ps.gz that you can grab.

  part00.ps.gz (25 pages) Title, Abstract, Lists, Abbreviations etc.
  part01.ps.gz (12 pages) Introduction
  part02.ps.gz (34 pages) A Model of Landscapes
  part03.ps.gz (38 pages) Crossover, Macromutation & Population-based Search
  part04.ps.gz (36 pages) Reverse Hillclimbing
  part05.ps.gz (41 pages) Evolutionary Algorithms and Heuristic Search
  part06.ps.gz (19 pages) Related Work & Conclusions
  part07.ps.gz (44 pages) Appendices & Bibliography

These files all need to be uncompressed (via gunzip). Gunzip is 
available from prep.ai.mit.edu in pub/gnu. If you don't want to go
to the trouble of installing gzip/gunzip, you can get an uncompressed
copy in the directory 'uncompressed' if that exists. If not, mail
me and I'll help you out.

If you do not have access to a postscript printer, you can get a
hardcopy of the dissertation by requesting SFI TR 95-05-048 from
mat@santafe.edu. 

Terry Jones (terry@santafe.edu).

----------------------------------------------------------------------------


        Evolutionary Algorithms, Fitness Landscapes and Search

                                  by

                             Terry Jones

                    Department of Computer Science
                       University of New Mexico
                         Albuquerque NM 87131
                          terry@santafe.edu




                               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@santafe.edu).