# Local optima networks for constrained search spaces

Jonathan E. Fieldsend, Arnaud Liefooghe, Katherine M. Malan, Sébastien Verel

► To cite this version:

Jonathan E. Fieldsend, Arnaud Liefooghe, Katherine M. Malan, Sébastien Verel. Local optima networks for constrained search spaces. GECCO 2025 – Genetic and Evolutionary Computation Conference, Jul 2025, Malaga, Spain. pp.204-212, 10.1145/3712256.3726303. hal-05022611

HAL Id: hal-05022611

https://hal.science/hal-05022611v1

Submitted on 7 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Local Optima Networks for Constrained Search Spaces

Jonathan E. Fieldsend

J.E Fieldsend@exeter.ac.uk

University of Exeter

Exeter, UK

Katherine M. Malan

malankm@unisa.ac.za

University of South Africa

Pretoria, South Africa

Arnaud Liefooghe

arnaud.liefooghe@univ-littoral.fr

Univ. Littoral Côte d'Opale, UR 4491, LISIC

F-62100 Calais, France

Sébastien Verel

verel@univ-littoral.fr

Univ. Littoral Côte d'Opale, UR 4491, LISIC

F-62100 Calais, France

## Abstract

Local Optima Networks (LONs) 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.

## CCS Concepts

* Mathematics of computing → Combinatorial optimization;
* Graph theory; *Human-centered computing* → Visualization;
* Visualization design and evaluation methods.

## Keywords

landscape analysis, constraint handling, explainability, visualisation

## ACM Reference Format:

Jonathan E. Fieldsend, Arnaud Liefooghe, Katherine M. Malan, and Sébastien Verel. 2025. Local Optima Networks for Constrained Search Spaces. In *Genetic and Evolutionary Computation Conference (GECCO '25), July 14–18, 2025, Malaga, Spain*. ACM, New York, NY, USA, 9 pages. https://doi.org/10.1145/3712256.3726303

<figure><img src="image_2.png" /></figure>

This work is licensed under a Creative Commons Attribution 4.0 International License.
GECCO '25, Malaga, Spain

© 2025 Copyright held by the owner/author(s).

ACM ISBN 979-8-4007-1465-8/2025/07

https://doi.org/10.1145/3712256.3726303

## 1 Introduction

Fitness landscape analysis started as a largely theoretical notion in evolutionary computation, but has recently been applied in practical ways to analyse many different types of search spaces from multi-objective landscapes [7] and landscapes of systems biology models [5], to error landscapes in machine learning [17]. Techniques have been proposed for analysing search landscapes over the last few decades (for a catalogue see [17, 18]). Arguably the two most widely applied approaches developed in the last 15 years are Local Optima Networks (LONs) [22], mostly used in the context of discrete search spaces<fnref n="1" />, and Exploratory Landscape Analysis (ELA) [21] for continuous search spaces, with the associated `flacco` package [11]. These two approaches are, however, not defined for constrained search spaces (beyond search space bounds — i.e. “box” constraints in continuous spaces). This significantly reduces their usefulness in practice, given the pervasiveness of constraints in real-world problem scenarios.

There has been some work on applying landscape analysis to constrained search spaces. Malan et al. [20] introduced the notion of a violation landscape and defined metrics for characterising these landscapes in relation to fitness for continuous spaces. These metrics were later applied to combinatorial spaces [19], and used as the basis for automated constraint handling selection for metaheuristics [13, 15, 16]. Recent studies by Vodopija et al. [28] and Alsouly et al. [2] extended these ideas into the domain of multi-objective constrained search spaces.

As a search landscape analysis technique, LONs provide a graph-based model of a high-dimensional search space that can be visualised in two or three dimensions using layout algorithms. The LON graph is constructed by extracting the local optima and analysing how these local optima are positioned in the search space in relation to other optima. The nodes of the graph are optima and the edges represent neighbourhood between the basins of attraction surrounding optima. In this way, a LON is a high-level representation of the global structure of the search space and can capture (through visualisations and graph metrics) how easy or difficult it could be for search algorithms to find good solutions.

LONs have been widely used to gain insight into complex optimisation problems. Some examples of the practical application of LONs include: analysing the neural architecture search spaces of convolutional neural networks for image classification [23]; explaining the effect of different encodings on the difficulty experienced

<footnote n="1">¹For approaches to applying LONs to continuous spaces, see e.g. [1, 6, 7, 27].</footnote>
by search algorithms in simultaneously optimising robot design and controllers [24]; the influence of different optimization criteria and variation operators on the task of optimising Boolean function construction [8]; and understanding the complexity of tuning hyperparameters for search algorithms [3].

Building on the success of LONs, we provide the following contributions in this work:

(1) We extend the LON framework to represent constrained problems, embedding preorder operators [4] in the widely-employed hill-climb approach for LON construction, to derive local optima.

(2) We introduce the concept of infeasible traps (and corresponding distinct graph nodes) to denote regions where local search results in an infeasible solution, highlighting when particularly explorative search will be required for problems.

(3) We introduce the concept of hybrid basins which straddle feasible and infeasible regions, and convey the proportion of support derived from these distinct region types.

(4) We derive two edge forms, which capture paths exclusively through feasible regions, and those which cross infeasible regions.

(5) We introduce the constrained LON, which combines both feasible and infeasible space into a single graph.

(6) We illustrate constrained LONs for a range of problem types and forms.

The work proceeds as follows. Section 2 sets out the standard definition and components of a LON, Section 3 describes the properties of some common constraint types, Section 4 details our proposal, and Section 5 illustrates the constrained LONs induced by a range of different problems. The work concludes with a summary in Section 6, which also details some future research directions.

## 2 Characterising Problem Structure using LONs

Without loss of generality let us consider optimisation problems of the form<fnref n="2" />

$$ \mathbf{x}^* = \arg \max_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x}) \quad (1) $$

