The Evolution of Size and Shape
Advances in Genetic Programming 3, chapter 8, MIT Press, Cambridge, MA, USA, (June 1999)Abstract
The phenomenon of growth in program size in genetic
programming populations has been widely reported. In a
variety of experiments and static analysis we test the
standard protective code explanation and find it to be
incomplete. We suggest bloat is primarily due to
distribution of fitness in the space of possible
programs and because of this, in the absence of bias,
it is in general inherent in any search technique using
a variable length representation.
We investigate the fitness landscape produced by
program tree-based genetic operators when acting upon
points in the search space. We show bloat in common
operators is primarily due to the exponential shape of
the underlying search space. Nevertheless we
demonstrate new operators with considerably reduced
bloating characteristics. We also describe mechanisms
whereby bloat arises and relate these back to the shape
of the search space. Finally we show our simple random
walk entropy increasing model is able to predict the
shape of evolved programs.