# Adaptive sampled walk: A simple and efficient autonomous local search

Matthieu Basseur, Arnaud Liefooghe, Sara Tari

► To cite this version:

Matthieu Basseur, Arnaud Liefooghe, Sara Tari. Adaptive sampled walk: A simple and efficient autonomous local search. Evolutionary Computation, In press, pp.1-25. 10.1162/EVCO.a.382. hal-05517226

HAL Id: hal-05517226

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

Submitted on 18 Feb 2026

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>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Adaptive Sampled Walk: A Simple and Efficient Autonomous Local Search

**Matthieu Basseur**

Univ. Littoral Côte d'Opale, UR 4491, LISIC, F-62100 Calais, France

matthieu.basseur@univ-littoral.fr

**Arnaud Liefooghe**

Univ. Littoral Côte d'Opale, UR 4491, LISIC, F-62100 Calais, France

arnaud.liefooghe@univ-littoral.fr

**Sara Tari**

Univ. Littoral Côte d'Opale, UR 4491, LISIC, F-62100 Calais, France

sara.tari@univ-littoral.fr

**Abstract**

We introduce and explore the automation and adaptation of partial neighborhood local search. Unlike traditional approaches requiring extensive parameter tuning, we design our approach to operate with minimal prerequisites. Specifically, we extend the sampled walk and ID walk algorithms by using distance-based calculations over a sliding window to determine the number of neighbors to evaluate at each step. To validate their performance, we empirically evaluate these parameter-free methods on four challenging combinatorial optimization benchmark problem classes from the literature, comparing them against fixed-parameter versions across multiple values. Our experiments show that, despite their simplicity, generic nature, and absence of parameters, these approaches achieve robust and competitive results across diverse problems—including different solution representations, neighborhood structures, and fitness landscape characteristics—thus validating the viability of generic autonomous local search methods.

**Keywords**

Combinatorial optimization, evolutionary computation, local search, parameter control, fitness landscapes.

# 1 Introduction

In recent years, evolutionary computation and optimization research has shifted toward more sophisticated benchmarking (Bartz-Beielstein et al., 2020). These studies examine problem instances, performance comparison, and experimental methodologies—providing essential tools and guidance to improve the quality and reliability of empirical research.

In particular, to better understand different optimization approaches, it is crucial to select a representative set of algorithms for the benchmark study. Bartz-Beielstein et al. (2020) suggest incorporating both diverse algorithm families and state-of-the-art methods.

Since optimization algorithms have hyperparameters and are sensitive to their settings, the authors recommend using automated algorithm configuration (AAC) for setting them (López-Ibáñez et al., 2016; Hutter et al., 2009, 2011). One of the main arguments is that AAC provides configurations with less bias than manual configuration. While this is definitely a good recommendation, especially for algorithms with multiple hyperparameters, AAC also comes with some drawbacks. One challenge is that
new users must invest time to learn how to use an AAC tool effectively. More impor-
tantly, AAC is an offline process that requires a training phase to determine good hy-
perparameters for a given algorithm under a given problem class and usage scenario.
This training phase can be time-consuming, especially when configuring multiple al-
gorithms or evaluating performance across different computational budgets. Since an
algorithm's best configuration can vary depending on the instance being optimized,
the AAC training phase typically focuses on instances with homogeneous characteris-
tics, similar to the target optimization problem. This implies that the process must be
repeated when dealing with instances with heterogeneous characteristics (as with man-
ual configuration), making it even more time-consuming. This limitation is especially
challenging when working with instances that have unusual characteristics or no com-
parable precedents.

An alternative to manual configuration when AAC is not fully suitable is *online* configuration, with a dynamic control of parameter settings (Doerr and Doerr, 2020; Huang et al., 2020). However, this approach also has key limitations: it works best with few hyperparameters, and it often requires integration with reinforcement learning—such as multi-armed bandit or Q-learning.

A comprehensive analysis and classification of automated parameter setting tech-
niques can be found in Huang et al. (2020). Most of these techniques share a funda-
mental characteristic: their decisions rely on performance measures directly tied to the
objective function values. The algorithm favors mechanisms or values that yield better
fitness scores. While connecting parameter settings to fitness (or its gradient) seems
intuitive, this approach provides only a local indicator and cannot effectively evalu-
ate the algorithm's ability to explore the search landscape. We propose an alternative
automated parameter control method that focuses on analyzing the trajectory through
the landscape instead of fitness values alone. Based on the adaptive parameter control
classification from Eiben et al. (1999) (revised by Doerr and Doerr (2020)), our approach
stands out by not being limited to the current search state nor to success or reward
mechanisms.

In this paper, we argue that straightforward autonomous algorithms, when clearly
described and easily adjustable, could be a valuable addition to existing tools. While
it would be unrealistic to claim these “ultra-generic” algorithms work for all optimiza-
tion problems, they could perform relatively well within a well-defined framework.
This framework requires three key elements: a search space, a fitness function, and a
neighborhood relation to navigate between solutions. Although problems with expen-
sive or noisy fitness functions or extremely complex neighborhood relations remain out
of reach, this representation encompasses many optimization problems and enables
extraction of key information from the search landscape. Additionally, a well-defined
neighborhood allows for precise calculation of distances between solutions.

Specifically, we propose adaptive versions of two simple partial neighborhood local search (PNLS) methods from the literature (Neveu et al., 2004; Tari et al., 2018). These PNLS are straightforward to develop, requiring only one parameter to be set after defining the neighborhood relation and stopping criterion. Prior research has revealed a strong correlation between effective parameter setting and exploration ability—measured in terms of distances covered between solutions seen. Drawing on this finding, we here develop automated versions that use distance-based calculations over a sliding window. These versions satisfy key benchmarking requirements: they are simple to implement, highly adaptable, and require no parameter tuning. To validate their performance, we evaluate these adaptive local search methods on four
challenging combinatorial optimization problems from the literature, comparing them
against fixed-parameter versions across multiple values. Overall, our study involves
evaluating 22 algorithm configurations across 70 problem instances from diverse prob-
lem classes, representing over 40 000 runs in total.

The paper is organized as follows. Section 2 introduces fitness landscapes and
partial neighborhood local search, which form the foundation of this study. Section 3
presents the proposed adaptive sampled walk (ASW) and adaptive ID walk (AID). Sec-
tion 4 provides a comprehensive experimental analysis on binary fitness landscapes
with varying characteristics in size, ruggedness, and neutrality. Section 5 investigates
the algorithms' adaptability through experiments on permutation problems. Finally,
Section 6 summarizes our contributions and outlines future research directions.

## 2 Background

This section introduces two main concepts. First, we describe fitness landscape analysis, a concept for analyzing black-box optimization problems and methods. Second, we present the partial neighborhood local search approaches considered in our study. Our goal is to leverage empirical tools from fitness landscape analysis to design autonomous local search.

2.1 Fitness Landscapes

The concept of fitness landscapes was introduced by Wright (1932) in evolutionary biol-
ogy. Since then, it has evolved into a valuable tool for studying complex systems across
various fields. In evolutionary computation, these landscapes provide an abstract rep-
resentation for analyzing algorithms across optimization problems. Fitness landscape
analysis (FLA) provides a framework to identify optimization challenges and better un-
derstand the dynamics of optimization algorithms (Merz, 2004; Pitzer and Affenzeller,
2012; Malan, 2021). A fitness landscape consists of three elements (X, N, f): the search
space X, the fitness function f: X → ℝ that assigns a quality score to each solution,
and N: X → 2<sup>X</sup>, which defines a neighborhood relation among solutions.

The search space and fitness function are typically derived from the problem defi-
nition itself—with some exceptions, e.g., for constraint handling or landscape smooth-
ing. The neighborhood relation, however, must align with the method’s variation op-
erators. FLA helps differentiate problems by characterizing them. Two of the most im-
portant characteristics are ruggedness and neutrality. Ruggedness describes how local
optima are distributed in the landscape. Rugged landscapes contain many local optima
with small basins of attraction, making them difficult to reach. Smooth landscapes, in
contrast, have fewer local optima with larger basins of attraction. Neutrality captures
the proportion of neighboring solutions that have identical fitness values—known as
neutral neighbors. High neutrality makes the search process harder by trapping it in
plateaus while failing to find better solutions.

In this work, we adopt fitness landscapes as a foundation for developing generic
autonomous search methods. We aim to design a robust approach that performs sat-
isfactorily across a wide range of combinatorial optimization problems, rather than
creating specialized methods for specific problems. While specialized approaches can
better leverage particular problem properties, this comes at the cost of reduced gener-
ality. Such a setting allows us to challenge our methods across varying levels of size,
ruggedness, and neutrality.
**Algorithm 1 SW(λ)**

1: $x^* \leftarrow x$ ← random initial solution

2: **while** stopping criterion not reached **do**

3: $P \leftarrow \lambda$ random neighbors of $x$

4: $x \leftarrow \operatorname*{argmax}_{z \in P}(f(z))$

5: $x^* \leftarrow \operatorname*{argmax}\{(f(x), f(x^*))\}$

6: **end while**

7: **return** $x^*$

## 2.2 Partial Neighborhood Local Search

Neighborhood-based algorithms form a broad class of optimization methods, primarily comprising local search algorithms. Local search operates by iteratively modifying a solution according to a neighborhood relation and selection strategy until meeting a stopping criterion. Typical examples of neighborhood for combinatorial optimization are the 1-flip operator that flips exactly one bit for binary representation, or interchange for QAP (see Section 5.2). While some approaches systematically evaluate the entire neighborhood of the current solution, others explore only portions of it. Some methods, like best improvement climbers, may require full neighborhood evaluation, while others deliberately limit their evaluation scope—e.g., first improvement climbers. *Partial neighborhood local search* (PNLS), which is the focus of this paper, uses a parameter to limit the number of neighbors evaluated per iteration. When properly configured, PNLS achieves an effective balance between exploration and exploitation (Tari et al., 2021).

$ID_{walk}$ is an example of PNLS method (Neveu et al., 2004). Along with a stopping criterion, it uses a single parameter $\lambda$, which defines the maximum number of randomly selected neighbors to evaluate per iteration. As soon as an improving neighbor is found, it simply replaces the current solution. However, when none of the $\lambda$ generated neighbors are improving, two variants are possible:

* $ID_{best}$, which selects the best among the $\lambda$ deteriorating neighbors,

* $ID_{any}$, which randomly selects one of the $\lambda$ deteriorating neighbors.

The *sampled walk* (SW) (Tari et al., 2018), shown in Algorithm 1, is another example. It evaluates exactly $\lambda$ neighbors from the current solution at each iteration and selects the best one. As one of the most straightforward PNLS algorithms, it performs selection without considering the current solution's fitness value. SW is equivalent to a $(1, \lambda)$ evolutionary algorithm in combinatorial optimization.

Indeed, evolutionary algorithms (EAs) can be categorized based on their selection mechanisms. Elitist ($\mu + \lambda$)-EAs retain the best solutions from one iteration to the next, ensuring monotonic progress and theoretical convergence guarantees (Rudolph, 1994). This elitism was long considered essential for both practical performance and theoretical convergence, as it prevents the loss of high-quality solutions and facilitates the exploration of promising regions in the search space. In contrast, non-elitist ($\mu, \lambda$)-EAs generate each new population solely from offspring, discarding the parent population entirely. This approach can help avoid premature convergence by enabling escapes from local optima. However, their effectiveness is sensitive to parameter settings. If the selection pressure is too high, non-elitist EAs may behave similarly to elitist ones; if too low, they struggle to efficiently optimize functions with a unique global opti-
mum (Corus et al., 2018; Dang et al., 2021; Doerr, 2022). For example, the (1, 1)-EA, which lacks any selection pressure, reduces to a random walk. In this study, we focus on (1, λ)-like local search algorithms, where we adapt λ to dynamically control selection pressure.

For both $ID_{walk}$ and $SW$, the single parameter $\lambda$ controls the balance between intensification and diversification. These PNLS algorithms have been studied across various optimization problems. Tari et al. (2022) compared their performance against tabu search and iterated local search on large landscapes. PNLS demonstrated rapid convergence to high-quality solutions, with $ID_{best}$ and $SW$ showing notably superior performance compared to other approaches. Sensitivity analysis revealed that PNLS perform effectively across a wide range of parameter values, though certain values produced superior results. The optimal value varies based on both budget and ruggedness level—higher ruggedness typically requiring higher $\lambda$ values. Interestingly, both $ID_{best}$ and $SW$ reached their peak performance with similar parameter configurations.

## 2.3 Preliminary Observations

One of the main focuses of this work is to assess $SW$'s ability to escape from basins of attraction based on $\lambda$ values. For illustration purposes, Figure 1 (partially taken from Tari et al. (2021)) shows a trajectory analysis of $SW$ under different settings of $\lambda$ on a pseudo-Boolean optimization problem (NK landscapes), in which $X = \{0, 1\}^n$ and $\mathcal{N}$ is the 1-flip neighborhood. The figure focuses on evaluating $SW$'s diversification capability. By computing the Hamming distance between solutions using a sliding window of size $w$ for different $\lambda$ values, we observe how the distance between encountered solutions is reduced when $\lambda$ is fixed with a higher value. The figure focuses on evaluating $SW$'s diversification ability, by computing the distance between solutions using a sliding window of size $w$, as well as the fitness of the best-encountered solution, under different $\lambda$ values. The plots report the results averaged over 10 runs per constant $\lambda$ value on several NK landscapes, with a stopping criterion of 1 million evaluations. The curves show average fitness, while the boxplots show the distribution of distances. Let us notice that using $\lambda = 1$ for $SW$ corresponds to a random walk, whereas $\lambda = n$ is more likely to get trapped into the first encountered suboptimal region.

From the figure, we observe that the best average fitness is reached at $\lambda = 16, 32, 16$, and $64$, respectively, from left to right and from top to bottom. Generally speaking, small $\lambda$ values lead to high diversification rates, this in turns leads to a large distance between solutions when they are compared after a given number of steps. On the contrary, higher values of $\lambda$ increase the intensification rate, solutions are thus prone to remain in a more reduced area of the search landscape. As such, larger $\lambda$ values tend to be less effective because they shift the search toward excessive intensification, reducing diversification and often leading to cycles or premature convergence. This aligns with selection pressure and the fundamental trade-off between intensification and diversification: lower $\lambda$ values promote exploration, while higher values favor exploitation. One of the strengths of PNLSs is that they usually do not require the systematic evaluation of the whole neighborhood and can thus perform more steps under the same budget, usually leading to better convergence.