where $\mathcal{X}$ is the given search domain. The LON is a graph object (i.e. nodes and edges) which seeks to convey the structure of $f$ – particularly the relative sizes of the basins supporting local optima (the proportion of local search paths which lead to each optima), and how easy/difficult it is to navigate between different optima/basins of attraction.

In order to construct a LON, one must have defined the tuple $(\mathcal{X}, f, N, L)$, where $\mathcal{X}$ and $f$ are as described above. $N(\mathbf{x})$ is a neighbourhood function which returns the set of neighbours of a given $\mathbf{x}$, and $L(N, \mathbf{x})$ is a local search algorithm, which given a neighbourhood function and a starting solution $\mathbf{x}$, returns the corresponding local optimum reached by commencing the local search from $\mathbf{x}$. As an example, where the search space is all bit-strings of length $n$ (i.e. $\mathcal{X} = \{0, 1\}^n$) then $N(\mathbf{x})$ may be the Hamming distance neighbourhood of distance 1 (i.e. all single bit-flip neighbours), and the local search algorithm $L$ may be a simple hill-climber (see Section 4).

Once the optima corresponding to a sample of locations in $\mathcal{X}$ are identified via $L$, the (approximated) LON can be built. The number of nodes in the graph equals the number of unique optima identified (in $\mathcal{X}$), node size is commonly proportional to their basin size, and node colour reflective of the corresponding optima quality.

Edges may be constructed in different ways, to reflect different procedures to explore beyond the local basins of attraction. Two popular approaches are (i) basin transitions [22], where local search is conducted from the set of neighbours of each basin membership for each optima in turn, and the resultant end points tracked (and linked); (ii) escape edges [25], where local search is conducted from each optima in turn, using a larger neighbourhood than that used to construct the basins. In both cases, nodes may have a self-loop (denoting that the set of neighbours includes other solutions from the same basin) and may have links to other nodes (indicating that the neighbour set considered includes solutions from other basins).

## 3 Types of Constrained Problems

Beyond the optimisation task set out in Eq. (1), there are often in practice further constraints which partition $\mathcal{X}$ into regions of feasible (legal) and infeasible (illegal) solutions. Feasible solutions being those that satisfy the inequality $(g_i)$ and equality $(h_i)$ constraints:

$$ g_i(\mathbf{x}) \le 0, \quad \forall i \quad (2) $$

$$ h_j(\mathbf{x}) = 0, \quad \forall j. \quad (3) $$

These may take different forms, and have varying interaction with $f$ – the most prominent being:

* a constraint function evaluation returns a degree of violation which therefore can inform the user/algorithm how far from satisfying the constraint(s) a solution is;

* a constraint function evaluation returns only one of two values (in effect a Boolean) denoting the constraint has been violated or satisfied, but no indication of the degree to which either state has occurred;

* when a constraint is violated, the corresponding $f(\mathbf{x})$ may still yield a value, or may have a null response for illegal solutions.

Figure 1 provides an illustration of the above types for a simple 1-dimensional continuous space, with a non-linear objective function, a non-linear inequality constraint, and two linear inequality constraints (these latter defining the two box constraints for the particular problem).

In general, the inequality and equality constraint violations are summarised into a single function $v(\mathbf{x})$ as:

$$ v(\mathbf{x}) = \sum_{i} w_i \max(0, g_i(\mathbf{x})) + \sum_{j} \omega_j I_{\text{true}}(h_j(\mathbf{x}) \neq 0) \quad (4) $$

where violation is given as a degree, and

$$ v(\mathbf{x}) = I_{\text{true}} \left( \sum_{i} \max(0, g_i(\mathbf{x})) + \sum_{j} I_{\text{true}}(h_j(\mathbf{x}) \neq 0) > 0 \right) \quad (5) $$

