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.


James Michael McDermott James McDermott has research interests in analytics, evolutionary design, and genetic programming. He was an Irish Research Council - Marie Curie post-doctoral fellow in Massachusetts Institute of Technology and is now lecturer and MSc programme director in Business Analytics in the Lochlann Quinn School of Business, University College Dublin. He was co-chair of EvoMUSART 2013 and 2014 and publication chair of EuroGP 2015, and will be co-chair of EuroGP 2016. He is associate editor of the ACM SIGEvolution newsletter.

Evolutionary computation methods e-session