
## 3 Fitness Landscapes 3.1 Introduction

First we recall a few fundamental concepts about fitness landscapes (see [18,19]
for a more detailed treatment). A landscape is a triplet (S, f, N**) where** S is a set of potential solutions **(also called search space),** N : S → 2 S, a neighborhood structure, is a function that assigns to every s ∈ S **a set of neighbors**
N(s), and f : S 7→ **IR is a fitness function that can be pictured as the "height"**
of the corresponding potential solutions. Often a topological concept of distance d **can be associated to a neighborhood**
N. A distance d : S × S 7→ IR + **is a function that associates with any two**
configurations in S **a nonnegative real number that verifies well-known properties.**
For example, for a binary coded GA, the fitness landscape S **is constituted by**
the boolean hypercube B = {0, 1}
lconsisting of the 2l**solutions for strings**
of length l **and the associated fitness values. The neighborhood of a solution,**
for the one-bit random mutation operator, is the set of points y ∈ B **that are**
reachable from x **by flipping one bit. A natural definition of distance for this**
landscape is the well-known Hamming **distance.**
Based on the neighborhood notion, one can define local optima as being configurations x for which (in the case of maximization): ∀y ∈ N(x), f(y) ≤ f(x)
Global optima are defined as being the absolute maxima (or minima) in the whole of S**. Other features of a landscape such as basins, barriers, or neutrality**
can be defined likewise[18]. Neutrality is a particularly important notion in our study, and will be dealt with further. A notion that will be used in the rest of this work is that of a walk **on a** landscape. A walk Γ from s to s
′
is a sequence Γ = (s0, s1, . . . , sm**) of solutions**
belonging to S **where** s0 = s, sm = s
′
and ∀i ∈ [1, m], si**is a neighbor of** si−1.

The walk can be random, for instance solutions can be chosen with uniform probability from the neighborhood, as in random sampling, or according to other weighted non-uniform distributions, as in Monte Carlo sampling, for example. It can also be obtained through the repeated application of a "move" operator, either stochastic or deterministic, defined on the landscape, such as a form of mutation or a deterministic hill-climbing strategy.