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

guided by fitness and many of the solution approaches could be described as
the application of 'common sense' (though some may be slightly surprising or
counter-intuitive). Where possible, we provide pointers to the SBSE literature,
indicating where the proposed solution approaches have already been explored
in the specific context of Software Engineering problem domains.

11.1 My Ideal Fitness Function Is Too Computationally Expensive

The most natural fitness function for a problem may turn out to be compu-
tationally expensive and this may mean that the whole search process takes a
long time. In most applications of SBSE, it is the computation of fitness that
occupies the largest part of the overall computational cost of the SBSE imple-
mentation. As such, it makes sense to consider techniques for controlling and
reducing this cost, where it is manageable. This issue, therefore, can be consid-
ered to be the problem of 'how can we compute fitness faster?'. We consider
three approaches: use a cheaper surrogate, parallelise and imbue the search with
domain knowledge.
Find a cheaper surrogate: Often, a computationally demanding fitness func-
tion can be reserved for evaluating the final result or for occasional fitness com-
putation, while a surrogate (or surrogates) is/are used for most of the fitness
evaluations used to guide the search. Even if the surrogate fitness function is
not a perfect guide, it can be computationally cheaper overall, to use a less
accurate fitness function (that still provides some guidance for the majority of
fitness computations). This approach has been used very little in Software En-
gineering, partly because many of the fitness functions used in SBSE tend to
be computationally inexpensive (they often come from works on metrics [42],
which are pre-designed to be computationally practical). Even when the metrics
used as fitness functions do prove to be computationally expensive, it is typi-
cally hard to find surrogates. However, as SBSE increasingly finds applications
in new software engineering areas there may also be a wider choice of available
metrics and it may turn out that the most suitable metrics are also those that
are more computationally expensive. We can therefore expect that there will be
a greater reliance on surrogate fitness computations in future work on SBSE.
To minimise the negative impact of using a surrogate that only captures part of
the true fitness or which includes noise, it may be advantageous to use multiple
surrogate fitness computations (as discussed later on in this section).

Parallelise: SBSE algorithms are known as 'embarrassingly parallel' [32] be-
cause of their potential for scalability through parallel execution of fitness com-
putations [72]. Recent work has shown how this parallelism can be exploited on
General Purpose Graphical Processing devices (GPGPUs) [110] with scale ups
in overall computation time up to a factor of 20. Because of the inherent paral-
lelism of SBSE algorithms and the wide availability of cheap multicore devices
we can expect a great deal more scalability research in future work on SBSE. In
the era of multicore computing, SBSE is well placed to make significant strides
forward in simple effective and scalable parallel solutions.