Quantifying the Exploration Performed by Metaheuristics

In this article we propose a formalisation of the concept of exploration performed by metaheuristics. In particular, we define and test a method for studying this aspect regardless of the specific approach implemented. Understanding the behaviour of metaheuristics is important for being able to boost their results. Measuring the exploration performed may help increase this understanding. We propose an experimental analysis to show how the measure of exploration defined may be used to this aim. We quantify the different level of exploration implied by different parameter settings in an ant colony optimisation and in a genetic algorithm for the travelling salesman problem. The results suggest that it may be possible to establish a relation between exploration and performance of the algorithm. © 2012 Copyright Taylor and Francis Group, LLC