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

An 8 by 8 fitness landscape
Fig. 2.1. Systematic exploration of the whole search space
code

Hill Climbing

Hill climbing an 8 by 8 fitness landscape

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
An 8 by 8 fitness landscape showing two two basins of attraction

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

A complicated rugged fitness landscape
Fig. 2.4. A rugged landscape.
code
A long path problem in the form of a continuous spiral

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

Effect of gray code: Making a simple 8 by fitness landscape complex

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