Evolutionary computation is a well-known example of a complex system. It is composed of many “moving parts” — the individuals of the population, which interact through competition based on fitness, and through the genetic operations of recombination and mutation.
An important issue throughout evolutionary computation is the exploration-exploitation trade-off. Should the algorithm try to exploit information it has already gathered, ie concentrate on known-good areas of the search space, or should it try to explore further afield? Although this topic has been studied extensively, there has been little work aiming to quantify the behaviour of an algorithm in this regard.
As a building block in the study of complex evolutionary systems, we focus on quantifying the exploration-exploitation behaviour of mutation operators. We propose an analytical measure: highly exploitative operators are associated with higher values for this measure, and highly explorative operators with lower values. It is tested in search spaces of bitstrings, permutations, and trees, and it is shown that the measure has predictive power. Analysis of the results across spaces of different sizes leads to a correction factor making the measure scale-independent. The implications of this measure and related methods for the choice of operators in practical search algorithms are described.
