Supplementary material for GECCO 2025 Paper "Local Optima Networks for Constrained Search Spaces"

Content (Please, start by uncompressing zip files) gecco2025_01_colon_examples.R creates all the CoLON visualizations provided in the paper (also availble in fig/) gecco2025_02_create_instances_rhomnk.sh creates the ρmnk-instances used in the statistical analysis gecco2025_03_compute_obj_rhomnk.py computes the fitness and violation values of all solutions from ρmnk-instances gecco2025_04_compute_CoLON.py computes the CoLON of ρmnk-instances gecco2025_05_colon_analysis.py computes the metrics of the CoLON of ρmnk-instances Reference Jonathan Fieldsend, Arnaud Liefooghe, Katherine Malan, Sébastien Verel. Local optima networks for constrained search spaces. Genetic and Evolutionary Computation Conference Companion (GECCO 2025), Málaga, Spain, 2025 Abstract 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.