Bridging Elementary Landscapes and a Geometric Theory of Evolutionary Algorithms: First Steps

Abstract

Based on a geometric theory of evolutionary algorithms, it was shown that all evolutionary algorithms equipped with a geometric crossover and no mutation operator do the same kind of convex search across representations, and that they are well-matched with generalised forms of concave fitness landscapes for which they provably find the optimum in polynomial time [13]. Analysing the landscape structure is essential to understand the relationship between problems and evolutionary algorithms. This paper continues such investigations by considering the following challenge: develop an analytical method to recognise that the fitness landscape for a given problem provably belongs to a class of concave fitness landscapes. Elementary landscapes theory provides analytic algebraic means to study the landscape structure [15]. This work begins linking both theories to better understand how such method could be devised using elementary landscapes. Examples on the well known One Max, Leading Ones, Not-All-Equal Satisfiability and Weight Partition problems illustrate the fundamental concepts supporting this approach.

1 Introduction

Context and Challenge. Since its early days, evolutionary computing (EC) grew rapidly and diversely, but lacking a fundamental and coherent theory [9]. Despite recent progress, still much work needs to be done regarding unification [2, 14]. Fitness landscapes have been helpful in that task since they define the search space structure by the fitness function of the problem and the search operators (i.e. the neighbourhood structure), thus linking three key elements of evolutionary algorithms (EAs): problems, algorithms and performance [14]. Particularly, EAs with geometric crossover but no mutation were proved to do an abstract form of convex search [11]. Moreover, this class of EAs is well-matched with globally concave (or convex, if minimising) landscapes, for which runtime exponentially better than pure random search can provably be guaranteed [13].

This paper focuses on fitness landscapes, and extends [13], aiming at developing an analytical method to recognise if a given fitness landscape of some combinatorial problem provably matches a concave (or convex) class of landscapes in general metric spaces. This method would provide insight to determine for which classes of problems and EAs good performance can be guaranteed. We propose elementary landscapes theory [15] as a fruitful choice to develop such method, because the following reasons suggest that certain classes of elementary landscapes relate to classes of (globally) concave landscapes and that elementary landscapes theory is at our disposal to analyse recombination spaces:

• Certain elementary landscapes have all local optima clustered in a single region of the search space. For instance, the landscape of the Linear Assignment problem. Moreover, for Boolean spaces with Hamming distance, it was shown that these elementary landscapes have a unique local optimum, thus coinciding with unimodal landscapes [7, 15, 18].

• Many combinatorial problems (such as Graph Coloring, Symmetric Travelling Salesman and Graph Bipartitioning) have elementary landscapes with local optima grouped only in a few clusters in the search space, suggesting an approximately globally concave (or convex) structure [8, 18].

• Certain recombination spaces (e.g. induced by uniform recombination) are homomorphic to mutation spaces, meaning that their associated landscapes can be compared with each other and that elementary landscapes theory extends to recombination spaces [5, 18].

Scope and Contributions. This paper begins linking elementary landscapes and the geometric framework to establish firm grounds to tackle the previous challenge. The major contributions of this work are:

• 1. Show that from both theories it is possible to restate recombination in terms of the other, that is enabling dual geometric and algebraic views, to justify that is not futile to propose elementary landscapes as an analytic tool.

• 2. Examples on four well-known combinatorial problems to clarify the connection between the structure of elementary landscapes and the globally concave classes of the geometric framework.

Although these contributions may appear only loosely connected, they complement each other as we will see in the following sections, and their connection will be further developed in future work.

Organisation. Section 2 introduces basic concepts about fitness landscapes. Sections 3 and 4 present key ideas of the geometric framework and elementary landscapes theory, respectively. Section 5 presents the main result of this study. Section 6 illustrates with examples the utility of elementary landscapes to analyse concave landscapes. Section 7 summarises this work and suggests future research.

2 Fitness Landscapes