These findings indicate that the ideal $\lambda$ value occurs when the distance between solutions decreases more gradually with respect to $\lambda$, and this observation remains valid while considering different instance sizes and ruggedness levels. This result, combined with the existence of a sufficiently wide interval of appropriate $\lambda$ values, suggests that finding an ideal value for this parameter is possible through distance computation.
<figure><img src="image_2.png" /><figcaption>Figure 1: Relation between SWsearch trajectory and performance with respect to a static value of λ. The boxplots show the distribution of distances between solutions at steps *i* and *i*+*n*/2 throughout a set of runs, while the curve shows the average fitness achieved for runs realized with several static λ values. The example problems are NK landscapes (Section 4.1) with different sizes and ruggedness levels *n* = {256, 1024} and *k* = {2, 12}. Fitness is to be maximized.</figcaption></figure>

These intuitive insights motivate the autonomous local search proposed below.

# 3 Autonomous Partial Neighborhood Local Search

As discussed above, the distance covered in a sliding window correlates with appropri-
ate λ values for SW. In this section, we build our proposal for the design of automated
sampled walk and ID walk algorithms, where the adaptive setting of λ is driven by a
distance measured over a sliding window.

## 3.1 Adapting Lambda based on Sliding Distance

As noted above, the distance reachable from the best-encountered solution is negatively impacted by $\lambda$, and the sliding distance between solutions follows the same pattern. This relationship suggests that $\lambda$ can be dynamically adjusted during the search process based on the distance between solutions. Specifically, increasing $\lambda$ can help reduce high travel distances during search, while decreasing $\lambda$ can expand smaller travel distances, thereby fine-tuning the exploration-exploitation trade-off. We argue that this principle could enable a robust autonomous PNLS that does not require prior parameter-tuning experiments.

Let us consider two extreme cases to illustrate this principle. When the distance $\delta = \text{distance}(x_t, x_{t-w})$ between two solutions after $w$ steps is zero, exploration is min-
<caption>**Algorithm 2 ASW for a (({0, 1})<sup>n</sup>, 1-flip, f) landscape**</caption>

1: $\lambda \leftarrow 1$
2: $t \leftarrow 0$
3: $x_0 \leftarrow \text{random initial solution}$
4: **while** stopping criterion not reached **do**
5:     $S \leftarrow \text{sample } \lambda \text{ random neighbors of } x_t$
6:     $t \leftarrow t + 1$
7:     $x_t \leftarrow \arg\max_{x \in S} f(x)$
8:     $\lambda \leftarrow \max(1, \text{distance}(x_t, x_{\max(t-w,0)}))$
9: **end while**
10: **return** $\arg\max_{x \in \{x_0, \dots, x_t\}} f(x)$

imal. This scenario requires maximum diversification for the next step, with the evaluation (and acceptance) of $\lambda = 1$ neighbor. Conversely, when the distance reaches the landscape's diameter $d$ (such that $\delta = d$), exploration is maximal<fnref n="1" />. The landscape diameter is simply the largest distance between any pair of solutions in the landscape. This case requires minimum diversification, where lambda can be set to $||N||$ (exhaustive enumeration of all neighbors).

Going further, the core principle is to define $\lambda$ adaptively, according to the algorithm's exploration capability: the larger the distance, the larger $\lambda$. Intuitively, it makes sense to map $\lambda$ values (from 1 to $||N||$) as a bijection of distance values (from 0 to $d$). Considering the simple case of binary fitness landscapes with $n$ variables under the 1-flip neighborhood, the landscape diameter equals the neighborhood size ($d = ||N|| = n$). A simple approach is to set $\lambda$ linearly with respect to $\delta$: $\lambda = \max(1, \delta)$, as $\lambda$ cannot equal zero. Though more sophisticated methods might exist for mapping $\lambda$ to observed $\delta$ values, experiments below show that both autonomous PNLS implementations naturally achieve a good balance between intensification and diversification. In the case of NK landscapes, SW achieve strong results when $\lambda$ value is similar to the corresponding sliding distance observed (see Figure 1).

Although the correlation between $\lambda$ and the sliding distance was observed only with SW, we propose automating both SW and ID<sub>best</sub> based on this principle.

## 3.2 Algorithms Description

We propose an adaptive sampled walk (ASW) and an adaptive ID Walk (AID). These PNLS algorithms are based on SW and ID<sub>best</sub>, respectively, where $\lambda$ adjusts dynamically based on the distance between solutions in a sliding window $w$. Algorithms 2 and 3 respectively give the general schemes of ASW and AID for pseudo-Boolean landscapes. These algorithms function identically to their static versions, with one key difference: they adjust $\lambda$ at the end of each iteration. Both algorithms must store only the last $w$ moves and track the best solution found during the search. While selecting $\lambda$ neighbors without replacement is theoretically preferable, we do not expect that using replacement would significantly impact algorithm performance.

# 4 Experimental Analysis on Pseudo-Boolean Problems

In this section, we analyze the performance of ASW and AID compared to their static versions. We begin with NK landscapes—well-known pseudo-Boolean optimization

<footnote n="1">¹We assume $w$ is defined such that $w > d$; e.g., $w = 2d$.</footnote>
<caption>**Algorithm 3 AID for a (({0, 1})^n, 1-flip, f) landscape**</caption>

1: $\lambda \leftarrow 1$
2: $t \leftarrow 0$
3: $x_0 \leftarrow$ random initial solution
4: **while** stopping criterion not reached **do**
5:     **candidate** $\leftarrow 0$
6:     **repeat**
7:         $x \leftarrow$ sample a random neighbor of $x_t$
8:         **candidate** $\leftarrow$ **candidate** + 1
9:         **if** (**candidate** = 1) or ($f(x) > f(x^*)$) **then**
10:             $x^* \leftarrow x$
11:         **end if**
12:     **until** (**candidate** = $\lambda$) or ($f(x^*) \ge f(x_t)$)
13:     $t \leftarrow t + 1$
14:     $x_t \leftarrow x^*$
15:     $\lambda \leftarrow \max(1, \text{distance}(x_t, x_{\max(t-w,0)}))$
16: **end while**
17: **return** $\arg\max_{x \in \{x_0, \dots, x_t\}} f(x)$

problems that exhibit varying levels of ruggedness and neutrality. These properties allow us to challenge how algorithms perform under different conditions. Despite their simplicity, we recall that ID<sub>best</sub> and SW are remarkably efficient at solving this class of problems (Tari et al., 2022). However, the effective setting of $\lambda$ varies across instances. We begin by examining non-neutral NK landscapes below.

## 4.1 NK Landscapes

### 4.1.1 Problem Formulation and instances

The NK model from Kauffman and Weinberger (1989) helps study optimization algorithms by controlling variable dependencies, and thus the ruggedness of the fitness landscape. An NK landscape is a pseudo-Boolean function that allows generating instances with adjustable variable interdependency. NK landscapes are defined by two parameters: $n$, representing the number of Boolean variables, and $k$, determining the degree of interdependency between variables. While $n$ sets the problem dimension, $k$ controls the ruggedness of the landscape: higher $k$ values result in more rugged landscapes. For a given $n$, we can tune the ruggedness by varying $k$ from 0 to $(n-1)$. The model consists of a $n \times k$ matrix of bit references ($\Pi_i$ functions) and a $2^{k+1} \times n$ matrix of fitness contributions ($C_i$ functions). The fitness function, to be maximized, is the average of the contribution functions:

$$f(x) = \frac{1}{n} \sum_{i=1}^{n} C_i(x_i, \Pi_i(x)) \qquad (1)$$

with $x_i$ the $i$-th bit (variable) of solution $x$. The $\Pi_i$ sub-functions determine bit dependencies: $\Pi_i(x) = \{x_{\pi_1(i)}, \dots, x_{\pi_k(i)}\}$, with $\pi_j(i) \in \{1, \dots, n\} \setminus \{i\}$. Each sub-function $C_i: \{0, 1\}^{k+1} \rightarrow [0, 1]$ determines the $i$-th contribution value based on $x_i$ and $\Pi_i(x)$.

We generate an independent NK landscape for each parameter combination below, yielding a total of 30 instances:

* Number of variables $n \in \{64, 128, 256, 512, 1024\}$,
* Variable interaction levels $k \in \{2, 4, 6, 8, 10, 12\}$.

