Constructing strength three covering arrays with augmented annealing |
| |
Authors: | Myra B Cohen |
| |
Institution: | a Department of Computer Science Computer Science and Engineering, University of Nebraska-Lincoln, Lincoln, NE 68588-0115, USA b Department of Computer Science and Engineering, Arizona State University, P.O. Box 878809, Tempe, AZ 85287, USA c Department of Computer Science, University of Vermont, Burlington, VT 05045, USA |
| |
Abstract: | A covering arrayCA(N;t,k,v) is an N×k array such that every N×t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. One application of these objects is to generate software test suites to cover all t-sets of component interactions. Methods for construction of covering arrays for software testing have focused on two main areas. The first is finding new algebraic and combinatorial constructions that produce smaller covering arrays. The second is refining computational search algorithms to find smaller covering arrays more quickly. In this paper, we examine some new cut-and-paste techniques for strength three covering arrays that combine recursive combinatorial constructions with computational search; when simulated annealing is the base method, this is augmented annealing. This method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide new bounds for some strength three covering arrays. |
| |
Keywords: | Software testing Combinatorial design Covering array Heuristic search Simulated annealing Orthogonal array Generalized Hadamard matrix |
本文献已被 ScienceDirect 等数据库收录! |
|