A Tabu Search hyper-heuristic strategy for t-way test suite generation

• HHH is the first strategy that adopts the hyper-heuristic approach for t-way test suite generation
• HHH introduces new approach for the heuristic selection and move acceptance mechanism based on three operators (i.e. improvement operator, diversify operator, and intensify operator) that are integrated into the Tabu search HLH.
• HHH outperforms existing strategies as far as optimality of test suite is concerned in many benchmarks.

This paper proposes a novel hybrid t-way test generation strategy (where t indicates interaction strength), called High Level Hyper-Heuristic (HHH). HHH adopts Tabu Search as its high level meta-heuristic and leverages on the strength of four low level meta-heuristics, comprising of Teaching Learning based Optimization, Global Neighborhood Algorithm, Particle Swarm Optimization, and Cuckoo Search Algorithm. HHH is able to capitalize on the strengths and limit the deficiencies of each individual algorithm in a collective and synergistic manner. Unlike existing hyper-heuristics, HHH relies on three defined operators, based on improvement, intensification and diversification, to adaptively select the most suitable meta-heuristic at any particular time. Our results are promising as HHH manages to outperform existing t-way strategies on many of the benchmarks.

Figure optionsDownload as PowerPoint slide