In combinatorial problems, it is natural to formalise the search space with configuration set X in terms of a move operator $m: X^n \rightarrow X^k$ mapping a vector of n parents into a vector of k offspring [16]. Mutation, acting on a single parent, is naturally connected with a neighbourhood relation that can be described as a connected graph, which can be undirected or directed depending on whether the neighbourhood is symmetric or not. Recombination, acting on pairs of individuals, is non-trivial with different possible formalisations (e.g. using hypergraphs [5]). Besides neighbourhoods, graphs can also be described naturally using graphic distances (e.g. length of shortest paths), which directly relate to metric spaces and more generally fitness landscapes [16].

Definition 1

A metric space $\mathscr {M}$ is defined as the pair (X, d), where X is a set of configurations and $d : X \times X \rightarrow \mathbb {R}$ is a metric; such that $\forall x,y,z \in X$: (I) non-negativity: $d(x, y) \ge 0$; (II) identity: $d(x, y) = 0 \iff x = y$; (III) symmetry: $d(x, y) = d(y, x)$ and (IV) triangle inequality: $d(x, y) \le d(x, z) + d(z, y)$.

Definition 2

A fitness landscape $\mathscr {F}$ can be defined as the pair $(\mathscr {M}, f)$, where $\mathscr {M}$ is a metric space, and $f: X \rightarrow \mathbb {R}$ is a real-valued fitness function that indicates the fitness of each configuration in X, the set of configurations in $\mathscr {M}$.

3 Geometric Framework

Moraglio proposed a general theory of EAs, independent of the problem and representation of solutions, solely based on an axiomatic definition of distance across metric spaces [10]. This allows to formalise mutation and crossover operators in terms of metric balls and geodesic intervals, respectively [20].

Definition 3

Let (X, d) be a metric space with configuration set X and metric d. Then, a closed ball centred at point $x \in X$ with radius $r \in \mathbb {R}_{\ge 0}$ is defined as and a geodesic interval or metric segment as , where $x, y \in X$ are called the extremes of the segment and d(x, y) its length.

Normally, implementations of heuristic search methods define probabilistic search operators, thus a probability distribution over the configuration set. In other words, move operators that return a subset of the possible neighbours. The geometric framework takes this into account when defining geometric operators [10].

Definition 4

Let (X, d) be a metric space and Im$[\star (\cdot )]$ denote the set of offspring produced with non-zero probability by an operator $\star$. Then, a unary operator $\mu _{\varepsilon } : X \rightarrow X$ is a geometric $\varepsilon$-mutation if $\forall x \in X \big (\text {Im}[\mu _{\varepsilon }(x)] \subseteq B_{d}[x; \varepsilon ]\big )$, where $\varepsilon \in \mathbb {R}_{\ge 0}$ is the smallest non-negative real number for which this condition holds. When $\varepsilon$ is not specified, $\varepsilon = 1$ is assumed. And, a binary operator $\chi : X \times X \rightarrow X$ is a geometric crossover if $\forall x,y \in X \big (\text {Im}[\chi (x, y)] \subseteq [x; y]_{d}\big )$.

Apart from its benefits regarding unification and formal design of EAs across representations, a geometric definition provides insight on the landscape properties that cause EAs to perform possibly much better than pure random search [10]. Abstract convexity in general metric spaces is one such property [20], which describes the structure induced by geometric crossovers and admits well-behaved generalisations from traditional (Euclidean) concave functions [10, 11].

Definition 5

Let a metric space , with configuration set X and metric d, and a fitness function f define a fitness landscape . Then, $\forall x,y,z \in X$, $\mathscr {F}$ is quasi-concave if $z \in \left[ x;y\right] _{d}$ and ; and average-concave if $z \sim \mathcal {U}\big (\left[ x;y\right] _{d}\big )$ and . Where $\mathcal {U}$ denotes the uniform probability distribution and $\mathbb {E}$ the expectation.

4 Elementary Landscapes Theory

Based on Grover’s work [6], Stadler developed an algebraic theory of fitness landscapes known as elementary landscapes (ELs) [15]. Here, regular undirected¹ graphs induced by mutation neighbourhoods are formalised using the graph or mutation Laplacian matrix $\mathbf {L}_{\mu }$ defined by the graph’s diagonal $\mathbf {D}$ and adjacency $\mathbf {A}$ matrices (Fig. 1):

(1)

Fig. 1.

Star graph $S_{4}$ (left) and its graph Laplacian matrix (right).

