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


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.

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.

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

Applied Soft Computing: Volume 109

FundersNational Research Foundation, Ministerio de Ciencia e Innovación and Ministerio de Ciencia e Innovación
Publication date30/09/2021
Publication date online14/05/2021
Date accepted by journal05/05/2021
PublisherElsevier BV

Research centres/groups