W. Langdon, and R. Poli. Genetic Programming 1998: Proceedings of the Third
Annual Conference, page 193--201. University of Wisconsin, Madison, Wisconsin, USA, Morgan Kaufmann, (22-25 July 1998)
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.
%0 Conference Paper
%1 langdon:1998:antspace
%A Langdon, W. B.
%A Poli, R.
%B Genetic Programming 1998: Proceedings of the Third
Annual Conference
%C University of Wisconsin, Madison, Wisconsin, USA
%D 1998
%E Koza, John R.
%E Banzhaf, Wolfgang
%E Chellapilla, Kumar
%E Deb, Kalyanmoy
%E Dorigo, Marco
%E Fogel, David B.
%E Garzon, Max H.
%E Goldberg, David E.
%E Iba, Hitoshi
%E Riolo, Rick
%I Morgan Kaufmann
%K (Monte Building Carlo Fe Fitness Half-and-half Landscape, Ramped Random Santa Search algorithms, blocks, genetic programming, sampling), trail,
%P 193--201
%T Why Ants are Hard
%U http://www.cs.bham.ac.uk/~wbl/ftp/papers/WBL.antspace_gp98.ps.gz
%X 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.
%@ 1-55860-548-7
@inproceedings{langdon:1998:antspace,
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.},
added-at = {2008-06-19T17:35:00.000+0200},
address = {University of Wisconsin, Madison, Wisconsin, USA},
author = {Langdon, W. B. and Poli, R.},
biburl = {https://www.bibsonomy.org/bibtex/296ccfb2def9d3a51724416cd05e9308c/brazovayeye},
booktitle = {Genetic Programming 1998: Proceedings of the Third
Annual Conference},
editor = {Koza, John R. and Banzhaf, Wolfgang and Chellapilla, Kumar and Deb, Kalyanmoy and Dorigo, Marco and Fogel, David B. and Garzon, Max H. and Goldberg, David E. and Iba, Hitoshi and Riolo, Rick},
interhash = {7cc16e612daed1290206d88d12980105},
intrahash = {96ccfb2def9d3a51724416cd05e9308c},
isbn = {1-55860-548-7},
keywords = {(Monte Building Carlo Fe Fitness Half-and-half Landscape, Ramped Random Santa Search algorithms, blocks, genetic programming, sampling), trail,},
month = {22-25 July},
notes = {GP-98. Based on \cite{langdon:1998:antspaceTR}},
pages = {193--201},
publisher = {Morgan Kaufmann},
publisher_address = {San Francisco, CA, USA},
size = {9 pages},
timestamp = {2008-06-19T17:44:50.000+0200},
title = {Why Ants are Hard},
url = {http://www.cs.bham.ac.uk/~wbl/ftp/papers/WBL.antspace_gp98.ps.gz},
year = 1998
}