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.
Users
Please
log in to take part in the discussion (add own reviews or comments).