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
evolution.
They are a metaphor used to help visualise problems.
In the metaphor landscapes are viewed as being like an area of
countryside.
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.
Exhaustive Search
Fig. 2.1.
Systematic exploration of the whole search space
code
Hill Climbing
Fig. 2.2.
Two hill climbing paths. One reaches the global optimum but the second
is trapped at the top of a local peak.
code
Fig. 2.3.
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
guide him.
code
Fitness Landscapes as Models of Problem Difficulty
Fig. 2.4.
A rugged landscape.
code
Fig. 2.5.
In this landscape the local gradient may eventually lead to the summit
but the path is much longer than the direct path.
code
An Example GP Fitness Landscape
Other Search Strategies
Difficulties with the Fitness Landscape Metaphor
Effect of Representation Changes
Fig. 2.9.
Landscape using binary coding.
This is the same landscape as
Figures 2.1-2.3
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
and,
in this example,
introduces more local peaks.
code