Algorithm Design and Empirical Analysis for Particle Swarm Optimization-Based Test Data Generation

How to generate a test dataset with high coverage and strong fault-revealing ability is a difficult problem, especially for software structural testing. Recently, meta-heuristic search has been confirmed to be an effective way to generate structural test data. In the paper, a swarm intelligence-based method is proposed to handle this problem. At first, the basic framework for search-based test data generation is discussed. Then, with regard to branch coverage criterion, the algorithm for generating test data based on particle swarm optimization (PSO) is proposed. Meanwhile, a new way to construct fitness function is defined according to the structure analysis for branch predicates in program under test. Subsequently, ten open published programs are used to perform experimental evaluation. The experimental results show that PSO outperforms genetic algorithm (GA) and simulated annealing (SA) in all four metrics, i.e., average coverage, success rate, average convergence generation and average time. In addition, other four PSO variant algorithms are also introduced and implemented to conduct comparison analysis with the basic PSO. The results indicate that the basic PSO is the most suitable algorithm for test data generation problem. On the contrary, comprehensive learning PSO (CLPSO) exhibits the worst performance in all variant algorithms.