Local Optima Networks for Constrained Search Spaces
Jonathan Edward Fieldsend, Arnaud Liefooghe, Katherine Mary Malan, Sebástien Vérel · Proceedings of the Genetic and Evolutionary Computation Conference · 2025
Local Optima Networks (LON)s have been used extensively to understand the global structure of optimisation problems and to study algorithm behaviour. The central idea is to compress the search space into a graph object capturing the local optima along with information on their basins of attraction and the connections between them. This enables the visualisation of high dimensional search spaces, and the extraction of metrics for characterising and contrasting different problem instances. In this paper we extend the canonical LON definition to encompass search spaces with constraints. We use a well-known pairwise comparison operator for constrained problems, and capture the features of the constraint violation landscape that present a challenge for such an operator, such as infeasible local traps. The concept of a constrained LON is illustrated through a range of problem instances. Most problems in the context of real-world applications have constraints. By including the notion of feasibility and constraint violation into the definition of LONs, it becomes possible to use this powerful analysis tool on a much wider range of real-world problems.