To formalise recombination neighbourhoods in terms of hypergraphs [5], a new concept called ‘P-structure’ given by $(X, \mathcal {R})$ was introduced [18], where X is a finite set with power set $\mathcal {P}(X)$ and $\mathcal {R} : X \times X \rightarrow \mathcal {P}(X)$ maps a pair of parents into the set of possible offspring. By a hypergraph we mean a graph with vertex set X and hyperedge set . Furthermore, the following subclass of P-structures is defined to capture some desirable properties of recombination operators.

Definition 6

A P-structure $(X, \mathcal {R})$ is a recombination structure if $\forall x,y,z \in X$: (I) fix-point: $\mathcal {R}(x, x) = \{ x \}$; (II) symmetry: $\mathcal {R}(x, y) = \mathcal {R}(y, x)$; (III) null-recombination: $\{x, y\} \subseteq \mathcal {R}(x, y)$; and (IV) size-monotonicity: if $z \in \mathcal {R}(x, y)$, then .

Laplacians $\mathbf {L}_{\mathcal {R}}$ for recombination P-structures can also be defined based on the identity matrix $\mathbf {I}$ and a generalised adjacency matrix $\mathbf {S}$ for hypergraphs [18]:

(2)

where the square matrix $\mathbf {S}$ has entries , and the non-square binary incidence matrix $\mathbf {H}$ with entries $\mathbf {H}_{z,(x,y)}$ tells whether z is offspring of x and y under $\mathcal {R}$.

To better grasp the generalised adjacency matrix $\mathbf {S}$ in (2), one may consider its associated stochastic matrix $\mathbf {T}_{z x}$ describing the transition probabilities of a recombination-based random walk on a graph, where a father x is mated with a randomly chosen mother y to produce an offspring z that will be the father in the next recombination [18]. It is defined as , where $p_{y}$ is the probability of choosing y from X, and $t^{z}_{xy}$ is the probability of z given x and y. $\mathbf {T}_{z x}$, $\mathbf {S}$ and $\mathbf {L}_{\mathcal {R}}$ relate as: . Although this assumes a uniform population and that all offspring occur with equal probability, it is possible to define weights for $\mathbf {S}$ to formalise more realistic population recombination-based search algorithms [17].

In the light of Grover’s work and the characterisations above, Stadler defines a non-flat fitness landscape as elementary if its zero-averaged fitness function (as a column vector) , with finite discrete domain $X = \{ x_{1}, x_{2}, \ldots , x_{n}\}$ representing the vertex set of an underlying connected graph, is an eigenfunction of a (generalised) Laplacian matrix $\mathbf {L}$ of the graph: $\mathbf {L} \tilde{f} = \lambda \tilde{f}$; where $\lambda > 0$ is the eigenvalue and the constant is the average fitness of a configuration in X [8, 15]. If a landscape f is not elementary, it can always be decomposed into a linear combination of ELs $f_{k}$ called its Fourier expansion: $f = a_{0} + \sum _{k > 0}^{\left| X\right| - 1} a_{k} f_{k}$, where scalars $a_{k}$ are the Fourier coefficients, $a_{0}$ is the average fitness and the eigenfunctions $f_{k}$ have corresponding eigenvalues $\lambda _{k}$ (in increasing order and counting multiplicities, ) such that $\mathbf {L} f_{k} = \lambda _{k} f_{k}$.

ELs have interesting geometric properties. One of them, proved by Grover [6], is that all local maxima (minima) have fitness higher (lower) than or equal to the average fitness: . This property is closely related to the idea of monotonic sequences of local optima (i.e. sequences of ever non-decreasing or non-increasing fitness) used, for instance, in the local optima networks model [19] to formalise the funnel structure of landscapes.

