A mutation rate of 0.005 was beneficial. Larger rates were disruptive, while lower rates were less effective. The probability of crossover was set to 1.0, meaning that selected individuals always crossed. This also helped achieve convergence sooner.

The GA was highly susceptible to selection noise. Meaningful results were only obtained after using stochastic remainder sampling and multipoint crossover (two points over a 24-bit chromosome).

Figure 4.6 is a histogram depicting the number of times each of the eighteen possible blocks of code was executed by both fitness algorithms at generation 50. The data used to produce Figure 4.6 was obtained from GA runs with a population multiplier of 14. This allowed both fitness algorithms to converge well before generation 50. With this large multiplier value both algorithms perform similarly in terms of speed of convergence. However, the histogram shows that the IPP fitness algorithm executed nodes 80 and 88 (columns 14 and 15 in Figure 4.6) more frequently than the LBTPB algorithm. Node 80 is the block of code entered by the default else statement on line 78 (Figure 4.1). Node 88 is a block of code (beginning on line 86) executed when the function’s input parameters do not form a triangle. The LBTPB algorithm produces more sets of test data forming equilateral, isosceles, and scalene triangles (nodes 95, 102, and 108). The LBTPB algorithm distributes test cases more evenly over the four possible outputs (not a triangle, equilateral, isosceles, and scalene).

Figure 4.6  Distribution of test cases over the 18 code blocks in trityp-easy.

FUTURE WORK

This chapter describes the use of Goldberg’s SGA with the reproduction, crossover, and mutation operators. There are other operators that should prove helpful to this work. These include marriage restriction and sharing to help create species of test data.

As mentioned earlier, a C language parser is required to produce the test data generator utility. Codings appropriate for other elements of the C language need to be developed (enumerated types, arrays, pointers, etc.). Some of the authors cited earlier have begun work in this area. Inclusion of their findings in the proposed utility may prove beneficial.

The LBTPB fitness function is a special case of a more general algorithm which considers unique nodes all along the thread of execution. This general case algorithm needs to be developed further and evaluated.

One goal of testing is to minimize the number of test cases required. The work described here creates stable sub-populations of redundant test cases. To minimize tester time, a method is needed to take the set of test data produced and find the minimum number of members that provide 100% line coverage. This problem is similar in nature to the Traveling Salesman problem and should be solvable with a second genetic algorithm performing a pure minimization.

CONCLUSIONS

Genetic algorithms are useful tools for generating sets of unit test provided certain conditions are met. These include using a sufficiently large population size to allow a stable and optimal population of test cases to form at the end of the run. A population size of ten times the McCabe cyclometric complexity is recommended.

The LBTPB fitness algorithm helps the GA converge sooner and distributes test cases more evenly over the module under test than the IPP fitness algorithm. Both fitness functions tested eventually converge given an adequate population size. The LBTPB fitness algorithm accomplishes this by rewarding test cases executing unique code.

A small bonus value aids convergence. Large bonus values are disruptive. This work suggests that a bonus of 5 fitness points helps the genetic algorithm search for better test cases without causing loss of coverage due to overzealous replacement.

REFERENCES

1  H. H. Sthamer, B. F. Jones, and D. E. Eyers (1994). Generating test data for ADA generic procedures using genetic algorithms. Proceedings of ACEDC 1994, 134-140, Plymouth, UK: University of Plymouth.

2  S. Xanthakis, C. Ellis, C. Skourlas, A. LeGall, S. Katsikas, and K. Karapoulios (1992). Application of genetic algorithms to software testing. Proceedings of the 5th International Conference on Software Engineering, 625-636, Toulouse, France.

3  A. L. Watkins (1995). The automatic generation of test data using genetic algorithms. In I. M. Marshall, W. B. Samson, and D. G. Edgar-Nevill (Eds.) Proceedings of the 4th Software Quality Conference, 2, 300-309, Dundee, UK.

4  D. E. Goldberg (1989). Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley Publishing Company, Inc.

5  T. McCabe (1976). A complexity measure. IEEE Trans. on Software Engineering, SE –2 (4), 308-320.