A penalty-based Tabu search for constrained covering arrays
| Autor: | Segla Kpodjedo, Philippe Galinier, Giulio Antoniol |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
business.industry Computation 020207 software engineering Context (language use) 02 engineering and technology Tabu search restrict 020204 information systems 0202 electrical engineering electronic engineering information engineering Test suite Local search (optimization) Guided Local Search Software system business Mathematics |
| Zdroj: | GECCO |
| Popis: | Combinatorial Interaction Testing is a black-box testing technique particularly used for highly configurable software systems, which involve a number of factors (and values) that can be combined, according to some constraints. In this context, constrained covering array (CCA) is a central combinatorial problem tasked with building a test suite of minimum size and maximum coverage of the factors' interactions.In this paper, we propose CATS (Covering Array by Tabu Search), a new penalty-based tabu search algorithm for the CCA problem. Our local search approach differs from the ones previously proposed primarily by its use of a search space that allows solutions that violate inter-factor constraints. Other prominent features of CATS are the definition of strategic moves used to restrict the neighborhood, and a technique to vary the tabu tenure throughout the search.We performed tests with CATS on 2-way constrained problems using 35 widely used benchmarks. Results suggest that CATS consistently outperforms previous approaches, both on the size of the test suites and the needed computation times. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|