Selected figures from the second chapter of
Foundation of Genetic programming
Chapter 2 Fitness Landscapes
The idea of fitness landscapes, firstly proposed in genetics by Sewall
Wright, is well established in artificial
They are a metaphor used to help visualise problems.
In the metaphor landscapes are viewed as being like an area of
Looking vertically down from a great height the countryside
appears like a map.
This corresponds to the area to be searched.
That is, the plan view is the search space.
The height of each point is analogous to the objective or
fitness value of the point.
Thus the task of finding the best solution to the problem
is equivalent to finding the highest mountain.
The problem solver is seen as a short-sighted explorer searching
for this point.
Systematic exploration of the whole search space
Two hill climbing paths. One reaches the global optimum but the second
is trapped at the top of a local peak.
Lines indicate the ultimate location of a hill climber
on the landscape shown in Figure 2.2.
All the starting points connected to a hill
are known as the hill's "basin of attraction".
In this example
there are two major basins of
attraction. The higher peak also has the larger basin.
This need not always be the case.
A third area is the flat swamp, where the explorer has no gradient to
Fitness Landscapes as Models of Problem Difficulty
A rugged landscape.
In this landscape the local gradient may eventually lead to the summit
but the path is much longer than the direct path.
An Example GP Fitness Landscape
Other Search Strategies
Difficulties with the Fitness Landscape Metaphor
Effect of Representation Changes
Landscape using binary coding.
This is the same landscape as
but using a binary coding rather than a Grey coding.
The labels ("Peak" etc.) refer to the original figures.
Recoding the parameters changes the topology of the landscape
in this example,
introduces more local peaks.