when violation is binary. The violation function $g_i(\mathbf{x})$ returns a negative value when the $\mathbf{x}$ is legal, and a positive value when it violates the $i$th constraint (whose magnitude denotes the degree of

<footnote n="2">²We restrict ourselves to single objective problems in this work, but highlight that multi-objective problems may also be characterised by graph structures inspired by LONs, e.g. [7, 12, 14].</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 1: Illustration of some different forms of constraint and objective function interaction. Blue line denotes *f*, red line denotes *v*. Box-constraint locations are indicated with a dashed black line. (a) Constraint function returns the degree of violation. (b) Constraint returns a Boolean (zero/one) violation value. (c) *f* returns null when *x* is infeasible.</figcaption></figure>

violation). *I*<sub>true</sub> returns 1 if the argument is true and returns 0 if it is false. All weighting terms *w*<sub>i</sub> and *ω*<sub>j</sub> are strictly positive.<fnref n="3" />

Constraints are often an important component of an optimisa-
tion problem, heavily influencing the difficulty of the task. Until
this point, they have been largely ignored in the work develop-
ing various LON approaches, which has tended to be restricted
to unconstrained bit-string domain problems, or box-constrained
continuous spaces—where the box-constraints simply define X
(meaning infeasible solutions are not considered during the search).
Fieldsend [6] discusses the handling of constraints in a LON, but
limits this to simply discarding any violating samples (i.e. excluding
them from neighbourhood generation, or potential start locations
for local search). In contrast, we propose here to directly include
constraint violating solutions in the construction of LONs used
to describe constrained problems, so that the effect of infeasible
regions on the landscape structure can be conveyed. To accomplish
this, we need to consider what local search looks like in infeasible
regions, the boundaries between feasible and infeasible space, and
how to define the new components and edge definitions for this
richer landscape. We now set out our proposals.

4 LONs for Constrained Spaces

A widely used local search method in the LON construction frame-
work is that of hill-climbing. Given a candidate solution x, the
hill-climbing approach queries the neighbourhood of this solution,
via N(x), and in the greedy hill-climbing approach moves to the
best performing member of N(x), subject to it performing better
than x. In first-improving hill-climbing, the algorithm moves to
the first processed neighbour which is better (usually with a ran-
domised processing order). In both cases the hill-climbing process is
repeated until no better solution is identified in the neighbourhood,
resulting in the hill-climb being terminated and the current location
being yielded as the local optima associated with the solution used
to initiate the hill-climb.

An immediate question is how we might extend the hill-climb
idea to infeasible spaces. Dealing with, and navigating across, in-
feasible spaces has long been an area of active research in applied
optimisation. A popular approach is that of Deb [4], which allows
a pairwise comparison of solutions drawn from any regions in X.
We can derive the better operator (▶) based on Deb's preorder [4] to
compare two candidate solutions, a and b. We can identify whether

<table><caption>Algorithm 1 Greedy hill-climbing: hill_climb(Χ, x)</caption>
  <tbody>
    <tr>
      <td>Require: X</td>
      <td>▷ Search domain</td>
    </tr>
    <tr>
      <td>Require: x</td>
      <td>▷ Start point of hill-climb, x ∈ X</td>
    </tr>
    <tr>
      <td>1: x<sup>end</sup> ← x</td>
      <td></td>
    </tr>
    <tr>
      <td>2: for x' ∈ N(x) do</td>
      <td>▷ Query each neighbour</td>
    </tr>
    <tr>
      <td>3: if x' ▷ x<sup>end</sup> then</td>
      <td>▷ If the neighbour is better (see Eq. (6))</td>
    </tr>
    <tr>
      <td>4: x<sup>end</sup> ← x'</td>
      <td>▷ Replace/update next location</td>
    </tr>
    <tr>
      <td>5: end if</td>
      <td></td>
    </tr>
    <tr>
      <td>6: end for</td>
      <td></td>
    </tr>
    <tr>
      <td>7: if x<sup>end</sup> ≠ x then</td>
      <td>▷ If moved to a better neighbour</td>
    </tr>
    <tr>
      <td>8: x<sup>end</sup> ← hill_climb(X, x<sup>end</sup>)</td>
      <td>▷ Recursive call to climb</td>
    </tr>
    <tr>
      <td>9: end if</td>
      <td></td>
    </tr>
    <tr>
      <td>10: return x<sup>end</sup></td>
      <td>▷ Return local optima</td>
    </tr>
  </tbody>
</table>

a is better than b, a ▷ b, as follows:

$$
(a \triangleright b) =
\begin{cases}
\text{true,} & \text{if } (v(a) \le 0) \land (v(b) > 0), \\
\text{true,} & \text{if } (v(a) > 0) \land (v(b) > 0) \land (v(a) < v(b)), \\
\text{true,} & \text{if } (v(a) \le 0) \land (v(b) \le 0) \land (f(a) > f(b)), \\
\text{false,} & \text{otherwise.}
\end{cases}
\tag{6}
$$