Following Kauffman and Weinberger (1989), bit references ($\Pi_i$) are generated through the random model of variable interactions, and fitness contributions ($C_i$) are uniformly distributed in $[0, 1[$.

### 4.1.2 Distance Measure

We consider here a bitstring solution representation, associated with the 1-flip neighborhood operator. The 1-flip distance between solutions is simply taken as the number of different bits, also known as the Hamming distance. One clear advantage of this distance measure is that its value can be updated in constant time after each step of the search process, by maintaining additional data structures:

* a second bitstring $x_{\text{diff}}$ that represents the differences between the current solution $x_t$ and the solution from $w$ iterations ago $x_{t-w}$,

* an list of integers *flips* that contains the last *w* flipped bits,

* a variable *distance* that corresponds to the distance from $x_{t-w}$ to $x_t$.

At each iteration, both the bit flipped $w$ steps ago and the newly flipped one in the reference bitstring are updated. The distance variable is updated based on the current flip and the one from $w$ steps ago (except for the first $w$ steps). Finally, the list of integers is updated by adding the current flip's index.

Let us look at an example of sliding distance measurement using a window size of $w = 5$. At current iteration $t$, we have the following:

<table><tr><td>x<sub>t-w</sub></td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>x<sub>t</sub></td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><td>x<sub>diff</sub></td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>flips</td><td>2</td><td>8</td><td>4</td><td>8</td><td>6</td><td></td><td></td></tr><tr><td>distance</td><td>3</td><td></td><td></td><td></td><td></td><td></td><td></td></tr></table>

At the next iteration $t + 1$, assuming the 4-th bit $x_t$ has been flipped, the data structure is updated as follows:

<table><tr><td>x<sub>t+1-w</sub></td><td>0</td><td><b>1</b></td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>x<sub>t+1</sub></td><td>0</td><td>1</td><td>1</td><td><b>1</b></td><td>0</td><td>1</td><td>0</td></tr><tr><td>x<sub>diff</sub></td><td>0</td><td><b>0</b></td><td>0</td><td><b>0</b></td><td>0</td><td>1</td><td>0</td></tr><tr><td>flips</td><td>8</td><td>4</td><td>8</td><td>6</td><td><b>4</b></td><td></td><td></td></tr><tr><td>distance</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr></table>

### 4.1.3 Fixed $\lambda$ for NK Landscapes

Previous experiments have shown that the best $\lambda$ value for NK landscapes correlates with both the problem dimension and the ruggedness level (Tari et al., 2022). On top of examining a wide range of $\lambda$ values across instances, we derive a simple rule based on $n$ and $k$ to determine an effective $\lambda$ setting for NK landscapes: $\lambda = \lfloor 2 \times \sqrt[3]{n} \times \sqrt{k} \rfloor$. Table 1 reports the resulting $\lambda$ values used for fixed versions of SW and ID algorithms, denoted as fixed below.

Although this method allows determining an adequate $\lambda$ value a priori, its computation depends on NK landscapes parameters and cannot be directly applied to other optimization problems. Indeed, deriving such a formula requires either deep a priori knowledge of the landscape or a computationally expensive benchmarking study.
<table><caption>Table 1: $\lambda$ values used in fixed SW and ID algorithms for the considered NK landscapes, such that $\lambda = \lfloor 2 \times \sqrt[3]{n} \times \sqrt{k} \rfloor$.</caption><thead><tr><th></th><th>k = 2</th><th>k = 4</th><th>k = 6</th><th>k = 8</th><th>k = 10</th><th>k = 12</th></tr></thead><tbody><tr><td>n = 64</td><td>11</td><td>16</td><td>19</td><td>22</td><td>25</td><td>27</td></tr><tr><td>n = 128</td><td>14</td><td>20</td><td>24</td><td>28</td><td>31</td><td>34</td></tr><tr><td>n = 256</td><td>17</td><td>25</td><td>31</td><td>35</td><td>40</td><td>43</td></tr><tr><td>n = 512</td><td>22</td><td>32</td><td>39</td><td>45</td><td>50</td><td>55</td></tr><tr><td>n = 1024</td><td>28</td><td>40</td><td>49</td><td>57</td><td>63</td><td>69</td></tr></tbody></table>

Moreover, we remark that the $k$ parameter is typically unknown when solving a blind NK landscape in a black-box optimization scenario. In contrast, we show in this paper that a simple, knowledge-free adaptive strategy can achieve comparable performance without these requirements on black-box optimization problems.

### 4.1.4 Experimental Setup

In the following, we experiment with both SW and ID under different settings of $\lambda \in \{8, 16, 24, 32, 48, 64, 80, 96, 128\}$, along with their NK-dependent fixed setting (fixed) and the proposed adaptive strategy based on sliding distance ASW and AID (also denoted auto below). This results in 22 variants per instance (16 for $n = 64$, given that $\lambda$ must be at most $n$). We conduct 30 runs per algorithm on each instance, starting from the same set of 30 randomly generated solutions. Each run terminates after 100 million evaluations. Our experiments aim to assess whether automated PNLS consistently delivers robust, high-quality results across varied fitness landscapes. For simplicity, we set the initial value $\lambda = 1$ for adaptive methods to maximize diversification at the start. To calculate solution distances and adaptively adjust lambda, we use a sliding window of size $w$. This window must exceed the average distance between random solutions—enabling distinction between random and intensification trajectories—while remaining computationally manageable. We set $w = 2 \times n$, where $n$ is the problem size, which corresponds to the landscape diameter in NK landscapes. In the context of fitness landscape analysis, we remark that $\lambda$ serves not as a parameter but as a derived value, calculated from distance measurements inherent to the landscape definition. While $w$ must be set, we show that it can be derived directly from the landscape diameter. Some experiments are provided in Section 4.1.6 to verify the low sensitivity of $w$ parameterization once its value is set according to the landscape diameter.

### 4.1.5 Performance Comparison

Results are reported in Table 2. For each instance, there are two rows: SW results on top and ID results below. The table reports:

* the fitness of the best-seen solution (for future comparison),

* the relative deviation from best, on average (in brackets),

* the number of competing algorithms that significantly outperform the one under consideration, based on a non-parametric Wilcoxon signed rank test at a significance level of 0.05 with Bonferroni correction for multiple comparisons. A lower rank is better, with a rank of 0 indicating the algorithm is not outperformed by any other.
<table><caption>Table 2: Statistical rank and relative fitness deviation of SW and ID variants on NK landscapes.</caption><thead><tr><th>n</th><th>k</th><th>best</th><th>algo</th><th>8</th><th>16</th><th>24</th><th>32</th><th>48</th><th>64</th><th>80</th><th>96</th><th>128</th><th>auto</th><th>fixed</th></tr></thead><tbody><tr><td rowspan="2">64</td><td rowspan="2">2</td><td rowspan="2">0.721068</td><td>SW</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.001)</td><td>10 (.005)</td><td>12 (.014)</td><td>14 (.035)</td><td>-</td><td>-</td><td>-</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>ID</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td><td>10 (.005)</td><td>12 (.016)</td><td>14 (.044)</td><td>-</td><td>-</td><td>-</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td rowspan="2">64</td><td rowspan="2">4</td><td rowspan="2">0.792968</td><td>SW</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.001)</td><td>10 (.006)</td><td>12 (.029)</td><td>14 (.079)</td><td>-</td><td>-</td><td>-</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>ID</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.001)</td><td>10 (.008)</td><td>12 (.033)</td><td>14 (.091)</td><td>-</td><td>-</td><td>-</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td rowspan="2">64</td><td rowspan="2">6</td><td rowspan="2">0.804522</td><td>SW</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.001)</td><td>10 (.012)</td><td>12 (.041)</td><td>14 (.091)</td><td>-</td><td>-</td><td>-</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>ID</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td><td>10 (.009)</td><td>12 (.037)</td><td>14 (.106)</td><td>-</td><td>-</td><td>-</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td rowspan="2">64</td><td rowspan="2">8</td><td rowspan="2">0.806931</td><td>SW</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td><td>10 (.011)</td><td>12 (.046)</td><td>14 (.120)</td><td>-</td><td>-</td><td>-</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>ID</td><td>0 (.001)</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.006)</td><td>12 (.041)</td><td>14 (.116)</td><td>-</td><td>-</td><td>-</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td rowspan="2">64</td><td rowspan="2">10</td><td rowspan="2">0.804905</td><td>SW</td><td>10 (.020)</td><td>0 (.002)</td><td>0 (.004)</td><td>8 (.013)</td><td>13 (.044)</td><td>14 (.124)</td><td>-</td><td>-</td><td>-</td><td>0 (.002)</td><td>0 (.003)</td></tr><tr><td>ID</td><td>10 (.023)</td><td>0 (.002)</td><td>0 (.002)</td><td>8 (.008)</td><td>12 (.036)</td><td>14 (.113)</td><td>-</td><td>-</td><td>-</td><td>0 (.003)</td><td>0 (.002)</td></tr><tr><td rowspan="2">64</td><td rowspan="2">12</td><td rowspan="2">0.807217</td><td>SW</td><td>10 (.035)</td><td>0 (.010)</td><td>0 (.013)</td><td>8 (.021)</td><td>12 (.055)</td><td>14 (.141)</td><td>-</td><td>-</td><td>-</td><td>0 (.012)</td><td>0 (.014)</td></tr><tr><td>ID</td><td>10 (.037)</td><td>0 (.010)</td><td>0 (.011)</td><td>5 (.018)</td><td>12 (.048)</td><td>14 (.131)</td><td>-</td><td>-</td><td>-</td><td>0 (.010)</td><td>0 (.014)</td></tr><tr><td rowspan="2">128</td><td rowspan="2">2</td><td rowspan="2">0.742374</td><td>SW</td><td>6 (.002)</td><td>0 (.000)</td><td>6 (.002)</td><td>7 (.003)</td><td>12 (.006)</td><td>14 (.016)</td><td>15 (.024)</td><td>18 (.031)</td><td>20 (.045)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>ID</td><td>6 (.002)</td><td>0 (.000)</td><td>0 (.001)</td><td>6 (.002)</td><td>12 (.007)</td><td>14 (.014)</td><td>14 (.018)</td><td>17 (.030)</td><td>20 (.053)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td rowspan="2">128</td><td rowspan="2">4</td><td rowspan="2">0.795857</td><td>SW</td><td>10 (.008)</td><td>0 (.000)</td><td>0 (.001)</td><td>7 (.004)</td><td>10 (.011)</td><td>14 (.021)</td><td>14 (.030)</td><td>18 (.042)</td><td>20 (.088)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>ID</td><td>10 (.008)</td><td>0 (.000)</td><td>0 (.001)</td><td>0 (.003)</td><td>10 (.009)</td><td>13 (.019)</td><td>15 (.031)</td><td>16 (.038)</td><td>20 (.082)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td rowspan="2">128</td><td rowspan="2">6</td><td rowspan="2">0.806442</td><td>SW</td><td>10 (.024)</td><td>0 (.001)</td><td>3 (.004)</td><td>8 (.009)</td><td>10 (.023)</td><td>14 (.034)</td><td>16 (.049)</td><td>17 (.058)</td><td>20 (.107)</td><td>0 (.002)</td><td>3 (.004)</td></tr><tr><td>ID</td><td>11 (.027)</td><td>0 (.001)</td><td>3 (.003)</td><td>8 (.007)</td><td>10 (.019)</td><td>11 (.030)</td><td>15 (.043)</td><td>16 (.053)</td><td>20 (.097)</td><td>0 (.001)</td><td>3 (.003)</td></tr><tr><td rowspan="2">128</td><td rowspan="2">8</td><td rowspan="2">0.807766</td><td>SW</td><td>15 (.047)</td><td>1 (.011)</td><td>0 (.008)</td><td>6 (.013)</td><td>10 (.023)</td><td>12 (.037)</td><td>14 (.045)</td><td>18 (.062)</td><td>20 (.112)</td><td>0 (.009)</td><td>0 (.010)</td></tr><tr><td>ID</td><td>15 (.049)</td><td>4 (.012)</td><td>0 (.007)</td><td>0 (.009)</td><td>10 (.022)</td><td>12 (.031)</td><td>13 (.040)</td><td>17 (.054)</td><td>20 (.116)</td><td>0 (.008)</td><td>0 (.008)</td></tr><tr><td rowspan="2">128</td><td rowspan="2">10</td><td rowspan="2">0.805577</td><td>SW</td><td>17 (.064)</td><td>10 (.027)</td><td>0 (.016)</td><td>0 (.017)</td><td>7 (.023)</td><td>12 (.035)</td><td>14 (.046)</td><td>16 (.059)</td><td>20 (.120)</td><td>0 (.019)</td><td>0 (.017)</td></tr><tr><td>ID</td><td>18 (.066)</td><td>10 (.030)</td><td>0 (.016)</td><td>0 (.016)</td><td>7 (.022)</td><td>11 (.032)</td><td>14 (.043)</td><td>15 (.053)</td><td>20 (.114)</td><td>0 (.018)</td><td>0 (.017)</td></tr><tr><td rowspan="2">128</td><td rowspan="2">12</td><td rowspan="2">0.793505</td><td>SW</td><td>18 (.065)</td><td>10 (.029)</td><td>0 (.016)</td><td>0 (.015)</td><td>5 (.020)</td><td>11 (.030)</td><td>15 (.045)</td><td>16 (.052)</td><td>20 (.118)</td><td>0 (.018)</td><td>0 (.016)</td></tr><tr><td>ID</td><td>18 (.067)</td><td>11 (.032)</td><td>0 (.018)</td><td>0 (.015)</td><td>0 (.017)</td><td>10 (.025)</td><td>12 (.035)</td><td>15 (.048)</td><td>20 (.110)</td><td>4 (.019)</td><td>0 (.015)</td></tr><tr><td rowspan="2">256</td><td rowspan="2">2</td><td rowspan="2">0.744766</td><td>SW</td><td>10 (.007)</td><td>2 (.001)</td><td>0 (.001)</td><td>6 (.002)</td><td>10 (.009)</td><td>13 (.013)</td><td>16 (.021)</td><td>16 (.027)</td><td>19 (.032)</td><td>0 (.001)</td><td>2 (.001)</td></tr><tr><td>ID</td><td>11 (.008)</td><td>2 (.001)</td><td>0 (.001)</td><td>6 (.002)</td><td>10 (.007)</td><td>11 (.010)</td><td>16 (.022)</td><td>16 (.026)</td><td>20 (.035)</td><td>0 (.001)</td><td>2 (.001)</td></tr><tr><td rowspan="2">256</td><td rowspan="2">4</td><td rowspan="2">0.794025</td><td>SW</td><td>12 (.019)</td><td>6 (.002)</td><td>0 (.001)</td><td>5 (.003)</td><td>10 (.012)</td><td>12 (.019)</td><td>14 (.027)</td><td>18 (.034)</td><td>20 (.046)</td><td>0 (.001)</td><td>0 (.001)</td></tr><tr><td>ID</td><td>13 (.021)</td><td>6 (.002)</td><td>0 (.001)</td><td>0 (.003)</td><td>10 (.010)</td><td>11 (.017)</td><td>13 (.023)</td><td>16 (.030)</td><td>20 (.046)</td><td>0 (.001)</td><td>0 (.001)</td></tr><tr><td rowspan="2">256</td><td rowspan="2">6</td><td rowspan="2">0.806716</td><td>SW</td><td>20 (.052)</td><td>8 (.010)</td><td>0 (.003)</td><td>3 (.005)</td><td>9 (.014)</td><td>12 (.023)</td><td>13 (.029)</td><td>15 (.035)</td><td>18 (.044)</td><td>0 (.004)</td><td>0 (.005)</td></tr><tr><td>ID</td><td>20 (.054)</td><td>9 (.013)</td><td>0 (.004)</td><td>0 (.004)</td><td>8 (.011)</td><td>12 (.019)</td><td>13 (.025)</td><td>15 (.032)</td><td>18 (.043)</td><td>0 (.003)</td><td>0 (.004)</td></tr><tr><td rowspan="2">256</td><td rowspan="2">8</td><td rowspan="2">0.803831</td><td>SW</td><td>20 (.073)</td><td>11 (.028)</td><td>0 (.012)</td><td>0 (.010)</td><td>8 (.017)</td><td>10 (.026)</td><td>11 (.031)</td><td>15 (.037)</td><td>18 (.049)</td><td>0 (.011)</td><td>0 (.012)</td></tr><tr><td>ID</td><td>21 (.078)</td><td>12 (.031)</td><td>5 (.013)</td><td>0 (.009)</td><td>5 (.014)</td><td>10 (.023)</td><td>11 (.028)</td><td>16 (.037)</td><td>18 (.047)</td><td>0 (.010)</td><td>0 (.010)</td></tr><tr><td rowspan="2">256</td><td rowspan="2">10</td><td rowspan="2">0.792664</td><td>SW</td><td>20 (.080)</td><td>16 (.038)</td><td>9 (.017)</td><td>0 (.010)</td><td>0 (.009)</td><td>8 (.017)</td><td>11 (.023)</td><td>14 (.028)</td><td>16 (.038)</td><td>4 (.012)</td><td>0 (.009)</td></tr><tr><td>ID</td><td>21 (.084)</td><td>18 (.041)</td><td>9 (.019)</td><td>0 (.010)</td><td>0 (.008)</td><td>5 (.013)</td><td>10 (.019)</td><td>13 (.025)</td><td>15 (.034)</td><td>5 (.012)</td><td>0 (.009)</td></tr><tr><td rowspan="2">256</td><td rowspan="2">12</td><td rowspan="2">0.78341</td><td>SW</td><td>20 (.086)</td><td>18 (.046)</td><td>1 (.026)</td><td>6 (.015)</td><td>0 (.011)</td><td>3 (.013)</td><td>6 (.018)</td><td>13 (.024)</td><td>15 (.032)</td><td>6 (.016)</td><td>0 (.011)</td></tr><tr><td>ID</td><td>20 (.088)</td><td>19 (.050)</td><td>15 (.029)</td><td>5 (.016)</td><td>0 (.010)</td><td>0 (.012)</td><td>6 (.016)</td><td>6 (.018)</td><td>14 (.029)</td><td>6 (.017)</td><td>0 (.011)</td></tr><tr><td rowspan="2">512</td><td rowspan="2">2</td><td rowspan="2">0.752002</td><td>SW</td><td>10 (.012)</td><td>1 (.002)</td><td>0 (.001)</td><td>8 (.004)</td><td>10 (.013)</td><td>14 (.020)</td><td>16 (.027)</td><td>18 (.031)</td><td>20 (.035)</td><td>0 (.002)</td><td>0 (.002)</td></tr><tr><td>ID</td><td>11 (.013)</td><td>2 (.002)</td><td>0 (.002)</td><td>4 (.004)</td><td>10 (.011)</td><td>14 (.019)</td><td>16 (.025)</td><td>17 (.030)</td><td>18 (.033)</td><td>0 (.002)</td><td>0 (.002)</td></tr><tr><td rowspan="2">512</td><td rowspan="2">4</td><td rowspan="2">0.788798</td><td>SW</td><td>17 (.035)</td><td>2 (.006)</td><td>0 (.004)</td><td>0 (.006)</td><td>10 (.012)</td><td>13 (.018)</td><td>14 (.024)</td><td>16 (.031)</td><td>18 (.041)</td><td>1 (.006)</td><td>1 (.006)</td></tr><tr><td>ID</td><td>19 (.038)</td><td>5 (.007)</td><td>0 (.003)</td><td>0 (.005)</td><td>10 (.011)</td><td>10 (.015)</td><td>13 (.020)</td><td>15 (.029)</td><td>17 (.037)</td><td>0 (.005)</td><td>0 (.005)</td></tr><tr><td rowspan="2">512</td><td rowspan="2">6</td><td rowspan="2">0.804817</td><td>SW</td><td>20 (.068)</td><td>9 (.017)</td><td>0 (.006)</td><td>1 (.008)</td><td>8 (.015)</td><td>11 (.021)</td><td>14 (.028)</td><td>15 (.031)</td><td>18 (.041)</td><td>3 (.009)</td><td>3 (.011)</td></tr><tr><td>ID</td><td>21 (.072)</td><td>11 (.022)</td><td>0 (.006)</td><td>0 (.006)</td><td>8 (.014)</td><td>10 (.019)</td><td>12 (.025)</td><td>15 (.029)</td><td>18 (.038)</td><td>1 (.008)</td><td>1 (.009)</td></tr><tr><td rowspan="2">512</td><td rowspan="2">8</td><td rowspan="2">0.801912</td><td>SW</td><td>20 (.092)</td><td>18 (.044)</td><td>9 (.021)</td><td>2 (.012)</td><td>1 (.013)</td><td>8 (.019)</td><td>11 (.024)</td><td>15 (.029)</td><td>16 (.037)</td><td>0 (.010)</td><td>2 (.012)</td></tr><tr><td>ID</td><td>21 (.095)</td><td>19 (.047)</td><td>11 (.023)</td><td>4 (.013)</td><td>0 (.010)</td><td>8 (.017)</td><td>9 (.022)</td><td>11 (.025)</td><td>15 (.033)</td><td>0 (.010)</td><td>0 (.009)</td></tr><tr><td rowspan="2">512</td><td rowspan="2">10</td><td rowspan="2">0.791617</td><td>SW</td><td>20 (.102)</td><td>18 (.057)</td><td>16 (.035)</td><td>9 (.020)</td><td>0 (.011)</td><td>0 (.013)</td><td>8 (.017)</td><td>11 (.023)</td><td>15 (.031)</td><td>4 (.014)</td><td>0 (.012)</td></tr><tr><td>ID</td><td>21 (.104)</td><td>19 (.061)</td><td>17 (.037)</td><td>11 (.023)</td><td>0 (.011)</td><td>0 (.012)</td><td>6 (.016)</td><td>9 (.020)</td><td>14 (.026)</td><td>4 (.014)</td><td>0 (.011)</td></tr><tr><td rowspan="2">512</td><td rowspan="2">12</td><td rowspan="2">0.778697</td><td>SW</td><td>20 (.102)</td><td>18 (.062)</td><td>16 (.039)</td><td>13 (.024)</td><td>4 (.012)</td><td>0 (.008)</td><td>2 (.011)</td><td>8 (.015)</td><td>12 (.021)</td><td>8 (.014)</td><td>0 (.009)</td></tr><tr><td>ID</td><td>21 (.105)</td><td>19 (.065)</td><td>17 (.043)</td><td>15 (.028)</td><td>4 (.012)</td><td>0 (.009)</td><td>0 (.010)</td><td>5 (.014)</td><td>12 (.020)</td><td>5 (.014)</td><td>0 (.009)</td></tr><tr><td rowspan="2">1024</td><td rowspan="2">2</td><td rowspan="2">0.743523</td><td>SW</td><td>12 (.017)</td><td>2 (.003)</td><td>0 (.002)</td><td>4 (.005)</td><td>10 (.012)</td><td>12 (.016)</td><td>16 (.023)</td><td>18 (.027)</td><td>20 (.032)</td><td>7 (.006)</td><td>2 (.003)</td></tr><tr><td>ID</td><td>15 (.020)</td><td>5 (.004)</td><td>0 (.002)</td><td>2 (.003)</td><td>10 (.010)</td><td>12 (.016)</td><td>15 (.022)</td><td>16 (.025)</td><td>20 (.033)</td><td>6 (.006)</td><td>1 (.003)</td></tr><tr><td rowspan="2">1024</td><td rowspan="2">4</td><td rowspan="2">0.788879</td><td>SW</td><td>20 (.039)</td><td>4 (.008)</td><td>0 (.004)</td><td>1 (.005)</td><td>7 (.010)</td><td>13 (.017)</td><td>14 (.022)</td><td>16 (.025)</td><td>18 (.035)</td><td>4 (.008)</td><td>3 (.007)</td></tr><tr><td>ID</td><td>21 (.044)</td><td>7 (.009)</td><td>0 (.004)</td><td>0 (.004)</td><td>4 (.009)</td><td>12 (.014)</td><td>13 (.019)</td><td>15 (.023)</td><td>18 (.034)</td><td>4 (.007)</td><td>3 (.007)</td></tr><tr><td rowspan="2">1024</td><td rowspan="2">6</td><td rowspan="2">0.798798</td><td>SW</td><td>20 (.077)</td><td>15 (.025)</td><td>2 (.007)</td><td>0 (.005)</td><td>4 (.011)</td><td>10 (.015)</td><td>12 (.020)</td><td>14 (.024)</td><td>19 (.033)</td><td>7 (.012)</td><td>4 (.010)</td></tr><tr><td>ID</td><td>21 (.082)</td><td>17 (.029)</td><td>2 (.008)</td><td>0 (.005)</td><td>2 (.008)</td><td>8 (.013)</td><td>12 (.018)</td><td>12 (.022)</td><td>16 (.028)</td><td>2 (.009)</td><td>3 (.009)</td></tr><tr><td rowspan="2">1024</td><td rowspan="2">8</td><td rowspan="2">0.794565</td><td>SW</td><td>20 (.098)</td><td>18 (.048)</td><td>14 (.024)</td><td>4 (.010)</td><td>0 (.006)</td><td>5 (.011)</td><td>9 (.016)</td><td>13 (.020)</td><td>16 (.028)</td><td>1 (.007)</td><td>4 (.010)</td></tr><tr><td>ID</td><td>21 (.102)</td><td>19 (.052)</td><td>16 (.028)</td><td>9 (.013)</td><td>0 (.006)</td><td>4 (.010)</td><td>8 (.014)</td><td>10 (.016)</td><td>13 (.024)</td><td>0 (.007)</td><td>0 (.008)</td></tr><tr><td rowspan="2">1024</td><td rowspan="2">10</td><td rowspan="2">0.784313</td><td>SW</td><td>20 (.109)</td><td>18 (.062)</td><td>16 (.039)</td><td>14 (.024)</td><td>2 (.008)</td><td>0 (.007)</td><td>6 (.010)</td><td>10 (.013)</td><td>12 (.019)</td><td>0 (.006)</td><td>0 (.007)</td></tr><tr><td>ID</td><td>21 (.112)</td><td>19 (.066)</td><td>17 (.042)</td><td>15 (.026)</td><td>5 (.009)</td><td>0 (.006)</td><td>3 (.008)</td><td>6 (.011)</td><td>12 (.016)</td><td>0 (.006)</td><td>0 (.005)</td></tr><tr><td rowspan="2">1024</td><td rowspan="2">12</td><td rowspan="2">0.775083</td><td>SW</td><td>20 (.114)</td><td>18 (.071)</td><td>16 (.049)</td><td>14 (.034)</td><td>10 (.016)</td><td>0 (.008)</td><td>0 (.008)</td><td>5 (.010)</td><td>10 (.016)</td><td>3 (.010)</td><td>0 (.008)</td></tr><tr><td>ID</td><td>21 (.118)</td><td>19 (.074)</td><td>17 (.052)</td><td>15 (.037)</td><td>11 (.018)</td><td>0 (.009)</td><td>0 (.008)</td><td>0 (.009)</td><td>10 (.015)</td><td>1 (.009)</td><td>0 (.008)</td></tr></tbody></table>

