Automatic test data generation for path testing using GAs

Genetic algorithms (GAs) are inspired by Darwin's the survival of the fitte st theory. This paper discusses a genetic algorithm that can automatically generate test cases to test a selected path. This algorithm takes a selecte d path as a target and executes sequences of operators iteratively for test cases to evolve. The evolved test case will lead the program execution to achieve the target path. To determine which test cases should survive to pr oduce the next generation of fitter test cases, a metric named normalized e xtended Hamming distance (NEHD, which is used to determine whether the fina l test case is found) is developed. Based on NEHD, a fitness function named SIMILARITY is defined to determine which test cases should survive if the final test case has not been found. Even when there are loops in the target path, SIMILARITY can help the algorithm to lead the execution to flow alon g the target path. (C) 2001 Elsevier Science Inc. All rights reserved.