Improving Multi-Objective Test Case Selection by Injecting Diversity in Genetic Algorithms

A way to reduce the cost of regression testing consists of selecting or prioritizing subsets of test cases from a test suite according to some criteria. Besides greedy algorithms, cost cognizant additional greedy algorithms, multi-objective optimization algorithms, and multi-objective genetic algorithms (MOGAs), have also been proposed to tackle this problem. However, previous studies have shown that there is no clear winner between greedy and MOGAs, and that their combination does not necessarily produce better results. In this paper we show that the optimality of MOGAs can be significantly improved by diversifying the solutions (sub-sets of the test suite) generated during the search process. Specifically, we introduce a new MOGA, coined as DIversity based Genetic Algorithm (DIV-GA), based on the mechanisms of orthogonal design and orthogonal evolution that increase diversity by injecting new orthogonal individuals during the search process. Results of an empirical study conducted on eleven programs show that DIV-GA outperforms both greedy algorithms and the traditional MOGAs from the optimality point of view. Moreover, the solutions (sub-sets of the test suite) provided by DIV-GA are able to detect more faults than the other algorithms, while keeping the same test execution cost.

1 Introduction

Regression testing consists of re-testing software that has been modified. Such an activity is required to verify whether new changes have introduced errors into unchanged parts, endangering their behaviors [69]. Re-testing the whole software system by executing all the available test cases might be too expensive and unfeasible, especially for large systems [25] , [55]. Running some test suites can take hours, even days, so developers cannot exercise the system instantly or in reasonable time [58]. The problem is clearly amplified by the growth of the test suites as the system evolves.