exploration process so as to increase the probability of finding a solution, and thus
reduce the amount of search needed. Heuristics do not guarantee success, however,
and the result therefore remains intrinsically uncertain.
Probably the most common heuristic method is hill climbing. The idea is that
each point in the problem space is evaluated in terms of its “goodness” or “fitness”,
i.e. how close it is to the ideal situation. The fitness value of a point is represented
vertically, as the “elevation” of that possibility above the plane. Excellent solutions
then correspond to high peaks, awful possibilities to deep valleys. This introduction of
the vertical dimension to represent the fitness of a possible situation turns the problem
space into a fitness landscape [Gavrilets, 2004]. The hill-climbing heuristic then
means that the agent exploring the landscape will simply move from point to point in
the direction of steepest ascent. This means that whenever the agent needs to choose
between different options for the next step, it will choose the step that increases
fitness most, in the hope that by continuing in this direction it will eventually reach
the fitness peak, i.e. the best solution in the neighborhood. The disadvantage of the
hill-climbing method is that the best local solution is in general not the best overall
solution. The local hill may actually be much lower than the highest mountain. But
once you are on the top of that hill all the roads by definition lead downwards, and
therefore the hill-climbing method is no longer useful as a guide to indicate the
highest peak.
The notions of hill-climbing and fitness landscape are defined on an abstract
space of possibilities. The underlying assumption is that the agent does not know the
fitness of a possibility until it has reached it. Therefore, the agent can only explore
locally: it cannot plan ahead, and decide to move in a particular direction because the
faraway prospect in that direction looks promising. This is a good model of totally
ignorant or blind processes of exploration, such as the random variation that underlies
evolution through natural selection [Campbell, 1960]. More sophisticated agents, such
as animals or humans, on the other hand, can to some degree foresee the
consequences of their actions, and thus make choices that do not immediately increase
fitness because they anticipate that they will lead to greater fitness in the longer term.
This implies the use of more complex and powerful heuristics than hill climbing.
However, the landscape metaphor remains useful as a way to understand how the
agent decides in what direction it will go. To illustrate that, we need to go back from
abstract landscapes of possibilities to real landscapes with rocks and trees.
There exists an interesting scientific literature on the aesthetic qualities of
landscapes [e.g. Aoki, 1999; Ruso et al., 2003]: what are the features of a landscape
that make it more or less attractive to a human observer? Some of the attraction can be
explained rather straightforwardly on the basis of evolutionary psychology: most
people like features such as lakes, animals, trees and flowers which indicate the
presence of resources (water, food, shelter...) that enhance fitness. They similarly
tend to dislike features that indicate hindrances or dangers, such as storm clouds,
sharp objects, snakes, and darkness. This fits in with the postulated tendency of an
- 22 -