We can incorporate this into a hill-climbing framework (see Al-
gorithm 1) as it allows us to directly compare neighbours under
a quality measure irrespective of whether one or both of the pair
considered are infeasible. Note, in some special cases further dis-
tinctions between solutions can be made. If v(x) returns a degree
of violation (rather than a Boolean), then for two solutions which
are both feasible and of equal quality under f, we may prefer that
which is further from the infeasible region (i.e. has the lower v
value). Similarly, if f(x) is accessible in regions of infeasible space,
then for two solutions which are equally infeasible, we may prefer
to move to the solution with the better value under f.

There are emergent properties that come from using Eq. (6) in
a hill-climb to generate LONs. As we illustrate in Figure 2, such
an operator has the potential to induce basins which rather than
supporting local optima, instead support an infeasible point, which
while being better (or no worse) than all of its neighbours, is never-
theless not a permitted solution to the optimisation task. We denote
such basins traps, and the corresponding attractor locations as in-
feasible trap points. This leads to a number of interesting properties
that we can convey in our proposed constrained LON framework.

<footnote n="3"><sup>3</sup>In the examples we present later in Section 5 we use equal weights.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 2: Different forms of constraint and objective function interaction. Basin with global optimum in yellow. (a) LON for the objective function $f(x)$ illustrated in Figure 1 (constraints ignored). (b) LON for $f(x)$ only where constraints are satisfied (following [6]). (c) LON of the violation landscape $v(x)$. (d) Proposed constrained LON. (e) objective and constraint functions annotated with the improvement directions in the hill-climbs (regions beyond box-constraints not considered).</figcaption></figure>

<table><caption>Table 1: Node and edge definitions and symbols for constructing a constrained LON (yellow is used for global optima). Code is available to recreate the subsequent figures (including options to select your own colour schemes) at https://doi.org/10.5281/zenodo.15118578.</caption><thead><tr><th></th><th>Symbol</th><th>Definition</th></tr></thead><tbody><tr><td>nodes</td><td>●<br>◆<br>■</td><td><strong>Feasible basin</strong>: contains feasible points only and leads to a <strong>feasible local optimum</strong>.<br><strong>Mixed basin</strong>: contains both feasible and infeasible points and leads to a <strong>feasible local optimum</strong>.<br>(The size of the blue portion indicates the proportion of the basin that is feasible.)<br><strong>Infeasible local trap</strong>: contains infeasible points only and leads to an <strong>infeasible trap point</strong>.</td></tr><tr><td>edges</td><td>→<br>→→</td><td>Path(s) through feasible regions only.<br>Path(s) which include at least one step through an infeasible region.</td></tr></tbody></table>
## 4.1 Concept of a CoLON

Figure 2 uses the running illustration to derive a constrained LON. In the bottom subplot (Figure 2(e)), the blue points on the x-axis denote the local optima, and the red square denotes an infeasible trap point. Black arrows above $f$ and $v$ denote the direction of the hill-climb induced by Eq. (6). Vertical green lines denote the boundaries of local optima basins/infeasible local traps, and dashed red lines highlight the transition locations in $x$ between feasible and infeasible regions.

Above the fitness and violation graphs, four versions of LONs are illustrated. Figure 2(a) illustrates a LON of $f(x)$ alone, i.e. that ignores the constraints. This shows a sequence of five connected basins of attraction with the largest containing the global optimum (indicated in yellow). Figure 2(b) shows the LON of $f(x)$ restricted to feasible solutions. We see how the infeasible regions induce subgraphs of the LON that are disconnected and how the global optimum basin from the unconstrained LON has been dropped, with the optimum now in the basin on the left. The third LON (Figure 2(c)) shows the structure of $v(x)$ as if it was the objective function to minimise.

Finally, in Figure 2(d) we illustrate the constrained LON (CoLON), where a key to the symbols used is provided in Table 1. We define three types of nodes:

* A **feasible basin** (solid blue circle) that contains only feasible solutions and leads to a feasible local optimum. The size of the circle denotes the size of the basin of attraction.

* A **mixed basin** (a diamond shape in blue and red) that contains both feasible and infeasible solutions and leads to a feasible local optimum. The proportion of blue in a mixed basin is indicative of the proportion of the basin consisting of feasible solutions.

* An **infeasible local trap** (solid red square) that contains only infeasible solutions and leads to an infeasible trap point. The size of the square denotes the size of the trap.

As explained in Section 2 for standard LONs, both basin transition and escape edges can be defined for a CoLON using the same weight definitions. Edge weights are derived from the proportion of paths that connect pairs of local optima. Each path represents the sequence of solutions from $x^{start}$ to $x^{end}$ observed during the hill-climbing procedure in Algorithm 1. As a consequence, two types of edges are defined for CoLONs:

* Paths through feasible regions only (solid blue arrows). The width of the arrow is indicative of the number of feasible paths.

