- 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=10.1.1.40.6500",
-
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}",
