Test Scenario Generation And Prioritization Method Based On Meta-heuristic Algorithm

Software testing is one of the vital techniques for maintaining high quality of the software and improving software reliability. With the wide application of software development based on UML and the process of the Rational Unified Process(RUP) development, software testing based on UML has gradually became the main research direction of the Model Based Testing. Search based software engineering problems can be transformed into optimization problems, which can be further solved by applying meta-heuristics. On the problem of generating and prioritizing test scenario based on UML activity diagram model, the most commonly used meta-heuristic technique is genetic algorithm(GA).GA is introduced into the scenario generation problem, which provides necessary impetus to get divergent test scenarios. However, the GA is time-consuming because of having a poor local search and slow convergent speed at later evolution process. And with the rapid growth in size and complexity of software, it is hardly possible to make exhaustive testing during the testing process. What's more, testing is required to discover maximum errors within limited time and money. So, test scenarios should be prioritized according to some requirements. Test scenarios prioritization aims to concentrate the testing effort upon those parts which are critical and complex.1) For the test scenario generation based on UML activity diagram, this paper presents the hybrid genetic algorithm(HGA), which contains GA and hill climbing algorithm. This method solve the problem of poor local search of the GA. And by adding new members at the beginning of each operation of the hybrid genetic algorithm to avoid precocious phenomenon. By comparing with the other method, this method not only solves the localized optimization but also improves the efficiency of the generation of test scenarios effectively and reduces the software testing cost.2) For the test scenario prioritization based on UML activity diagram, this paper presents the prioritization technique. First, activity diagram should be converted to the control flow graph. Then, by DFS traversing this graph and generating all possible test paths. At last, this paper prioritizes those path. The prioritization method combines genetic algorithm and particle swarm algorithm(PSO). This method solves the problem that the genetic algorithm can lose the information of the former because of the change of the population by using the memory ability of the PSO algorithm. And by comparing with the other method, this method not only can generate a critical test scenario that must be tested first, but also greatly improves the efficiency of the test scenario prioritization.3) Finally, some UML activity diagrams are used to illustrate the algorithm and Java language is used to verify the algorithm. The results show that the improved algorithm enhances the ability of processing activity diagram.