* Paths that must pass through at least one infeasible solution to reach the basin/trap (red dashed arrows).

In this work, we define a feasible edge's weight as the proportion of feasible paths. An alternative definition could use the proportion of feasible solutions among those encountered across paths. We keep this alternative definition open for future research.

The CoLON in Figure 2(d) illustrates each of these components. We see two feasible basins of attraction (the leftmost containing the global optimum denoted in yellow), both with many paths leading back to the basin (fat blue arrows). There are four mixed basins. The two on the left have relatively few feasible solutions (small proportions of blue), while the two on the right have larger

proportions of feasible solutions in the basins. We see from the dashed red arrows, that it is only possible to move between the two leftmost mixed basins by traversing through infeasible space. A single infeasible local trap is evident (red square) indicating that a hill-climber minimising the level of violation will become trapped.

As the illustration in Figure 2 is for a one dimensional problem, links between nodes are only ever of one of the two types for the basin transition edges, as basins abut one another at a maximum of a single solution — however we can see that self-loops for mixed basins can consist of both types. We will see in later illustrations that nodes may be connected to each other via both link types in certain circumstances.

## 4.2 Information Collected by Construction

Through the process of constructing a CoLON, we collect the following information about nodes (local optima and basins) and edges. The main node features include the fitness and violation score of the corresponding local optimum. Basins are characterised by their size, the proportion of feasible solutions they contain, and the average adaptive path length from $x^{start}$ to $x^{end}$, along with the proportion of feasible solutions on these paths. As discussed in the previous section, feasible weights can be defined either by the proportion of feasible paths or by the proportion of feasible solutions on paths between local optima. These two definitions provide different information that may be valuable depending on the chosen algorithm and constraint-handling strategy.

In this work, we analyse fully enumerable landscapes. Using a recursive strategy and the hill-climber from Algorithm 1, we compute the adaptive paths from all solutions. For binary strings of length $n$, the time complexity to enumerate the basins and local optima is $O(n \cdot 2^n)$. The enumeration of escape edges at distance 2 can be performed in $O(n_l \cdot n^2)$, where $n_l$ is the number of nodes. Our Python implementation (to be made available upon acceptance) handles equivalent neighbours by assigning probabilistic membership of solutions to multiple basins.

## 5 Illustrative Examples

This section presents selected examples that highlight key differences in CoLONs. We focus on small problems to provide an unbiased view of the landscape through complete enumeration. Following previous LON studies, we examine binary spaces with a 1-flip neighbourhood (Hamming distance 1) and escape edges using a 2-bit-flip perturbation strength.

The examples that follow were chosen to highlight the effect of different problem characteristics on the search space. Through visualisation of CoLONs we illustrate the effect on the global structure of the search space of (1) an increase in the rate of feasibility, (2) different correlation levels between the fitness and constraint violation, and (3) different levels of ruggedness in both the fitness and violation landscapes. In all the following visualisations, only edges with weights above 0.05 are shown. As such the numbers of edges in the captions may exceed the number shown in the figures.

### 5.1 Impact of Feasibility Rate

*Knapsack.* We begin by experimenting with a couple of knapsack instances, focusing on the canonical 0/1 knapsack problem [10]. In
<figure><img src="image_5.png" /><figcaption>Figure 3: CoLONs for example knapsack problems at a (a) low, and (b) high feasibility rate.</figcaption></figure>

this formulation, we have *n* items, each with a weight and profit value, along with a maximum knapsack capacity. Using binary variables to indicate whether each item is included in the knapsack, we aim to maximise total profit while keeping the total weight under capacity. For this example, we use the same *n* = 10 items with integer profits and weights randomly generated between 1 and 1000. We consider two knapsack capacities: one allowing 20% feasible solutions and another allowing 80% feasible solutions. The corresponding CoLONs are shown in Figure 3.

For these knapsack instances, increasing the feasibility rate from 20% to 80% results in a more than 5-fold increase in the number of feasible basins, while the number of mixed basins remains much the same. We also see a more connected structure (doubling of the number of feasible paths) and an increase in the size of the mixed global optimum basin.

**NK-landscapes.** We now examine more complex fitness and violation functions by extending binary NK-landscapes [9] with an added constraint. This combinatorial benchmark helps reveal how variable interactions influence the landscape difficulty. The NK-landscape model has *n* components, each contributing to the overall fitness of the solution. Each component interacts with *k* others, thus affecting its own contribution. As the number of interactions per variable (*k*) increases, the fitness function develops more local optima and becomes more rugged, making the search process harder. On top of the conventional NK-landscape fitness function, we add a constraint function that shares the same mathematical formulation but with distinct coefficients. A solution is feasible only if its constraint value falls below a specified threshold, with the violation function measuring the linear gap to feasibility. This construction is similar to the knapsack constraint, but extends beyond linear constraints. We follow the random model from Kauffman [9] for

variable interactions. The coefficients of the fitness and constraint functions are both uniformly distributed in [0, 1].

