@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 = 	{},
  address =	{University of Wisconsin, Madison, Wisconsin, USA},
  publisher_address = 	{San Francisco, CA, USA},
  month = 	{22-25 July},
  note = 	{To be presented at GP-98},
  publisher = 	{Morgan Kaufmann},
  email       = {W.B.Langdon@cs.bham.ac.uk, R.Poli@cs.bham.ac.uk},
  keywords =    {genetic algorithms, genetic programming, Santa Fe trail, Random Search (Monte Carlo sampling), Fitness Landscape, Building blocks, Ramped Half-and-half},
  ISBN =        {},
  url =         {ftp://ftp.cs.bham.ac.uk/pub/authors/W.B.Langdon/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 langdon:1998:antspaceTR}
)