A genetic algorithm for corrective retesting. (c1995)

Abstract

The optimal retesting problem is that of determining the minimum number of test cases needed for revalidating modified software in the maintenance phase. We present a genetic algorithm (GA) for solving this problem, based on the program's flow graph and an integer programming problem formulation. The algorithm deviates from classical GAs in that it incorporates some design choices to guarantee a final feasible solution and to improve the efficiency of the genetic search. These choices include elitist ranking, random feasibilization, penalization, and a hybridized hill-climbing procedure. The main advantage of this algorithm is that it does not suffer from exponential explosion for large program sizes. Further, the experimental results show that it finds an optimal number of retests faster than other known methods.