Figure 4 shows the CoLON obtained for four constrained NK-landscapes, each with *n* = 10 variables and *k* = 2 interactions per variable for both fitness and constraint functions. The constraint threshold was configured to make 1%, 20%, 80% and 99% of binary strings feasible, respectively. The impact of an increase in feasibility is visually evident in the progression from left to right in Figure 4: we see a change in colour from predominantly red to predominantly blue in both nodes and edges. We also see the only infeasible local traps in Figure 4a and the only feasible basins appear in Figure 4d.

## 5.2 Impact of Fitness-Violation Correlation

Having analysed the impact of the feasibility rate, we now explore how the correlation between fitness and constraint values shapes the CoLON. To do so, we continue our analysis with constrained NK-landscapes, this time experimenting with fitness and constraint coefficients.

Drawing from the ρMNK-landscapes benchmark generator—multi-objective NK-landscapes with correlation [26]—we generate fitness and constraint contribution values using a multivariate uniform distribution that determines the correlation between both functions. We configure the generator to create either a positive correlation between fitness and violation values or, by contrast, conflicting functions. We remark that this correlation affects only the infeasible region of the landscape, since feasible solutions always have a violation value of 0. We analyse the CoLON structure for two constrained NK-landscapes with *n* = 10, *k* = 2, and 50% feasibility. Figure 5a presents an instance with negative fitness-violation correlation while Figure 5b shows one with positive correlation.
<figure><img src="image_6.png" /><figcaption>Figure 4: CoLONs for example NK-landscapes at a (a) very low (b) low, (c) high, and (d) very high feasibility rate (no fitness-violation correlation, *k* = 2).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 5: CoLONs for NK-landscapes with (a) conflicting, and (b) correlated fitness and violation (50% feasibility, *k* = 2).</figcaption></figure>

Interestingly, the landscape with conflicting fitness and violation functions generates significantly more local optima. While there is one basin of attraction with 100% feasibility, it is among the smallest, with all other nodes being mixed basins. In contrast, landscapes with positively correlated fitness and violation functions contain significantly fewer nodes—all mixed basins—with sparse connections through infeasible regions. This pattern makes sense because improving fitness naturally leads to being closer to feasibility and vice versa, creating an easier landscape to navigate. In both cases, the global optimum resides in one of the largest basins.

## 5.3 Impact of Fitness and Violation Ruggedness

Up to this point, we have analysed constrained NK-landscapes where both the fitness and constraint functions share the same (moderate) level of ruggedness. A key question emerges: How does the CoLON structure change when fitness and constraint functions have different levels of ruggedness—that is, when the constraint is smoother than the fitness or the other way around?

Figure 6 contrasts two CoLON examples: one with a rugged fitness function (*k* = 4) paired with a smooth constraint (*k* = 1), and another with a smooth fitness function (*k* = 1) paired with a rugged constraint (*k* = 4). Both examples use constrained NK-landscapes with *n* = 10, 50% feasibility, and independent fitness and violation values.

An intriguing difference emerges between the two landscapes. With half of the solutions being feasible (50% feasibility in both cases), a smooth fitness landscape with a rugged violation landscape in Figure 6b depicts a much less complex global structure, consisting of 5 mixed basins with the global basin being the largest. In contrast, the CoLON in Figure 6a contains 18 mixed basins with non-optimal basins being larger than the global basin. This suggests that it would be more challenging to find the global optimum for the instance visualised in Figure 6a. In these examples, the ruggedness of the fitness function had a larger impact on problem difficulty than the ruggedness of the violation function. Further investigation is needed to verify whether this pattern holds true in general.

<caption>Figure 6: CoLONs for example NK-landscapes with (a) rugged fitness and smooth violation, and (b) smooth fitness and rugged violation (50% feasibility, no fitness-violation correlation).</caption>
## 5.4 Insights through CoLON Metric Analysis

The insights provided by the visualisation of CoLONs can be further enhanced through analysis of metrics extracted from the graph. Using the ρ MNK-landscapes benchmark generator, we create 30 random instances with dimension n = 16 for each values of k ∈ {0, 1, 2, 4}, and a fitness-violation correlation in {-0.8, 0.0, 0.8}. Recall that, with negative correlation, both fitness and feasibility improve. Figure 7 reports the average value from metrics with respect to the feasibility rate across these constrained NK-landscapes.

The number of nodes and the graph density follow the patterns of classical LONs based on ruggedness (k) [22]. However, the number of nodes peaks at an intermediate feasible rate, with this peak shifting according to the fitness-violation correlation. When the feasible rate exceeds 5%, the proportion of infeasible local traps to total nodes remains small, but this proportion increases to about 10% at lower feasible rates. Interestingly, the proportion of infeasible solutions seen during adaptive walks falls below the overall feasible rate. This occurs because the hill-climber prioritises the selection of feasible solutions. Finally, at lower feasible rates, most edges represent paths that traverse the infeasible region rather than being entirely feasible. Ultimately, these metrics provide a comprehensive picture of the CoLON across instances with varying properties.