Another important aspect of ELs is their global structure. There are two major classes depending on the index p (ignoring multiplicities) of the eigenvalue: Fujiyama or single-peaked [7], and non-Fujiyama. Fujiyama are those ELs with the smallest non-zero eigenvalue ($\lambda _{1}$), that is $\mathbf {L} \tilde{f} = \lambda _{p = 1} \tilde{f}$; characterised for having all local optima clustered in a single region of the space [18]. In particular, for Boolean spaces with Hamming distance they have a unique global optimum [15]. Non-Fujiyama are those ELs for $p > 1$ with local optima clustered in more than one region; indeed, many combinatorial problems fall here with $p = 2$ (e.g. Max Cut) [8]. More formally, by clusters we mean discrete nodal domains [1] (Fig. 2). These are the maximally connected subgraphs induced by the vertex subsets and , denoting the weak positive and negative nodal sets respectively, for a given graph with vertex set V and eigenfunction f (i.e. the fitness function) on V. Similarly, strong nodal sets are defined using a strict inequality instead. Note that, for a zero-averaged function, $V_{+}$ and $V_{-}$ induce subgraphs separating precisely above and below average configurations. Interestingly, the number of discrete nodal domains can be upper-bounded a priori, provided that we know p, using Proposition 1, generally, and the more sharp Proposition 2 specifically for Boolean spaces; which were proved in [1, 4].

Fig. 2.

An eigenfunction defined on the star graph $S_{4}$ (right), with eigenvalue $\lambda _{1} = 1$ of the graph Laplacian, and its induced discrete nodal domains (left): two weak and four strong. Positive nodes in ‘black’, negative nodes in ‘white’ and zero nodes in ‘grey’.

Proposition 1

Given a generalised Laplacian of a connected graph, any eigenfunction $f_{k}$ corresponding to the k-th eigenvalue $\lambda _{k}$ with multiplicity r has at most k weak and $k + r - 1$ strong nodal domains.

Proposition 2

For an eigenfunction f with eigenvalue 2p, where p is its index ignoring multiplicities and N the number of vertices of the Boolean hypercube, the number W(f) of weak nodal domains is upper-bounded as:

(3)

5 Main Results

To analyse the landscapes induced by geometric crossovers (Definition 4) using ELs theory, it is necessary to prove that geometric crossovers belong to the class of recombination P-structures (Definition 6). Connecting both theories (Sects. 3 and 4) can help to develop dual geometric and algebraic views with which tackle the challenge of identifying generalised concave landscape classes using ELs theory, and give insight on explaining the good performance behind convex search (Sect. 1). Next, we prove that all geometric crossovers, regardless of the metric, are recombination P-structures.

Lemma 1

Let (X, d) be any metric space. Then, $\forall x,y \in X$ and any metric d, $(X, [x,y]_{d})$ is a recombination P-structure.

Proof

We need to prove that metric segments fulfil the axioms of recombination P-structures.

• (I) Fix-point. The only possible z in $\left[ x; x\right] _{d} = \{ z \in X \mid d(x, z) + d(z, x) = d(x, x) \}$ is exactly x. Therefore, $\left[ x; x\right] _{d} = \{x\}$.

• (II) Symmetry. $\left[ x; y\right] _{d} = \left[ y; x\right] _{d}$ follows immediately from the symmetry axiom of metric segments.

• (III) Null-recombination. $\{x, y\} \subseteq \left[ x; y\right] _{d}$ holds by definition, since the extremes x and y of the segment are always included in the segment.

• (IV) Size-monotonicity. To prove that if $z \in \left[ x; y\right] _{d}$, then , we can recall that all metric segments fulfil monotonicity [20]: $\forall x,y,z \in X$ if $z \in \left[ x; y\right] _{d}$ then $\left[ x; z\right] _{d} \subseteq \left[ x; y\right] _{d}$. Therefore, it follows .    $\square$

Unfortunately, to prove equivalence in the other direction it is necessary to restrict recombination P-structures to those that precisely produce offspring $z \in \mathcal {R}(x, y)$ lying in the geodesic interval between parents x and y, since in general not all recombination P-structures fulfil this property [3].

Example 1

Consider $\mathcal {R}_{\ell }$ returning offspring lying on longest paths between parents. This can generate offspring beyond the geodesic interval between parents (i.e. in the extension ray [20]), e.g. $[000; 011]_{d_{\text {H}}} \not \ni 111 \in \mathcal {R}_{\ell }(000, 011)$ where $d_{\text {H}}$ is the Hamming distance. Indeed, extended line recombination, which generates offspring in the extension ray, is not a geometric crossover for any metric [12].

