A model for characterising the collective dynamic behaviour of evolutionary algorithms

Exploration and exploitation are considered essential notions in evolutionary algorithms. However, a precise interpretation of what constitutes exploration or exploitation is clearly lacking and so are specific measures for characterising such notions. In this paper, we start addressing this issue by presenting new measures that can be used as indicators of the exploitation behaviour of an algorithm. These work by characterising the extent to which available information guides the search. More precisely, they quantify the dependency of a population's activity on the observed fitness values and genetic material, utilising an empirical model that uses a coarse-grained representation of population dynamics and records information about it. The model uses the k-means clustering algorithm to identify the population's "basins of activity". The exploitation behaviour is then captured by an entropy-based measure based on the model that quantifies the strength of the association between a population's activity distribution and the observed fitness landscape information. In experiments, we analysed the effects of the search operators and their parameter settings on the collective dynamic behaviour of populations. We also analysed the effect of using different problems on algorithm behaviours.We define a behavioural landscape for each problem to identify the appropriate behaviour to achieve good results and point out possible applications for the proposed model.