Why Ants are Hard

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

  author =       "W. B. Langdon and R. Poli",
  title =        "Why Ants are Hard",
  institution =  "University of Birmingham, School of Computer Science",
  year =         "1998",
  number =       "CSRP-98-4",
  month =        jan,
  note =         "Presented at GP-98",
  keywords =     "genetic algorithms, genetic programming",
  file =         "/1998/CSRP-98-04.ps.gz",
  URL =          "ftp://ftp.cs.bham.ac.uk/pub/tech-reports/1998/CSRP-98-04.ps.gz",
  URL =          "http://www.cs.ucl.ac.uk/staff/W.Langdon/antspace_csrp-98-04/",
  URL =          "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=",
  abstract =     "The problem of programming an artificial ant to follow
                 the Santa Fe trail is used as an example program search
                 space. Analysis of shorter solutions shows they have
                 many of the characteristics often ascribed to manually
                 coded programs. Enumeration of a small fraction of the
                 total search space and random sampling characterise it
                 as rugged with many 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. These 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.

                 Previously reported genetic programming, simulated
                 annealing and hill climbing performance is shown not to
                 be much better than random search on the Ant problem.",
  notes =        "See also \cite{langdon:1998:antspace}",

Genetic Programming entries for William B Langdon Riccardo Poli