For better readability, the top 4 methods for each instance are highlighted using a grayscale shading.
Results from static $\lambda$ settings confirm the observations from previous studies (Tari et al., 2022): best $\lambda$ values increase with both landscape size and ruggedness. $ID_{best}$ and $SW$ achieve similar performance rankings. The main factor affecting their performance is the $\lambda$ parameter. $ID_{best}$ performs better with slightly higher $\lambda$ values than $SW$. This aligns with $ID_{best}$'s ability to select improving neighbors without generating $\lambda$ neighbors at each iteration. However, no static $\lambda$ value proves robust across all landscapes. While variants with $\lambda = 48$ show the most stability, with a worst rank of 12, they rarely achieve top rankings. Similarly, variants with $\lambda = 24$ perform well in many instances but lack reliability, particularly on larger, more rugged landscapes (higher $k$ values), where they rank among the lowest performers.

Interestingly, the most robust approaches are the fixed ones, where the value of $\lambda$ is determined by NK landscape parameters ($n$ and $k$), as these consistently rank among the best. Though this formula applies specifically to NK landscapes, the results suggest that an effective $\lambda$ value can potentially be determined using landscape characteristics. The main challenge lies in empirically determining these characteristics before running the algorithm—a possible prospect for future investigations. It is important to remind that $k$ is unknown in a black-box scenario.

Adaptive variants (auto) produce slightly less robust results than fixed variants, though they consistently rank among the best methods. With larger instances, while they appear less often in top positions, they maintain strong performance—ASW achieving no worse than rank 8 and AID no worse than rank 6. Though their overall results are slightly below, these experiments show that both ASW and AID handle NK landscapes robustly. Moreover, the adaptive approach provides better generalization and simpler application to other problems, as will be demonstrated in later sections.

### 4.1.6 Sensitivity Analysis of the Window Size

In our experiments, the sliding window size $w$ is derived directly from the landscape diameter $d$ (where $d = n$ for NK landscapes). The measured distance aims to capture the diversification level of $SW$ by comparing its trajectory to that of a random walk. Since the diameter $d$ matches the minimum number of steps required for a random

<table><caption>Table 3: Statistical rank and relative fitness deviation of ASW on NK landscapes with different sliding window sizes ($w$).</caption><thead><tr><th>n</th><th>k</th><th>w = n/2</th><th>w = n</th><th>w = 2n</th><th>w = 4n</th></tr></thead><tbody><tr><td>128</td><td>1</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>128</td><td>2</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>128</td><td>4</td><td>0 (.001)</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>128</td><td>6</td><td>0 (.001)</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.001)</td></tr><tr><td>128</td><td>8</td><td>1 (.007)</td><td>1 (.004)</td><td>0 (.002)</td><td>0 (.000)</td></tr><tr><td>128</td><td>10</td><td>2 (.009)</td><td>0 (.004)</td><td>0 (.001)</td><td>0 (.000)</td></tr><tr><td>128</td><td>12</td><td>3 (.009)</td><td>0 (.003)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>256</td><td>1</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>256</td><td>2</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>256</td><td>4</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.001)</td><td>0 (.000)</td></tr><tr><td>256</td><td>6</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td>256</td><td>8</td><td>0 (.004)</td><td>0 (.000)</td><td>0 (.002)</td><td>0 (.000)</td></tr><tr><td>256</td><td>10</td><td>2 (.007)</td><td>0 (.003)</td><td>0 (.002)</td><td>0 (.000)</td></tr><tr><td>256</td><td>12</td><td>3 (.010)</td><td>1 (.004)</td><td>0 (.003)</td><td>0 (.000)</td></tr><tr><td>512</td><td>1</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.000)</td><td>0 (.001)</td></tr><tr><td>512</td><td>2</td><td>0 (.000)</td><td>0 (.001)</td><td>0 (.000)</td><td>0 (.001)</td></tr><tr><td>512</td><td>4</td><td>0 (.002)</td><td>0 (.000)</td><td>0 (.003)</td><td>0 (.002)</td></tr><tr><td>512</td><td>6</td><td>0 (.000)</td><td>0 (.001)</td><td>0 (.002)</td><td>0 (.003)</td></tr><tr><td>512</td><td>8</td><td>0 (.002)</td><td>0 (.000)</td><td>0 (.002)</td><td>0 (.001)</td></tr><tr><td>512</td><td>10</td><td>0 (.003)</td><td>0 (.001)</td><td>0 (.001)</td><td>0 (.000)</td></tr><tr><td>512</td><td>12</td><td>3 (.006)</td><td>0 (.003)</td><td>0 (.000)</td><td>0 (.000)</td></tr></tbody></table>
walk to reach any solution from its starting point, we hypothesize that the window size $w$ should be chosen to reflect this scale. This section provides experiments to validate this observation.

Under a similar experimental setup, we conducted runs on NK landscapes with ASW using the following settings for $w \in \{n/2, n, 2n, 4n\}$, with $n = d$ being the NK landscape diameter. Results are reported in Table 3 where the integer values indicate how many times each ASW version is statistically outperformed by any of the other three. Values in bracket represent the average deviation to the best fitness for the corresponding instance.

Our analysis reveals very minor differences between the considered values for $w$. Notably, there is no significant difference between $w = 2n$ and $w = 4n$, and neither is statistically outperformed by smaller values of $w$. While larger $w$ values tend to yield marginally better results, this improvement becomes statistically insignificant once $w > n$.

The results can be intuitively interpreted as follows. In a binary fitness landscape of size $n$, the expected distance between two random solutions is $n/2$. We here set the $\lambda$ value based on the degree of similarity of SW with a random walk—i.e., a $(1,\lambda)$-EA. For a random walk, the distance after $n/2$ steps is typically less than $n/2$ because we may flip the same bits multiple times. In fact, the expected distance achieved after $k$ random moves can be computed using the Jukes and Cantor (1969) correction from genomics. For a binary string of size $n$, the expected distance is about $0.31n$, $0.43n$, $0.49n$, and $0.4998n$ after $n/2$, $n$, $2n$, and $4n$ random moves, respectively.

Given these findings, we set the sliding window to twice the landscape diameter ($w = 2n$) as the default in our experiments.

### 4.1.7 Anytime Performance

Previous results examined performance under a fixed budget of 100 million evaluations. We now investigate how performance changes across various budgets by analyzing the algorithms' anytime behavior. Recall that SW and ID evaluate at most $\lambda$ neighbors per iteration, resulting in more evaluations per iteration and fewer iterations in comparison with $\lambda = 1$. Figure 2 shows the average relative deviation from the best-known results over time for SW and ID variants on four representative NK landscapes. Note that both the number of evaluations and fitness deviations are shown on logarithmic scales.

The figures on top report results for SW variants, revealing minimal changes in the best $\lambda$ value across different budgets for static variants. The fixed $\lambda$ setting consistently ranks among the closest methods to the best-known solutions. ASW (auto) shows similar performance, but only on rugged landscapes. On smoother landscapes, ASW initially performs worse than other variants before becoming one of the best—a shift occurring early in the search process, before 100k evaluations. The bottom figures show the counterpart for ID variants. At 100 evaluations, ID variants outperform SW variants because they completed more iterations, as ID does not evaluate $\lambda$ neighbors at every step. AID's ranking among ID variants is lower than ASW's ranking among SW variants in the early stages of the search process. This suggests that this method of adjusting $\lambda$ may be more effective when the number of evaluated neighbors per iteration remains constant.

