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

Raw Data Representation

Search Algorithm

Metrics or
Properties

Fitness Function

Fig. 11. Overall Architecture of SBSE Approach

6 Understanding Your Results

6.1 Fair Comparison
Due to the stochastic nature of optimisation algorithms, searches must be re-
peated several times in order to mitigate against the effects of random variation.
In the literature, experiments are typically repeated 30-50 times.
When comparing two algorithms, the best fitness values obtained by the
searches concerned are an obvious indicator to how well the optimisation pro-
cess performed. However, in order to ensure a fair comparison, it is important to
establish the amount of effort expended by each search algorithm, to find those
solutions. This effort is commonly measured by logging the number of fitness
evaluations that were performed. For example, it could be that an algorithm
found a solution with a better fitness value, but did so because it was afforded
a higher number of trials in which to obtain it. Or, there could be trade-offs,
for example search A may find a solution of good fitness early in the search,
but fail to improve it, yet search B can find solutions of slightly better fitness,
but requiring many more fitness evaluations in which to discover it. When a cer-
tain level of fitness is obtained by more than one search algorithm, the average
number of fitness evaluations over the different runs of the experiments by each
algorithm is used to measure the cost of the algorithm in obtaining that fitness,
or to put it another way, its relative eciency .
For some types of problem, e.g. test data generation, there is a specific goal
that must be attained by the search; for example the discovery of test data
to execute a particular branch. In such cases, merely 'good' solutions of high
fitness are not enough - a solution with a certain very high fitness value must be
obtained, or the goal of the search will not be attained. In such cases, best fitness
is no longer as an important measure as the success rate , a percentage reflecting
the number of times the goal of the search was achieved over the repetitions of
the experiment. The success rate gives an idea of how effective the search was
at achieving its aim.

6.2 Elementary Statistical Analysis
The last section introduced some descriptive statistics for use in Search Based
Software Engineering experiments, but also inferential statistics may be applied