Software Test Data Generation Based On Memetic Algorithm

With the rapid development of the software, people’s worry about the safety of software is deeper and deeper. Software defects can cause huge property losses and even endanger personal safety. Therefore software testing has gradually become the most important guarantee to the survival of software engineering. The purpose of software testing is to enhance the reliability of software. Software testing is a very time-consuming work. In a software engineering, test will consume nearly half of the development funds. Generally speaking, the main goal of test is to use the limited test data to find as much potential errors as possible. In this case, there is no need to doubt the importance of test case. The key to efficient testing is that how to reduce the amount of test data while increasing the coverage. The researchers have put forward a series of strategies in this area. However, these strategies have some defects. A new method of software test data generation is searching for the optimal solution in the possible solution domain with the feedback information which is produced by the target program while the target program is running. This method views test data generation as an optimization problem, namely using the heuristic search algorithm to find the optimal solution. Genetic algorithm(GA) is used in test data generation at the highest frequency and shows high efficiency. But from the perspective of performance, genetic algorithm still has some limitations. In some cases, it will get into trouble.Memetic algorithm is introduced in this thesis, and it is applied to test data generation. Memetic algorithm is based on genetic algorithm but it has local search ability which can effectively restrain premature phenomenon. The fitness function and the local search mechanism of Memetic algorithm are designed in this thesis. Then the performance of Memetic algorithm is analyzed through experiments. In this thesis, the performance of an algorithm is analyzed from two aspects—iteration time and convergence speed. Iteration time refers to the elapsed time it takes for an algorithm from start to finish. Convergence speed depends on the amount of iteration generated by each run of the algorithm, the smaller the amount of iteration, the higher the speed. Iteration time represents the executive ability of the algorithm; convergence speed represents the search ability of the algorithm.The generation of test data for multiple paths coverage is also a reliable way to improve the efficiency of test data generation. It can use the similarity between paths to reduce repeated iteration time. Memetic algorithm is used in this thesis to realize multipath test data generation. Its specific design methods are studied and its performance is also analyzed in this thesis. But in multipath test data generation field, the shortcomings of Memetic algorithm are also exposed. It takes longer iteration time. Therefore, from the perspective of the average iteration time, particle swarm optimization(PSO) is introduced to modify Memetic algorithm in this thesis. The partial performance of PSO algorithm can effectively enhance the local search ability of Memetic algorithm. At the same time, PSO has smaller amount of calculation, which can reduce the iteration time of Memetic algorithm. Memetic algorithm and the improved Memetic algorithm are contrasted at the end of this thesis through experiments.Experiments show that Memetic algorithm can improve the efficiency of test data generation and the performance of Memetic algorithm in both single path and multipath is superior to genetic algorithm.