This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

Evolutionary Algorithms, Fitness Landscapes and Search

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Terry Jones
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" algorithms is presented that allows the determination of details of the basin of attraction 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 heuristic functions, a measure of search difficult is obtained. The measure, fitness distance correlation, is a remarkably reliableble 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.

Download Info
To our knowledge, this item is not available for download. To find whether it is available, there are three options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page whether it is in fact available.
3. Perform a search for a similarly titled item that would be available.

Publisher Info
Paper provided by Santa Fe Institute in its series Working Papers with number 95-05-048.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length:
Date of creation: May 1995
Date of revision:
Handle: RePEc:wop:safiwp:95-05-048

Contact details of provider:
Postal: 1399 Hyde Park Road, Santa Fe, New Mexico 87501
Web page: http://www.santafe.edu/sfi/publications/working-papers.html
More information through EDIRC

For technical questions regarding this item, or to correct its listing, contact: (Thomas Krichel).

Related research
Keywords:

Cited by:
(explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)

  1. Koen Frenken & Luigi Marengo & Marco Valente, 1999. "Interdependencies, nearly-decomposability and adaption," CEEL Working Papers 9903, Computable and Experimental Economics Laboratory, Department of Economics, University of Trento, Italia. [Downloadable!]
Statistics
Access and download statistics

Did you know? All top Economics journals are listed on RePEc.

This page was last updated on 2009-12-16.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.