Fitness causes bloat: Mutation

The problem of evolving, using mutation, an articial ant to follow the Santa Fe trail is used to study the well known genetic programming feature of growth in solu-tion length. Known variously as \bloat", \ u " and increasing \structural complex-ity", this is often described in terms of in-creasing \redundancy " in the code caused by \introns". Comparison between runs with and with-out tness selection pressure, backed by Price's Theorem, shows the tendency for solutions to grow in size is caused by tness based selection. We argue that such growth is inherent in using a xed evaluation func-tion with a discrete but variable length rep-resentation. With simple static evaluation search converges to mainly nding trial so-lutions with the same tness as existing trial solutions. In general variable length allows many more long representations of a given solution than short ones. Thus in search (without a length bias) we expect longer representations to occur more often and so representation length to tend to in-crease. I.e. tness based selection leads to bloat.