基于改进粒子群的组合测试用例生成技术研究

发布时间：2018-10-15 12:31

【摘要】：组合测试作为一种基于规约的软件测试方法,旨在从待测软件面临的庞大组合空间中,选取少量但有效的测试用例,生成覆盖程度高、揭错能力强的测试用例集。但组合测试用例生成是NP难问题,需要在多项式时间内求解组合问题,因此需要采用元启发式搜索算法来解决该问题。相较于其他元启发式搜索算法,粒子群算法在覆盖表生成规模和执行时间上更具有竞争力。本文系统回顾和总结了利用粒子群算法生成组合测试用例集的已有研究成果,针对可变力度组合测试问题和粒子群算法的参数选取问题,将改进的one-test-at-a-time策略和自适应粒子群算法相结合,提出了一种可处理任意覆盖强度的组合测试用例生成方法。本文的主要研究工作和贡献概括如下:(1)针对实际待测软件中存在的约束问题,提出了一种类似于避免选择策略的方法对约束条件预先处理,在生成测试用例前时对无效的约束组合进行剔除,在一定程度上缩减需覆盖组合集的大小,避免了无效组合所引起的适应度值的误差。(2)针对one-test-at-a-time策略组合选取问题,提出了两种优先级度量方法:覆盖组合度量方法和因素取值度量方法,在生成单个测试用例的过程中,优先选取了权值最大的组合用于单个测试用例的生成,避免了原始算法存在的随机性和盲目性。(3)针对粒子群算法参数配置问题,分别对惯性权重、学习因子、种群大小和迭代次数4个参数进行合理的设定,使粒子群算法更加适用于覆盖表的生成。对于惯性权重,根据粒子的优劣对惯性权重进行自适应调整,以粒子与当前全局最优解之间的距离作为粒子优劣的评价标准;对于学习因子,提出了一种学习因子动态调整策略,使得学习因子随着不同的迭代过程进行改变;对种群大小和迭代次数进行深入探讨,针对组合集大小设定相应的取值。为验证本文所提出的改进策略的有效性,采用MATLAB编程实现本文提出的改进算法与原始算法进行实验对比,实验结果证明改进的算法在生成测试用例集规模和算法执行时间上具有一定的优势。
[Abstract]:As a kind of software testing method based on specification, combinatorial testing aims to select a small number of effective test cases from the huge combination space of the software to be tested, so as to generate a set of test cases with high coverage and strong error-detection ability. However, combinatorial test case generation is a NP problem, which needs to be solved in polynomial time. Therefore, meta-heuristic search algorithm is needed to solve the problem. Compared with other meta-heuristic search algorithms, PSO is more competitive in the scale and execution time of overlay table generation. This paper systematically reviews and summarizes the existing research results of generating combinatorial test case sets using particle swarm optimization algorithm, aiming at variable strength combinatorial testing problem and particle swarm optimization algorithm parameter selection problem. Combining the improved one-test-at-a-time strategy with the adaptive particle swarm optimization (APSO), a combined test case generation method, which can deal with arbitrary coverage strength, is proposed. The main research work and contributions of this paper are summarized as follows: (1) aiming at the constraint problems existing in the actual software to be tested, a method similar to avoiding the selection strategy is proposed to pre-process the constraint conditions. Before generating test cases, the invalid combination of constraints is eliminated, the size of the combination set to be covered is reduced to a certain extent, and the error of fitness caused by the invalid combination is avoided. (2) aiming at the problem of one-test-at-a-time policy combination selection, In this paper, two priority measurement methods are proposed: overlay combination measure method and factor value measure method. In the process of generating a single test case, the combination with the largest weights is selected first for the generation of a single test case. The randomness and blindness of the original algorithm are avoided. (3) aiming at the parameter assignment problem of particle swarm optimization, four parameters such as inertia weight, learning factor, population size and iteration times are set reasonably. PSO is more suitable for generating overlay table. For inertial weight, the inertia weight is adaptively adjusted according to the particle's merits and demerits, and the distance between particle and the current global optimal solution is taken as the evaluation criterion of particle's superiority and inferiority. A dynamic adjustment strategy of learning factors is proposed to change the learning factors with different iterative processes, and the population size and iteration times are discussed in depth, and the corresponding values are set for the size of the combination set. In order to verify the effectiveness of the improved strategy proposed in this paper, the improved algorithm proposed in this paper is implemented by MATLAB programming and compared with the original algorithm. The experimental results show that the improved algorithm has some advantages in generating the size of test case set and the execution time of the algorithm.
【学位授予单位】：浙江理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.53;TP18

【参考文献】