A Network Science Approach to Analysing, Comparing, and Evaluating Population-based Metaheuristics

Abstract

Inspired by natural processes such as evolution and collective animal behaviour, population-based metaheuristics have gained popularity due to their ability to solve complex optimisation problems. However, understanding these algorithms' underlying principles and behaviours remains a challenge. This dissertation proposes using interaction networks as a framework to model and study the behaviour of population-based metaheuristics. We present three case studies involving eleven algorithms tested on ten optimisation problems. The results demonstrate that the characteristics of the interaction networks, including degree distribution, number of hubs, and clusters, are closely tied to the underlying aspects of the algorithms. Structural similarities between networks are measured using metrics such as portrait divergence, allowing for comparisons of behaviour across different sources of inspiration. Convergence patterns and exploration-exploitation capabilities are identified by analysing the network evolution and measuring the portrait divergence. Additionally, this framework allows for the evaluation of the impact of operators and parameters on algorithms behaviour. Compared to similar network-based frameworks, the results suggest the existence of unique network structures arising from capturing different aspects of the algorithms. Finally, clustering methods are employed to group them based on their interaction patterns or search trajectories, leading to two novel classifications of population-based metaheuristics that consider only these facets.