Search trajectory networks: A tool for analysing and visualising the behaviour of metaheuristics

Citation

Ochoa G, Malan KM & Blum C (2021) Search trajectory networks: A tool for analysing and visualising the behaviour of metaheuristics. Applied Soft Computing, 109, Art. No.: 107492. https://doi.org/10.1016/j.asoc.2021.107492

Abstract
A large number of metaheuristics inspired by natural and social phenomena have been proposed in the last few decades, each trying to be more powerful and innovative than others. However, there is a lack of accessible tools to analyse, contrast and visualise the behaviour of metaheuristics when solving optimisation problems. When the metaphors are stripped away, are these algorithms different in their behaviour? To help to answer this question, we propose a data-driven, graph-based model, search trajectory networks (STNs) in order to analyse, visualise and directly contrast the behaviour of different types of metaheuristics. One strength of our approach is that it does not require any additional sampling or algorithmic methods. Instead, the models are constructed from data gathered while the metaheuristics are solving the optimisation problems. We present our methodology, and consider in detail two case studies covering both continuous and combinatorial optimisation. In terms of metaheuristics, our case studies cover the main current paradigms: evolutionary, swarm, and stochastic local search approaches.

Keywords
Algorithm analysis; Search trajectories; Complex networks; Continuous optimisation; Combinatorial optimisation; Visualisation

Journal
Applied Soft Computing: Volume 109

People

Professor Gabriela Ochoa

Professor, Computing Science