Improved mixed neighborhood tabu search by random selection for combinatorial interaction testing

Abstract EN

Combinatorial interaction testing (CIT) is a technique used to find minimal test suite among configuration options of a System Under Test (SUT) that uses a Covering Array (CA) as a combinatorial structure.

CIT is very effective for reducing the costs of the testing process that uses a sampling technique instead of exhaustive testing.

This paper proposes the modification of Mixed Neighborhood Tabu Search (RMiTS) algorithm using the random selection strategy.

The base MiTS algorithm is originally used for generating t-way Mixed Covering Array (MCA).

The modification improves the algorithm performance (running time) to cover all possible input configuration combinations to produce the optimal or near-optimal test suites.

The modified algorithm is evaluated through a comparison against the base MiTS algorithm to confirm the performance improvements.

Also, it is compared to a state-of-the-art algorithm known as Advanced Combinatorial Test Tool (ACTS) to confirm its efficiency.

The experimental results confirm the effectiveness of the modifications that improved the performance for all applied benchmarks, and also it shows that RMiTS is more efficient than ACTS.