关键词: 软件测试, 测试场景, UML活动图, 遗传算法, 爬山法, 局部性

Abstract: Reducing cost of software testing is the essential issue in the study of software testing optimization. Genetic Algorithm（GA） is introduced into the software testing, 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. This paper presents the Hybrid Genetic Algorithm（HGA） in test scenarios generation based on Unified Modeling Language’s（UML） activity diagram, it contains genetic algorithm and hill climbing algorithm. This new algorithm accelerates the speed of generation of the test scenarios from the UML activity diagram, adding new members at the beginning of each operation of the hybrid genetic algorithm to avoid localized optimization. Experimental results show that the approach not only solves the localized optimization effectively but also greatly improves the efficiency of the generation of test scenarios compared with the simple genetic algorithm and reduces the software testing cost.

Key words: software testing, test scenarios, UML activity diagram, genetic algorithm, hill climbing, localized optimization