Evolutionary Computation and Metaheuristics - Automatic Generation of Combinatorial Test Data - page 51

The total number of distinct pairwise configurations covered by the chromosome C 1
is 5 (because there is a common element in N 1 and N 2 ). So the fitness function value
of C 1 is 5

12.
Recently, McCaffrey [ 32 , 34 ] implemented (in C#) a test data generation method,
which is also based on genetic algorithms. The technique/tool is called GAPTS. It
first maps all possible parameter values to consecutive integers, e.g., 0

/

6.
They serve as the gene values. A chromosome is represented as an array of integers.
For instance, suppose the SUT has three parameters. Then a test case is represented
by a sequence of three integers, and the array

, 1 , 2 ,...,

is a
chromosome, which denotes a test suite of four test cases. The fitness function is
simply defined as the total number of distinct pairs in the chromosome representation
of test cases.
McCaffrey discussed some issues in the implementation, such as the population
size and mutation rate. The population size is set to 20, and the mutation rate is fixed
as 0

[ 0 , 3 , 6 , 1 , 2 , 5 , 1 , 4 , 5 , 0 , 2 , 6 ]

001. His experimentation indicates that, mutation rates larger than 0.001 tend to
modify good solutions too often, which result in slow convergence; mutation rates
smaller than 0.001 often lead to premature convergence to nonoptimal solutions.
McCaffrey compared the tool GAPTS with other tools like AETG and PICT. In
general, GAPTS produces comparable or smaller test suites, but it requires much
longer time.
The above works only deal with pairwise testing. And they apply the GA to the
whole array. Alternatively, it is also possible to apply GA to obtain a single test case.

.

5.3.2 Applying GA to Obtain a Good Test Case

Recall that AETG is a greedy algorithm which constructs a test suite by repeatedly
adding a test case that covers as many uncovered interactions as possible. In each
iteration, it creates many candidate test cases and selects the one that covers the
largest number of newly covered combinations. Clearly, this can be regarded as an
optimization problem.
Shiba et al. [ 43 ] extended the basic AETG algorithm with the genetic algorithm,
and obtained the test generation procedure AETG-GA.
In AETG-GA, each test case is treated as a chromosome. The fitness function

for a test case s is the number of new t -way combinations that are not covered
by the given test suite but are covered by s .
One feature of AETG-GA is that, in each generation, the best

f ( s )

chromosomes
in the population are kept and they survive to the next generation. This is called the
elite strategy in Shiba et al. [ 43 ].

σ