In Figure 3, we show how $\lambda$ evolves over time for ASW and AID. Both adaptive versions show a sharp increase in $\lambda$ at the search's start to intensify the process. This increase occurs more rapidly and reaches higher values for AID, because it can select
<figure><img src="image_3.png" /><figcaption>Figure 2: Anytime performance of SW and ID variants on selected NK landscapes.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3: Evolution of $\lambda$ for ASW and AID on selected NK landscapes.</figcaption></figure>

improving neighbors without evaluating all $\lambda$ neighbors, while ASW takes a slightly more intensification-focused path. For both methods, $\lambda$ then drops significantly—at around 1 000 evaluations for $n = 128$ and 10 000 evaluations for $n = 512$. The value then stabilizes after several thousand evaluations for $n = 128$ and about 100k evaluations for $n = 512$. Interestingly, for larger instances, the adaptive lambda settles near the value used in FSW. Although more intensification is required at the start of the search process, the peak in $\lambda$ evolution might be lower under another initial $\lambda$ value.

## 4.2 NKq Landscapes

The first set of experiments assessed the robustness of ASW and AID on landscapes with adjustable ruggedness, though these landscapes lack neutrality. Neutrality is a common property in fitness landscapes, and is an important factor affecting optimization algorithm performance. There exist NK landscape variants that allow for the creation of landscapes with adjustable neutrality levels, such as NKq landscapes (Newman and Engelhardt, 1998). In this model, fitness contributions $C_i$ are discretized, where fewer possible values lead to a higher probability of neutral neighbors. The discretization is controlled by a parameter $q \ge 2$, which specifies the co-domain size of functions $C_i$. Maximum neutrality occurs at $q = 2$ and diminishes as $q$ increases.<fnref n="2" /> In other words, $q$ represents the number of distinct values each fitness contribution can take. For $q = 2$, each contribution is either 0 or 1. For further details, readers are referred to Newman and Engelhardt (1998).

<footnote n="2">²While $q = 1$ would technically yield the highest neutrality rate, it would produce entirely flat landscapes.</footnote>
<table><caption>Table 4: Statistical rank and relative fitness deviation of SW and ID variants on NKq landscapes.</caption><thead><tr><th>q</th><th>n</th><th>k</th><th>best</th><th>algo</th><th>8</th><th>16</th><th>24</th><th>32</th><th>48</th><th>64</th><th>80</th><th>96</th><th>128</th><th>auto</th><th>fixed</th></tr></thead><tbody><tr><td rowspan="2">2</td><td rowspan="2">128</td><td rowspan="2">4</td><td rowspan="2">0.984375</td><td>SW</td><td>11 (.013)</td><td>0 (.000)</td><td>0 (.003)</td><td>8 (.007)</td><td>10 (.012)</td><td>11 (.018)</td><td>17 (.029)</td><td>17 (.038)</td><td>20 (.058)</td><td>0 (.000)</td><td>0 (.002)</td></tr><tr><td>ID</td><td>13 (.020)</td><td>0 (.002)</td><td>0 (.000)</td><td>3 (.003)</td><td>9 (.008)</td><td>11 (.015)</td><td>12 (.018)</td><td>13 (.025)</td><td>20 (.055)</td><td>0 (.001)</td><td>0 (.001)</td></tr><tr><td rowspan="2">2</td><td rowspan="2">128</td><td rowspan="2">10</td><td rowspan="2">0.984375</td><td>SW</td><td>18 (.069)</td><td>11 (.033)</td><td>1 (.021)</td><td>0 (.017)</td><td>0 (.021)</td><td>11 (.030)</td><td>14 (.042)</td><td>16 (.049)</td><td>20 (.106)</td><td>5 (.021)</td><td>0 (.017)</td></tr><tr><td>ID</td><td>19 (.077)</td><td>14 (.038)</td><td>2 (.021)</td><td>0 (.017)</td><td>0 (.017)</td><td>3 (.022)</td><td>11 (.029)</td><td>12 (.037)</td><td>20 (.109)</td><td>1 (.021)</td><td>0 (.016)</td></tr><tr><td rowspan="2">2</td><td rowspan="2">512</td><td rowspan="2">4</td><td rowspan="2">0.980469</td><td>SW</td><td>20 (.048)</td><td>9 (.009)</td><td>0 (.004)</td><td>2 (.006)</td><td>10 (.012)</td><td>12 (.018)</td><td>15 (.022)</td><td>16 (.027)</td><td>19 (.036)</td><td>4 (.007)</td><td>2 (.006)</td></tr><tr><td>ID</td><td>21 (.063)</td><td>12 (.017)</td><td>3 (.005)</td><td>0 (.003)</td><td>0 (.005)</td><td>8 (.010)</td><td>11 (.014)</td><td>11 (.015)</td><td>16 (.024)</td><td>0 (.004)</td><td>0 (.003)</td></tr><tr><td rowspan="2">2</td><td rowspan="2">512</td><td rowspan="2">10</td><td rowspan="2">0.962891</td><td>SW</td><td>20 (.116)</td><td>18 (.066)</td><td>16 (.041)</td><td>14 (.027)</td><td>1 (.012)</td><td>0 (.009)</td><td>3 (.012)</td><td>4 (.014)</td><td>13 (.022)</td><td>7 (.015)</td><td>1 (.011)</td></tr><tr><td>ID</td><td>21 (.126)</td><td>19 (.076)</td><td>17 (.050)</td><td>15 (.034)</td><td>7 (.016)</td><td>0 (.010)</td><td>0 (.008)</td><td>0 (.010)</td><td>4 (.014)</td><td>10 (.017)</td><td>7 (.016)</td></tr><tr><td rowspan="2">5</td><td rowspan="2">128</td><td rowspan="2">4</td><td rowspan="2">0.859375</td><td>SW</td><td>10 (.009)</td><td>0 (.000)</td><td>6 (.002)</td><td>8 (.004)</td><td>10 (.011)</td><td>15 (.022)</td><td>15 (.030)</td><td>16 (.036)</td><td>20 (.087)</td><td>0 (.000)</td><td>0 (.001)</td></tr><tr><td>ID</td><td>11 (.012)</td><td>0 (.000)</td><td>0 (.001)</td><td>7 (.002)</td><td>10 (.008)</td><td>12 (.015)</td><td>14 (.022)</td><td>15 (.027)</td><td>20 (.078)</td><td>0 (.000)</td><td>0 (.000)</td></tr><tr><td rowspan="2">5</td><td rowspan="2">128</td><td rowspan="2">10</td><td rowspan="2">0.867188</td><td>SW</td><td>17 (.066)</td><td>9 (.026)</td><td>0 (.016)</td><td>0 (.015)</td><td>6 (.022)</td><td>13 (.036)</td><td>14 (.046)</td><td>17 (.058)</td><td>20 (.123)</td><td>2 (.017)</td><td>0 (.016)</td></tr><tr><td>ID</td><td>19 (.072)</td><td>10 (.031)</td><td>0 (.016)</td><td>0 (.012)</td><td>2 (.018)</td><td>9 (.028)</td><td>13 (.040)</td><td>14 (.048)</td><td>20 (.115)</td><td>2 (.019)</td><td>0 (.013)</td></tr><tr><td rowspan="2">5</td><td rowspan="2">512</td><td rowspan="2">4</td><td rowspan="2">0.853027</td><td>SW</td><td>19 (.040)</td><td>8 (.009)</td><td>0 (.005)</td><td>0 (.007)</td><td>10 (.013)</td><td>12 (.018)</td><td>14 (.025)</td><td>15 (.028)</td><td>19 (.040)</td><td>0 (.007)</td><td>0 (.006)</td></tr><tr><td>ID</td><td>20 (.046)</td><td>9 (.012)</td><td>0 (.005)</td><td>0 (.005)</td><td>5 (.009)</td><td>10 (.015)</td><td>13 (.022)</td><td>14 (.026)</td><td>15 (.031)</td><td>0 (.005)</td><td>0 (.005)</td></tr><tr><td rowspan="2">5</td><td rowspan="2">512</td><td rowspan="2">10</td><td rowspan="2">0.852051</td><td>SW</td><td>20 (.111)</td><td>18 (.063)</td><td>15 (.037)</td><td>11 (.023)</td><td>0 (.011)</td><td>5 (.013)</td><td>6 (.016)</td><td>11 (.021)</td><td>15 (.032)</td><td>2 (.013)</td><td>0 (.010)</td></tr><tr><td>ID</td><td>21 (.116)</td><td>19 (.068)</td><td>17 (.042)</td><td>13 (.026)</td><td>0 (.011)</td><td>0 (.010)</td><td>2 (.013)</td><td>8 (.017)</td><td>12 (.025)</td><td>4 (.014)</td><td>0 (.011)</td></tr></tbody></table>

### 4.2.1 Performance Comparison

In this section, we analyze eight NKq instances with two different values for size, interdependency levels, and neutrality levels. Using the same experimental setup and methods described earlier, we present our results in Table 4.

The fixed settings of $\lambda$ for SW and IDbest has not been previously studied on neutral NK landscapes. For these methods, when $q = 5$, the ideal $\lambda$ value corresponds to that found in standard (non-neutral) NK landscapes. As neutrality increases ($q = 2$), the ideal $\lambda$ value slightly increases for both methods. When ruggedness is higher ($k = 10$), the gap in best $\lambda$ values between SW and IDbest becomes more pronounced than in standard NK landscapes. This gap further increases at higher neutrality levels ($q = 5$).

Let us now turn our attention to fixed variants. fixed SW and ID consistently rank among the best methods—except perhaps on the largest instance with higher ruggedness and neutrality rates. While fixed ID typically performs well on NK landscapes without neutrality at this size and ruggedness level, an interesting discrepancy emerges: the best $\lambda$ value matches for SW and IDbest, which is not the case here. This difference might stem from the fixed $\lambda$ value, given the larger gap between ideal $\lambda$ values. The formula appears less effective when applied to larger, more rugged landscapes with high neutrality levels.

Overall, on such neutral landscapes, the adaptive variants perform slightly less efficiently compared to standard NK landscapes. Their robustness is higher when there is no or low neutrality, yet they remain notably higher than any static $\lambda$ value.

### 4.2.2 Anytime Performance

In Figure 4, we report the anytime performance of SW and ID variants on four selected NKq landscapes with the highest level of neutrality ($q = 2$). The behavior of these approaches is similar to what was observed on standard NK landscapes. The relative efficiency of static $\lambda$ values shows more variation, and the main difference is that the peak performance of ASW and AID is significantly lower compared to standard NK landscapes with the same $n$ and $k$ values.

Figure 5 shows the evolution of $\lambda$ over time for ASW and AID. Both methods exhibit an initial increase in $\lambda$ at the search process's start, followed by a swift decrease and
<figure><img src="image_5.png" /><figcaption>Figure 4: Anytime performance of SW and ID variants on selected NKq landscapes.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: Evolution of $\lambda$ for ASW and AID on selected NKq landscapes.</figcaption></figure>

stabilization. AID reaches its $\lambda$ peak sooner than with standard NK landscapes. This is likely due to its immediate selection of improving or neutral neighbors. After $\lambda$ stabilizes, the gap between ASW and AID becomes more distinct. Compared to non-neutral NK landscapes, these values show closer alignment with fixed $\lambda$ for $n = 128$, but is higher for $n = 512$.

# 5 Experimental Analysis on Permutation Problems

In this section, we expand our analysis beyond pseudo-Boolean problems and examine two permutation problems previously studied with PNLS: the quadratic assignment problem (QAP) and the permutation flowshop scheduling problem (FSP). These problems require different neighborhood operators, which also broadens our previous analysis. We define distance measures for these landscapes and discuss how to adjust $\lambda$ according to these distances.

## 5.1 Quadratic Assignment and Flowshop Scheduling Problems

**QAP.** The quadratic assignment problem (QAP) is an NP-hard permutation problem (Sahni and Gonzalez, 1976). In QAP, one must allocate $n$ units to $n$ locations according to two matrices: one for distances between pairs of location $(d_{ij})_{1 \le i,j \le n}$, and one for flows between pairs of units $(f_{rs})_{1 \le r,s \le n}$. A solution $x \in \mathcal{X}$ describes the allocations of units to locations. The objective function, to be minimized, is the sum of
distances multiplied by the corresponding flows. It is defined as follows:

$$f(x) = \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij} f_{x_i x_j} \qquad (2)$$

where $x_i$ represents the i-th element of solution $x$.

In the following we consider 23 QAP instances from the QAPLIB (Burkard et al., 1997). We focus on two classes:

* sko instances have rectangular distances and pseudo-random numbers as entries in flow matrices. We analyze all 13 instances from this class.

* tai instances come in two variants: those ending with an a are uniformly generated, while those ending with a b are asymmetric and randomly generated. We analyze 10 instances from this class, spanning approximately the same dimension range as sko instances.

**FSP.** The permutation flowshop scheduling problem (FSP) is also a widely-studied NP-hard permutation combinatorial optimization problem (Garey et al., 1976). An FSP instance consists of $n$ jobs to be scheduled on $m$ machines, where $n \times m$ values represent the processing time of each job on each machine. A solution $x$ is a permutation of jobs and corresponds to a specific scheduling plan. This scheduling is identical across all machines and must satisfy the following constraints: (1) a job cannot be processed on two machines simultaneously, and (2) only one job can be processed at the time on any given machine. All jobs must be processed sequentially on all machines, beginning with the first machine and proceeding in order. The objective function $C_{max}$, to be minimized, represents the total completion time (or makespan) and is defined as follows:

$$C_{max}(x) = \max_{i \in [1..n]} \{s_{im} + t_{im}\} \qquad (3)$$

where $t_{ij}$ represents the processing time of job $i$ on machine $j$, and $s_{ij}$ is the time at which job $i$ starts on machine $j$.

We consider 9 FSP instances from Taillard (1993), with $n \in \{50, 70, 100\}$ jobs and $m \in \{10, 15, 20\}$ machines. Processing times are generated following a discrete uniform distribution in [1..99]. The benchmark parameters—particularly the number of machines— is known to affect the ruggedness and neutrality of FSP.

