Advertisement

Search, Binary Representations and Counting Optima

  • Soraya Rana
  • L. Darrell Whitley
Chapter
Part of the The IMA Volumes in Mathematics and its Applications book series (IMA, volume 111)

Abstract

Choosing a good representation is a vital component of solving any search problem. However, choosing a good representation for a problem is as difficult as choosing a good search algorithm for a problem. Wolpert and Мacready’s No Free Lunch theorem proves that no search algorithm is better than any other over all possible discrete functions. We elaborate on the No Free Lunch theorem by proving that there tend to be a small set of points that occur as local optima under almost all representations. Along with the analytical results, we provide some empirical evaluation of two representations commonly used in genetic algorithms: Binary Reflected Gray coding and standard Binary encoding.

Key words

genetic algorithms evolutionary computing search mathematical foundations 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. [1]
    Keith E. Mathias and L. Darrell Whitley, Changing representations during search: A comparative study of delta coding,Journal of Evolutionary Computation, 2 (3) pp. 249–278, 1994.CrossRefGoogle Scholar
  2. [2]
    H. Mühlenbein, Evolution in time and space: The parallel genetic algorithm,In G. Rawlins, editor, Foundations of Genetic Algorithms, pp. 316–337, Morgan Kaufmann, 1991.Google Scholar
  3. [3]
    Nicholas J. Radcliffe and Patrick D. Surry, Fundamental limitations on search algorithms: Evolutionary computing in perspective,In Jan van Leeuwen, editor, Lecture Notes in Computer Science, volume 1000 Springer-Verlag, 1995.Google Scholar
  4. [4]
    Darrell Whitley, Keith Mathias, Soraya Rana, and John Dzubera, Evaluating evolutionary algorithms, Artificial Intelligence Journal, 85 August 1996.Google Scholar
  5. [5]
    David H. Wolpert and William G. Macready, No free lunch theorems for search, Technical Report SFI-TR-95–02–010, Santa Fe Institute, July 1995.Google Scholar

Copyright information

© Springer Science+Business Media New York 1999

Authors and Affiliations

  • Soraya Rana
    • 1
  • L. Darrell Whitley
    • 1
  1. 1.Computer Science DepartmentColorado State UniversityFort CollinsUSA

Personalised recommendations