Search Based Software Engineering: Techniques, Taxonomy, Tutorial - Empirical Software Engineering and Verification - page 6

have to hand, already, an implementation of some metric of interest. With a very
little effort this can be turned into a fitness function and so the 'learning curve'
and infrastructural investment required to get started with SBSE is among the
lowest of any approach one is likely to encounter.
4 Commonly Used Algorithms
Random search is the simplest form of search algorithm that appears frequently
in the software engineering literature. However, it does not utilise a fitness func-
tion, and is thus unguided, often failing to find globally optimal solutions (Figure
2). Higher quality solutions may be found with the aid of a fitness function, which
supplies heuristic information regarding the areas of the search space which may
yield better solutions and those which seem to be unfruitful to explore further.
The simplest form of search algorithm using fitness information in the form of
a fitness function is Hill Climbing. Hill Climbing selects a point from the search
space at random. It then examines candidate solutions that are in the 'neighbour-
hood' of the original; i.e. solutions in the search space that are similar but differ
in some aspect, or are close or some ordinal scale. If a neighbouring candidate
solution is found of improved fitness, the search 'moves' to that new solution.
It then explores the neighbourhood of that new candidate solution for better
solutions, and so on, until the neighbourhood of the current candidate solution
offers no further improvement. Such a solution is said to be locally optimal ,and
may not represent globally optimal solutions (as in Figure 3a), and so the search
is often restarted in order to find even better solutions (as in Figure 3b). Hill
Climbing may be restarted as many times as computing resources allow.
Pseudo-code for Hill Climbing can be seen in Figure 4. As can be seen, not
only must the fitness function and the 'neighbourhood' be defined, but also the
type of 'ascent strategy'. Types of ascent strategy include 'steepest ascent', where
all neighbours are evaluated, with the ascending move made to the neighbour
offering the greatest improvement in fitness. A 'random' or 'first' ascent strategy,
on the other hand, involves the evaluation of neighbouring candidate solutions at
random, and the first neighbour to offer an improvement selected for the move.
portion of
search space
containing globally
optimal solutions
randomly-generated
solutions
Space of all possible solutions
Fig. 2. Random search may fail to find optimal solutions occupying a small proportion
of the overall search space (adapted from McMinn [66])