Anatomy of the Attraction Basins:
Breaking with the Intuition
Leticia Hernando
Intelligent Systems Group, Department of Computer Science and Artificial
Inteligencia, University of the Basque Country UPV/EHU, 20018 San Sebastián, España
leticia.hernando@ehu.eus
Alexander Mendiburu
Intelligent Systems Group, Department of Computer Architecture and Technology,
University of the Basque Country UPV/EHU, 20018 San Sebastián, España
alexander.mendiburu@ehu.eus
Jose A. Lozano
Intelligent Systems Group, Department of Computer Science and Artificial
Inteligencia, University of the Basque Country UPV/EHU, 20018 San Sebastián,
Spain Basque Center for Applied Mathematics (BCAM), 48009 Bilbao, España
ja.lozano@ehu.eus
https://doi.org/10.1162/evco_a_00227
Abstracto
Solving combinatorial optimization problems efficiently requires the development of
algorithms that consider the specific properties of the problems. En este sentido, local
search algorithms are designed over a neighborhood structure that partially accounts
for these properties. Considering a neighborhood, the space is usually interpreted as a
natural landscape, with valleys and mountains. Under this perception, it is commonly
believed that, if maximizing, the solutions located in the slopes of the same mountain
belong to the same attraction basin, with the peaks of the mountains being the local
optima. Desafortunadamente, this is a widespread erroneous visualization of a combinatorial
landscape. De este modo, our aim is to clarify this aspect, providing a detailed analysis of, primero,
the existence of plateaus where the local optima are involved, y segundo, the proper-
ties that define the topology of the attraction basins, picturing a reliable visualization of
the landscapes. Some of the features explored in this article have never been examined
antes. Por eso, new findings about the structure of the attraction basins are shown. El
study is focused on instances of permutation-based combinatorial optimization prob-
lems considering the 2-exchange and the insert neighborhoods. As a consequence of
this work, we break away from the extended belief about the anatomy of attraction
basins.
Palabras clave
Permutation-based combinatorial optimization problems,
basins, local search, landscape visualization.
local optima, attraction
1
Introducción
Local search algorithms have been one of the most developed metaheuristics used to
solve combinatorial optimization problems (COPs). These algorithms are defined to
work under a neighborhood structure built, on most occasions, by an operator. Allá-
delantero, their behavior will be conditioned by the properties that this neighborhood im-
poses on the search space, namely the landscape properties. De este modo, many authors have
already noticed the importance of studying these landscape features in order to predict,
Manuscrito recibido: 18 Noviembre 2016; revisado: 15 Enero 2018; aceptado: 13 Febrero 2018.
© 2018 Instituto de Tecnología de Massachusetts
Computación evolutiva 27(3): 435–466
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
in advance, the performance of local search algorithms, or to use them in the develop-
ment of new proposals (Albrecht et al., 2008, 2010; Alyahya and Rowe, 2014; Caruana
and Mullin, 1999; Chicano et al., 2012; Fonlupt et al., 1999; Hernando et al., 2011; Mat-
tfeld and Bierwirth, 1999; Merz, 2004; Merz and Freisleben, 2001; Ochoa et al., 2011,
2014; Prügel-Bennett and Tayarani-Najaran, 2012; Reeves, 1999; Reeves and Aupetit-
Bélaidouni, 2004; Tayarani-Najaran and Prügel-Bennett, 2014, 2015a, 2015b; Tomassini
et al., 2008; Verel, Ochoa et al., 2011; watson, 2010; Moser et al., 2016). Some of these
works assume that the topology defined by the neighborhoods in the combinatorial
spaces is analogous to that found in the continuous domain. In the continuous space,
there always exists a ball of radius r > 0 and centered at each of the local optima which
is included in its attraction basin. This intuition has been transferred to the combinato-
rial space. Por lo tanto, it is commonly believed that local search algorithms draw paths
in a mountainous landscape, y, depending on the neighborhood, we could find a dif-
ferent number of mountains with different heights and sizes (Hernando et al., 2013b,
2016b; Mattfeld and Bierwirth, 1999; Tayarani-Najaran and Prügel-Bennett, 2014).
Although this thought is widespread across the literature and it has usually been ac-
cepted by the research community, other authors have started to notice a contradiction
with experimental results. Por ejemplo, in Tomassini et al. (2008), a representation of
the landscape as local optima networks was proposed, eso es, a graph where the nodes
were the local optima and the edges accounted for the probabilities of connecting the
different attraction basins. They showed that the number of edges was extremely large,
eso es, each of the attraction basins connects with almost all of the remaining attraction
basins (Daolio et al., 2010, 2014). This result led them to think of a different landscape pic-
ture than the smooth standard representation of 2D landscapes, where the basins of attraction
are visualized as real mountains. De hecho, the first study that warned about this visualiza-
tion of the combinatorial landscape was published in 1999 (Fonlupt et al., 1999). En eso
trabajar, the authors already stated that basins of attraction seem to be highly intertwined, giv-
ing a canyon-like structure to the landscape, rather than a crater-like structure. Sin embargo,
this finding was ignored by those works referring to it (Stützle, 2006; Preux and Talbi,
1999; Angel and Zissimopoulos, 2002; Bouziri et al., 2009). Por ejemplo, seven years
after that publication, the author in Stützle (2006) contradicted it: Intuitivamente, the search
landscape can be imagined as a (multi-dimensional) mountainous region with hills, craters, y
valleys. The problem is that even in more recent works, these kinds of declarations are
still found, as in Tayarani-Najaran and Prügel-Bennett (2015b) cual, for minimization
problemas, dice: each local optimum has a bowl shape basin of attraction.
As can be observed, different intuitions of the combinatorial landscapes coexist in
the literature. The reason for this is the difficulty in understanding the topology of the
combinatorial spaces. In all these papers, the authors try to provide an interpretation
about the combinatorial landscape, giving insights according to the observed results
collected from landscape features analyses, but without a solid study of the topology of
the space under a specific neighborhood. Precisely, this is the objective of this article: a
examine topological features of the attraction basins of the local optima, in order to pro-
vide a reliable comprehension. Each local optimum has an attraction basin associated;
sin embargo, it is already known that many different neighboring local optima with the
same fitness could appear in a given instance. En este caso, the local optima belong to a
plateau and we could consider that they share the attraction basin. De este modo, the study of the
plateaus containing local optima is the starting point for the analysis of the topology of
the attraction basins (Hoos and Stützle, 2004; watson, 2010). In the literature, the graphs
composed by neighboring solutions with the same fitness value, have been sometimes
known as neutral networks; and when these solutions are local optima, they are called
436
Volumen de cálculo evolutivo 27, Número 3
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Anatomy of the Attraction Basins
the local optimum neutral networks. This concept of neutral network emerged in the
literature less than 10 years ago, and it has been analyzed for some problems: the NK
landscapes (Verel, Ochoa et al., 2011), the permutation flowshop problem (Marmion
et al., 2011b; Daolio et al., 2014), or the traveling salesman problem (Ochoa and Veer-
apen, 2018). Desafortunadamente, the plateaus containing local optima are not detected by the
common local search algorithms, even though their behavior is highly conditioned by
the presence of these plateaus, as they are trapped inside them. So, in the last decade,
some authors identified this situation, and modified common local search algorithms,
such as the hill-climbing algorithm, in order to escape from the plateaus (Sutton et al.,
2010; Marmion et al., 2011a; Tayarani-Najaran and Prügel-Bennett, 2014, 2015b, 2015a;
Prügel-Bennett and Tayarani-Najaran, 2012; Humeau et al., 2013).
The final purpose of this article is, by studying topological features of the attraction
basins, to shed light on the different misunderstandings and contradictions that have
arisen in the last two decades in our research community. We focus on COPs based on
permutations, eso es, those where the search space is the set of permutations of size n.
Particularly, we work with the permutation flowshop scheduling problem (PFSP), el
linear ordering problem (LOP), and the quadratic assignment problem (QAP). Primero, nosotros
examine the locally optimal solutions returned by a classical hill-climbing algorithm
with the aim of providing knowledge related to the plateaus. En segundo lugar, we study those
features of the attraction basins that we consider essential in order to understand their
topología: the roundness of the attraction basins, the centrality of the local optima, y
the interior and frontier of the attraction basins. Although the frontier of the attraction
basins has already been explored in previous works (Fonlupt et al., 1999; Tomassini
et al., 2008; Verel et al., 2008; Ochoa et al., 2014), in this article we take a step forward,
studying the evolution of the neighboring solutions in the same attraction basin with
the increase of the distance to the local optimum. A lo mejor de nuestro conocimiento, este
propiedad, together with the roundness of the attraction basins and the centrality of the
local optima, has never been analyzed before. We include a deep discussion about the
obtained results, emphasizing the importance of the work presented in this article by
giving clues of how to use these discoveries in, Por ejemplo, the design of efficient local
search algorithms, and pointing out the potential uses these new findings could have
in the combinatorial optimization field. We also present two examples for the graphical
representation of the attraction basins.
The rest of the article is organized as follows. The concepts of local optimum,
plateau, and attraction basin are formally introduced in Section 2. The topological fea-
tures considered in the analysis are explained in Section 3. En la sección 4, we carry out
the experiments in order to, primero, classify the solutions returned by the hill-climbing
algorithm in terms of plateaus; and secondly, examine the properties of the attraction
basins necessary to understand their topology. Some examples of the visualization of
the anatomy of the attraction basins are shown in Section 5. Finalmente, en la sección 6, el
conclusions and future work are presented.
2 Definitions
2.1 Neighborhood
A combinatorial optimization problem (COP) consists of finding the optimal solutions
de (from now on, maximizing) a function
F : (cid:2) −→ R
pag (cid:3)−→ f (pag ),
Volumen de cálculo evolutivo 27, Número 3
437
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
where the search space, (cid:2), is a finite or countable infinite set. Específicamente, we work with
instances of permutation-based COPs. So, from now on, (cid:2) is the set of permutations of
size n, de este modo, the search space is of size n!.
We focus on local search algorithms, which are one of the most developed meta-
heuristics used to solve COPs. These algorithms are defined to work under a neighbor-
hood structure. A neighborhood N in a search space (cid:2) is a mapping that assigns, to each
solution σ ∈ (cid:2), a non-empty set of neighboring solutions N (pag ):
norte : (cid:2) −→ P ((cid:2))\∅
pag (cid:3)−→ N (pag ),
where P ((cid:2)) is the powerset of (cid:2).
Adding the concept of neighborhood to the instance of a COP, we define a land-
scape as the triple (F, (cid:2), norte ), where f is the objective function to optimize (Reidys and
Stadler, 2002). Two examples of the most commonly used neighborhoods in the space of
permutations are given by the 2-exchange and the insert operators (Taillard, 1990; Angel
and Zissimopoulos, 2002; Schiavinotto and Stützle, 2005; Chicano et al., 2012). Given a
permutation σ = (pag (1) · · · σ (norte)), one swap movement between the i-th and j -th items,
Sj
i (pag ), is defined as follows:
i (pag ) = Sj
Sj
i (pag (1) · · · σ (i − 1)pag (i)pag (i + 1) · · · σ (j − 1)pag (j )pag (j + 1) · · · σ (norte))
= (pag (1) · · · σ (i − 1)pag (j )pag (i + 1) · · · σ (j − 1)pag (i)pag (j + 1) · · · σ (norte)).
De este modo, the 2-exchange neighborhood, NS, considers that two solutions are neighbors if one
is generated by swapping two elements of the other:
NS (pag ) =
n−1(cid:2)
norte(cid:2)
yo=1
j =i+1
Sj
i (pag ).
Given a permutation σ = (pag (1) · · · σ (norte)), the insertion of the i-th item into the j -th po-
posición, for i > j , is defined as follows:
i>j (pag ) = I j
I j
i>j (pag (1) · · · σ (j − 1)pag (j )pag (j + 1) · · · σ (i − 1)pag (i)pag (i + 1) · · · σ (norte))
= (pag (1) · · · σ (j − 1)pag (i)pag (j )pag (j + 1) · · · σ (i − 1)pag (i + 1) · · · σ (norte)),
while for i < j :
i
⎭
∪
i=2
j i+1
⎫
⎬
⎭ .
I j
i
Allowing for the equality in the above equation, we have the definition of relaxed
local optimum. In the literature, this is commonly known as local optimum. Eso es, a
solution σ ∗ ∈ (cid:2) is a relaxed local optimum, or simply, local optimum if
F (σ ∗
).
F (σ ∗
We define a connecting path L(σ1, σr ) between a solution σ1
) ≥ f (pag ), ∀σ ∈ N (σ ∗
).
σr ∈ (cid:2) as a sequence L(σ1, σr ) = (σ1, p2, . . . , σr ) dónde
∈ (cid:2) and another solution
p2
∈ N (σ1), σ3
∈ N (p2), . . . , σr ∈ N (σr−1).
A plateau is a set of solutions P = {σ1, p2, . . . , σr } that fulfills (Hoos and Stützle, 2004;
watson, 2010; Sutton et al., 2010):
(i) ∀σi, σj ∈ P, F (σi ) = f (σj ).
(ii) ∀σi, σj ∈ P, ∃L(σi, σj ) ⊆ P.
(iii) P is maximal, es decir., (cid:15) ∃Q complying (i) y (ii) such that P ⊂ Q.
A plateau P is a local optimal plateau or closed plateau (Hoos and Stützle, 2004; watson,
el
2010; Sutton et al., 2010) if all the solutions in P are local optima. We denote by P ∗
local optimal plateaus. De este modo, being P ∗
(cid:2)
a local optimal plateau:
{σ ∗} = P ∗.
σ ∗ ∈P∗
σ ∗ is loc opt.
The plateaus P that contain local optima as well as solutions that are not local optima
are usually known in the literature as benches (watson, 2010) or as open plateaus (Hoos
and Stützle, 2004; Sutton et al., 2010). Por lo tanto, if P is an open plateau:
(cid:2)
σ ∗∈P
σ ∗is loc opt.
{σ ∗} ⊂ P.
Given a plateau P we will denote by O∗
in the plateau:
P the set composed by all the local optima found
O∗
P =
(cid:2)
{σ ∗}.
σ ∗∈P
σ ∗is loc opt.
Finalmente, there are also kinds of plateaus that do not contain any local optimum, called
unoptimal plateaus.
En figura 1, we represent four different structures found in a figurative combinato-
rial space where the neighboring solutions are joined by an edge. These examples show
a strict local optimum 1(a), a local optimal plateau 1(b), an open plateau 1(C), and an
unoptimal plateau 1(d). The strict and relaxed local optima are in red. So, notice that all
the solutions that form the local optimal plateau (1b) are relaxed local optima. Sin embargo,
in an open plateau (1C), we do find solutions that are not local optima (in black), y
also relaxed local optima. In both cases, 1(b) y 1(C), the red points form the set O∗
PAG . En
the unoptimal plateaus 1(d), no local optima are found.
It is very important to note that all local optimum σ ∗
will necessarily belong to one,
and only one, of the three following cases:
Volumen de cálculo evolutivo 27, Número 3
439
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
Cifra 1: Representation of a strict local optimum (a), a local optimal plateau (b), un
open plateau (C), and an unoptimal plateau (d) in a figurative combinatorial landscape
when considering a maximization problem. The nodes represent the solutions of the
search space and they are connected according to a neighborhood. The height indicates
the objective function values. The solutions in red are the local optima, the nonoptimal
solutions that belong to a plateau are in black, while the rest of the solutions are in gray.
1. Be a strict local optimum.
2. Belong to a local optimal plateau.
3. Belong to an open plateau.
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
2.3 Attraction Basin of a Local Optimum
, B(σ ∗
The attraction basin of a local optimum σ ∗
), is composed of all the solutions which
lead to the local optimum σ ∗, after applying a greedy local search algorithm to them. Nosotros
denote by H the operator that associates, to each solution σ , the local optimum obtained
after applying the algorithm. Different definitions could be given for the attraction basin
depending on the nature of the operator H (ver, Por ejemplo, Verel, Daolio et al., 2011
and Watson, 2010 for stochastic operators). We work with a deterministic H; entonces, el
attraction basin of a local optimum, B(σ ∗
), is the set that can be defined in the following
way:
(cid:9)
(cid:10)
B(σ ∗
) =
σ ∈ (cid:2) | h(pag ) = σ ∗
.
440
Volumen de cálculo evolutivo 27, Número 3
Anatomy of the Attraction Basins
It is also important to define the attraction basin of a plateau. We define this set as
the union of the attraction basins of all the local optima that belong to such a plateau
(Klemm et al., 2014):
(cid:2)
B(PAG ) =
B(σ ∗
).
σ ∗∈O∗
PAG
Por supuesto, we cannot refer to an attraction basin of an unoptimal plateau, as it does not
contain any local optimum.
This definition of attraction basin of a plateau is consistent with the definitions
found in the literature (Verel, Ochoa et al., 2011; Daolio et al., 2014). In these works,
the plateaus formed by local optima were defined as local optima neutral networks
(LONN). The attraction basin of a LONN was defined as the set of all the solutions
of the search space that belong to the attraction basin of any of the local optima that
compose the LONN.
When two neighboring solutions belong to different attraction basins, it is said that
2 ) as neighboring
the attraction basins are neighbors; eso es, we define B(σ ∗
attraction basins if
1 ) y B(σ ∗
∃σ ∈ B(σ ∗
1 ) and ∃σ (cid:8) ∈ B(σ ∗
2 ) such that σ (cid:8) ∈ N (pag ).
In the same way, the attraction basins of two different plateaus, PAG
si
1 y P
2, are neighbors
∃σ ∈ B(PAG
1) and ∃σ (cid:8) ∈ B(PAG
2) such that σ (cid:8) ∈ N (pag ).
3 Topology of the Attraction Basins
The attraction basin of a local optimum depends on the algorithm used. Además,
when using a deterministic algorithm, an important property is derived from the con-
cept of attraction basins of the local optima: they define a partition of (cid:2).
The distance d defined by both the swap and the insert neighborhoods is a metric,
eso es, ∀σ1, p2, σ3
∈ (cid:2):
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
= σ2,
(i) d(σ1, p2) = 0 ⇐⇒ σ1
(ii) d(σ1, p2) = d(p2, σ1),
(iii) d(σ1, σ3) ≤ d(σ1, p2) + d(p2, σ3).
Ahora, we can study topological features of the attraction basins. Particularly, we focus on
three properties: the roundness of the attraction basins, the centrality of the local optima
within the attraction basins, and the interior and frontier of the attraction basins.
3.1 Roundness of the Attraction Basins
We define the roundness of the attraction basins using the concept of closed ball. A closed
ball Br (Pi ) of radius r > 0 and centered at a permutation π ∈ (cid:2) es:
Br (Pi ) = {σ ∈ (cid:2)|d(pag, Pi ) ≤ r}.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Considering the closed ball Br ∗ (σ ∗
d(σi, σ ∗
radius r ∗ = max
σi ∈B(σ ∗ )
) centered at the local optimum σ ∗
and with a
), we say that an attraction basin B(σ ∗
) is round if
B(σ ∗
) = Br ∗ (σ ∗
).
Volumen de cálculo evolutivo 27, Número 3
441
l. Hernando, A. Mendiburu, y j. A. Lozano
Asimismo, we define a closed ball Br (PAG ) of radius r > 0 and centered at a plateau P
como:
where dmin(pag, PAG ) = min
σ ∗∈O∗
PAG
Br (PAG ) = {σ ∈ (cid:2)|dmin(pag, PAG ) ≤ r},
d(pag, σ ∗
).
En este caso, we consider that the attraction basin of a plateau B(PAG ) is round if
B(PAG ) = Br ∗ (PAG ),
where r ∗ = max
σi ∈B(PAG )
dmin(σi, PAG ).
3.2 Centrality of the Local Optima
Let us suppose σ ∗
), and let us consider the measure
Dσ ∗ (pag ) as the sum of the distances between σ and the rest of the permutations in B(σ ∗
):
(cid:11)
to be a local optimum and σ ∈ B(σ ∗
Dσ ∗ (pag ) =
d(σi, pag ).
σi ∈B(σ ∗ )
Si
σ ∗ = arg min
σi ∈B(σ ∗ )
Dσ ∗ (σi ),
then we say that the local optimum is centered within the attraction basin.
In the case of having a set of local optima belonging to a plateau P, we calculate the
measure D as follows.
If σ ∈ B(PAG ) and σ /∈ O∗
PAG
DP (pag ) = min
σi ∈O∗
PAG
d(σi, pag ) +
(cid:11)
∈B(PAG )
σi
∗
σi /∈O
PAG
d(σi, pag ),
y
DP (O∗
PAG ) =
(cid:11)
∈B(PAG )
σi
∗
σi /∈O
PAG
mín.
σj ∈O∗
PAG
d(σj , σi ).
As in the previous case, we say that the plateau is centered within the attraction
basin if
∀σ ∈ B(PAG ), σ /∈ O∗
PAG ,
DP (O∗
PAG ) < DP (σ ).
3.3
Interior and Frontier of the Attraction Basins
We differentiate the interior and the frontier of an attraction basin set. The interior of the
attraction basin of a local optimum σ ∗
)), is the subset composed of all the solutions
in B(σ ∗
) which also have all their neighbors in B(σ ∗
, I (B(σ ∗
):
I (B(σ ∗
)) = {σ | σ ∈ B(σ ∗
) ∧ N (σ ) ⊂ B(σ ∗
)}.
, F (B(σ ∗
So, the frontier of the attraction basin of a local optimum σ ∗
)), is composed of all
the solutions in the attraction basin B(σ ∗) that are not located in its interior, F (B(σ ∗)) =
B(σ ∗
) \ I (B(σ ∗
)):
F (B(σ ∗
)}.
Similarly, we define the interior of the attraction basin of a plateau P,
I (B(P )) = {σ | σ ∈ B(P ) ∧ N (σ ) ⊂ B(P )},
)) = {σ | σ ∈ B(σ ∗
) ∧ N (σ ) (cid:15)⊂ B(σ ∗
and the frontier of the attraction basin of a plateau P,
F (B(P )) = {σ | σ ∈ B(P ) ∧ N (σ ) (cid:15)⊂ B(P )}.
442
Evolutionary Computation Volume 27, Number 3
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
/
/
e
d
u
e
v
c
o
a
r
t
i
c
e
-
p
d
l
f
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
e
v
c
o
_
a
_
0
0
2
2
7
p
d
/
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
Anatomy of the Attraction Basins
4
Experiments
The topological features of the attraction basins described in Section 3 are analyzed in
order to connect the observed results with a comprehension of the structure of the at-
traction basins. This will help us to contradict the commonly found extrapolation from
the continuous domain to the combinatorial space, which is responsible for a visualiza-
tion of the landscape full of mountains and valleys: the assumption that a ball of radius
r > 0 and centered at the local optima is included in their attraction basins. For this pur-
pose, we focus on permutation-based problems, and divide our analysis in two parts:
the study of the type of solution returned by a classical deterministic hill-climbing algo-
rithm in terms of plateaus, and the exploration of the topology of the attraction basins
regarding the roundness, the centrality of the local optima and the interior and frontier
of the attraction basins. Primero, the experimental design is detailed, and then the results
are shown, followed by a thorough discussion relating them to the topology defined.
4.1
Experimental Design
We work with instances of the permutation flowshop scheduling problem (PFSP), el
linear ordering problem (LOP), and the quadratic assignment problem (QAP), cual
are known to be NP-hard problems (Garey et al., 1976; Mishra and Sikdar, 2004; Sahni
and Gonzalez, 1976). The flowshop scheduling problem can be stated as follows: allá
are b jobs to be scheduled in c machines. A job consists of c operations and the j -th oper-
ation of each job must be processed on machine j for a specific processing time without
interruption. We consider that the jobs are processed in the same order on different ma-
chines. Generally, the objective of the PFSP is to find the order in which the jobs have to
be scheduled on the machines, minimizing the total flow time.
In the LOP, given a matrix B = [bij ]n×n of numerical entries, we have to find a si-
multaneous permutation of the rows and columns of B, such that the sum of the entries
above the main diagonal is maximized (or equivalently, the sum of the entries below
the main diagonal is minimized).
The QAP consists of allocating a set of facilities to a set of locations, with a cost
function associated to the distance and the flow between the facilities. The objective is
to assign each facility to a location such that the total cost is minimized. Específicamente, nosotros
are given two n × n input matrices with real values H = [hij ] and D = [dkl], where hij is
the flow between facility i and facility j , and dkl is the distance between location k and
location l. As PFSP and QAP are minimization problems, they have been transformed
into maximization problems by simply reversing the sign of the cost function.
The solutions of these three problems are coded as permutations of size n, so the
search space is of size n!. We use a deterministic best-improvement local search (ver
Algoritmo 1) to solve the instances. It is important to notice that the neighbors are eval-
uated in a specific order, de modo que, in the case of two neighbors having the same function
valor, the algorithm will always choose the first encountered. Específicamente, para el 2-
exchange, the neighbors are explored swapping the items i and j in ascending order:
the i-th item increases from 1 to n − 1 y, for each value of i, the j -th item goes from
i + 1 to n. For the insert, the neighborhood is evaluated taking the i-th item and insert-
ing it in the j -th position, also in order, with i increasing from 1 to n, and for each value
of i, the j -th item also increases from 1 to n, always considering j (cid:15)= i.
The instances used in the experiments have been taken from three well-known
benchmarks. The PFSP instances were obtained from the Taillard’s benchmark (Tail-
lard, 1993), the LOP instances from the xLOLIB benchmark (Schiavinotto and Stützle,
2005), and the QAP instances from the QAPLIB (Burkard et al., 1997). Primero, we choose 8
Volumen de cálculo evolutivo 27, Número 3
443
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
instances for each problem (numbered from 1 a 8) for which the number of local optima
and their attraction basins are exhaustively computed according to the 2-exchange (NS)
and the insert (NI ) neighborhoods. Eso es, Algoritmo 1 is applied to each solution of the
search space, for both neighborhoods separately. As this implies a high computational
costo, the original instances were reduced in order to work with permutations of size
norte = 10, so that the experimentation is computationally affordable: |(cid:2)| = 10! ≈ 3.63 · 106.
In the case of the PFSP, we reduce the instances considering 10 jobs and 5 máquinas.
En segundo lugar, in order to check if those properties observed in the small instances are also
shared by higher dimensions, we work with 4 original instances of each problem of size
norte = 50 (50 jobs and 10 machines in the case of the PFSP instances). For these instances,
Algoritmo 1 is applied to a sample of initial solutions of size M = 500. De este modo, a sample of
local optima is obtained. In each run of the algorithm, a sample of solutions belonging to
the attraction basin of each local optimum is also encountered: the initial solution plus
all the solutions found in the path to the local optimum. We analyze the different fea-
tures of the attraction basins of this sample of local optima. Por supuesto, we do not aim to
guarantee that all the different landscapes have the same properties as those observed
in this article.
En resumen, we use 8 + 4 instances for each problem, taking into account the
2-exchange and the insert neighborhoods, eso es, a total of 72 different landscapes
are analyzed. The specific instances used in the experimentation are available in the
website.1
Local Optima and Local Optimal Plateaus
4.2
Algoritmo 1 returns a local optimum σ ∗ ∈ (cid:2) such that, by definition, F (σ ∗
F (pag ), ∀σ ∈ N (σ ∗
sarily match one, and only one, of the three following options:
). As previously mentioned, this local optimal solution σ ∗
) ≥
will neces-
(i) Be a strict local optimum.
(ii) Belong to a local optimal plateau.
(iii) Belong to an open plateau.
Papers about neutral networks can be found for NK landscapes (Verel, Ochoa et al.,
2011) and PFSP (Marmion et al., 2011b, and Daolio et al., 2014). To the best of our knowl-
borde, there are no analyses about the neutrality carried out for the LOP and the QAP. En
the case of PFSP, while Marmion et al. (2011b) and Daolio et al. (2014) used makespan
1http://www.sc.ehu.es/ccwbayes/members/leticia/AnatomyOfAB/Instances.html
444
Volumen de cálculo evolutivo 27, Número 3
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Anatomy of the Attraction Basins
as the objective function, our approach focuses on the total flow time. De hecho, en el
literature, the only work analyzing the neutrality for the total flow time is Hernando
et al. (2017). Además, in this article, we explicitly present the number and sizes of the
plateaus, distinguishing between the local optimal and the open plateaus, which has
not been reflected in any previous work. Our aim, in this section, is to explore those
plateaus formed by local optima, as a first step in our topological analysis of the basins
of attraction.
We report in Table 1, for the different instances of the problems and the different
neighborhoods, in the columns labeled LO, the number of different solutions output by
Algoritmo 1. In the case of the small instances (norte = 10), this is the total number of local
optima, while for the larger instances (norte = 50), it reflects the number of different solu-
tions obtained after applying Algorithm 1 to the sample of 500 random initial solutions.
Entonces, we show in the strict LO, LO plateau, and open plateau columns, (i) the number of
strict local optima, (ii) the number of local optimal plateaus, y (iii) the number of
open plateaus, respectivamente. Notice that the unoptimal plateaus are not included in this
analysis because no local optimum belongs to them. These plateaus of the smaller, como
well as the larger, instances have been calculated starting with each of the observed lo-
cal optima and exploring recursively the neighboring solutions until no more solutions
with the same fitness are found. Notice that the sum of the strict LO, LO plateau, y
open plateau columns is not necessarily the same as the number of LO (more than one
LO can belong to the same plateau). De hecho, añadimos, entre paréntesis, the average and the
standard deviation of the number of solutions forming the plateaus. Remember that
the local optimal plateaus are composed only of local optima, while the open plateaus
include other nonoptimal solutions. We emphasize in bold, for the smaller instances,
whether the global optimum is a strict local optimum or whether it belongs to a local
optimal plateau. Obviamente, the global optima can never belong to an open plateau.
Sin embargo, in the case of multiple global optima, some of them could be strict local op-
tima while others could form one or more plateaus, meaning that the global optima of
the instance belong to two different classes of local optima: (i) y (ii).
Regarding the results, very different values are obtained for instances of the same
problema. En general, the presence of plateaus is remarkable. The average size of all the
plateaus found in the PFSP instances, under both neighborhoods, is around 2 (con un
low standard deviation). In the smaller LOP instances, for the 2-exchange neighbor-
hood, the number of plateaus is higher than for the insert neighborhood. For the larger
LOP instances, the number of plateaus is high and their size is considerably large. Mayoría
of the QAP smaller instances contain a large number of plateaus under both neighbor-
capuchas, pero, en general, for the larger instances, except for the Wil50 instance, el presidente-
ence of plateaus is small. Finalmente, for all the PFSP instances the global optima are strict
local optima. Sin embargo, in LOP and QAP, strict global optima as well as global optimal
plateaus are found, according to the instance.
En general, the presence of local optima belonging to plateaus is a tangible aspect of
permutation-based combinatorial problems, o, al menos, one should not work with these
problems assuming that they do not exist. One of the main conclusions derived from this
study is that, usually, Algoritmo 1 gets trapped inside the plateaus. Although we find
instances with plateaus composed by just two solutions, Algoritmo 1 is not designed
to detect and escape from them. Por supuesto, we cannot overlook the fact that some au-
thors have already studied the number and extension of the plateaus. In Marmion et al.
(2011b), the authors concluded that plateaus with local optima are numerous and large
for the PFSP. Sin embargo, the objective function to minimize considered in that work was
Volumen de cálculo evolutivo 27, Número 3
445
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
t
norte
mi
r
mi
F
F
i
d
mi
h
t
,
s
d
oh
oh
h
r
oh
b
h
gramo
i
mi
norte
t
r
mi
s
norte
i
mi
h
t
d
norte
a
mi
gramo
norte
a
h
C
X
mi
–
2
mi
h
t
gramo
norte
i
r
mi
d
i
s
norte
oh
C
PAG
A
q
mi
h
t
d
norte
a
PAG,
oh
l
mi
h
t
PAG,
S
F
PAG
mi
h
t
F
oh
mi
C
norte
a
t
s
norte
i
h
C
a
mi
r
oh
F
:
1
mi
yo
b
a
t
,
)
oh
l
t
C
i
r
t
s
(
a
metro
i
t
pag
oh
yo
a
C
oh
yo
t
C
i
r
t
s
F
oh
r
mi
b
metro
tu
norte
mi
h
t
,
s
norte
oh
i
t
tu
yo
oh
s
mi
s
mi
h
t
metro
oh
r
F
.
d
mi
t
r
oh
pag
mi
r
s
i
)
oh
l
(
s
pag
oh
t
s
1
metro
h
t
i
r
oh
gramo
yo
A
mi
h
t
h
C
i
h
w
norte
i
s
norte
oh
i
t
tu
yo
oh
s
F
oh
r
mi
b
metro
tu
norte
D
oh
oh
h
R
oh
B
h
GRAMO
I
mi
norte
t
R
mi
S
norte
I
D
oh
oh
h
R
oh
B
h
GRAMO
I
mi
norte
mi
GRAMO
norte
A
h
C
X
mi
–
2
/
mi
gramo
a
r
mi
v
a
mi
h
t
s
mi
s
mi
h
t
norte
mi
r
a
pag
norte
i
gramo
norte
i
t
a
C
i
d
norte
i
,
d
mi
yo
i
a
t
mi
d
mi
r
a
)
tu
a
mi
t
a
yo
pag
norte
mi
pag
oh
(
s
tu
a
mi
t
a
yo
pag
norte
mi
pag
oh
d
norte
a
,
)
tu
a
mi
t
a
yo
pag
oh
l
(
s
tu
a
mi
t
a
yo
pag
yo
a
metro
i
t
pag
oh
yo
a
C
oh
yo
F
oh
r
mi
b
metro
tu
norte
mi
h
t
yo
a
b
oh
yo
gramo
mi
h
t
mi
r
mi
h
w
s
norte
oh
i
t
tu
yo
oh
s
F
oh
s
mi
pag
y
t
mi
h
t
,
s
mi
C
norte
a
t
s
norte
i
r
mi
yo
yo
a
metro
s
mi
h
t
r
oh
F
.
s
tu
a
mi
t
a
yo
pag
mi
h
t
gramo
norte
i
metro
r
oh
F
s
norte
oh
i
t
tu
yo
oh
s
F
oh
r
mi
b
metro
tu
norte
mi
h
t
F
oh
norte
oh
i
t
a
i
v
mi
d
d
r
a
d
norte
a
t
s
.
d
yo
oh
b
norte
i
d
mi
z
i
s
a
h
pag
metro
mi
mi
r
a
d
norte
tu
oh
F
mi
r
a
a
metro
i
t
pag
oh
.
)
0
0
0
/
0
0
2
(
1
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
2
(
2
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
2
(
1
.
.
)
0
0
0
/
0
0
0
(
0
.
tu
a
mi
t
a
yo
pag
norte
mi
pag
oh
tu
a
mi
t
a
yo
pag
oh
l
.
)
0
0
0
/
0
0
2
(
1
.
.
)
0
0
0
/
0
0
2
(
2
.
.
)
2
1
2
/
0
5
3
(
2
.
.
)
0
0
0
/
0
0
2
(
1
.
.
)
0
0
0
/
0
0
2
(
3
.
.
)
0
0
0
/
0
0
2
(
1
.
.
)
0
0
0
/
0
0
2
(
1
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
4
7
0
/
0
4
2
(
5
1
.
.
)
6
4
0
/
3
1
2
(
3
2
.
.
)
7
9
0
/
3
3
2
(
1
2
.
.
)
9
3
1
/
0
5
2
(
0
2
.
.
)
2
5
0
/
0
2
2
(
1
2
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
4
(
1
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
2
(
2
2
.
.
)
3
4
0
/
9
0
2
(
2
2
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
1
3
0
/
0
1
2
(
2
2
.
.
)
0
0
0
/
0
0
3
(
.
.
)
0
0
0
/
0
0
2
(
.
.
)
0
0
1
/
0
0
3
(
.
1
1
3
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
0
0
/
0
0
5
1
(
.
1
.
)
4
9
3
0
1
2
/
0
0
6
9
9
2
(
4
.
.
)
0
0
0
/
0
0
5
3
7
(
1
.
.
)
0
0
5
4
6
/
6
3
2
2
5
4
1
(
3
0
4
.
.
)
4
8
6
2
4
/
1
9
4
6
8
(
2
2
.
.
)
2
4
2
4
1
/
3
9
9
5
5
(
3
1
1
.
.
)
4
5
5
7
6
/
8
9
7
5
6
1
8
(
5
9
3
.
.
)
3
3
8
9
5
/
6
3
.
2
2
5
8
(
7
9
.
)
5
5
6
9
2
/
8
1
.
2
9
6
(
5
4
4
.
)
3
8
3
0
1
/
4
4
.
2
1
3
(
7
8
2
.
)
7
3
4
5
6
/
2
1
.
0
5
4
4
3
(
5
0
1
t
C
i
r
t
s
oh
l
2
7
6
6
9
7
2
9
3
3
2
2
6
4
7
5
4
8
5
4
7
5
4
1
1
0
0
0
1
0
0
0
0
0
0
oh
l
tu
a
mi
t
a
yo
pag
norte
mi
pag
oh
tu
a
mi
t
a
yo
pag
oh
l
t
C
i
r
t
s
oh
l
oh
l
3
7
8
8
6
1
1
3
3
4
4
2
0
0
5
0
0
5
0
0
5
0
0
5
1
1
3
2
9
4
)
0
0
.
0
/
0
0
.
0
(
0
)
0
0
.
0
/
0
0
.
2
(
2
)
0
5
.
0
/
5
2
.
2
(
4
)
9
2
.
0
/
8
0
.
2
(
2
1
)
2
8
.
0
/
9
2
.
2
(
4
1
)
0
0
.
0
/
0
0
.
2
(
1
1
)
9
1
.
1
/
1
7
.
2
(
1
2
)
0
5
.
0
/
6
1
.
2
(
9
1
)
0
5
.
0
/
6
1
.
2
(
9
1
)
5
7
.
0
/
6
2
.
2
(
3
2
)
0
0
.
0
/
0
0
.
2
(
1
2
)
9
7
.
0
/
9
3
.
2
(
8
2
)
0
0
.
0
/
0
0
.
0
(
0
)
0
0
.
0
/
0
0
.
2
(
4
)
4
8
.
7
/
8
9
.
7
(
4
4
)
4
5
.
2
/
7
7
.
4
(
1
3
)
0
9
.
4
/
9
9
.
6
(
9
7
)
3
1
.
9
/
1
6
.
0
1
(
9
4
5
1
)
6
3
.
7
9
/
9
7
.
6
7
(
4
3
)
0
0
.
0
/
0
0
0
(
.
)
0
0
.
0
/
0
0
0
(
.
)
0
0
.
0
/
0
0
.
2
(
)
0
0
.
0
/
0
0
.
2
(
)
0
0
.
0
/
0
0
.
2
(
)
0
0
.
0
/
0
0
.
2
(
)
0
0
.
0
/
0
0
.
2
(
)
0
0
.
0
/
0
0
.
2
(
)
0
0
.
0
/
0
0
.
2
(
)
7
1
.
0
/
3
0
.
2
(
)
0
0
.
0
/
0
0
.
2
(
)
3
6
.
0
/
3
2
.
2
(
)
0
0
.
0
/
0
0
.
0
(
)
0
0
.
0
/
0
0
.
0
(
0
0
9
2
6
1
4
1
7
2
4
3
7
1
0
3
0
0
)
0
5
.
0
/
5
2
.
2
(
4
)
4
0
.
1
/
5
7
.
2
(
8
)
3
2
.
1
/
9
8
.
2
(
8
2
)
5
0
.
1
/
1
1
.
3
(
9
)
0
0
.
0
/
0
0
.
5
1
(
2
9
9
3
2
)
5
1
.
1
2
6
0
1
/
1
4
.
5
0
8
3
1
(
2
2
)
0
0
.
0
/
0
0
.
5
3
7
(
1
0
0
5
7
6
4
0
0
5
0
0
4
)
7
7
.
2
0
1
/
4
0
.
0
2
6
8
8
(
3
6
3
)
4
6
.
9
8
/
4
0
.
9
7
5
3
1
(
7
3
1
)
3
1
.
5
2
4
/
6
3
.
9
7
9
9
1
(
9
9
2
)
2
8
.
9
4
2
/
9
7
.
0
4
5
2
2
(
1
0
2
)
9
9
.
7
9
2
/
1
2
.
3
0
0
0
5
(
5
1
3
)
3
3
.
4
0
3
/
1
0
.
8
7
9
5
4
(
5
8
1
)
0
2
.
1
5
3
/
9
7
.
5
6
2
5
6
(
5
2
3
)
4
7
.
5
4
2
/
7
5
.
1
6
5
4
9
(
5
7
1
1
1
2
2
6
3
7
6
1
9
5
4
1
4
9
1
4
7
2
4
5
4
3
4
4
2
6
4
2
4
4
3
1
0
2
1
5
2
2
9
0
0
0
0
0
0
1
1
4
2
8
5
3
8
7
1
1
8
5
1
5
2
2
5
9
2
0
0
5
0
0
5
0
0
5
0
0
5
3
1
4
2
2
1
1
9
2
1
1
7
1
6
2
2
5
3
7
0
0
5
0
0
5
0
0
5
0
0
5
2
5
6
8
1
2
3
4
5
6
7
8
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
0
0
.
0
1
_
0
5
i
a
t
1
0
.
0
1
_
0
5
i
a
t
2
0
.
0
1
_
0
5
i
a
t
3
0
.
0
1
_
0
5
i
a
t
1
2
3
4
5
6
7
8
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
C
mi
mi
5
7
mi
b
–
norte
pag
norte
5
7
mi
b
–
norte
i
oh
5
7
mi
b
–
norte
t
oh
t
5
7
mi
b
–
norte
PAG
S
F
PAG
PAG
oh
l
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
446
Volumen de cálculo evolutivo 27, Número 3
D
oh
oh
h
R
oh
B
h
GRAMO
I
mi
norte
t
R
mi
S
norte
I
D
oh
oh
h
R
oh
B
h
GRAMO
I
mi
norte
mi
GRAMO
norte
A
h
C
X
mi
–
2
.
d
mi
tu
norte
i
t
norte
oh
C
:
1
mi
yo
b
a
t
Anatomy of the Attraction Basins
.
)
0
0
0
/
0
0
2
(
1
.
.
)
0
0
0
/
0
0
2
(
2
.
.
)
0
0
0
/
0
0
0
(
0
.
.
)
0
2
4
/
9
9
3
(
.
6
1
1
.
)
6
6
8
3
1
2
/
1
0
8
0
2
(
6
6
6
2
.
.
)
3
8
3
1
1
4
1
/
7
3
9
4
1
6
(
.
2
4
7
1
.
)
6
5
8
4
5
8
8
/
7
0
1
3
8
0
9
(
.
0
8
5
3
.
)
0
0
0
/
0
0
2
(
9
.
.
)
0
0
0
/
0
0
0
(
0
.
)
0
0
.
0
/
0
0
2
(
6
2
.
.
)
8
4
3
3
1
1
1
/
4
0
2
4
2
4
(
.
2
7
9
.
)
7
2
5
1
7
1
/
1
5
4
8
1
(
4
3
3
1
.
.
)
0
0
0
/
0
0
.
0
(
0
.
)
0
0
0
/
0
0
.
2
(
2
3
.
)
0
0
0
/
0
0
.
2
(
6
.
)
3
4
0
/
4
1
.
2
(
9
9
.
)
8
4
0
/
2
1
.
2
(
4
3
2
.
)
7
3
0
/
9
0
.
2
(
3
6
8
.
)
0
1
1
/
0
5
.
2
(
8
5
8
1
.
)
6
4
1
/
4
7
.
2
(
0
6
0
1
.
)
0
0
0
/
0
0
.
0
(
0
.
)
0
0
0
/
0
0
.
0
(
0
.
)
0
0
0
/
0
0
.
0
(
0
.
)
4
0
1
/
7
4
.
2
(
0
2
1
tu
a
mi
t
a
yo
pag
norte
mi
pag
oh
tu
a
mi
t
a
yo
pag
oh
l
t
C
i
r
t
s
oh
l
3
1
7
2
4
7
3
4
5
2
7
1
8
8
3
3
2
1
4
6
1
0
9
6
0
1
0
6
5
1
0
9
9
4
8
9
4
0
0
5
4
6
2
oh
l
3
1
7
2
4
6
4
4
5
7
9
2
2
5
3
5
3
3
4
6
1
4
9
3
5
1
2
1
1
9
0
6
3
2
1
0
0
5
0
0
5
0
0
5
0
0
5
)
0
0
.
0
/
0
0
.
0
(
0
)
0
0
.
0
/
0
0
.
2
(
4
)
0
0
.
0
/
0
0
.
0
(
0
)
9
0
.
1
1
/
4
5
.
7
(
3
6
)
4
2
.
9
/
5
9
.
6
(
2
5
1
)
5
2
.
3
/
5
9
.
3
(
3
2
2
)
6
8
.
5
5
4
4
/
7
5
.
6
1
9
2
(
0
7
.
)
0
0
0
/
0
0
.
0
(
0
)
0
0
.
0
/
0
0
.
2
(
5
.
)
7
6
0
/
0
3
.
2
(
0
1
.
)
0
0
0
/
0
0
.
0
(
.
)
0
0
0
/
0
0
.
0
(
0
0
)
8
5
.
0
/
0
2
.
2
(
5
2
)
0
3
.
5
/
6
7
.
7
(
4
3
)
5
0
.
2
9
9
6
3
/
3
3
.
1
9
5
2
2
(
2
9
1
)
9
9
.
0
1
/
2
9
.
2
1
(
6
2
tu
a
mi
t
a
yo
pag
norte
mi
pag
oh
tu
a
mi
t
a
yo
pag
oh
l
)
0
0
.
0
/
0
0
.
2
(
2
)
0
0
.
0
/
0
0
.
2
(
1
)
0
0
.
0
/
0
0
.
0
(
0
)
3
4
.
8
/
5
6
.
5
(
4
4
2
)
0
0
.
0
/
0
0
.
2
(
)
0
0
.
0
/
0
0
.
0
(
)
0
0
.
0
/
0
0
.
0
(
1
0
0
)
8
0
.
1
/
1
5
.
2
(
2
9
t
C
i
r
t
s
oh
l
9
1
4
9
8
6
4
7
4
8
8
2
6
9
2
0
0
1
7
4
9
9
4
0
0
5
4
6
1
oh
l
9
1
8
0
1
5
6
1
4
7
4
6
7
4
8
9
5
2
5
7
4
7
4
0
0
5
0
0
5
0
0
5
0
4
8
1
1
2
3
4
5
6
7
8
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
t
s
norte
I
b
0
5
a
pag
i
l
a
0
5
i
a
t
b
0
5
i
a
t
0
5
yo
i
W.
PAG
A
q
Volumen de cálculo evolutivo 27, Número 3
447
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
Mesa 2: Number of permutations of size 10 at the different distances from a given so-
lution according to the type of neighborhood.
re = 1 re = 2 re = 3
re = 4
re = 5
re = 6
re = 7
re = 8
re = 9
2-exchange
Insert
45
81
870
2521
9450
38281
63273
296326
269325
1100902
723680
1604098
1172700
569794
1026576
16795
362880
1
the makespan, instead of the total flow time, as in this article. According to a recent
trabajar (Hernando et al., 2017) there is a lower number of local optima sharing the fitness
value when minimizing the total flow time than when minimizing the makespan. En-
deed, Mesa 1 shows that, for the PFSP instances, the presence of local optima belonging
to plateaus is not so high.
Once the plateaus are explored, we take into account that those local optima be-
longing to a plateau share the same attraction basin. An attraction basin, de este modo, will be
the attraction basin of a strict local optima or that of a plateau (optimal or open).
4.3
Topology of the Attraction Basins
From our point of view, the structure of the attraction basins can be characterized by
these principal aspects: roundness of the attraction basins, centrality of the local optima,
and interior and frontier of the attraction basins. We examine these topological features
of the attraction basins of the strict local optima, the open plateaus, and the local optimal
plateaus.
4.3.1 Roundness of the Attraction Basins
As was explained in Section 3.1, an attraction basin is considered to be round if all the
solutions at distance 1, 2, . . . until a certain distance r from the local optimum or the
plateau are within the attraction basin. We record, for the smaller instances, for each
local optimum, the proportion of solutions belonging to its attraction basin that are at
different distances from it. Just as a reference, en mesa 2, we show the total number of
solutions at different distances from any solution in the space of permutations of size
10. Notice that these values differ from the number of solutions at different distances
when referring to a plateau. The distance between one plateau and one solution is the
minimal distance between this solution and all the solutions in the plateau. Por ejemplo,
if a plateau is formed by two solutions, the number of permutations at distance one is
the sum of the number of the neighbors of both solutions, eliminating repetitions and
both solutions themselves. Además, en este caso, the maximum reachable distance
would be 8. For the larger instances, we take those local optima obtained in the sample
of size 500, y, as it is impossible to check the solutions at all the possible distances
from them, we focus on those at distance 1. So, we analyze if the solutions at distance
1 from each of the local optima (or distance 1 from the plateaus) belong to its same
attraction basin. We also record, among the solutions found in the sample for each local
optimum, the maximum distance at which a solution is within the attraction basin.
En figura 2, the results are plotted distinguishing between problems and neighbor-
capuchas. In the x-axis of the figures the distance to the local optimum is indicated and
the y-axis shows the percentage of solutions that belong to their attraction basins. Para
the smaller instances (bars in gray), the average value obtained in each landscape and
the maximum and minimum percentages found are represented. Those instances of
448
Volumen de cálculo evolutivo 27, Número 3
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Anatomy of the Attraction Basins
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Cifra 2: Average, maximum, and minimum percentage of solutions that are at different
distances from the local optima and that belong to its attraction basin, for the instances
del (from top to bottom) PFSP, LOP, and QAP, considering the 2-exchange and the
insert neighborhoods. For the instances with n = 10 (bars in gray), the results at all the
possible distances are shown, while for the instances with n = 50 (bars in black), justo
those at distance 1, which is the only computationally affordable in a reasonable time.
The graphs on the right represent the average (and maximum) of the maximal distances
found in the sample obtained for the attraction basins of the instances with n = 50.
the LOP that present just one local optimum under the insert neighborhood have been
removed from Figure 2. The average percentage of solutions in the attraction basin de-
creases with the distance to the local optimum. The maximum and the minimum per-
centage found for a local optimum also decreases with the distance to the local optimum
for the three problems considering the 2-exchange neighborhood. This also happens for
the QAP and the insert neighborhood. Sin embargo, for the PFSP and LOP under the in-
sert neighborhood, we find that the maximum percentage encountered increases when
Volumen de cálculo evolutivo 27, Número 3
449
l. Hernando, A. Mendiburu, y j. A. Lozano
reaching the longest distances. The reason for this phenomenon is that, for the insert
neighborhood, the number of possible solutions decreases quickly at long distances
y, Por ejemplo, for those strict local optima, there is just 1 possible solution at dis-
tance 9 (ver tabla 2). Por lo tanto, if we find a strict local optimum whose solution at the
maximum distance belongs to its attraction basin, we will find that 100% of the solutions
(just one) at this distance belongs to it, as observed for the PFSP.
Regarding the smaller instances, the average percentage of solutions at distance 1
from the local optima is lower than 100. This means that, on average, we can find neigh-
boring solutions of the local optima that belong to different attraction basins. Obviamente,
in all the problems and neighborhoods we find at least one local optimum with all its
neighbors belonging to its own attraction basin: the global optima or the global opti-
mal plateaus. The results obtained for the larger instances (bars in black) confirm this
resultado. Taking into account the local optima found in the sample, on average, hay
a probability higher than 0 of finding a neighboring solution of the local optima be-
longing to a different attraction basin. In all the scenarios, we find local optima whose
attraction basins contain solutions far from them. In the case of the smaller instances,
solutions at distance 8 o 9 to the local optima are found in the attraction basins. Para
the larger instances, En figura 2 we add a graph showing the average of the maximum
distances from the local optima at which a solution inside the attraction basin has been
found. The maximum distance encountered in all the attraction basins is also included
(the gray triangles). The dashed line indicates the maximum possible distance (49). C.A-
cording to these plots, solutions far from the local optima are also inside their attraction
basins. Notice that the maximum distances presented here are lower bounds of the real
unos, this is because we are exploring just a sample of the solutions of the attraction
basins. Sin embargo, in this sample for the LOP and QAP using the 2-exchange neighbor-
hood, attraction basins with solutions at the maximum possible distance from the local
optima have already been found.
The percentage of the solutions in an attraction basin is related with the escape rate
analyzed in a number of works, como, Merz (2004) and Daolio et al. (2014). The es-
cape rate is a measure that gives the probability of reaching a different attraction basin.
According to all those works, the escape rate increases with the distance to the local op-
tima, that is precisely what can be observed in Figure 2: the decrease of the percentage
of the solutions in the attraction basins means the growth of the percentage of the solu-
tions in different attraction basins. Although examining the roundness of the attraction
basins and delving into the escape rate produce closely related information, we consider
that our perspective is more suitable for giving explicit knowledge about the topology
of the attraction basins and helps in the visualization of the structure of these sets.
En general, Cifra 2 reveals that, on average, the local optima are located in the fron-
tier of the attraction basins, as they have a number of neighboring solutions belonging
to a different attraction basin. Sin embargo, on average, we also find solutions at the longest
distances from them that do belong to their attraction basins. This structure clearly dif-
fers from the concept of roundness.
4.3.2 Centrality of the Local Optima
We aim to study the position of the local optima within the attraction basins. Para esto
purpose, we focus on the centrality of the local optima inside the attraction basins.
As seen in Section 3.2, the local optima (or the plateaus) are considered to be cen-
tered if they minimize the average distance to the rest of the solutions in the attraction
basin. In order to examine this point, calculamos, for each solution in each attraction
450
Volumen de cálculo evolutivo 27, Número 3
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Anatomy of the Attraction Basins
Dσ ∗
|B(σ ∗ )| o
basin, the previously defined measure D. As computing this experiment for the larger
instances is unaffordable, it has been done just for those smaller instances. For this ex-
perimento, we show, as representative cases, one instance of each problem (8th instance
of PFSP, 8th instance of LOP, and 8th instance of QAP) and we report, En figura 3, el
results obtained for the attraction basins of the global optima as well as the results ob-
tained for all the attraction basins of all the local optima of each of the selected instances.
The figures with the distances of the remaining instances are available at the website.2 In
DP
the x-axis of Figure 3 the average distance, eso es,
|B(PAG )| , is indicated, while its
variance is represented in the y-axis. So, each point in gray shows the average/variance
of the distances for those solutions that are not local optima, and the points in red rep-
resent the local optima. The three figures in the first and third columns display the
distances for the solutions of the attraction basins of the global optima under the 2-
exchange and the insert neighborhoods, respectivamente. In the second and fourth columns,
the distances of the different solutions of each attraction basin have been scaled to the in-
terval [0,1] in order to compare different results belonging to different attraction basins.
Each of these plots shows the scaled average and variance of the distance from each
solution of the search space to the remaining solutions in its same attraction basin. So,
a total of 10! points are plotted, highlighting in red those referring to the local optima.
All the plots are very similar for all the problem instances. The global optima have
a really small average distance to the rest of the permutations in their attraction basins.
From those graphs that represent all the solutions of the search space, we can deduce
that not only the global optima, but also all of the local optima of the instance have a
lower average distance than the rest of the solutions of the attraction basins. De hecho,
a large proportion of the local optima have their average scaled values equal to zero.
We conclude that the local optima are located close to the barycenter of the attraction
basins, as they have the minimal (or almost the minimal) average distances to the rest
of the solutions: en general, they are almost centered within the attraction basins. El
large variance observed in some of the local optima (particularly, for the insert neighbor-
hood), corresponds with the behavior observed in Figure 2: not all the solutions close
to the local optima are in their attraction basins, y, at the longest distances, alguno
solutions are found which belong to them.
Interior and Frontier of the Attraction Basins
4.3.3
According to the study about the roundness of the attraction basins (Sección 4.3.1), en
most cases, the local optima are located in the frontier of the attraction basins. We de-
velop two different analyses for a deep examination regarding the interior and frontier
of the attraction basins. Primero, we check whether each solution in the attraction basins
is located in the interior, and for each attraction basin we record the number of neigh-
boring attraction basins. Próximo, we explore the evolution of the number of neighboring
attraction basins and the evolution of the neighboring solutions that share the same
attraction basin, as the distance to the local optimum increases.
I. The interior and the neighboring relations of the attraction basins
En mesa 3 nosotros reportamos, for each instance, distinguishing between the 2-exchange
and the insert neighborhoods, the percentage of the solutions found in the attrac-
tion basins that have all their neighboring solutions in their same attraction basin
(interior solutions). For the smaller instances, all the solutions of the search space
are checked, mientras, for the larger instances, the percentages refer to the solutions
2http://www.sc.ehu.es/ccwbayes/members/leticia/AnatomyOfAB/centralityLO.html
Volumen de cálculo evolutivo 27, Número 3
451
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
norte
oh
i
t
C
a
r
t
t
a
mi
h
t
norte
i
s
norte
oh
i
t
tu
yo
oh
s
mi
h
t
F
oh
t
s
mi
r
mi
h
t
oh
t
s
mi
C
norte
a
t
s
i
d
mi
h
t
F
oh
mi
C
norte
a
i
r
a
v
d
norte
a
mi
gramo
a
r
mi
v
a
mi
h
t
,
norte
i
s
a
b
norte
oh
i
t
C
a
r
t
t
a
mi
h
t
F
oh
norte
oh
i
t
tu
yo
oh
s
h
C
a
mi
r
oh
F
:
3
mi
r
tu
gramo
i
F
,
metro
oh
t
t
oh
b
oh
t
pag
oh
t
metro
oh
r
F
(
PAG
A
q
mi
h
t
F
oh
mi
C
norte
a
t
s
norte
i
h
t
8
mi
h
t
d
norte
a
PAG
oh
l
mi
h
t
F
oh
mi
C
norte
a
t
s
norte
i
h
t
8
mi
h
t
PAG,
S
F
PAG
mi
h
t
F
oh
mi
C
norte
a
t
s
norte
i
h
t
8
mi
h
t
r
oh
F
norte
w
oh
h
s
mi
r
a
norte
i
s
a
b
yo
a
C
oh
yo
mi
h
t
oh
t
i
gramo
norte
d
norte
oh
pag
s
mi
r
r
oh
C
s
t
yo
tu
s
mi
r
mi
h
t
.
)
y
yo
mi
v
i
t
C
mi
pag
s
mi
r
,
t
h
gramo
i
r
oh
t
t
F
mi
yo
metro
oh
r
F
(
s
d
oh
oh
h
r
oh
b
h
gramo
i
mi
norte
t
r
mi
s
norte
i
d
norte
a
mi
gramo
norte
a
h
C
X
mi
–
2
mi
h
t
gramo
norte
i
s
tu
,
)
y
yo
mi
v
i
t
C
mi
pag
s
mi
r
.
y
a
r
gramo
norte
i
mi
r
a
s
norte
oh
i
t
tu
yo
oh
s
F
oh
t
s
mi
r
mi
h
t
F
oh
mi
s
oh
h
t
mi
yo
i
h
w
,
d
mi
r
norte
i
mi
r
a
a
metro
i
t
pag
oh
452
Volumen de cálculo evolutivo 27, Número 3
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Anatomy of the Attraction Basins
Mesa 3: Percentage of the number of solutions that fall in the interior of the attraction
basins and, for the smaller instances, the last column shows the average number of
neighboring attraction basins.
strict LO +
LO plateau +
plateau
% in the interior of the
attraction basins
Significar
(Variance) Maximum Minimum
Average number
of neighboring
att. bas.
2-EXCHANGE
PFSP
LOP
QAP
INSERT
PFSP
Inst 1
Inst 2
Inst 3
Inst 4
Inst 5
Inst 6
Inst 7
Inst 8
tai50_10.00
tai50_10.01
tai50_10.02
tai50_10.03
Inst 1
Inst 2
Inst 3
Inst 4
Inst 5
Inst 6
Inst 7
Inst 8
N-be75eec
N-be75np
N-be75oi
N-be75tot
Inst 1
Inst 2
Inst 3
Inst 4
Inst 5
Inst 6
Inst 7
Inst 8
Lipa50b
Tai50a
Tai50b
Wil50
Inst 1
Inst 2
Inst 3
Inst 4
Inst 5
Inst 6
Inst 7
Inst 8
11
24
49
81
111
157
219
294
500
500
500
500
13
24
54
57
81
97
36
23
500
500
500
500
19
103
141
474
440
544
104
218
474
500
500
500
3
7
7
8
13
30
42
24
0.0392 (0.0037)
0.0169 (0.0021)
0.0020 (0.0000)
0.0016 (0.0000)
0.0010 (0.0000)
0.0007 (0.0000)
0.0012 (0.0000)
0.0007 (0.0000)
0.0159 (0.0422)
0.0000 (0.0000)
0.0071 (0.0255)
0.0205 (0.0775)
0.0075 (0.0003)
0.0320 (0.0241)
0.0002 (0.0000)
0.0003 (0.0000)
0.0008 (0.0000)
0.0002 (0.0000)
0.0013 (0.0000)
0.0180 (0.0052)
0.0000 (0.0000)
0.0085 (0.0195)
0.0000 (0.0000)
0.0000 (0.0000)
0.0095 (0.0010)
0.0036 (0.0001)
0.0008 (0.0000)
0.0011 (0.0000)
0.0005 (0.0000)
0.0003 (0.0000)
0.0015 (0.0000)
0.0001 (0.0000)
0.3846 (18.2420)
0.0887 (0.4069)
0.0714 (0.4059)
0.1747 (0.8887)
0.0628 (0.0037)
0.0166 (0.0008)
0.0167 (0.0020)
0.0064 (0.0002)
0.0284 (0.0105)
0.0002 (0.0000)
0.0002 (0.0000)
0.0010 (0.0000)
0.1531
0.2026
0.0387
0.0420
0.0214
0.0231
0.0221
0.0288
2.7027
0.0000
3.5714
5.0000
0.0458
0.7606
0.0026
0.0110
0.0087
0.0117
0.0166
0.3420
0.0000
2.7397
0.0000
0.0000
0.1311
0.0588
0.0288
0.0304
0.0190
0.0180
0.0441
0.0059
67.4419
7.4074
8.4746
11.8644
0.1212
0.0616
0.1171
0.0447
0.3691
0.0024
0.0068
0.0094
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
10.00
23.00
47.76
75.73
106.41
146.82
200.34
260.86
12.00
23.00
51.41
54.04
78.91
89.67
33.83
20.26
18.00
97.07
130.68
398.33
377.24
423.57
91.77
152.19
2.00
6.00
6.00
7.00
12.00
29.00
40.81
23.00
Volumen de cálculo evolutivo 27, Número 3
453
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
strict LO +
LO plateau +
plateau
LOP
tai50_10.00
tai50_10.01
tai50_10.02
tai50_10.03
Inst 1
Inst 2
Inst 3
Inst 4
Inst 5
Inst 6
Inst 7
Inst 8
N-be75eec
N-be75np
N-be75oi
N-be75tot
QAP Inst 1
Inst 2
Inst 3
Inst 4
Inst 5
Inst 6
Inst 7
Inst 8
Lipa50b
Tai50a
Tai50b
Wil50
500
500
500
500
1
1
1
1
3
2
1
5
500
432
500
400
2713
4432
2796
16427
4956
14219
5160
4640
500
500
500
500
Mesa 3: Continuado.
% in the interior of the
attraction basins
Significar
(Variance)
0.0000 (0.0000)
0.0000 (0.0000)
0.0045 (0.0103)
0.0096 (0.0232)
100.0000 (0.0000)
100.0000 (0.0000)
100.0000 (0.0000)
100.0000 (0.0000)
0.1612 (0.0052)
0.4072 (0.1448)
100.0000 (0.0000)
0.7944 (3.1556)
0.0524 (0.3991)
2.7516 (37.4291)
0.0305 (0.1204)
0.1546 (1.1971)
0.0000 (0.0000)
0.0002 (0.0000)
0.0001 (0.0000)
0.0009 (0.0001)
0.0001 (0.0000)
0.0005 (0.0001)
0.0000 (0.0000)
0.0000 (0.0000)
0.0000 (0.0000)
0.0000 (0.0000)
0.0000 (0.0000)
0.0000 (0.0000)
Maximum Minimum
0.0000
0.0000
2.2727
2.5641
100.0000
100.0000
100.0000
100.0000
0.2216
0.6763
100.0000
3.9722
10.0000
29.4118
4.6512
16.9811
0.0199
0.0876
0.0606
0.4348
0.0358
0.2283
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
100.0000
100.0000
100.0000
100.0000
0.0818
0.1381
100.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
Average number
of neighboring
att. bas.
—
—
—
—
2.00
1.00
—
3.60
558.08
1167.52
771.59
1453.54
1214.20
1356.76
1180.41
909.66
found in the sample (not only the 500 initial random solutions, but also those
solutions that the algorithm finds in the paths until it reaches the local optima).
The first column in Table 3 shows the sum of the number of strict LO, LO plateau,
and plateau seen in Table 1. In the second column of Table 3, the average per-
centage of the interior solutions with its variance is reported, and the third and
fourth columns provide the maximum and the minimum percentages found for
each of the instances.
En general, the percentages are really small, with the exception of those in-
stances that have just one local optimum, para cual, obviamente, 100% del
solutions are located in the interior of the only attraction basin (all of the so-
lutions of the search space are in the same attraction basin). We also find some
high maximum percentages for the QAP larger instances under the 2-exchange
neighborhood and for the LOP larger instances under the insert neighborhood.
Sin embargo, the average percentages obtained for these instances are very low. Este
result matches with some previous works where it was found that, for different
optimization problems, most of the solutions were located in the frontier of the
454
Volumen de cálculo evolutivo 27, Número 3
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Anatomy of the Attraction Basins
attraction basins (Fonlupt et al., 1999; Tomassini et al., 2008; Verel et al., 2008;
Ochoa et al., 2014).
The fact that there is a really low number of solutions in the interior of the
attraction basins leads us to report in the last column, for the smaller instances,
the average number of neighboring attraction basins. Asombrosamente, for most of
the instances of all problems, and considering both neighborhoods, we find that
this average value is really high: close to the total number of local optima. Ba-
sically, we could conclude that, for each pair of attraction basins, we can find
two neighboring solutions belonging to each of them: almost all of the attraction
basins are neighboring attraction basins. This result reveals that all the attraction
basins are intertwined in the search space.
II. Evolution of the neighboring attraction basins with the distance to the local
optima
We still do not know if each of these solutions in the frontier touches just one
or more attraction basins. Además, we do not know if the distance from
the frontier solution to the local optimum affects this number of neighboring
attraction basins. So, in order to take a step forward in the analysis about the
frontier of the attraction basins, we delve into the neighboring relations of the
attraction basins as the distance to the local optima increases.
En este sentido, for each solution, we study (i) the number of its neighbors that
belong to its same attraction basin, y (ii) for all those neighbors that do not be-
long to that attraction basin, we record the number of different attraction basins
observado. Notice that, when working with n = 10, each solution can have a max-
imum of 45 y 81 different neighboring attraction basins, for the 2-exchange
and the insert neighborhoods, respectivamente (the size of the neighborhood in each
caso). In the case of n = 50, this maximum number is 1225 y 2401, respectivamente.
En figura 4, the results are distinguished between problems and neighborhoods.
The results are also separated for the larger and the smaller instances, indicando
norte = 10 and n = 50 in each case. In all the graphs, the x-axis indicates the distance
of the solutions in the attraction basins to the local optima. For n = 10, this dis-
tance goes from 1 a 9 (the maximum possible distance for both neighborhoods),
and for n = 50 it goes from 1 a 49. In each graph, the y-axis shows the following:
(i) in gray, the average of the proportion of neighboring solutions that fall in the
same attraction basin.
(ii) in black, the average of the proportion of the number of different neighboring
attraction basins per number of neighboring solutions.
For the three problems a general behavior is observed. The average proportion
of the number of neighbors belonging to the same attraction basin decreases with
the distance to the local optima, while the average proportion of the number of
different neighboring attraction basins increases. Eso es, those solutions that are
close to the local optimum have a large proportion of their neighbors inside the
same attraction basin. The solutions that are far from the local optimum have a
small number of neighbors in the same attraction basin. Al mismo tiempo, el
number of different neighboring attraction basins is large. It seems that if we
take all the solutions of an attraction basin, we will find that the connectivities
with other different attraction basins are higher for those solutions at long dis-
tances from the local optima. The behavior for the LOP instances with the insert
neighborhood is different than in the rest of the landscapes. We could say that in
Volumen de cálculo evolutivo 27, Número 3
455
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Cifra 4: Average of the proportion of the number of different neighboring attraction
basins and of the proportion of the number of neighbors belonging to the same attrac-
tion basin, according to the distance of the solutions to the local optimum. The differ-
ent graphs show the results for the instances of the PFSP, LOP, and QAP (from top to
abajo), when considering the 2-exchange (izquierda) and the insert (bien) neighborhoods.
Inside each of these graphs, the smaller (norte = 10) and the larger (norte = 50) instances are
distinguished.
456
Volumen de cálculo evolutivo 27, Número 3
Anatomy of the Attraction Basins
this scenario, the attraction basins are less interconnected with each other than
in the others.
We should take into account that the attraction basins are built by the local
search algorithm. It draws paths that start at a certain point and continue from
neighboring to neighboring solutions, ending at the local optimum. Por lo tanto,
the starting point has at least one neighbor in the same attraction basin, y el
rest of the points visited across the path have at least two neighbors in the same
attraction basin. In the case of a solution having three or more neighbors be-
longing to the attraction basin, it means that either the paths are not completely
disconnected and they share a number of solutions, or they are so close to each
other that the solutions in one path are neighbors of those of the other paths.
In order to examine this point, we add a blue line in all the graphs of Figure
4. This blue line indicates the proportion of 2 divided by the size of the neigh-
borhood; eso es, 2/45 y 2/81 in the case of n = 10 for the 2-exchange and the
insert neighborhoods, respectivamente, y 2/1225 y 2/2401 for n = 50 para el 2-
exchange and the insert neighborhoods, respectivamente. So, if the gray triangle is
above the blue line, it means that, on average, the solutions have three or more
neighbors in the same attraction basin. For the instances of size n = 10, the blue
line is always below the average proportion of the number of neighbors in the
same attraction basin, even for those solutions at the longest distances. Para el
instances of size n = 50, for the insert neighborhood, this average proportion is
also higher than the blue line for all the distances. Considering the 2-exchange
neighborhood, just for those solutions at the longest distances, the average of the
number of neighbors in the same attraction basin is equal to or lower than 2. Y-
der this result, we can assert that the paths drawn by the local search algorithm
are interconnected with each other or, al menos, they are close to each other.
4.4 Discusión
The attraction basins can be understood as long intertwined rivers that flow into the dif-
ferent local optima, instead of being mountains in a landscape. De hecho, each attraction
basin is composed of several of those rivers ending at the same local optimum, mientras
at the same time, each of them could have different tributaries. Además, the end of
those rivers can be made up of more than one local optimum that have the same objec-
tive function value, forming a plateau. The local optima or the plateaus composed by
local optima are centered in the attraction basin. Sin embargo, we should be cautious
with this perception, because by understanding the combinatorial optimization land-
scapes as if we were in a 3D natural landscape, we could be misunderstanding the real
anatomy.
Two main conclusions regarding the performance of the algorithms based on lo-
cal search could be derived from this understanding of the combinatorial landscapes.
Primero, we have seen that the local search is sometimes trapped inside a plateau which
has a better neighboring solution, giving the possibility of reaching a better local op-
timum. Por lo tanto, the number and extension of the plateaus containing local optima
should be taken into account when referring to the difficulty of the algorithm for a spe-
cific instance. En segundo lugar, until now, it was believed that the larger an attraction basin,
the further we should go from the local optimum to escape from it and find a differ-
ent one. Sin embargo, as can be observed in this study, on average, just one movement in
the neighborhood is enough to find a new attraction basin, porque, usually, the local
Volumen de cálculo evolutivo 27, Número 3
457
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
optima are located in the frontier of the attraction basins. Obviamente, the probability of
finding different attraction basins increases with the distance to the local optimum.
All the information gathered in this article could be used for the design of new
algoritmos. Particularly, iterated local search (ILS) algoritmos, which are built to escape
from the local optima (Lourenço et al., 2003, 2010). Most of these implementations use
a specific operator in the local search and apply a different operator to escape from
the local optima. Some other authors design ILS algorithms, which escape from the
local optima by applying a large number of movements of the same operator used in
the local search. Sin embargo, with this new knowledge about the attraction basins,
we could find other more simple and effective ways of escaping from the attraction
basins. It just depends on the aim of the researcher: exploitation versus exploration.
Por un lado, we know that, on average, once a local optimum is found, just by
checking all the solutions at distance one, we will find at least one solution belonging to
the attraction basin of a different local optimum. Además, this new local optimum
has a better objective function value than the previous one because that solution has
a neighbor with better fitness than the local optimum, y, por lo tanto, the new local
optimum will also have better fitness than the previous one. En este caso, we do not
need to check any acceptance criterion for the new local optimum, as we are sure that
this new local optimum improves the value of the previous one. Sin embargo, as previously
mentioned, the probability of finding new attraction basins at distance one from the
local optima is lower than at higher distances. That is why, por otro lado, cuando nosotros
are interested in finding a high number of different attraction basins (exploration), el
results of this article recommend looking among those solutions in the attraction basins
that are far from the local optima. Inside the set of their neighboring solutions, there is a
high probability of finding a large number of different attraction basins. Sin embargo,
en este caso, the acceptance criterion should be evaluated, as we do not have information
about the goodness of those new local optima.
The applicability of our results is not limited to the design of algorithms that solve
instances of COPs; en efecto, these results are also useful for improving the development
of the study of other features of the landscape. En primer lugar, having information about the
structure of the attraction basins helps in the estimation of their size, as was seen in
Hernando et al. (2016a). En segundo lugar, this anatomy of the attraction basins can be a use-
ful tool to estimate the number of local optima of the instance, as it is already known
that some of the existing methods to estimate the number of local optima are based on
the distribution of the sizes of the attraction basins (Hernando et al., 2013a). Más-
más, we can discover from this study those regions of the search space that, with high
probabilidad, contain different local optima or contain solutions belonging to different
attraction basins. This information could somehow be used to estimate the number of
non-observed local optima in the sample.
5 Visualizing the Attraction Basins
We show two examples of the visualization of the attraction basins. Primero, we choose
a specific instance, and we show, in a more visual way, sin embargo, all the information
analyzed in the article, in order to provide the reader with an intuition about the con-
nections between the different attraction basins of one instance. En segundo lugar, we choose
a specific attraction basin of an instance, and give a representation by means of a net-
work showing all the paths encountered until the local optimum is reached. We consider
that these two examples help to understand the conclusions collected from the results
obtained in the previous sections. The specific examples presented here have been
458
Volumen de cálculo evolutivo 27, Número 3
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Anatomy of the Attraction Basins
chosen as representative cases. These are small but large enough to visualize the stud-
ied features. More examples of similar representations for other different instances and
attraction basins are available at the website.3
5.1
Ejemplo 1: Interrelation of the Attraction Basins of One Instance
In order to provide an example of how all the attraction basins found in an instance
are interrelated, for each of the 7 local optima of the 2nd PFSP instance under the in-
sert neighborhood, we plot the proportion of the number of solutions at the different
distances from each of the local optima that belong to each of the different attraction
basins. Eso es, plots (a)–(gramo) En figura 5 show the results obtained for the 1st to the 7th
local optima, respectivamente. Notice that, in this instance, all the local optima are strict local
optima. The local optima are sorted according to their objective function value (the 1st
local optimum being the global optimum) and each color refers to the attraction basin
of each of the local optima, maintaining the relation between colors and local optima
en el 7 plots. Específicamente, the proportion in red, yellow, verde, aquamarine, azul, en-
digo, and purple will refer to the attraction basins from the 1st to the 7th local optima,
respectivamente, in all the 7 plots. Without wanting to lose perspective and being aware of
the non-round shape of the attraction basins, we represent them as bullseyes. The cor-
responding local optimum is centered in the bullseye and 9 concentric rings represent
the solutions at the 9 possible distances. So, at each of these distances, the proportion of
solutions belonging to the distinct attraction basins are plotted with different colors.
By showing these bullseyes, we provide an intuition on how solutions belonging to
different attraction basins appear while going further from the local optima. Sin embargo,
all the solutions inside a specific color are not necessarily all together as in the rings
of the bullseyes. Eso es, as previously mentioned, the attraction basins are interrelated
with many connectivities appearing among them. So, a figure in which all the colors
mixed with each other would be more realistic. Sin embargo, we found this representation a
bit awkward and, por lo tanto, in order to complete this information, we decided to include
a graph accompanying each bullseye. We gather the solutions of each attraction basin
according to their distance to the local optimum. Entonces, for each of these solutions, nosotros
record the number of its neighbors that belong to the same attraction basin. The black
bars represent the average number of the neighboring solutions in the same attraction
basin according to the distance from the local optimum (given by the x-axis). Notice
that the maximum value of the bars is 81, because under the insert neighborhood, este
is the number of neighboring solutions. The width of the gray bars is proportional to the
average number of different attraction basins found at each distance. Según estos
figures, all the local optima of this instance, except the two local optima with highest
aptitud física, always have neighboring permutations in a different attraction basin. Además,
for all the local optima (including the global optimum) we find solutions at distance one
that have neighboring solutions belonging to different attraction basins. This means that
paths belonging to other different attraction basins are mixed with them from a distance
of just 1.
5.2
Ejemplo 2: The Attraction Basin of One Local Optimum
The visualization of an attraction basin is not an easy task. The large number of per-
mutations in the search space and the considerably large number of neighbors for each
solución, together with the non-ordered permutation space, means that any plot in 2D
3http://www.sc.ehu.es/ccwbayes/members/leticia/AnatomyOfAB/visualization.html
Volumen de cálculo evolutivo 27, Número 3
459
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Cifra 5: The bullseyes represent, for the 1st to the 7th local optimum (para (a)–(gramo), respetar-
activamente) the proportion of the number of solutions that belong to the different attraction
basins (plotted in different colors) according to the distance from the local optimum (lo-
cated in the center of the bullseye). For the solutions of each of the attraction basins, el
bars in black show the average proportion of neighbors belonging to the same attraction
basin according to the distance to the local optimum. The width of the bars in gray is
proportional to the number of the different neighboring attraction basins.
460
Volumen de cálculo evolutivo 27, Número 3
Anatomy of the Attraction Basins
Cifra 6: Visualization of an attraction basin of a local optimal plateau found in the 7th
instance of the PFSP with the 2-exchange neighborhood, considering only the steps of
the algorithm (izquierda) and taking into account, as far as possible, the distances between all
the solutions (bien).
or 3D should be interpreted with caution. Aquí, we propose a way of visualizing the
attraction basins by means of directed graphs. Each node of the graph represents one
solution belonging to the attraction basin. Edges between nodes indicate that the node
at the end of the edge is the best neighbor of the node at the start of the edge. The color
of the nodes changes with the distance to the local optimum. Particularly, rojo, yellow,
verde, light blue, dark blue, and purple are used to represent the solutions at distances
0 (the local optima), 1, 2, 3, 4, y 5, respectivamente. The size of the nodes and the width of
the edges also decrease as the distance to the local optimum increases.
Cifra 6 presents two different graphs illustrating the same attraction basin of a
local optimal plateau of the 7th instance of the PFSP when using the 2-exchange neigh-
borhood. Both graphs have been created using the igraph package in the R programming
idioma (Csárdi and Nepusz, 2006). Cifra 6 (izquierda) represents this attraction basin con-
sidering the steps that the algorithm takes until it reaches the local optimal plateau (y
not the distances between the solutions). For this purpose, we add the layout_with_kk
option when plotting the graph in R. En este caso, there are two local optima (the nodes
in red) forming the local optimal plateau. This visualization could lead us to think that
the structure defined by an attraction basin is perfectly ordered in the search space and
close to the convexity, roundness and symmetry. Sin embargo, as previously mentioned, en
this plot, the distances between each pair of solutions in the attraction basin have not
been considered. Además, we should point out that the number of edges that each of
the nodes of the graph, and especially the local optima, have is really small compared
with the maximum possible number (45 neighbors). This means that solutions belong-
ing to different attraction basins are mixed, as can be seen in Example 1.
In an attempt to visualize this attraction basin in a more realistic way, we force
the graph to take into account the distances between all the solutions that belong to
the attraction basin (Cifra 6 (bien)). We use the sammon function also found in R
Volumen de cálculo evolutivo 27, Número 3
461
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
(Venables and Ripley, 2002), which maps a high-dimensional space to a 2D space, intentando
to preserve those distances in the high-dimensional space (Sammon, 1969). Por supuesto,
the resulting graph does not fulfill exactly all the distances between each pair of nodes,
because visualizing the permutation space in 2D is impossible. Sin embargo, it allows us to
observe that the real structure of the attraction basins is more complex than one could
try to imagine, y, por supuesto, much more complex than that shown in Figure 6 (izquierda).
The visualization in the 3D space can be found at the website.4
6 Conclusions and Future Work
The landscape of combinatorial problems has been described by many authors as a set
of mountains and valleys, resembling the continuous domain. This widespread idea has
been the basis for the design of algorithms. Sin embargo, as a few authors already noticed,
some results found for the features of the attraction basins contradict this. Unfortu-
nately, these works have been ignored in practice. Por lo tanto, our aim in this article has
been to analyze a number of topological properties of the attraction basins in order to
provide knowledge about their structure and to break with the extended and mistaken
intuition about the anatomy of the attraction basins.
A deep analysis of the features of the attraction basins has been developed. El
fact of having local optima forming plateaus is a remarkable aspect of the instances of
permutation-based COPs. De este modo, we usually find that the algorithm gets trapped inside
the plateaus. Por esta razón, they could be seen as a complexity measure for the in-
posturas, o, al menos, the number and extension of plateaus could be a supplement to
the number of local optima when dealing with the difficulty of the instances. It is fun-
damental to take the plateaus into account when analyzing the landscape features or
when proposing a new algorithm. We used this information about plateaus to gather
all the local optima that belong to a plateau, so as to consider that they share the same
attraction basin. It was found that, on average, there are neighboring solutions of the
local optima or of the plateaus that do not belong to their attraction basins. Sin embargo,
at the same time, there are usually some solutions far from the local optima which still
belong to its attraction basin. This information totally differs from the concept of round-
ness. Sin embargo, the local optima are located almost centered within the attraction basins.
Además, not only the local optima but also an incredibly high percentage of the so-
lutions of the attraction basins fall into the frontier. So, we could say that the interior
of the attraction basins is almost empty. The attraction basins are neighbors of a large
number of the remaining attraction basins. En este sentido, the solutions far from the local
optima and inside their attraction basins present a larger number of neighboring attrac-
tion basins than those solutions nearer to the local optima. De hecho, each of the attraction
basins can be seen as a number of long rivers, with tributaries, that flow into the local
optimum (or local optimal plateau). The different rivers are interconnected with each
other or, al menos, very close to each other.
The understanding of the landscapes in combinatorial optimization has been one of
the main challenges when developing and improving algorithms. This work not only
breaks with an erroneous extended belief about the attraction basin shapes, pero también
provides valuable information for the design of new algorithms based on local search.
Por ejemplo, this work clearly helps in the development of Iterated Local Search algo-
rithms when looking for an effective way to escape from the local optima. De hecho, nosotros
4http://www.sc.ehu.es/ccwbayes/members/leticia/AnatomyOfAB/visualization/visualizeOneAB
.html
462
Volumen de cálculo evolutivo 27, Número 3
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Anatomy of the Attraction Basins
plan to add information about the objective function value of the local optima to our
analysis of the neighboring relations between the attraction basins. En este sentido, nosotros
hope that we will find regularities of the distances to the local optima where they have
more connectivities with other better local optima. Además, this article also provides
useful knowledge to improve those methods that estimate the number of local optima
or the sizes of the attraction basins.
Expresiones de gratitud
This work has been partially supported by the Research Groups 2013-2018 (IT-609-13)
programas (Basque Government) and TIN2016-78365R (Spanish Ministry of Economy,
Industry and Competitiveness). Jose A. Lozano is also supported by BERC 2014-2017
and Elkartek programs (Basque government) and Severo Ochoa Program SEV-2013-
0323 (Spanish Ministry of Economy and Competitiveness).
Referencias
Albrecht, A., carril, PAG., and Steinhofel, k. (2008). Combinatorial landscape analysis for k-SAT in-
posturas. In IEEE Congress on Evolutionary Computation, páginas. 2498–2504.
Albrecht, A., carril, PAG., and Steinhofel, k. (2010). Analysis of local search landscapes for k-SAT
instancias. Mathematics in Computer Science, 3(4):465–488.
Alyahya, K., and Rowe, j. mi. (2014). Phase transition and landscape properties of the number
partitioning problem. 14th European Conference on Evolutionary Computation in Combinatorial
Optimisation, páginas. 206–217.
Angel, MI., and Zissimopoulos, V. (2002). On the hardness of the quadratic assignment problem
with metaheuristics. Journal of Heuristics, 8(4):399–414.
Bouziri, h., Mellouli, K., and Talbi, E.-G. (2009). The k-coloring fitness landscape. Journal of Com-
binatorial Optimization, 21(3):306–329.
Burkard, R. MI., Karisch, S. MI., and Rendl, F. (1997). Qaplib—A quadratic assignment problem
library. Journal of Global Optimization, 10(4):391–403.
Caruana, r., and Mullin, METRO. (1999). Estimating the number of local minima in big, nasty search
spaces. In Proceedings of IJCAI-99 Workshop on Statistical Machine Learning for Large-Scale
Optimization.
Chicano, F., Daolio, F., Ochoa, GRAMO., Verel, S., Tomassini, METRO., and Alba, mi. (2012). Local optima net-
obras, landscape autocorrelation and heuristic search performance. In Proceedings of Paral-
lel Problem Solving from Nature, páginas. 337–347. Lecture Notes in Computer Science, volumen. 7492.
Saltador.
Csárdi, GRAMO., and Nepusz, t. (2006). The igraph software package for complex network research.
InterJournal, Complex Systems(1695):1–9.
Daolio, F., Verel, S., Ochoa, GRAMO., and Tomassini, METRO. (2010). Local optima networks of the quadratic
assignment problem. In IEEE Congress on Evolutionary Computation, páginas. 2145–3152.
Daolio, F., Verel, S., Ochoa, GRAMO., and Tomassini, METRO. (2014). Local optima networks of the permuta-
tion flow-shop problem. In Artificial Evolution, páginas. 41–52. Lecture Notes in Computer Science,
volumen. 8752.
Fonlupt, C., Robilliard, D., Preux, PAG., and Talbi, E.-G. (1999). Fitness landscapes and performance
of meta-heuristics. In Meta-Heuristics: Advances and Trends in Local Search Paradigms for Opti-
mization, páginas. 257–268.
Volumen de cálculo evolutivo 27, Número 3
463
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
Garey, METRO. r., Johnson, D. S., and Sethi, R. (1976). The complexity of flowshop and jobshop
programación. Mathematics of Operations Research, 1(2):117–129.
Hernando, l., Daolio, F., Veerapen, NORTE., and Ochoa, GRAMO. (2017). Local optima networks of the per-
mutation flowshop scheduling problem: Makespan vs. total flow time. In IEEE Congress on
Computación evolutiva, páginas. 1964–1971.
Hernando, l., Mendiburu, A., and Lozano, j. A. (2013a). An evaluation of methods for estimating
the number of local optima in combinatorial optimization problems. Evolutionary Computa-
ción, 21(4):625–658.
Hernando, l., Mendiburu, A., and Lozano, j. A. (2013b). Generating customized landscapes
in permutation-based combinatorial optimization problems. In International Conference on
Learning and Intelligent Optimization, páginas. 299–303.
Hernando, l., Mendiburu, A., and Lozano, j. A. (2016a). Estimating attraction basin sizes (páginas. 458–
467). cham: Saltador.
Hernando, l., Mendiburu, A., and Lozano, j. A. (2016b). A tunable generator of instances of
permutation-based combinatorial optimization problems. IEEE Transactions on Evolutionary
Cálculo, 20(2):165–179.
Hernando, l., Pascual, j. A., Mendiburu, A., and Lozano, j. A. (2011). A study on the complex-
ity of TSP instances under the 2-exchange neighbor system. In Foundations of Computational
Inteligencia, páginas. 15–21.
Hoos, h. h., and Stützle, t. (2004). Stochastic local search: Foundations and applications. San Fran-
cisco: Morgan Kaufmann.
Humeau, J., Liefooghe, A., Talbi, E.-G., and Verel, S. (2013). ParadisEO-MO: From fitness land-
scape analysis to efficient local search algorithms. Journal of Heuristics, 19(6):881–915.
Klemm, K., Qin, J., and Stadler, PAG. F. (2014). Geometry and coarse-grained representations of land-
scapes. Recent advances in the theory and application of fitness landscapes. Berlin Heidelberg:
Saltador.
Lourenço, h. r., Martín, oh. C., and Stützle, t. (2003). Iterated local search. Handbook of metaheuris-
tics (páginas. 320–353). Bostón: Saltador.
Lourenço, h. r., Martín, oh. C., and Stützle, t. (2010). Iterated local search: Framework and appli-
cations. Handbook of metaheuristics (páginas. 363–397). Bostón: Saltador.
Marmion, M.-E., Dhaenens, C., Jourdan, l., Liefooghe, A., and Verel, S. (2011a). Nils: A neutrality-
based iterated local search and its application to flowshop scheduling. In P. Merz and J.-K.
hao (Editores.), Evolutionary computation in combinatorial optimization: 11th European Conference
(páginas. 191–202) Torino, Italia: Springer Berlin Heidelberg.
Marmion, M.-E., Dhaenens, C., Jourdan, l., Liefooghe, A., and Verel, S. (2011b). On the neutrality
of flowshop scheduling fitness landscapes. In Learning and Intelligent OptimizatioN Confer-
ence, páginas. 238–252.
Mattfeld, D. C., and Bierwirth, C. (1999). A search space analysis of the job shop scheduling prob-
lem. Annals of Operations Research, 86:441–453.
Merz, PAG. (2004). Advanced fitness landscape analysis and the performance of memetic algorithms.
Computación evolutiva, 12(3):303–325.
Merz, PAG., and Freisleben, B. (2001). Memetic algorithms for the travelling salesman problem. Com-
plex Systems, 13(4):297–345.
Mishra, S., and Sikdar, k. (2004). On approximability of linear ordering and related NP-
optimization problems on graphs. Discrete Applied Mathematics, 136(2-3):249–269.
464
Volumen de cálculo evolutivo 27, Número 3
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
Anatomy of the Attraction Basins
Moser, I., Gheorghita, METRO., and Aleti, A. (2016). Identifying features of fitness landscapes and re-
lating them to problem difficulty. Computación evolutiva, 25(3):407–437.
Ochoa, GRAMO., and Veerapen, norte. (2018). Mapping the global structure of TSP fitness landscapes. Jour-
nal of Heuristics, 24(3):265–294.
Ochoa, GRAMO., Verel, S., Daolio, F., and Tomassini, METRO. (2011). Clustering of local optima in combina-
torial fitness landscapes. In C. Coello-Coello (Ed.), Learning and intelligent optimization, volumen.
6683, páginas. 454–457. Berlin Heidelberg: Saltador.
Ochoa, GRAMO., Verel, S., Daolio, F., and Tomassini, METRO. (2014). Recent advances in the theory and appli-
cation of fitness landscapes. En H. Richter and A. Engelbrecht (Editores.), Emergence, complejidad
and computation, volumen. 6, capítulo, Local optima networks: A new model of combinatorial fit-
ness landscapes, páginas. 233–262. Berlin Heidelber: Saltador.
Preux, PAG., and Talbi, mi. GRAMO. (1999). Towards hybrid evolutionary algorithms. International Transac-
tions in Operational Research, 6(6):557–570.
Prügel-Bennett, A., and Tayarani-Najaran, METRO. h. (2012). Maximum satisfiability: Anatomy of the
fitness landscape for a hard combinatorial optimization problem. IEEE Transactions on Evo-
lutionary Computation, 16(3):319–338.
Reeves, C., and Aupetit-Bélaidouni, METRO. (2004). Estimating the number of solutions for SAT prob-
lemas. Parallel Problem Solving from Nature, páginas. 101–110. Lecture Notes in Computer Science,
volumen. 3242.
Reeves, C. R. (1999). Landscapes, operators and heuristic search. Annals of Operations Research,
86:473–490.
Reidys, C. METRO., and Stadler, PAG. F. (2002). Combinatorial landscapes. SIAM Review, 44(1):3–54.
Sahni, S., and Gonzalez, t. (1976). P-complete approximation problems. Revista de la ACM,
23(3):555–565.
Sammon, j. W.. (1969). A nonlinear mapping for data structure analysis. IEEE Transactions on Com-
puters, C-18(5):401–409.
Schiavinotto, T., and Stützle, t. (2005). The Linear Ordering Problem: Instances, search space anal-
ysis and algorithms. Journal of Mathematical Modelling and Algorithms, 3(4):367–402.
Stützle, t. (2006). Iterated local search for the quadratic assignment problem. European Journal of
Operational Research, 174(3):1519–1539.
suton, A. METRO., Howe, A. MI., and Whitley, l. D. (2010). Directed plateau search for max-k-sat. En
Proceedings of SoCS, páginas. 90–97.
Taillard, mi. (1990). Some efficient heuristic methods for the flow shop sequencing problem. Euro-
pean Journal of Operational Research, 47(1):65–74.
Taillard, mi. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Re-
buscar, 64(2):278–285.
Tayarani-Najaran, METRO. h., and Prügel-Bennett, A. (2014). On the landscape of combinatorial opti-
mization problems. IEEE Transactions on Evolutionary Computation, 18(3):420–434.
Tayarani-Najaran, METRO. h., and Prügel-Bennett, A. (2015a). Anatomy of the fitness landscape for
dense graph-colouring problem. Swarm and Evolutionary Computation, 22:47–65.
Tayarani-Najaran, METRO. h., and Prügel-Bennett, A. (2015b). Quadratic assignment problem: A land-
scape analysis. Evolutionary Intelligence, 8(4):165–184.
Tomassini, METRO., Vérel, S., and Ochoa, GRAMO. (2008). Complex-network analysis of combinatorial spaces:
The NK landscape case. Physical Review E, 78(6):66–114.
Volumen de cálculo evolutivo 27, Número 3
465
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
.
/
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
l. Hernando, A. Mendiburu, y j. A. Lozano
Venables, W.. NORTE., and Ripley, B. D. (2002). Modern applied statistics with S. 4ª edición. Nueva York:
Saltador.
Verel, S., Daolio, F., Ochoa, GRAMO., and Tomassini, METRO. (2011). Local optima networks with escape
bordes. In International Conference on Artificial Evolution, páginas. 10–23.
Verel, S., Ochoa, GRAMO., and Tomassini, METRO. (2008). The connectivity of nk landscapes’ basins: A net-
work analysis. In Artificial Life XI: Proceedings of the 11th International Conference on the Simu-
lation and Synthesis of Living Systems, páginas. 648–655.
Verel, S., Ochoa, GRAMO., and Tomassini, METRO. (2011). Local optima networks of NK landscapes with
neutralidad. IEEE Transactions on Evolutionary Computation, 15(6):783–797.
watson, J.-P. (2010). An introduction to fitness landscape analysis and cost models for local search.
Handbook of metaheuristics (páginas. 599–623). volumen. 146. Berlina: Saltador.
yo
D
oh
w
norte
oh
a
d
mi
d
F
r
oh
metro
h
t
t
pag
:
/
/
d
i
r
mi
C
t
.
metro
i
t
.
/
/
mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d
yo
F
/
/
/
/
2
7
3
4
3
5
1
8
5
8
6
1
2
mi
v
C
oh
_
a
_
0
0
2
2
7
pag
d
/
.
F
b
y
gramo
tu
mi
s
t
t
oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3
466
Volumen de cálculo evolutivo 27, Número 3