## 6 Conclusion and Future Work

LONs are well-established tools that provide valuable insights into complex search spaces and help analyse the challenges faced by local search and evolutionary computation algorithms in solving hard optimisation problems. By capturing key features of the search space and representing it as a graph, they enable visualisation and comparison of high-dimensional optimisation landscapes. In addition, metrics can be extracted from LONs to numerically characterise problem instances and analyse how algorithm components affect search difficulty. Until now, however, this powerful analysis tool has been limited to modelling unconstrained optimisation problems, despite constraints playing a critical role in optimisation.

With this paper, we introduce the constrained LON (CoLON) which combines both feasible and infeasible regions into a single graph. Our main contribution extends the (unconstrained) LON model to capture the interplay between fitness and violation functions, introducing concepts such as feasible and mixed local optima, and infeasible traps. We derive two types of edges between basins of attraction: paths that are exclusively feasible and those that cross infeasible regions. Through illustrative examples across different problem types, we demonstrate how the CoLON effectively characterises problem structures, including feasibility rate, fitness-constraint correlation, and the relative difficulty of fitness versus violation. The proposed model provides valuable insights into search difficulties and has important implications for constrained optimisation. We will make our code and data publicly available upon acceptance to facilitate further research in this direction.

Building on these foundations, we have identified several research directions. First, we plan to extend the model to handle multiple constraints with separate violation functions. We will also explore alternative constraint-handling mechanisms (pairwise ordering) beyond Deb's preorder. Additionally, we will investigate how the CoLON and its related network metrics can help explain

<figure><img src="image_8.png" /><figcaption>**Figure 7:** Average CoLON metrics for NK-landscapes, with different degrees of fitness-violation correlation displayed in columns.</figcaption></figure>

algorithm performance, with a particular focus on the integrated constraint-handling technique—being penalty-based methods, feasible rules, multi-objective approaches, or simply ignoring constraints. These advances will allow us to apply the CoLON concept to real-world problems, including those from continuous and mixed optimisation, thus offering deeper insights into how fitness and constraint functions interact in practical problem solving.

## Acknowledgments

JF and KM would like to thank LISIC, University of Littoral Côte d'Opale for financially supporting their research visits in October 2024, which led to this work. This work has benefited from the support of the National Research Agency under France 2030, MAIA Project ANR-22-EXES-0009.
## References

[1] Jason Adair, Gabriela Ochoa, and Katherine M. Malan. 2019. Local optima networks for continuous fitness landscapes. In *Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '19)*. ACM. https://doi.org/10.1145/3319619.3326852

[2] Hanan Alsouly, Michael Kirley, and Mario Andrés Muñoz. 2023. An Instance Space Analysis of Constrained Multiobjective Optimization Problems. *IEEE Transactions on Evolutionary Computation* 27, 5 (Oct. 2023), 1427–1439. https://doi.org/10.1109/tevc.2022.3208595

[3] Christopher W Cleghorn and Gabriela Ochoa. 2021. Understanding parameter spaces using local optima networks: a case study on particle swarm optimization. In *Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '21)*. ACM, 1657–1664. https://doi.org/10.1145/3449726.3463145

[4] Kalyanmoy Deb. 2000. An efficient constraint handling method for genetic algorithms. *Computer Methods in Applied Mechanics and Engineering* 186, 2–4 (June 2000), 311–338. https://doi.org/10.1016/s0045-7825(99)00389-8

[5] Kevin Doherty, Khulood Alyahya, Ozgur E Akman, and Jonathan E Fieldsend. 2017. Optimisation and landscape analysis of computational biology models: a case study. In *Proceedings of the Genetic and Evolutionary Computation Conference Companion*. ACM, 1644–1651.

[6] Jonathan E. Fieldsend. 2024. Scalable Local Optima Networks for Continuous Search Spaces. In *Artificial Evolution*.

[7] Jonathan. E. Fieldsend and Khulood Alyahya. 2019. Visualising the landscape of multi-objective problems using local optima networks. In *Proceedings of the Genetic and Evolutionary Computation Conference Companion*. ACM, 1421–1429.

[8] Domagoj Jakobovic, Stjepan Picek, Marcella S.R. Martins, and Markus Wagner. 2021. Toward more efficient heuristic construction of Boolean functions. *Applied Soft Computing* 107 (Aug. 2021), 107327. https://doi.org/10.1016/j.asoc.2021.107327

[9] S. A. Kauffman. 1993. *The Origins of Order*. Oxford University Press.

[10] Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. *Knapsack problems*. Springer.

[11] Pascal Kerschke and Heike Trautmann. 2019. *Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems Using the R-Package Flacco*. Springer International Publishing, 93–123. https://doi.org/10.1007/978-3-030-25147-5_7