## 5.2 Neighborhood, Distance Measures and $\lambda$

In the following, we consider the neighborhood operators the most commonly used on each problem: interchange for the QAP and insert for the FSP. Both operators act on permutations and are commonly used for their respective problems: interchange swaps the positions of two elements in the permutation, while insert moves an element to a new position, shifting the intervening elements accordingly.

Given the landscapes resulting from these operators, we seek to compute the distance between two solutions that corresponds to the minimum number of moves required to connect them. Computing such distances is not trivial but can be done in reasonable time for both operators (Schiaviinotto and Stützle, 2007). For interchange, the distance corresponds to the permutation size minus the number of cycles between the two permutations, and is computed in $O(n)$ (Cicirello and Cernera, 2013). For insert,
the distance corresponds to *n* minus the longest common subsequence. This computation can be made in $O(n^2)$ using a simple implementation. However, the computation can be improved to $O(n \log(n))$ with a clever implementation (Hernando et al., 2016).

Let us now focus on setting $\lambda$ values. Consider a diameter function $D(n)$ that computes the diameter of an instance of size $n$, and a neighborhood size function $\Delta(n)$. We need to define a mapping function $\Lambda(\delta)$ that transforms a distance ($\le \Delta(n)$) into a lambda value ($\le \Lambda(n)$). For many combinatorial optimization problems, $D$ and $\Delta$ depend solely on $n$ and increase with it. Distances varies between 0 and $n$, whereas $\lambda$ values are between 1 and $||N||$. In such case, a simple way to achieve such a mapping is to define $\Lambda(\delta) = \Delta(D^{-1}(\delta))$. Let $S_k$ denote SW's current solution after $k$ steps. At a given step $k$, we propose to define $\lambda$ as the number of neighbors of $S_k$ that drive the search to move toward solution $S_{k-w}$. Defining $\Lambda(\delta) = \Delta(D^{-1}(\delta))$ leads to approximate such values.

To transpose distance values to $\lambda$ values in the context of FSP and QAP, we must consider their associated landscape diameter and neighborhood size. The diameter of FSP and QAP landscapes equals the permutation size minus 1. Both neighborhood sizes are quadratic in $n$, though the interchange neighborhood is about twice as large—specifically, $(n-1)^2$ for FSP and $n(n-1)/2$ for QAP.

As such, we define $\lambda$ such that if the distance $\delta$ reaches the landscape diameter, the entire neighborhood should be explored. Given that the maximal distance $\delta$ is $n-1$ for both neighborhood operators, we adjust the neighborhood size formula by setting $n$ to $\delta+1$. This ensures that, when $\delta$ is maximal, $\lambda$ matches the neighborhood size. This gives us the following formula (ensuring $\lambda > 0$):

* QAP: $\Lambda(\delta) = \max(\delta(\delta + 1)/2, 1)$,

* FSP: $\Lambda(\delta) = \max(\delta^2, 1)$.

This definition creates a mapping from increasing distance values to increasing $\lambda$ values, as the maximal value of $\delta$ is $n-1$. When the exploration rate is minimal (distance equals to 0 or 1), the adaptive setting is $\Lambda(\delta) = 1$, which leads ASW to make a random move. Conversely, when the exploration rate is maximal, $\Lambda(\delta)$ is automatically set to the neighborhood size, and ASW selects the best neighbor.

## 5.3 Experimental Results on QAP

Below, we begin by analyzing results on QAP instances.

### 5.3.1 Performance Comparison

We conduct experiments on the 23 considered QAP instances using static SW and IDbest with $\lambda \in \{25, 50, 75, 100, 150, 200, 300, 400, 600, 800\}$. These configurations, when combined with the proposed adaptive parameter schemes (ASW and AID), lead to a total of 22 algorithms (except for the two smallest instances). We use the same stopping criterion and number of runs as in the previous experiments.

Results are reported in Table 5. Interestingly, SW and IDbest achieve their best results with a higher $\lambda$ value for tai*a* instances than tai*b* instances. The ideal $\lambda$ value increases with the landscape size for tai*a*, while it is always the smallest one for tai*b*. On both cases, SW and IDbest achieve their best results under similar $\lambda$ values. For sko instances, SW and IDbest with $\lambda = 200$ are always top-ranked, but at least two other values typically lead to similar results. For the smallest sko instances, $\lambda = 150$ consistently works, while for the largest ones, $\lambda = 300$ consistently works. On these
<table><caption>Table 5: Statistical rank and relative fitness deviation of SW and ID variants on QAP instances.</caption><thead><tr><th>instance</th><th>best</th><th>algo</th><th>25</th><th>50</th><th>75</th><th>100</th><th>150</th><th>200</th><th>300</th><th>400</th><th>600</th><th>800</th><th>auto</th></tr></thead><tbody><tr><td rowspan="2">tai40a</td><td rowspan="2">3139370</td><td>SW</td><td>18 (.036)</td><td>15 (.021)</td><td>12 (.013)</td><td>6 (.009)</td><td>0 (.004)</td><td>0 (.004)</td><td>3 (.006)</td><td>7 (.009)</td><td>14 (.018)</td><td>-6 (.008)</td><td></td></tr><tr><td>ID</td><td>18 (.037)</td><td>16 (.022)</td><td>12 (.014)</td><td>6 (.009)</td><td>0 (.005)</td><td>0 (.004)</td><td>1 (.005)</td><td>5 (.007)</td><td>13 (.016)</td><td>-6 (.008)</td><td></td></tr><tr><td rowspan="2">tai40b</td><td rowspan="2">637250948</td><td>SW</td><td>0 (.040)</td><td>3 (.085)</td><td>4 (.096)</td><td>4 (.091)</td><td>4 (.095)</td><td>4 (.103)</td><td>5 (.103)</td><td>3 (.089)</td><td>5 (.107)</td><td>-1 (.057)</td><td></td></tr><tr><td>ID</td><td>0 (.035)</td><td>3 (.075)</td><td>3 (.080)</td><td>3 (.075)</td><td>3 (.079)</td><td>3 (.079)</td><td>6 (.083)</td><td>6 (.083)</td><td>10 (.085)</td><td>-0 (.046)</td><td></td></tr><tr><td rowspan="2">tai50a</td><td rowspan="2">4957568</td><td>SW</td><td>20 (.041)</td><td>18 (.029)</td><td>16 (.022)</td><td>14 (.016)</td><td>7 (.009)</td><td>3 (.006)</td><td>0 (.004)</td><td>0 (.004)</td><td>7 (.008)</td><td>12 (.014)</td><td>7 (.009)</td></tr><tr><td>ID</td><td>21 (.043)</td><td>18 (.029)</td><td>16 (.023)</td><td>14 (.017)</td><td>8 (.009)</td><td>3 (.006)</td><td>0 (.004)</td><td>0 (.004)</td><td>4 (.006)</td><td>11 (.011)</td><td>7 (.009)</td></tr><tr><td rowspan="2">tai50b</td><td rowspan="2">459688989</td><td>SW</td><td>0 (.010)</td><td>2 (.040)</td><td>2 (.044)</td><td>2 (.044)</td><td>2 (.053)</td><td>2 (.055)</td><td>2 (.061)</td><td>2 (.057)</td><td>3 (.061)</td><td>2 (.063)</td><td>2 (.046)</td></tr><tr><td>ID</td><td>0 (.011)</td><td>2 (.046)</td><td>2 (.050)</td><td>2 (.051)</td><td>3 (.057)</td><td>2 (.057)</td><td>8 (.061)</td><td>8 (.063)</td><td>9 (.064)</td><td>11 (.065)</td><td>2 (.045)</td></tr><tr><td rowspan="2">tai60a</td><td rowspan="2">7229070</td><td>SW</td><td>20 (.047)</td><td>18 (.034)</td><td>16 (.027)</td><td>14 (.022)</td><td>12 (.016)</td><td>9 (.011)</td><td>1 (.006)</td><td>0 (.004)</td><td>0 (.005)</td><td>5 (.008)</td><td>8 (.010)</td></tr><tr><td>ID</td><td>20 (.048)</td><td>18 (.035)</td><td>16 (.028)</td><td>14 (.023)</td><td>13 (.017)</td><td>10 (.012)</td><td>4 (.007)</td><td>0 (.005)</td><td>0 (.005)</td><td>4 (.007)</td><td>8 (.010)</td></tr><tr><td rowspan="2">tai60b</td><td rowspan="2">608215054</td><td>SW</td><td>0 (.013)</td><td>2 (.039)</td><td>2 (.052)</td><td>5 (.072)</td><td>9 (.078)</td><td>5 (.072)</td><td>5 (.067)</td><td>8 (.086)</td><td>6 (.074)</td><td>6 (.079)</td><td>4 (.063)</td></tr><tr><td>ID</td><td>0 (.014)</td><td>2 (.035)</td><td>2 (.042)</td><td>3 (.052)</td><td>4 (.059)</td><td>6 (.063)</td><td>6 (.063)</td><td>6 (.065)</td><td>6 (.064)</td><td>6 (.065)</td><td>2 (.044)</td></tr><tr><td rowspan="2">tai80a</td><td rowspan="2">13578346</td><td>SW</td><td>20 (.046)</td><td>18 (.035)</td><td>16 (.029)</td><td>14 (.025)</td><td>12 (.020)</td><td>10 (.016)</td><td>8 (.011)</td><td>4 (.007)</td><td>0 (.004)</td><td>0 (.004)</td><td>5 (.009)</td></tr><tr><td>ID</td><td>21 (.047)</td><td>19 (.036)</td><td>17 (.030)</td><td>15 (.026)</td><td>12 (.021)</td><td>10 (.017)</td><td>8 (.012)</td><td>4 (.008)</td><td>2 (.005)</td><td>0 (.003)</td><td>5 (.009)</td></tr><tr><td rowspan="2">tai80b</td><td rowspan="2">819901280</td><td>SW</td><td>0 (.013)</td><td>2 (.022)</td><td>4 (.036)</td><td>4 (.042)</td><td>7 (.048)</td><td>8 (.055)</td><td>6 (.049)</td><td>7 (.054)</td><td>8 (.056)</td><td>10 (.056)</td><td>6 (.049)</td></tr><tr><td>ID</td><td>0 (.013)</td><td>2 (.023)</td><td>4 (.035)</td><td>4 (.038)</td><td>6 (.043)</td><td>6 (.045)</td><td>7 (.047)</td><td>7 (.048)</td><td>9 (.049)</td><td>11 (.050)</td><td>4 (.044)</td></tr><tr><td rowspan="2">tai100a</td><td rowspan="2">21166614</td><td>SW</td><td>20 (.046)</td><td>18 (.036)</td><td>16 (.030)</td><td>14 (.027)</td><td>12 (.022)</td><td>10 (.018)</td><td>8 (.014)</td><td>6 (.011)</td><td>2 (.007)</td><td>0 (.004)</td><td>3 (.008)</td></tr><tr><td>ID</td><td>21 (.047)</td><td>19 (.037)</td><td>17 (.031)</td><td>15 (.028)</td><td>12 (.023)</td><td>11 (.020)</td><td>8 (.014)</td><td>6 (.011)</td><td>2 (.007)</td><td>0 (.005)</td><td>3 (.008)</td></tr><tr><td rowspan="2">tai100b</td><td rowspan="2">1188293476</td><td>SW</td><td>0 (.015)</td><td>0 (.017)</td><td>1 (.025)</td><td>3 (.027)</td><td>4 (.033)</td><td>4 (.032)</td><td>5 (.036)</td><td>5 (.039)</td><td>9 (.044)</td><td>8 (.045)</td><td>5 (.036)</td></tr><tr><td>ID</td><td>0 (.014)</td><td>0 (.016)</td><td>0 (.021)</td><td>2 (.025)</td><td>5 (.031)</td><td>6 (.032)</td><td>6 (.035)</td><td>7 (.036)</td><td>9 (.038)</td><td>9 (.038)</td><td>4 (.032)</td></tr><tr><td rowspan="2">sko42</td><td rowspan="2">15812</td><td>SW</td><td>14 (.011)</td><td>10 (.003)</td><td>3 (.001)</td><td>0 (.001)</td><td>0 (.001)</td><td>0 (.001)</td><td>10 (.005)</td><td>13 (.010)</td><td>15 (.016)</td><td>20 (.027)</td><td>0 (.001)</td></tr><tr><td>ID</td><td>14 (.012)</td><td>10 (.003)</td><td>7 (.001)</td><td>0 (.001)</td><td>0 (.001)</td><td>0 (.001)</td><td>10 (.003)</td><td>12 (.008)</td><td>18 (.018)</td><td>19 (.024)</td><td>0 (.001)</td></tr><tr><td rowspan="2">sko49</td><td rowspan="2">23386</td><td>SW</td><td>16 (.014)</td><td>12 (.005)</td><td>8 (.002)</td><td>6 (.001)</td><td>0 (.001)</td><td>0 (.001)</td><td>7 (.003)</td><td>11 (.006)</td><td>16 (.011)</td><td>18 (.018)</td><td>0 (.001)</td></tr><tr><td>ID</td><td>19 (.015)</td><td>12 (.005)</td><td>8 (.003)</td><td>6 (.001)</td><td>0 (.001)</td><td>0 (.001)</td><td>6 (.003)</td><td>9 (.005)</td><td>16 (.011)</td><td>16 (.015)</td><td>0 (.001)</td></tr><tr><td rowspan="2">sko56</td><td rowspan="2">34458</td><td>SW</td><td>18 (.015)</td><td>12 (.007)</td><td>5 (.004)</td><td>0 (.003)</td><td>0 (.002)</td><td>0 (.003)</td><td>7 (.004)</td><td>10 (.007)</td><td>16 (.012)</td><td>17 (.015)</td><td>0 (.002)</td></tr><tr><td>ID</td><td>20 (.016)</td><td>12 (.007)</td><td>7 (.004)</td><td>0 (.003)</td><td>0 (.002)</td><td>0 (.002)</td><td>0 (.004)</td><td>8 (.006)</td><td>15 (.010)</td><td>16 (.012)</td><td>0 (.002)</td></tr><tr><td rowspan="2">sko64</td><td rowspan="2">48498</td><td>SW</td><td>20 (.017)</td><td>13 (.007)</td><td>8 (.004)</td><td>4 (.002)</td><td>0 (.001)</td><td>0 (.002)</td><td>3 (.003)</td><td>7 (.005)</td><td>14 (.009)</td><td>17 (.012)</td><td>0 (.001)</td></tr><tr><td>ID</td><td>21 (.018)</td><td>14 (.007)</td><td>8 (.004)</td><td>5 (.003)</td><td>0 (.002)</td><td>0 (.002)</td><td>0 (.003)</td><td>9 (.005)</td><td>13 (.007)</td><td>15 (.010)</td><td>0 (.001)</td></tr><tr><td rowspan="2">sko72</td><td rowspan="2">66256</td><td>SW</td><td>20 (.018)</td><td>14 (.008)</td><td>11 (.005)</td><td>4 (.003)</td><td>0 (.002)</td><td>0 (.002)</td><td>0 (.003)</td><td>8 (.006)</td><td>12 (.007)</td><td>13 (.009)</td><td>0 (.002)</td></tr><tr><td>ID</td><td>20 (.019)</td><td>15 (.009)</td><td>11 (.005)</td><td>6 (.004)</td><td>0 (.002)</td><td>0 (.002)</td><td>0 (.003)</td><td>11 (.006)</td><td>13 (.009)</td><td>0 (.003)</td><td></td></tr><tr><td rowspan="2">sko81</td><td rowspan="2">92014</td><td>SW</td><td>20 (.013)</td><td>9 (.007)</td><td>0 (.005)</td><td>0 (.004)</td><td>0 (.005)</td><td>0 (.004)</td><td>3 (.007)</td><td>9 (.007)</td><td>11 (.009)</td><td>16 (.011)</td><td>0 (.006)</td></tr><tr><td>ID</td><td>21 (.014)</td><td>11 (.008)</td><td>0 (.005)</td><td>0 (.005)</td><td>0 (.004)</td><td>0 (.005)</td><td>0 (.005)</td><td>8 (.007)</td><td>11 (.009)</td><td>15 (.010)</td><td>0 (.004)</td></tr><tr><td rowspan="2">sko90</td><td rowspan="2">115556</td><td>SW</td><td>20 (.019)</td><td>17 (.010)</td><td>11 (.006)</td><td>8 (.005)</td><td>0 (.003)</td><td>0 (.003)</td><td>0 (.004)</td><td>5 (.005)</td><td>8 (.006)</td><td>11 (.008)</td><td>0 (.003)</td></tr><tr><td>ID</td><td>21 (.020)</td><td>18 (.010)</td><td>13 (.007)</td><td>8 (.005)</td><td>1 (.003)</td><td>0 (.003)</td><td>0 (.003)</td><td>0 (.003)</td><td>7 (.005)</td><td>11 (.007)</td><td>0 (.003)</td></tr><tr><td rowspan="2">sko100a</td><td rowspan="2">152046</td><td>SW</td><td>20 (.019)</td><td>18 (.010)</td><td>12 (.006)</td><td>10 (.004)</td><td>4 (.003)</td><td>0 (.002)</td><td>0 (.003)</td><td>0 (.003)</td><td>10 (.006)</td><td>12 (.007)</td><td>0 (.002)</td></tr><tr><td>ID</td><td>21 (.020)</td><td>19 (.010)</td><td>13 (.007)</td><td>10 (.005)</td><td>4 (.003)</td><td>0 (.002)</td><td>0 (.002)</td><td>0 (.003)</td><td>8 (.005)</td><td>10 (.006)</td><td>0 (.002)</td></tr><tr><td rowspan="2">sko100b</td><td rowspan="2">153898</td><td>SW</td><td>20 (.018)</td><td>18 (.009)</td><td>13 (.006)</td><td>9 (.005)</td><td>0 (.003)</td><td>0 (.003)</td><td>0 (.003)</td><td>1 (.004)</td><td>9 (.006)</td><td>9 (.005)</td><td>0 (.002)</td></tr><tr><td>ID</td><td>21 (.019)</td><td>19 (.010)</td><td>14 (.006)</td><td>9 (.005)</td><td>1 (.003)</td><td>0 (.003)</td><td>0 (.003)</td><td>0 (.002)</td><td>6 (.005)</td><td>9 (.005)</td><td>0 (.003)</td></tr><tr><td rowspan="2">sko100c</td><td rowspan="2">147868</td><td>SW</td><td>20 (.018)</td><td>16 (.010)</td><td>11 (.006)</td><td>2 (.005)</td><td>0 (.003)</td><td>0 (.003)</td><td>0 (.004)</td><td>1 (.005)</td><td>7 (.007)</td><td>16 (.010)</td><td>0 (.004)</td></tr><tr><td>ID</td><td>21 (.019)</td><td>16 (.010)</td><td>11 (.007)</td><td>5 (.005)</td><td>1 (.004)</td><td>0 (.003)</td><td>0 (.003)</td><td>0 (.003)</td><td>6 (.006)</td><td>12 (.008)</td><td>0 (.004)</td></tr><tr><td rowspan="2">sko100d</td><td rowspan="2">149614</td><td>SW</td><td>20 (.018)</td><td>18 (.010)</td><td>13 (.006)</td><td>11 (.005)</td><td>2 (.004)</td><td>0 (.003)</td><td>0 (.003)</td><td>2 (.004)</td><td>10 (.005)</td><td>11 (.007)</td><td>0 (.003)</td></tr><tr><td>ID</td><td>21 (.019)</td><td>19 (.010)</td><td>15 (.007)</td><td>11 (.005)</td><td>2 (.003)</td><td>0 (.002)</td><td>0 (.002)</td><td>0 (.003)</td><td>2 (.004)</td><td>11 (.006)</td><td>0 (.003)</td></tr><tr><td rowspan="2">sko100e</td><td rowspan="2">149174</td><td>SW</td><td>20 (.020)</td><td>16 (.010)</td><td>9 (.006)</td><td>4 (.005)</td><td>0 (.004)</td><td>0 (.003)</td><td>0 (.004)</td><td>0 (.005)</td><td>8 (.007)</td><td>13 (.009)</td><td>0 (.004)</td></tr><tr><td>ID</td><td>21 (.020)</td><td>17 (.010)</td><td>12 (.007)</td><td>6 (.006)</td><td>0 (.004)</td><td>0 (.003)</td><td>0 (.004)</td><td>2 (.005)</td><td>6 (.007)</td><td>15 (.009)</td><td>0 (.004)</td></tr><tr><td rowspan="2">sko100f</td><td rowspan="2">149060</td><td>SW</td><td>20 (.019)</td><td>18 (.010)</td><td>12 (.006)</td><td>4 (.005)</td><td>0 (.004)</td><td>0 (.003)</td><td>0 (.004)</td><td>0 (.004)</td><td>12 (.007)</td><td>12 (.007)</td><td>0 (.004)</td></tr><tr><td>ID</td><td>21 (.020)</td><td>19 (.010)</td><td>12 (.007)</td><td>8 (.005)</td><td>1 (.004)</td><td>0 (.003)</td><td>0 (.004)</td><td>1 (.004)</td><td>9 (.006)</td><td>12 (.007)</td><td>0 (.003)</td></tr></tbody></table>

