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

k=3

t1 t3 t0 t2 t5 t4 t1 t3 t0 t5 t2 t4

p1 o1

t5 t2 t3 t1 t4 t0 t5 t2 t3 t1 t0 t4 p2 o2

Fig. 10. Illustration of crossover operator for permutation-based representations fol-
lowing Antoniol et al.

5.2 Fitness Function

The recommended first step to design the fitness function is to look for an
existing metric that measures the quality we are optimising for. If one exists,
it often provides not only a quick and easy way to evaluate the search-based
approach to the problem but also a channel to compare the results to other
existing techniques.
Themetricthatiswidelyusedtoevaluate the effectiveness of TCP techniques
is Average Percentage of Faults Detected (APFD) [28]. Higher APFD values
mean that faults are detected earlier in testing. Suppose that, as the testing
progresses, we plot the percentage of detected faults against the number of tests
executed so far: intuitively, APFD would be the area behind the plot.
However, calculation of APFD requires the knowledge of which tests detected
which faults. As explained in Section 5, the use of this knowledge defies the
purpose of the prioritisation because fault detection information is not available
until all tests are executed. This forces us to turn to the widely used surro-
gate, structural coverage. For example, Average Percentage of Blocks Covered
(APBC) is calculated in a similar way to APFD but, instead of percentage of
detected faults, percentage of blocks covered so far is used. In regression testing
scenarios, the coverage information of tests are often available from the previous
iteration of testing. While the recent modification that we are testing against
might have made the existing coverage information imprecise, it is often good
enough to provide guidance for prioritisation, especially when regression testing
is performed reasonably frequently.

5.3 Putting It All Together

The representation of solutions and the fitness function are the only problem-
specific components in the overall architecture of SBSE approach in Figure 11.
It is recommended that these problem specific components are clearly separated
from the search algorithm itself: the separation not only makes it easier to reuse
the search algorithms (that are problem independent) but also helps testing and
debugging of the overall approach (repeatedly used implementations of search
algorithms can provide higher assurance).