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.
