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