基于多目标粒子群算法的测试用例优先级排序研究

发布时间：2018-01-11 21:24

本文关键词：基于多目标粒子群算法的测试用例优先级排序研究　出处：《西南大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着社会信息化步伐的加快,计算机软件在各行各业发挥的作用越来越大,软件的质量也受到越来越多的关注。软件测试贯穿软件的整个生命周期,是保证软件质量的重要方法和有效手段。由于客户需求的变更,软件规模的增大,软件更新换代速度的加快等原因使回归测试用例集规模越来越庞大,也使回归测试的工作量急剧增加。受人力、时间等回归测试成本的限制,传统的回归测试方法很难胜任现在的回归测试任务。因此,如何提高回归测试效率成为了广大研究人员关心的问题,其具有非常重要的研究价值和现实意义。研究人员就如何提高回归测试效率提出了很多方法,主要包括测试用例选择、测试用例集约简和测试用例优先级排序。其中,前两种方法要对测试用例进行修改或删除,这些不可逆的操作可能会遗漏能够发现错误的测试用例。本文主要针对测试用例优先级排序技术进行深入研究。通过分析当前国内外测试用例优先级排序的研究现状,提出一种基于多目标粒子群算法的测试用例优先级排序框架,并对如何克服粒子群优化算法自身的不足进行了研究。以前的多目标测试用例优先级排序大多是采用对多个优化目标进行加权求和后再排序的方法,该方法权值分配受人的主观思想影响大,不够智能。基于进化算法进行搜索的方法比较可行,但进化算法本身的交叉和变异机制比较复杂,在遇到大规模问题时效率有所下降。本文设计了一种基于多目标粒子群算法的测试用例优先级排序框架,选用APSC和EET作为优化目标。针对多目标测试用例排序的具体情况,设计了粒子的编码方式。由于标准粒子群优化算法是基于连续空间进行搜索的,而二进制离散粒子群优化算法的编码方式和映射机制比较复杂,它们都不适合用于多目标测试用例排序,对此本文提出了一种在离散空间进行搜索的方法。在非支配排序方式上,为降低算法的时间复杂度,只选择被支配数为0的解。粒子群优化算法的优点很多,但是它的不足之处是容易陷入局部最优。对此,本文提出一种基于Additional策略的全局极值动态调整算法,从而引导粒子群朝着优秀解的方向飞行。Additional策略是一种典型的贪心算法,它的特点是具有反馈机制。在更新全局极值之前,采用Additional策略的思想比较个体极值与全局极值的优劣。即把已排序测试用例覆盖的语句行去掉后再计算个体极值和全局极值的语句覆盖率,然后结合执行时间比较个体极值和全局极值的优劣,选择更好的作为新的全局极值。通过该方法动态地更新全局极值,引导粒子群的搜索方向,从而避免粒子群陷入局部最优。最后选取SIR库中的程序用于对比实验。通过比较不同方法之间的Pareto最优解集的分布和测试用例优先级序列的APFD值,验证了本文所提方法能够获得更优的Pareto最优解集和较高的错误检测速率。
[Abstract]:With the acceleration of the pace of social informatization, computer software plays a more and more important role in various industries, and the quality of software is paid more and more attention. Software testing runs through the whole life cycle of software. It is an important method and effective means to guarantee the quality of software. Because of the change of customer demand, the increase of software scale and the speed of software renewal, the scale of regression test case set becomes larger and larger. Because of the limitation of manpower and time, the traditional regression test method is difficult to do the task of regression test. How to improve the efficiency of regression testing has become a concern of the majority of researchers, which has very important research value and practical significance. Researchers have put forward a lot of methods on how to improve the efficiency of regression testing. It mainly includes test case selection, test case reduction and priority ranking of test cases. Among them, the first two methods need to modify or delete test cases. These irreversible operations may omit test cases that can find errors. This paper mainly focuses on the test case priority ranking technology. Through the analysis of the current domestic and foreign test case priority ranking research. The status quo. A test case priority ranking framework based on multi-objective particle swarm optimization is proposed. And how to overcome the shortcomings of particle swarm optimization (PSO) algorithm is studied. Most of the previous multi-objective test cases priority ranking is based on the weighted summation of multiple optimization objectives before sorting. The method is not intelligent enough because of the influence of subjective thoughts. The search method based on evolutionary algorithm is feasible, but the crossover and mutation mechanism of evolutionary algorithm itself is complex. In this paper, we design a test case priority ranking framework based on multi-objective particle swarm optimization algorithm. APSC and EET are chosen as the optimization targets. According to the specific situation of multi-objective test case sorting, the particle coding method is designed. Because the standard particle swarm optimization algorithm is based on continuous space search. However, the binary discrete particle swarm optimization algorithm is not suitable for multi-objective test case sorting because of its complexity in coding and mapping mechanism. In this paper, we propose a search method in discrete space. In order to reduce the time complexity of the algorithm, we only choose the solution with the dominant number 0. The particle swarm optimization algorithm has many advantages. However, it is easy to fall into local optimum. In this paper, a global extremum dynamic adjustment algorithm based on Additional strategy is proposed. Thus, it is a typical greedy algorithm to guide the particle swarm to fly towards the direction of excellent solution. Its characteristic is that it has a feedback mechanism, before updating the global extremum. The idea of Additional strategy is used to compare the advantages and disadvantages of individual extremum and global extremum, that is to say, the sentence coverage rate of individual extremum and global extremum is calculated after the sentence lines covered by sorted test cases are removed. Then combining the execution time to compare the advantages and disadvantages of individual extremum and global extremum choose better as the new global extremum. Through this method the global extremum is dynamically updated to guide the search direction of PSO. Finally, the program in the SIR library is selected for the comparison experiment. By comparing the distribution of the Pareto optimal solution set among different methods and the AP of the test case priority sequence, we choose the program in the SIR library to compare the distribution of the Pareto optimal solution set and the AP of the test case priority sequence. FD value. It is verified that the proposed method can obtain better Pareto optimal solution set and higher error detection rate.
【学位授予单位】：西南大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.53;TP18

【参考文献】