Definition 7

A recombination P-structure $(X, \mathcal {R})$, for a connected graph G with vertex set X, that $\forall x, y \in X$ fulfils the axiom $\mathcal {R}(x, y) \subseteq I(x,y)$, where I(x, y) is the set of all shortest paths between x and y in G, is a geometric recombination P-structure denoted by $\mathcal {R}_{\text {g}}$.

Theorem 1

Let (X, d) be any graphic metric space. Then, all geometric recombination P-structures $\mathcal {R}_{\text {g}}$ are equivalent to all geometric crossovers $\chi$ defined on (X, d). That is, $\forall x, y \in X \big ( \mathcal {R}_{\text {g}}(x, y) = \chi (x, y) \big )$.

Proof

The proof follows immediately from Lemma 1, and Definitions 4 and 7 of geometric crossovers and geometric recombination P-structures respectively.    $\square$

Interestingly, all recombination P-structures fulfil the inbreeding properties (Theorem 2), that is breeding between close relatives, common to all geometric crossovers and independent of the metric used, which were proposed as a test for non-geometricity of crossovers: if any of them fails, then a crossover is not geometric [12].

Theorem 2

Let $(X, \mathcal {R})$ be any recombination P-structure. Then, $\mathcal {R}$ satisfies all inbreeding properties of geometric operators: purity, convergence and partition.

Proof

• Purity: The recombination of one parent with itself can only produce the parent itself. Follows immediately from the fix-point axiom of recombination P-structures: $\forall x \in X$, $\mathcal {R}(x, x) = \{x\}$.

• Convergence: The recombination of one parent with one offspring cannot produce the other parent of that offspring, unless the offspring and the second parent coincide. We want to prove that $\forall x,y,z,s \in X$ if $z \in \mathcal {R}(x, y)$ and $s \in \mathcal {R}(x, z)$, then $s = y \implies z = y$. Let $z \in \mathcal {R}(x, y)$ such that $z \ne y$, and $s \in \mathcal {R}(x, z)$. We want to show that actually $s \ne y$ too. From the size-monotonicity axiom of recombination structures we know:

  $$\begin{aligned} \left| \mathcal {R}(x, z)\right| < \left| \mathcal {R}(x, y)\right| , \end{aligned}$$

  (4)

  since $y \ne z \in \mathcal {R}(x, z)$. Besides, either $s = z$ or $s \ne z$. If $s = z$, then we know automatically that $s \ne y$, since $s = z \ne y$. If on the other hand $s \ne z$, then:

  $$\begin{aligned} \left| \mathcal {R}(x, s)\right| < \left| \mathcal {R}(x, z)\right| . \end{aligned}$$

  (5)

  If s was allowed to be y, then $\left| \mathcal {R}(x, s)\right| = \left| \mathcal {R}(x, y)\right|$, however by (5):

  $$\begin{aligned} \left| \mathcal {R}(x, s)\right| = \left| \mathcal {R}(x, y)\right| < \left| \mathcal {R}(x, z)\right| \end{aligned}$$

  (6)

  thus contradicting (4). Therefore, $s \ne y$ for the $s \ne z$ case. Consequently, the only possibility left for $s = y$ is that $z = y$.

• Partition: If z is a child of x and y, then the recombination of x and z, and the recombination of y and z, cannot produce a common grandchild s other than z. Another way to phrase it is that both recombinations must produce two different grandchildren when they are not z. That is, we want to prove that $\forall x,y,z,s_{1},s_{2} \in X$ if $z \in \mathcal {R}(x, y)$, $s_{1} \in \mathcal {R}(x, z)$ and $s_{2} \in \mathcal {R}(z, y)$, then $s_{1} \ne s_{2}$. Without loss of generality, let $z \in \mathcal {R}(x, y)$ such that $z \ne y$, and assume the opposite: $s_{1} = s_{2}$. Then, we know by the convergence property that $s_{1} \ne y$. Analogously, exchanging the roles of the parents x and y using the symmetry axiom of recombination structures, we know $s_{2} \ne x$. Observe, however, that there are no restrictions in having $s_{1} = x$ and $s_{2} = y$. But, since we assumed $s_{1} = s_{2}$, we find the following contradictions: $x = s_{1} = s_{2} \ne x$, and $y = s_{2} = s_{1} \ne y$. Therefore, $s_{1} \ne s_{2}$.    $\square$

