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

exceptionally good results for determining the module boundaries of source code
that remained unsurpassed by more sophisticated algorithms from 1998 [64] until
2011 [77]. Furthermore, the multi objective genetic algorithm that found better
solutions only managed to do so at a cost of two orders of magnitude more fitness
evaluations [77].
Korel [59] was one of the first authors to apply a search based optimisation
approach to a software engineering problem. He used a hill climbing approach
for software test input generation. Though this problem has been very widely
studied, this hill climbing approach still proved to be an attractive approach
17 years later, when it was studied and (favourably) compared empirically and
theoretically to a more sophisticated genetic algorithm [49], suggesting that a
hybrid that combined both hill climbing (local search) and genetic algorithms
(global search) was the best approach for test data generation [50].
Hill climbing can also be used to help to understand the nature of the solu-
tions found. For example, through multiple hill climbs, we can find the set of
common building blocks that are found in all good solutions. This can help to
understand the problem and also may be a way to make subsequent techniques
more effective. This approach to locating building blocks using multiple runs
of a hill climber was applied by Mahdavi et al. [62], who used a distributed
cluster of machines to perform multiple hill climbs in parallel for the software
modularisation problem. The results were the building blocks of 'good modules'
(those which were cohesive and exhibited low coupling) for a particular architec-
ture of dependencies. Mahdavi et al. also showed that the initial identification
of building blocks could improve the performance of the subsequent search.
For all these reasons, faced with a large number of possible algorithms with
which to start, it seems sensible to adopt hill climbing as the first optimisation
algorithm. If the results are promising then within a very short space of time, the
novice SBSE researcher will have migrated from finishing reading this tutorial
to starting to write their own first SBSE paper; perhaps in as little as a matter
of days.
Step 5: The natural next step is to try some different search based algorithms.
A good place to start is those described in Section 4 since these have been
commonly applied and so there will be a wealth of previous results with which to
compare. Following this, the SBSE researcher is already going beyond what can
be covered in a single tutorial such as this and is thus referred to the literature
on search based optimisation. A good overview of search techniques can be found
in the text book by Burke and Kendall [19].
Step 6: Having implemented several SBSE algorithms and obtained results, the
next step is to analyse these results. In this paper we have set out some of the
common statistical techniques used to analyse SBSE work in Section 6. Nat-
urally, this can only provide an overview of some commonly used approaches,
but it should be sucient to address some of the most obvious initial ques-
tions; those to which a referee would naturally expect answers. Using these tech-
niques the results can be developed to become the basis for an experimental or