Path test data generation using adaptive simulated annealing particle swarm optimization

Software testing is an effective means of ensuring software quality. The cost of software testing is the main component of the total cost of software development. The generation of test data is very important in testing, because the efficiency of testing depends on the test data used. A significant part of software testing automation is the test data generation. How to automatically generate test datasets is still an open problem. Search-based software testing (SBST) is a process of generating test data that employs meta-heuristic methods to resolve tough NP-hard problems. The test data generation problem belongs to NP-hard problems. This paper focuses on the automatic generation of test data for path coverage based on control flow criteria in structural testing. Some meta-heuristic algorithms have been used to search for software test data. To advance the efficiency and effectiveness of path test data generation, an adaptive simulated annealing particle swarm optimization (ASAPSO) algorithm is proposed. The probabilistic jumping property of simulated annealing (SA) algorithm is introduced into the particle swarm optimization (PSO) algorithm to make the particle accept bad solution at a certain probability during the searching process, and therefore boost the capacity of the proposed algorithm to bounce from the local optimum. The fitness function is constructed by the branch function superposition to properly guide the search process. In addition, to improve the convergence speed of the algorithm, an adaptive adjustment scheme based on inertial weight and an adjustment scheme based on learning factor are proposed as well. The experimental results show that the proposed method can effectually avoid premature convergence and effectively upgrades the efficiency of generating test data automatically. It is also competitive in solving other complicated optimization problems.