Since all recombination P-structures fulfil the inbreeding properties but only geometric recombination P-structures are equivalent to geometric crossovers (Theorem 1), from Theorem 2 we conclude the following.

Corollary 1

The inbreeding properties of geometric crossovers are necessary but not sufficient conditions to determine if a crossover is geometric.

This resolves the question of whether the inbreeding properties are sufficient or not for geometricity, which was left open in [12]. In the light of this result, it would be worth identifying additional inbreeding properties that when considered jointly would be sufficient to guarantee that a crossover is geometric.

6 Discrete Nodal Domains for Uniform Recombination in Boolean Spaces with Hamming Distance: Examples

Section 5 justified that proposing ELs theory to analyse the abstract concave classes of the geometric framework is not futile by showing that geometric crossovers are a specific case of recombination P-structures, and that certain recombination P-structures coincide with geometric crossovers; thus motivating a dual interpretation on landscapes induced by recombination. This section clarifies, with illustrative examples, how discrete nodal domains (Sect. 4) help analyse the structure of landscapes induced by uniform recombination in Boolean spaces with Hamming distance in particular, and how they link to global concavity. The examples considered are on two artificial problems, One Max and Leading Ones, and two NP-complete problems [6]:

• Not-All-Equal Satisfiability (NAES). An instance is a set of clauses and its fitness is the number of satisfied clauses. A clause consists of three literals (i.e. a binary variable or its complement) not containing simultaneously a binary variable and its complement, and it is satisfied if there are at least two distinct literals such that one is 0 and the other is 1.

• Weight Partition (WP). An instance is a vector of n weights $w_{i}$ corresponding to objects $o_{i}$, for . The problem consists in finding an assignment of weights such that $f(w_{1}, \ldots , w_{n}) = \left( \sum _{i = 1}^{n} w_{i}s_{i}\right) ^{2}$ is minimised.

Figure 3, obtained using Mathematica², summarises key aspects of the problems’ landscape structure. Although the examples considered are for the three-dimensional Boolean hypercube embedded in the hypergraph induced by uniform recombination [18], we have observed equivalent results in higher dimensions.

Next, we see how the global landscape structure could be inferred analytically. For ELs this is possible by knowing the corresponding eigenvalues, since from their indexes we can tell whether they are Fujiyama or non-Fujiyama and also upper-bound the number weak nodal domains using Proposition 2 (Sect. 4). Then, we will explain why Leading Ones poses certain problems for this analytical approach.

Fig. 3.

Strongly positive (‘black dots’) and negative (‘white dots’) discrete nodal domains for the (a) Not-All-Equal satisfiability (NAES), (b) Weight Partitioning (WP), (c) One Max and (d) Leading Ones problems on the three-dimensional hypercube. $W_{+}$, $S_{+}$, $W_{-}$ and $S_{-}$ denote the number of weakly positive, strongly positive, weakly negative and strongly negative domains respectively; and p denotes the order of the eigenvalue $(\lambda _{p})$ for each of the eigenfunctions $f_{\text {NAES}}$, $f_{\text {WP}}$, $f_{\text {OneMax}}$ and $f_{\text {LeadingOnes}}$.

Eigenvalues of Elementary Landscapes. To find them we need to know the uniform recombination Laplacian $\mathbf {L}_{\mathcal {R}}$ for the three-dimensional hypercube (see Lemma C7 [18]): . We observe that this Laplacian has eigenvalues $\lbrace 0,{\,} 8,{\,} 8,{\,} 8,{\,} 12,{\,} 12,{\,} 12,{\,} 14\rbrace$ (in increasing order and starting at index 0); and that One Max is elementary for $\lambda _{1} = 8$, and NAES and WP for $\lambda _{2} = 12$: $\mathbf {L}_{\mathcal {R}} \tilde{f}_{\text {OneMax}} = 8 * \tilde{f}_{\text {OneMax}}$, $\mathbf {L}_{\mathcal {R}} \tilde{f}_{\text {NAES}} = 12 * \tilde{f}_{\text {NAES}}$ and $\mathbf {L}_{\mathcal {R}} \tilde{f}_{\text {WP}} = 12 * \tilde{f}_{\text {WP}}$.

