The University of Sussex

Evolvability, neutrality and search difficulty

Tom Smith, Phil Husbands, Michael O'Shea

Analysis of problem search spaces is crucial if we are to use artificial evolutionary techniques to produce good solutions to difficult problems. In this paper, we apply the concept of evolvability in order to highlight the differences between two non-trivial search spaces, for which significant differences in the time required to evolve good solutions has previously been shown. We define a set of evolvability metrics based on the distribution of solution offspring fitnesses, and show that the metrics do predict the difficulty of finding good solutions in a class of tunably rugged and neutral landscapes. In applying the metrics to the search space defined by a robotics visual shape discrimination task, we find no evidence that evolvability changes during neutral epochs. However, the evolvability measures do show differences between the search spaces defined by two different robot control architectures. In particular we see a decrease in the number of non-deleterious mutations for one architecture, allowing the evolving population to contain a larger number and variety of good genotypes on which the evolutionary process can work.

Download compressed postscript file