Abstract:The design of fitness function plays one of most important roles in search based test data generation. While in some special program structures, such as nested structure, unstructured jump statements, and return/break statements, the existing fitness functions can't evaluate all the branches. The currently used approaches are to change the source program so that the branches can be evaluated completely. Changing source program might not only affect the program structure and result in errors, but also be hard to implement automatically. To solve the problem, this paper presents an approach of test case generation based on combination of schema using particle swarm optimization. First, a definition called "schema" is presented for all the branches which are able to improve the fitness value, and the branch function of the schema is obtained, solving the problem of partial evaluation. Then, a crossover is designed to place search on all the individuals which have the minimum value of branch function of the schema. The crossover views each schema as a whole and combines all the schemata into a single individual, as a result the crossover can not only prevent schemata destroyed in the process of evolution, but also improve the fitness value of individuals because of the combination. Furthermore, a local search strategy is used for the best particle in each generation in the process of test case generation. Experiments on some benchmark programs and open source programs are performed. The experimental results show that the proposed approach has obvious advantages in average coverage and generations comparing with other methods.