One Max, NAES and WP. From the eigenvalues we know that One Max is a Fujiyama EL ($p = 1$), that is with a unique global optimum and single-peaked. This agrees with the fact that is a linear pseudo-Boolean function whose Fourier expansion using Walsh functions has only non-zero terms in the 0-th and 1-st orders thus elementary for $p = 1$. Whereas NAES and WP are non-Fujiyama ELs of order $p = 2$. These results are a consequence of Corollaries 2 and 3 in [18], proving that eigenfunctions of the mutation Laplacian (1) are also eigenfunctions of the uniform recombination Laplacian (2). Besides, one notes that the eigenvalue $(\lambda _{2} = 12)$ for NAES and WP does not coincide with the eigenvalue $(\lambda _{2} = 4)$ obtained for the mutation Laplacian [8]. Nevertheless, that is expected: two spaces may have identical eigenfunctions but different eigenvalues, possibly affecting the correlation between fitness values (i.e. ruggedness) of the landscape [18]. Thus, two landscapes may have identical number of nodal domains (i.e. same global structure) and different ruggedness.

Number of Weak Nodal Domains. Proposition 2 provides upper-bounds for the number of weak nodal domains; for One Max, NAES and WP we have: , and . This means that One Max has two weak nodal domains corresponding to two major clusters of local optima, separated by the hyperplane described by the average fitness. NAES and WP have at most four weak nodal domains and thus we cannot expect more than four clusters. Particularly, for $p = 1$ and $p = 2$, the upper-bounds remain constant regardless of the dimension (Table 4.1 in [1]).

Leading Ones. We observed in Mathematica that Leading Ones has the same number of discrete nodal domains as One Max by computing them. From Fig. (3d) one may think that Leading Ones is an EL for $p = 1$; however, it is not elementary neither for recombination nor mutation neighbourhoods, but a sum of n elementary landscapes. The reason is that is a k-bounded pseudo-Boolean function that is a sum of Walsh functions where the bitwise non-linearity is at most k bits. For Leading Ones $k = n$, thus the highest order is $p = n$ (i.e. the bit string length). This means that we cannot use Propositions 1 and 2 to know a priori the number of discrete nodal domains, since in general they do not hold when the landscape is a sum of ELs. Finding those cases where they hold is an open problem [1].

Concluding, discrete nodal domains are a promising analytic tool with which tackle the challenge of identifying landscape classes, because they capture key information of the landscape structure and can be related to ELs via eigenvalues and eigenfunctions. Then, what the abstract concave classes would correspond to? Previous observations suggest Fujiyama ELs ($p = 1$), since they overlap with single-peaked landscapes. For instance, One Max can be shown to be average-concave [13] and we now know that One Max is Fujiyama. Further research will confirm whether this intuition is correct.

7 Conclusions

The geometric framework has been successful in finding proper subclasses of EAs and fitness landscapes with provably polynomial runtime guarantees, however missing analytical means for landscape structure analysis. Besides, ELs theory provides a fine-grained analysis of the landscape structure in terms of its spectrum (i.e. eigenvalues and eigenfunctions) and discrete nodal domains, but lacking EAs dynamics modelling and runtime results. The ultimate goal of this research is precisely unifying these two frameworks, aiming at developing complementary geometric and algebraic views on fitness landscape analysis, to better understand when and why EAs perform well.

This paper took the first steps towards such goal by putting together for the first time both frameworks and highlighting their key ideas. First, proving that all geometric crossovers can be conceived as recombination P-structures, and that there exists a specific subclass of these that match geometric crossovers (Sect. 5). Then, illustrating and clarifying with examples how discrete nodal domains could help to identify concave landscape classes for problems that are elementary, by analysing their spectrum (Sect. 6). The next important steps would be to formalise the concave classes in terms of discrete nodal domains and convex search in ELs theory. Also, it would be worth researching whether landscape funnels can be formalised in terms of discrete nodal domains.