Why Ants are Hard

Created by W.Langdon from gp-bibliography.bib Revision:1.2031

@InProceedings{langdon:1998:antspace,
  author =       "W. B. Langdon and R. Poli",
  title =        "Why Ants are Hard",
  booktitle =    "Genetic Programming 1998: Proceedings of the Third
                 Annual Conference",
  year =         "1998",
  editor =       "John R. Koza and Wolfgang Banzhaf and 
                 Kumar Chellapilla and Kalyanmoy Deb and Marco Dorigo and 
                 David B. Fogel and Max H. Garzon and 
                 David E. Goldberg and Hitoshi Iba and Rick Riolo",
  pages =        "193--201",
  address =      "University of Wisconsin, Madison, Wisconsin, USA",
  publisher_address = "San Francisco, CA, USA",
  month =        "22-25 " # jul,
  publisher =    "Morgan Kaufmann",
  keywords =     "genetic algorithms, genetic programming, Santa Fe
                 trail, Random Search (Monte Carlo sampling), Fitness
                 Landscape, Building blocks, Ramped Half-and-half",
  ISBN =         "1-55860-548-7",
  URL =          "http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/WBL.antspace_gp98.pdf",
  URL =          "http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/WBL.antspace_gp98.ps.gz",
  URL =          "http://www.cs.bham.ac.uk/~wbl/ftp/papers/WBL.antspace_gp98.ps.gz",
  size =         "9 pages",
  abstract =     "The problem of programming an artificial ant to follow
                 the Santa Fe trail is used as an example program search
                 space. genetic programming, simulated annealing and
                 hill climbing performance is shown not to be much
                 better than random search on the Ant
                 problem.

                 Enumeration of a small fraction of the total search
                 space and random sampling characterise it as rugged
                 with multiple plateaus split by deep valleys and many
                 local and global optima. This suggests it is difficult
                 for hill climbing algorithms.

                 Analysis of the program search space in terms of fixed
                 length schema suggests it is highly deceptive and that
                 for the simplest solutions large building blocks must
                 be assembled before they have above average fitness. In
                 some cases we show solutions cannot be assembled using
                 a fixed representation from small building blocks of
                 above average fitness. This suggest the Ant problem is
                 difficult for Genetic Algorithms.

                 Random sampling of the program search space suggests on
                 average the density of global optima changes only
                 slowly with program size but the density of neutral
                 networks linking points of the same fitness grows
                 approximately linearly with program length. This is
                 part of the cause of bloat.",
  notes =        "GP-98. Based on \cite{langdon:1998:antspaceTR}",
}

Genetic Programming entries for William B Langdon Riccardo Poli