Simulated annealing and genetic algorithms for optimal regression testing

The optimal regression testing problem is one of determining the minimum nu mber of test cases needed for revalidating modified software in the mainten ance phase. We present two natural optimization algorithms, namely, a simul ated annealing and a genetic algorithm, for solving this problem. The algor ithms are based on an integer programming problem formulation and the progr am's control how graph. The main advantage of these algorithms, in comparis on with exact algorithms, is that they do not suffer from an exponential ex plosion for realistic program sizes. The experimental results, which includ e a comparison with previous algorithms, show that the simulated annealing and genetic algorithms find the optimal or near-optimal number of retests w ithin a reasonable time. Copyright (C) 1999 John Wiley & Sons, Ltd.