# Local Search Heuristics: Fitness Cloud Versus Fitness Landscape Collard Philippe And Verel Sebastien ´ And Clergue Manuel 1

arXiv:0709.4010v1 [cs.AI] 25 Sep 2007 Abstract. This paper introduces the concept of *fitness cloud* as an alternative way to visualize and analyze search spaces than given by the geographic notion of fitness landscape. It is argued that the fitness cloud concept overcomes several deficiencies of the landscape representation. Our analysis is based on the correlation between fitness of solutions and fitnesses of nearest solutions according to some neighboring. We focus on the behavior of local search heuristics, such as hill climber, on the well-known NK fitness landscape. In both cases the fitness vs. fitness correlation is shown to be related to the epistatic parameter K.

## Introduction

The fitness landscape has first been introduced in 1932 by the biologist Wright ([4]) as a metaphor for the visualization of evolution of an optimization process. Usually, on the basis of a n-dimensional search space, an extra dimension is added which represents the fitness of each solution. So, this (n **+ 1)**−dimension space can be interpreted like a landscape with valleys and peaks. This landscape is more or less rough according to the complexity of the problem. However, this view of the search space presents some limitations. It is hard to visualize a search space of dimension higher than 2; the concept of neighboring, induced by a distance, an operator or an heuristic, is not easily perceptible; it is difficult to locate, to count or to characterize the set of local optima, as soon as the landscape becomes rough; barriers of fitness between basins of attraction are not always highlighted and dynamics of search heuristics cannot be directly tracked on the landscape.

## 1 The Fitness Cloud

This section presents a complementary "point of view" to the geographical metaphor of landscape. The search space is noted S and the fitness function f is defined on S.

## 1.1 Bordering Fitness

Two solutions are regarded as neighbor if there is a transformation related to search heuristics or such an operator, which allows "to pass" from one solution to the other one. Let s be a solution in the search space, its *bordering fitness* ˜f(s), is defined as the fitness of a particular neighbor of s. The choice of one neighbor depends on the search heuristic only and we assume this choice to be unique.

1 University of Nice-Sophia Antipolis, I3S Laboratory, France, email:pc@unice.fr verel@i3s.unice.fr clerguem@i3s.unice.fr

## 1.2 Definition

For each solution in the solution space, a single point is plotted; the abscissa is its fitness and the ordinate is its bordering fitness. Thus, we obtain a scatterplot which informs about the correlation between fitness and bordering fitness (the so-called *Fitness Cloud* or FC). Formally, F C = {(f(x),
˜f(x)) | x ∈ S}. A *set of neutrality* of fitness ϕ, so-called Sϕ, is the set of solutions that have the fitness ϕ. Such a set corresponds to one abscissa in the fitness/fitness plan; according to this abscissa, a vertical slice from the cloud represents all the fitness values one can reach from this set of neutrality. From a given bordering fitness value ˜f, an horizontal slice represents all the fitness values from which one can reach ˜f.

To visualize the shape of the fitness cloud, we plot the three subsets of F C: F Cmin = {(ϕ, ϕ˜) | ϕ ∈ f (S), ϕ˜ **= min**
x∈Sϕ
˜f (x)},

F Cmax = {(ϕ, ϕ˜) | ϕ ∈ f(S), ϕ˜ **= max**
$L\in L\in L^{\prime}\setminus L^{\prime}=\{\alpha\in S_{\varphi}\}$
˜f(x)} and F C**mean** =
{(ϕ, ϕ˜) | ϕ ∈ f (S), ϕ˜ = **mean**
x∈Sϕ
˜f (x)}.

## 1.3 Evolvability On Fitness Cloud

Evolvability is defined by [2] as "the ability of random variations to sometimes produce improvement". There are three specific fitness values2(respectively **α, β, γ**) corresponding to the intersection of the curves (respectively F Cmin, F C**mean** and F Cmax) with the diagonal line ( ˜f = f). So, according to the fitness level ϕ, four cases can be enumerated (see fig. 2):

1. ϕ ≤ α: bordering fitness is always higher than fitness; applying the heuristic confers selective advantage.

2. **α < ϕ** ≤ β: the mean bordering fitness is higher than fitness.

Thus, on average the heuristic is selectively advantageous.

3. **β < ϕ** ≤ γ: the mean bordering fitness is lower than fitness. Thus, on average the heuristic is selectively deleterious.

4. **γ < ϕ**: bordering fitness is always lower than fitness. The heuristic is selectively deleterious.

## 2 Experimental Results On Nk-Landscape

The search space is the set of bit-string of length N **= 25**. Two strings are neighbors if their Hamming distance is one. All experiments are led on the same instance of NK-landscape with K **= 20**.

Datas are collected from an exhaustive enumeration of the search space3. Practically two fitness values are taken as equal if they both stand in the same interval of size 0.002.

2 Existence of which depends on both the problem and the heuristic 3 A sampling of the search also could be realize if it is large