Generation of Pairwise Test Sets Using a Genetic Algorithm

Pairwise testing is a combinatorial technique used to reduce the number of test case inputs to a system in situations where exhaustive testing with all possible inputs is not possible or prohibitively expensive. Given a set of input parameters where each parameter can take on one of a discrete set of values, a pairwise test set consists of a collection of vectors which captures all possible combinations of pairs of parameter values. The generation of minimal pairwise test sets has been shown to be an NP-complete problem and there have been several deterministic algorithms published. This paper presents the results of an investigation of generating pairwise test sets using a genetic algorithm. Compared with published results for deterministic pairwise test set generation algorithms, the genetic algorithm approach produced test sets which were comparable or better in terms of test set size in 39 out of 40 cases. However, the genetic algorithm approach required longer processing time than deterministic approaches in all cases. The results demonstrate that the generation of pairwise test sets using a genetic algorithm is possible, and suggest that the approach may be practical and useful in certain testing scenarios.