cases, there is minimal difference between the two methods in terms of recommended parameter setting and results

On *tai*b instances, AID and ASW are often among the best-ranked methods, especially on the smallest instances. While their ranking is decent, this is not the case for *tai*a instances. They tend to achieve better results on larger instances for this class. On sko instances, AID and ASW consistently rank among the best methods.

Overall, these experiments demonstrate that AID and ASW yield robust results across various QAP landscapes. Although they do not always achieve the best results on *tai* instances, their performance is more consistent than using a single static λ value across all instances. The results on sko instances indicate that AID and ASW perform more efficiently when there is a wider range of effective λ values
<figure><img src="image_7.png" /><figcaption>Figure 6: Anytime performance of SW and ID variants on selected QAP instances.</figcaption></figure>

### 5.3.2 Anytime Performance

Figure 6 shows the average relative deviation from the best known over time for each SW and ID variants on 6 selected QAP landscapes: 2 of type *tai*★*a*, 2 of type *tai*★*b* and 2 of type *sko*. Fixed methods demonstrate similar efficiency at the beginning of the search for ID variants. ID variants generally outperform SW variants early in the search, with exceptions for the *tai*100a and *sko* instances. Throughout the run, there is almost no variation in the relative efficiency of static variants when it comes to *tai* landscapes. On *tai*40a, both automated methods behave quite similarly, while on *tai*40b, ASW quickly ranks among the best SW variants whereas AID starts as the worst before eventually becoming the most efficient one (see previous section). On *tai*100a, the overall behavior of the considered algorithms slightly resembles what is observed on *sko* instances. On *tai*100b, automated methods are less efficient, but as discussed in the previous section, their relative performance improves with a higher budget—possibly indicating that they require more time to converge. There is more variation on *sko* landscapes. Automated methods are among the best ones rather quickly, and the behavior displayed in the two figures is representative of the general tendency on these instances.

Figure 7 reports the evolution of $\lambda$ for AID and ASW. As observed with NK and NKq landscapes, the $\lambda$ value peaks at the beginning of the search, before decreasing and stabilizing. On QAP, the peak occurs earlier for AID, but $\lambda$ stabilizes around similar values for both methods. For AID, the peak appears sooner on *tai*★*b* instances. On these instances, $\lambda$ decreases more slowly than on others, and the peak value is approximately the same for both methods, whereas it is typically lower for ASW. Interestingly, the evolution of $\lambda$ for AID on *tai*100a resembles that on *sko*100a, and the anytime efficiency is also similar for these two instances.

## 5.4 Experimental Results on FSP

This section presents and discusses the results obtained for the other permutation problem class under consideration: FSP.

### 5.4.1 Performance Comparison

The algorithm variants and experimental setup remain the same as in the previous section. Results are reported in Table 6. It is worth noting that for FSP instances with
<figure><img src="image_8.png" /><figcaption>Figure 7: Evolution of $\lambda$ for ASW and AID on selected QAP instances.</figcaption></figure>

<table><caption>Table 6: Statistical rank and relative fitness deviation of SW and ID variants on FSP instances.</caption><thead><tr><th>n</th><th>m</th><th>best</th><th>algo</th><th>25</th><th>50</th><th>75</th><th>100</th><th>150</th><th>200</th><th>300</th><th>400</th><th>600</th><th>800</th><th>auto</th></tr></thead><tbody><tr><td rowspan="2">50</td><td rowspan="2">10</td><td rowspan="2">3023</td><td>SW</td><td>19 (.008)</td><td>1 (.002)</td><td>0 (.002)</td><td>3 (.003)</td><td>3 (.003)</td><td>1 (.003)</td><td>4 (.004)</td><td>2 (.004)</td><td>7 (.005)</td><td>7 (.005)</td><td>0 (.002)</td></tr><tr><td>ID</td><td>19 (.008)</td><td>1 (.002)</td><td>0 (.001)</td><td>0 (.002)</td><td>1 (.003)</td><td>1 (.003)</td><td>2 (.003)</td><td>1 (.003)</td><td>4 (.004)</td><td>3 (.004)</td><td>0 (.001)</td></tr><tr><td rowspan="2">50</td><td rowspan="2">15</td><td rowspan="2">3344</td><td>SW</td><td>20 (.028)</td><td>16 (.019)</td><td>11 (.015)</td><td>9 (.012)</td><td>4 (.008)</td><td>1 (.006)</td><td>0 (.005)</td><td>4 (.008)</td><td>9 (.015)</td><td>16 (.023)</td><td>4 (.008)</td></tr><tr><td>ID</td><td>20 (.029)</td><td>16 (.020)</td><td>11 (.016)</td><td>9 (.012)</td><td>4 (.008)</td><td>0 (.006)</td><td>0 (.004)</td><td>4 (.008)</td><td>9 (.014)</td><td>16 (.020)</td><td>11 (.015)</td></tr><tr><td rowspan="2">50</td><td rowspan="2">20</td><td rowspan="2">3857</td><td>SW</td><td>20 (.025)</td><td>18 (.018)</td><td>15 (.013)</td><td>11 (.011)</td><td>0 (.009)</td><td>0 (.008)</td><td>0 (.008)</td><td>0 (.008)</td><td>0 (.009)</td><td>11 (.012)</td><td>0 (.008)</td></tr><tr><td>ID</td><td>20 (.026)</td><td>18 (.018)</td><td>16 (.014)</td><td>11 (.012)</td><td>1 (.009)</td><td>0 (.008)</td><td>0 (.007)</td><td>0 (.007)</td><td>1 (.009)</td><td>9 (.011)</td><td>12 (.012)</td></tr><tr><td rowspan="2">70</td><td rowspan="2">10</td><td rowspan="2">4029</td><td>SW</td><td>7 (.006)</td><td>0 (.003)</td><td>0 (.004)</td><td>2 (.005)</td><td>3 (.005)</td><td>4 (.005)</td><td>5 (.007)</td><td>6 (.007)</td><td>5 (.006)</td><td>7 (.006)</td><td>8 (.007)</td></tr><tr><td>ID</td><td>8 (.007)</td><td>0 (.003)</td><td>0 (.003)</td><td>1 (.004)</td><td>5 (.006)</td><td>6 (.006)</td><td>6 (.006)</td><td>6 (.006)</td><td>5 (.007)</td><td>5 (.006)</td><td>4 (.005)</td></tr><tr><td rowspan="2">70</td><td rowspan="2">15</td><td rowspan="2">4338</td><td>SW</td><td>20 (.031)</td><td>16 (.022)</td><td>14 (.015)</td><td>8 (.012)</td><td>1 (.008)</td><td>0 (.005)</td><td>0 (.006)</td><td>0 (.008)</td><td>4 (.010)</td><td>11 (.018)</td><td>0 (.009)</td></tr><tr><td>ID</td><td>20 (.031)</td><td>16 (.022)</td><td>14 (.017)</td><td>9 (.012)</td><td>0 (.008)</td><td>0 (.006)</td><td>0 (.006)</td><td>0 (.007)</td><td>4 (.010)</td><td>6 (.012)</td><td>14 (.019)</td></tr><tr><td rowspan="2">70</td><td rowspan="2">20</td><td rowspan="2">4714</td><td>SW</td><td>20 (.031)</td><td>18 (.023)</td><td>16 (.018)</td><td>13 (.015)</td><td>9 (.011)</td><td>4 (.008)</td><td>0 (.006)</td><td>0 (.007)</td><td>2 (.008)</td><td>6 (.012)</td><td>0 (.007)</td></tr><tr><td>ID</td><td>21 (.032)</td><td>18 (.023)</td><td>17 (.019)</td><td>14 (.016)</td><td>9 (.011)</td><td>5 (.009)</td><td>0 (.005)</td><td>0 (.006)</td><td>2 (.008)</td><td>5 (.010)</td><td>12 (.014)</td></tr><tr><td rowspan="2">100</td><td rowspan="2">10</td><td rowspan="2">5770</td><td>SW</td><td>3 (.001)</td><td>0 (.001)</td><td>0 (.001)</td><td>2 (.001)</td><td>3 (.002)</td><td>4 (.002)</td><td>10 (.003)</td><td>10 (.003)</td><td>5 (.002)</td><td>10 (.003)</td><td>12 (.004)</td></tr><tr><td>ID</td><td>3 (.001)</td><td>0 (.001)</td><td>0 (.001)</td><td>1 (.001)</td><td>3 (.001)</td><td>3 (.002)</td><td>4 (.002)</td><td>3 (.002)</td><td>10 (.003)</td><td>9 (.002)</td><td>0 (.001)</td></tr><tr><td rowspan="2">100</td><td rowspan="2">15</td><td rowspan="2">5882</td><td>SW</td><td>20 (.025)</td><td>12 (.016)</td><td>2 (.010)</td><td>0 (.008)</td><td>0 (.010)</td><td>0 (.009)</td><td>5 (.013)</td><td>8 (.013)</td><td>9 (.014)</td><td>11 (.015)</td><td>11 (.015)</td></tr><tr><td>ID</td><td>20 (.026)</td><td>13 (.016)</td><td>2 (.010)</td><td>0 (.008)</td><td>0 (.009)</td><td>0 (.010)</td><td>2 (.012)</td><td>2 (.012)</td><td>9 (.014)</td><td>11 (.015)</td><td>0 (.009)</td></tr><tr><td rowspan="2">100</td><td rowspan="2">20</td><td rowspan="2">6243</td><td>SW</td><td>20 (.029)</td><td>18 (.021)</td><td>16 (.015)</td><td>14 (.012)</td><td>9 (.008)</td><td>0 (.005)</td><td>0 (.004)</td><td>0 (.005)</td><td>4 (.008)</td><td>4 (.007)</td><td>0 (.006)</td></tr><tr><td>ID</td><td>21 (.030)</td><td>18 (.021)</td><td>16 (.016)</td><td>14 (.013)</td><td>9 (.008)</td><td>0 (.006)</td><td>0 (.004)</td><td>0 (.004)</td><td>0 (.006)</td><td>9 (.009)</td><td>0 (.006)</td></tr></tbody></table>

