Using Decision Trees to aid Algorithm Selection in Combinatorial Interaction Test Generation

It has been widely observed that there is no a single best CIT generation algorithm; instead, different algorithms perform best in terms of test suite size and time, also depending on different combinatorial models. Rather than following the traditional approach of leaving the choice of the best generator for a given class of models and for given testing requirements to the user, we want to automate the algorithm selection process among a given set of techniques (called portfolio). The proposed approach takes as input a distribution of combinatorial models and their test suites generated using several tools, then, using data-mining techniques, it permits to predict the algorithm that performs better given the cost estimated to execute a single test and the model characteristics. As predictors, we decide to use decision trees because they have been one of the most widely used decision support tool for many years. Their attraction lies in the simplicity of the resulting model, where a decision tree (at least one that is not too large) is quite easy to view, understand, and, importantly, explain even if it may not always deliver the best performances. We demonstrate the effectiveness of our approach to automated algorithm selection in extensive experimental results on data sets including models commonly presented in literature.