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

SBSE has been applied to many fields within the general area of Software
Engineering, some of which are already suciently mature to warrant their own
surveys. For example, there are surveys and overviews, covering SBSE for re-
quirements [111], design [78] and testing [3, 4, 65], as well as general surveys of
the whole field of SBSE [21, 36, 48].
This paper does not seek to duplicate these surveys, though some material
is repeated from them (with permission), where it is relevant and appropriate.
Rather, this paper aims to provide those unfamiliar with SBSE with a tutorial
and practical guide. The aim is that, having read this paper, the reader will
be able to begin to develop SBSE solutions to a chosen software engineering
problem and will be able to collect and analyse the results of the application of
SBSE algorithms.
By the end of the paper, the reader (who is not assumed to have any prior
knowledge of SBSE) should be in a position to prepare their own paper on
SBSE. The tutorial concludes with a simple step-by-step guide to developing the
necessary formulation, implementation, experimentation and results required for
the first SBSE paper. The paper is primarily aimed at those who have yet to
tackle this first step in publishing results on SBSE. For those who have already
published on SBSE, many sections can easily be skipped, though it is hoped that
the sections on advanced topics, case studies and the SBSE taxonomy (Sections 7,
8 and 9) will prove useful, even for seasoned Search Based Software Engineers.
The paper contains extensive pointers to the literature and aims to be suf-
ficiently comprehensive, complete and self-contained that the reader should be
able to move from a position of no prior knowledge of SBSE to one in which he or
she is able to start to get practical results with SBSE and to consider preparing
a paper for publication on these results.
The field of SBSE continues to grow rapidly. Many exciting new results and
challenges regularly appear. It is hoped that this tutorial will allow many more
Software Engineering researchers to explore and experiment with SBSE. We
hope to see this work submitted to (and to appear in) the growing number of
conferences, workshops and special issue on SBSE as well as the general software
engineering literature.
The rest of the paper is organised as follows. Section 2 briefly motivates the
paper by setting out some of the characteristics of SBSE that have made it well-
suited to a great many Software Engineering problems, making it very widely
studied. Sections 3 and 4 describe the most commonly used algorithms in SBSE
and the two key ingredients of representation and fitness function. Section 5
presents a simple worked example of the application of SBSE principles in Soft-
ware Engineering, using Regression Testing as an exemplar. Section 6 presents
an overview of techniques commonly used to understand, analyse and interpret
results from SBSE. Section 7 describes some of the more advanced techniques
thatcanbeusedinSBSEtogobeyondthesimple world of single objectives for
which we seek only to find an optimal result. Section 8 presents four case studies
of previous work in SBSE, giving examples of the kinds of results obtained. These
cover a variety of topics and involve very different software engineering activities,