known global optima, the best solution found either reaches it or comes very close to it (with the optimum being achieved for $n = 100$ and $m = 10$). This result is significant for two reasons: (1) among the instances from Taillard (1993), renowned for their complexity, (2) the considered approaches are in no way specifically designed for the FSP—they are highly generic with minimal parameters, which further highlights their relevance.

Results from variants with a fixed $\lambda$ indicate that the ideal $\lambda$ value increases as the neutrality level decreases (i.e., when there are more machines). For a given number of machines $m$, the ideal $\lambda$ value remains stable across the different number of jobs $n$ considered in this study. At higher neutrality levels, $ID_{best}$ is among the best methods for a wider range of $\lambda$ values.

On all instances, at least one adaptive method ranks in the top 4. The lowest rank achieved is 14 for AID and 12 for ASW, yet in both cases, the other adaptive variant ranks best. These results demonstrate that adaptive walks achieve robust results on these FSP instances. However, using a fixed value of $\lambda = 200$ leads to more robust results across all 9 instances. Moreover, the difference in efficiency between AID and ASW on some instances is larger than what was observed on the previous problems. These differences warrant further investigation, which we leave open for future research.
<figure><img src="image_9.png" /><figcaption>Figure 8: Anytime performance of SW and ID variants on selected FSP instances.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 9: Evolution of $\lambda$ for ASW and AID on selected FSP instances.</figcaption></figure>

### 5.4.2 Anytime Performance

We now report the anytime performance of SW and ID variants on 4 selected FSP landscapes in Figure 8. The relative efficiency between methods varies more than in previous problems, especially on landscapes with lower neutrality levels (with more machines). AID quickly becomes one of the best ID variants, except on the instance with $n = 50$ and $m = 20$. ASW's relative efficiency evolves differently: it initially shows middle-range performance compared to other SW variants, then shows a decline, before ultimately ranking among the best methods—except for the instance with $n = 100$ and $m = 10$.

Finally, Figure 9 shows the evolution of $\lambda$ for ASW and AID on FSP. At the beginning of the search, $\lambda$ is significantly higher for AID. Across all instances, $\lambda$ peaks earlier for AID and has nearly stabilized by the time $\lambda$ peaks for ASW. The stabilized $\lambda$ value is similar for both methods when having $n = 50$ jobs, but differs when having $n = 100$ jobs. The instance with $n = 100$ jobs and $m = 10$ machines show a distinctive evolution of $\lambda$ compared to other instances. The difference between peak and stabilized $\lambda$ values is less pronounced, and the stabilized values are closer for both methods.

## 6 Concluding Remarks and Discussion

In this paper, we presented an adaptive, automated setting for partial neighborhood local search algorithms, with a special focus on sampled walk and ID walk. These parameter-free algorithms operate with minimal requirements: only a stopping criterion and knowledge of the landscape $(\mathcal{X}, \mathcal{N}, f)$. Despite potential restrictions in
defining these characteristics, our approach offers sufficient flexibility to apply such autonomous local search to diverse optimization problem classes.

Our empirical evaluation across four benchmark problems (and 70 problem instances in total) demonstrates that the proposed ASW and AID achieve competitive performance despite their parameter-free nature. Notably, these algorithms performed well across varied solution representations, neighborhood structures, and fitness landscape characteristics—suggesting the viability of generic, autonomous local search methods. Our study drives us to think that fully automated heuristics can be designed without complete reliance on automated algorithm selection and configuration. However, several significant challenges remain to be addressed in this research direction.

A primary limitation concerns distance measurement computation. While ASW and AID prove highly effective on randomly generated isotropic landscapes, black-box optimization of real-world problems often presents non-isotropic neighborhood and landscape characteristics. Despite this challenge, calculating or estimating distance/diameter remains frequently possible. For instance, the 2-opt neighborhood operator—commonly used in routing problems—lacks an efficient exact distance computation algorithm, a challenge proven to be NP-hard (Caprara, 1997), though potentially tractable (Bérard et al., 2005). Moreover, complex neighborhood operators (such as k-opt for the traveling salesperson problem) and non-isotropic neighborhood structures create additional difficulties when adapting ASW and AID principles.

To address these limitations, future work should explore using observed landscape characteristics during search to dynamically adjust the $\lambda$ value. Our experiments demonstrate that incorporating landscape information can guide appropriate $\lambda$ configuration. Another research direction is to formalize the proposed approach for any landscape $(X, \mathcal{N}, f)$. This paper presented a possible mapping between distance and $\lambda$ values for some neighborhood structures. However, we believe a general concept could apply universally to any landscape, for example by defining $\lambda$ according to the number of neighbors moving closer to solutions found at previous iterations.

Several additional promising extensions of this work also warrant investigation. First, while our adaptive strategy demonstrates that a simple heuristic relationship between distance and neighborhood size can yield competitive performance, we acknowledge that alternative mappings could be explored to determine whether they offer further improvements. This includes reward-based parameter control approaches, which may provide additional insights. Second, the exploratory strength of partial neighborhood local search could be complemented by advanced hill-climbing techniques to intensify search around promising solutions—thus ensuring that the best encountered solutions are actually local optima. Finally, extending adaptive partial neighborhood local search to multi-objective optimization represents a compelling research direction, especially given recent evidence of its effectiveness in these domains (Basseur et al., 2024).

**Acknowledgments.** We are grateful to the reviewers for their insightful comments and constructive feedback, which greatly improved the quality of this paper. This work has benefited from the support of the National Research Agency under France 2030, MAIA Project ANR-22-EXES-0009.

**References**

Bartz-Beielstein, T., Doerr, C., Berg, D. v. d., Bossek, J., Chandrasekaran, S., Eftimov, T., Fischbach, A., Kerschke, P., La Cava, W., Lopez-Ibanez, M., et al. (2020). Benchmarking in optimization: Best practice and open issues. arXiv preprint arXiv:2007.03488.
Basseur, M., Liefooghe, A., and Tari, S. (2024). MOW-P: A simple yet efficient partial neighborhood walk for multiobjective optimization. In *IEEE Congress on Evolutionary Computation* (CEC 2024), pages 1–8, Yokohama, Japan. IEEE.

Bérard, S., Bergeron, A., Chauve, C., and Paul, C. (2005). Perfect sorting by reversals is not always difficult. In Casadio, R. and Myers, G., editors, *Algorithms in Bioinformatics*, pages 228–238. Springer.

Burkard, R. E., Karisch, S. E., and Rendl, F. (1997). QAPLIB—a quadratic assignment problem library. *Journal of Global Optimization*, 10(4):391–403.

Caprara, A. (1997). Sorting by reversals is difficult. In *Annual International Conference on Research in Computational Molecular Biology* (RECOMB 1997), pages 75–83.

Cicirello, V. and Cernera, R. (2013). Profiling the distance characteristics of mutation operators for permutation-based genetic algorithms. In *Proceedings of the 26th International Florida Artificial Intelligence Research Society Conference (FLAIRS 2013)*, pages 46–51.

Corus, D., Dang, D., Eremeev, A. V., and Lehre, P. K. (2018). Level-based analysis of genetic algorithms and other search processes. *IEEE Transactions on Evolutionary Computation*, 22(5):707–719.

Dang, D., Eremeev, A. V., and Lehre, P. K. (2021). Escaping local optima with non-elitist evolutionary algorithms. In *Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021*, pages 12275–12283. AAAI Press.

Doerr, B. (2022). Does comma selection help to cope with local optima? *Algorithmica*, 84(6):1659–1693.

Doerr, B. and Doerr, C. (2020). *Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices*, pages 271–321. Springer International Publishing, Cham.

Eiben, A., Hinterding, R., and Michalewicz, Z. (1999). Parameter control in evolutionary algorithms. *IEEE Transactions on Evolutionary Computation*, 3(2):124–141.

Garey, M. R., Johnson, D. S., and Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. *Mathematics of operations research*, 1(2):117–129.

Hernando, L., Mendiburu, A., and Lozano, J. (2016). A tunable generator of instances of permutation-based combinatorial optimization problems. *IEEE Transactions on Evolutionary Computation*, 20(2):165–179.

Huang, C., Li, Y., and Yao, X. (2020). A survey of automatic parameter tuning methods for metaheuristics. *IEEE Transactions on Evolutionary Computation*, 24(2):201–216.

Hutter, F., Hoos, H. H., and Leyton-Brown, K. (2011). Sequential model-based optimization for general algorithm configuration. In Coello Coello, C. A., editor, *Learning and Intelligent Optimization, 5th International Conference, LION 5*, volume 6683 of Lecture Notes in Computer Science, pages 507–523. Springer, Heidelberg, Germany.

Hutter, F., Hoos, H. H., Leyton-Brown, K., and Stützle, T. (2009). ParamILS: An automatic algorithm configuration framework. *Journal of Artificial Intelligence Research*, 36:267–306.

Jukes, T. H. and Cantor, C. R. (1969). Evolution of protein molecules. *Mammalian Protein Metabolism*, 3:21–132.

Kauffman, S. A. and Weinberger, E. D. (1989). The NK model of rugged fitness landscapes and its application to maturation of the immune response. *Journal of Theoretical Biology*, 141(2):211–245.

López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Stützle, T., and Birattari, M. (2016). The irace package: Iterated racing for automatic algorithm configuration. *Operations Research Perspectives*, 3:43–58.
Malan, K. M. (2021). A survey of advances in landscape analysis for optimisation. *Algorithms*, 14(2):40.

Merz, P. (2004). Advanced fitness landscape analysis and the performance of memetic algorithms. *Evolutionary Computation*, 12(3):303-325.

Neveu, B., Trombettoni, G., and Glover, F. (2004). ID walk: A candidate list strategy with a simple diversification device. In *Principles and Practice of Constraint Programming (CP 2004)*, pages 423-437. Springer.

Newman, M. E. and Engelhardt, R. (1998). Effects of selective neutrality on the evolution of molecular species. *Proceedings of the Royal Society of London. Series B: Biological Sciences*, 265(1403):1333-1338.

Pitzer, E. and Affenzeller, M. (2012). A comprehensive survey on fitness landscape analysis. *Recent advances in intelligent engineering systems*, pages 161-191.

Rudolph, G. (1994). Convergence of non-elitist strategies. In Michalewicz, Z., editor, *Proceedings of the First IEEE International Conference on Evolutionary Computation (ICEC'94)*, pages 63-66. IEEE Press, Piscataway, NJ.

Sahni, S. and Gonzalez, T. (1976). P-complete approximation problems. *Journal of the ACM*, 23(3):555-565.

Schiavinotto, T. and Stützle, T. (2007). A review of metrics on permutations for search landscape analysis. *Computers & Operations Research*, 34(10):3143-3153.

Taillard, É. D. (1993). Benchmarks for basic scheduling problems. *European Journal of Operational Research*, 64(2):278-285.

Tari, S., Basseur, M., and Goëffon, A. (2018). Sampled walk and binary fitness landscapes exploration. In *Proceedings of Artificial Evolution (EA 2018)*, pages 47-57, Cham. Springer International Publishing.

Tari, S., Basseur, M., and Goëffon, A. (2021). On the use of (1, λ)-evolution strategy as efficient local search mechanism for discrete optimization: a behavioral analysis. *Natural Computing*, 20:345-361.

Tari, S., Basseur, M., and Goëffon, A. (2022). Partial neighborhood local searches. *International Transactions in Operational Research*, 29(5):2761-2788.

Wright, S. (1932). The roles of mutation, inbreeding, crossbreeding and selection in evolution. *Proceedings of the XI International Congress of Genetics*, 8:209-222.