Search Trajectory Networks of Population-based Algorithms in Continuous Spaces

Citation

Ochoa G, Malan KM & Blum C (2020) Search Trajectory Networks of Population-based Algorithms in Continuous Spaces. In: Castillo PA, Jiménez Laredo JL & Fernández de Vega F (eds.) Applications of Evolutionary Computation. EvoApplications 2020. Lecture Notes in Computer Science, 12104. Applications of Evolutionary Computation – 23rd International Conference, EvoApplications 2020, Seville, Spain, 15.04.2020-17.04.2020. Cham, Switzerland: Springer, pp. 70-85. https://doi.org/10.1007/978-3-030-43722-0_5

Abstract
We introduce search trajectory networks (STNs) as a tool to analyse and visualise the behaviour of population-based algorithms in continuous spaces. Inspired by local optima networks (LONs) that model the global structure of search spaces, STNs model the search tra-jectories of algorithms. Unlike LONs, the nodes of the network are not restricted to local optima but instead represent a given state of the search process. Edges represent search progression between consecutive states. This extends the power and applicability of network-based models to understand heuristic search algorithms. We extract and analyse STNs for two well-known population-based algorithms: particle swarm optimi-sation and differential evolution when applied to benchmark continuous optimisation problems. We also offer a comparative visual analysis of the search dynamics in terms of merged search trajectory networks.

Keywords
Continuous Optimisation; Local Optima Networks; Metaheuristics Behaviour; Search Trajectory Networks

People

Professor Gabriela Ochoa

Professor, Computing Science