[12] Arnaud Liefooghe, Bilel Derbel, Sébastien Verel, Manuel López-Ibáñez, Hernán Aguirre, and Kiyoshi Tanaka. 2018. *On Pareto Local Optimal Solutions Networks*. Springer International Publishing, 232–244. https://doi.org/10.1007/978-3-319-99259-4_19

[13] Arnaud Liefooghe and Katherine Mary Malan. 2023. Adaptive Landscape-aware Constraint Handling with Application to Binary Knapsack Problem. In *Proceedings of the Companion Conference on Genetic and Evolutionary Computation (GECCO '23 Companion)*. ACM, 2064–2071. https://doi.org/10.1145/3583133.3596405

[14] Arnaud Liefooghe, Gabriela Ochoa, Sébastien Verel, and Bilel Derbel. 2023. Pareto Local Optimal Solutions Networks with Compression, Enhanced Visualization and Expressiveness. In *Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '23)*. ACM, 713–721. https://doi.org/10.1145/3583131.3590474

[15] Katherine M. Malan. 2018. *Landscape-Aware Constraint Handling Applied to Differential Evolution*. Springer International Publishing, 176–187. https://doi.org/10.1007/978-3-030-04070-3_14

[16] Katherine M. Malan. 2021. *Online Landscape Analysis for Guiding Constraint Handling in Particle Swarm Optimisation*. Springer Singapore, 101–118. https://doi.org/10.1007/978-981-33-6710-4_5

[17] Katherine M. Malan. 2021. A Survey of Advances in Landscape Analysis for Optimisation. *Algorithms* 14, 2 (Jan. 2021), 40. https://doi.org/10.3390/a1402040

[18] Katherine M. Malan and Andries P. Engelbrecht. 2013. A survey of techniques for characterising fitness landscapes and some possible ways forward. *Information Sciences* 241 (Aug. 2013), 148–163. https://doi.org/10.1016/j.ins.2013.04.015

[19] Katherine M. Malan and I. Moser. 2019. Constraint Handling Guided by Landscape Analysis in Combinatorial and Continuous Search Spaces. *Evolutionary Computation* 27, 2 (June 2019), 267–289. https://doi.org/10.1162/evco_a_00222

[20] Katherine M. Malan, Johannes F. Oberholzer, and Andries P. Engelbrecht. 2015. Characterising constrained continuous optimisation problems. In *2015 IEEE Congress on Evolutionary Computation (CEC)*. IEEE, 1351–1358. https://doi.org/10.1109/cec.2015.7257045

[21] Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory landscape analysis. In *Proceedings of the 13th annual conference on Genetic and evolutionary computation (GECCO '11)*. ACM, 829–836. https://doi.org/10.1145/2001576.2001690

[22] Gabriela Ochoa, Marco Tomassini, Sébastien Vérel, and Christian Darabos. 2008. A study of NK landscapes' basins and local optima networks. In *Proceedings of the 10th annual conference on Genetic and evolutionary computation (GECCO'08)*. ACM, 555–562. https://doi.org/10.1145/1389095.1389204

[23] Nuno M. Rodrigues, Katherine M. Malan, Gabriela Ochoa, Leonardo Vanneschi, and Sara Silva. 2022. Fitness landscape analysis of convolutional neural network architectures for image classification. *Information Sciences* 609 (Sept. 2022), 711–726. https://doi.org/10.1016/j.ins.2022.07.040

[24] Sarah L. Thomson, Léni Le Goff, Emma Hart, and Edgar Buchanan. 2024. Understanding Fitness Landscapes in Morpho-Evolution via Local Optima Networks. In *Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '24)*. ACM, 114–123. https://doi.org/10.1145/3638529.3654059

[25] Sébastien Verel, Fabio Daolio, Gabriela Ochoa, and Marco Tomassini. 2012. Local optima networks with escape edges. In *Artificial Evolution: 10th International Conference, Evolution Artificielle, EA 2011, Angers, France, October 24-26, 2011, Revised Selected Papers 10*. Springer, 49–60.

[26] Sébastien Verel, Arnaud Liefooghe, Laetitia Jourdan, and Clarisse Dhaenens. 2013. On the Structure of Multiobjective Combinatorial Search Space: MNK-landscapes with Correlated Objectives. *European Journal of Operational Research* 227, 2 (2013), 331–342. https://doi.org/10.1016/j.ejor.2012.12.019

[27] Tamás Vinkó and Kitti Gelle. 2017. Basin Hopping Networks of continuous global optimization problems. *Central European Journal of Operations Research* 25 (2017), 985–1006.

[28] Aljoša Vodopija, Tea Tušar, and Bogdan Filipič. 2022. Characterization of constrained continuous multiobjective optimization problems: A feature space perspective. *Information Sciences* 607 (Aug. 2022), 244–262. https://doi.org/10.1016/j.ins.2022.05.106