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

dying out. Finally, a general migration of individuals takes place after every 20 th
generation, where subpopulations randomly exchange 10% of their individuals
with one another.

Results. Results with the CAS check example can be found in Table 1. The
search for test data was repeated 50 times with both the GA outlined in the
last section and random search. Random search simply constructs an input by
constructing a string where each of the 15 characters is selected at random. Both
algorithms were given a budget of 100,000 inputs to generate and execute the
program with, in order to find test data for a particular branch. Each branch
is denoted as L T

F, where L is the line number of the branch, while T and F
denote which of the true or false branches is being referred to.
The performance of the GA is compared with random search. In the table,
the average number of test data evaluations (fitness function evaluations for the
GA) is reported, unless the branch was not covered over the 50 runs with a
100% success rate, in which case the success rate is reported instead. As can be
seen from the table, random search is very effective, covering all the branches
of the example except 1 (branch 18F). The GA, on the other hand, achieves
100% coverage. Statistical tests were also performed, as outlined in Section 6.2.
For the majority of branches, there was no statistical difference in performance
between the two searches. However, for 18F and 19T, the GA was significantly

|

Table 1. Results with the CAS registry number checking program of Figure 15. The
average number of test data evaluations over 50 runs is reported for the branch and
algorithm if the success rate of finding test data to execute the branch was 100%,
else the success rate is reported instead. A figure appears in bold for the GA if its
performance was significantly better than random search.

Branch Search

Random Genetic Algorithm

4T 1 1

4F 1 1

7T 2 2

7F 1 1

8T 2 2

8F 8 8

10T 8 8

10F 2 2

17T 465 329

17F 1 1

18T 465 329

18F 0% 3,230

19T 4,270 802

19F 519 363