一种基于AP‑PSO算法的组合测试用例生成方法

摘要

本发明公开了一种基于AP‑PSO算法的组合测试用例生成方法，属于软件测试领域。本发明包括：通过静态分析获得需覆盖的组合级；调整one‑test‑at‑a‑time策略，将随机选取一个组合改为构造一个优先级度量函数，对每个组合进行优先级度量，选取优先级最高的组合；采用自适应粒子群算法生成单条测试用例，以种群粒子优劣为依据对惯性权重进行自适应调整，对粒子的最大速度进行控制，采用离散化方式对每个粒子的速度进行取整运算，并使用反射墙策略对粒子位置进行边界处理，防止飞出有效的搜索空间。本发明可适用于不同覆盖强度的覆盖表生成，有效缩减了组合测试用例集的规模，并大幅度提升了组合测试用例的生成效率。

说明书

技术领域

本发明属于软件测试领域，具体涉及一种基于AP-PSO算法的组合测试用例生成方法。

背景技术

软件测试是软件工程中保证软件质量的至关重要的环节，理想的软件测试方法需要同时具有高错误检测能力、低成本消耗和广泛的适用性等特点。组合测试作为一种基于规约的软件测试方法，旨在从待测软件面临的庞大组合空间中，选取少量但有效的测试用例，生成覆盖程度高、揭错能力强的测试用例集。

粒子群算法作为一种较新的启发式搜索算法，具有易理解、易实现、全局搜索能力强等特点，目前也被应用于该领域中。目前，在利用粒子群优化生成覆盖表的相关研究中，主要实现了两两组合覆盖测试用例生成，并未考虑更高覆盖力度以及交互力度不统一的情况。同时，参数的选取对算法性能有很大影响，绝大多数研究工作通常选取一组经验参数，没有考虑到参数选择在不同覆盖表上的特殊性。

因此，在粒子群算法具有良好的鲁棒性的前提下，将one-test-at-a-time策略和自适应粒子群算法相结合，根据粒子的优劣对惯性权重进行自适应调整，提出了一种可处理任意覆盖强度的组合测试用例生成方法。该算法能使该算法在覆盖表生成上具有更强的适用能力，在测试用例集规模和执行时间上均具有一定的优势。

发明内容

本发明的目的是对原始PSO算法进行改进，增加优先级度量函数和惯性权值的自适应调整策略，提供一种更加有效的组合测试用例生成方法。

本发明解决其技术问题所采用的技术方案如下：

定义：

测试用例——假设一个待测软件系统(SUT)受到n个独立因素的影响，这些因素形成一个有限集合F＝{f₁,f₂,…,f_k}，其中第i个因素f_i拥有l_i个可选取值，则其对应的有效取值集可表示为D_i＝{1,2,…,l_i}。那么，可以称n元组test＝(x₁,x₂,…,x_n)(x₁∈D₁,x₂∈D₂,…,x_n∈D_n)为SUT的一条测试用例。

固定力度覆盖表——CA(N；t,k,v)表示一个N×k的矩阵，每列可选取值个数为v，任意的N×t子矩阵包含了在v值域上的所有t元组。

可变力度覆盖表——VSCA(N；t,k,v,C)在CA(N；t,k,v)基础上，还满足包含一个或多个子矩阵C，并且C的覆盖强度大于t。

one-test-at-a-time策略：

在组合测试用例生成问题中，one-test-at-a-time策略由于其简单、有效、便于扩展等特点，成为应用最普遍的方法之一。固定力度组合测试和可变力度组合测试均被证实是一个NP-C问题，在使用one-test-at-a-time策略时，只能考虑使用多项式时间生成近似最优的测试用例，因此可将该策略与粒子群算法相结合用于覆盖表生成。该策略在组合集中采用随机选取的方式选取一个组合，并未考虑每个组合的优先级有所不同，若能选取更加有效的组合，可减少算法的迭代次数，使得算法的时间性能有所提升。因此，有必要构造一个优先级度量函数，用于度量每个组合的优先级。

粒子群算法：

该算法是采用一群随机粒子来模拟鸟集体飞行觅食的行为，通过集体的协作来达到最优目的，最早由Eberhat和kennedy于1995年提出。该算法将优化问题在搜索空间中的可能解表示为粒子在n维空间中的位置，通过粒子速度控制粒子飞行方向和距离，粒子i的速度和位置分别用V_i＝(v_i,1,v_i,2,…v_i,n)和X_i＝(x_i,1,x_i,2,…,x_i,n)来表示。该算法采用迭代的方法，在解空间中追随自身的最优粒子(pBest)和整个种群的最优粒子(gBest)来不断搜索，直到找到最优解或有效解。采用适应度函数fitness(p)来度量粒子的优劣，其返回值为测试用例p所能覆盖的组合数目。在第t次迭代中，每个粒子的速度和位置更新公式如下：

v_i，j(t+1)＝wv_i，j(t)+c₂r₂[gBest_i,j(t)-x_i，j(t)]+c₁r₁[pBest_i,j(t)-x_i，j(t)]

x_i，j(t+1)＝x_i，j(t)+v_i，j(t+1)

其中，v_i,j表示第i个粒子在第j维的速度，x_i,j表示第i个粒子在第j维的位置；w为惯性权值，表示粒子的历史速度对当前速度的影响；c₁和c₂为加速因子，分别表示粒子对自身历史最优和整体历史最优的学习能力；r₁和r₂是在[0,1]范围内服从均匀分布的两个随机数，用于保证种群的多样性。

附图说明

图1是改进的one-test-at-a-time策略的流程图。

图2是自适应粒子群算法的流程图。

图3是本发明基于AP-PSO算法的组合测试用例生成方法的总体流程图

具体实施方式

下面结合附图并通过具体实施方式来进一步描述本发明。

如图1-3所示，本发明所述的组合测试用例生成方法，将one-test-at-a-time策略与自适应粒子群算法相结合，提出了一种优先级度量函数和惯性权值自适应调整策略，用于组合测试用例生成，包括如下步骤：

步骤1：分析实际问题，计算因素个数n及每个因素的取值范围D_i＝{1,2,…,l_i}，并通过分析约束条件和覆盖强度，获得需覆盖的组合集S。

步骤2：根据优先级度量函数r_k计算每个组合的优先级，确定权值最大的组合c：

其中，r_k表示第k个组合的权值，c_i表示组合集中第i个组合，t_k表示组合c_k所

对应的一条缺省的测试用例，s表示组合集中所包含的组合数,P(cb_i,t_k)用于度量t_k是否包含cb_i。

步骤3：将组合c作为输入值，组合c可对应于一条仅有部分取值确定的测试用例，采用自适应粒子群算法给缺省的参数选取合适的取值；根据粒子的当前状态来对每个粒子的惯性权重进行自适应调整，得到覆盖组合数量最多的单条测试用例，存入测试用例集TS中；从组合覆盖集中剔除已覆盖的组合，得到新的组合覆盖集。具体步骤为：

步骤3.1：设定种群大小m，初始化每个粒子的位置矢量X_i和速度矢量V_i。

步骤3.2：计算每个粒子i的适应值fitness(X_i)，其返回值为粒子位置X_i在需覆盖组合集S中所能覆盖的组合数目。

步骤3.3：更新每个粒子i目前为止的自身最佳位置pBest_i和整个种群的最佳位置，根据适应值来确定，适应度值越高则粒子越优。

步骤3.4：根据粒子的优劣对惯性权重进行自适应调整，以粒子与当前最优粒子(gBest)之间的距离作为粒子优劣的评价标准。由于组合测试问题属于离散型组合优化问题，相较于欧式距离，采用曼哈顿距离进行距离度量更加适合,已知两个向量X＝{x₁,x₂,…,x_m}和Y＝{y₁,y₂,…,y_m}，两者的曼哈顿距离可表示为：

运用上述公式可计算出每个粒子i与最优粒子gBest之间的距离，为更好的度量粒子的优劣程度，进一步定义一个f值用于衡量粒子X_i与最优粒子之间的差异程度：

其中，MaxDist表示当前种群中距离当前最优粒子gBest的最大距离。f(X_i)值越大，表示粒子X_i与最优粒子之间的差异越大，应该增大惯性权重，提高粒子的全局搜索能力以便更快地找到最优解；反之，则需缩小惯性权重，提高粒子的局部搜索能力使其能够对周围进行细致的搜索。因此，建立符合上述规则的惯性权重调整模型：

其中，w_max,w_min分别表示初始化时惯性权重的最大值和最小值，根据上述公式可得到惯性权值w_i的取值。

步骤3.5：根据下述公式更新每个粒子的速度，并设定一个最大速度来限制粒子的速度，采用每个维度所对应因素取值范围的一半作为最大速度限制，即粒子的速度区间为[-l_j/2,l_j/2]。

v_i，j(t+1)＝wv_i，j(t)+c₂r₂[gBest_i，j(t)-x_i，j(t)]+c₁r₁[pBest_i，j(t)-x_i，j(t)]

步骤3.6：更新粒子位置x_i,j(t+1)＝x_i,j(t)+v_i,j(t+1)，并对其进行取整运算，使其符合离散组合问题，并按照反射墙策略进行边界处理，防止粒子在更新过程中飞出有效的搜索空间。即当粒子超越某一维边界时，使用反射墙策略公式h(x_i,j)对粒子进行反弹：

步骤3.7：重复步骤3.2～3.6，直到达到预设的最大迭代次数，返回最优粒子gBest，更新组合测试用例集TS(t+1)＝TS(t)∪{gBest}。

步骤4：计算最优粒子gBest所包含的组合s，剔除已覆盖的组合，得到新的组合覆盖集S(t+1)＝S(t)-s。

步骤5：重复步骤2～4，直到组合覆盖集S为空，输出测试用例集TS。

为了验证本发明的有效性，将优先级度量函数分别与原始粒子群算法和自适应粒子群算法相结合，采用MATLAB编程实现与之对应的P-PSO算法和AP-PSO算法，将该两种算法与PSO算法进行实验对比。本发明采用15个具有代表性的实例用于实验分析，涉及到覆盖矩阵、混合覆盖矩阵和可变力度覆盖矩阵各5组实例。

表1实验采用的15个覆盖表

由于粒子群算法中存在随机因素的影响，故在实证研究中，针对每组实验数据均独立运行20次，取其平均值作为对比数据。算法的参数设置为：种群大小m＝100，迭代次数n＝600，学习因子c₁＝c₂＝2。

表2 PSO、P-PSO和AP-PSO算法的比较

表2从测试用例集规模和算法运行时间这两个方面，给出了三种算法针对15个实例生成测试用例集的效果。从测试用例集规模上看，除较为简单的覆盖表CA1外，P-PSO算法和AP-PSO算法均优于PSO算法，尤其是对于较为复杂的覆盖表具有明显的优势，例如CA5、MCA9和MCA10等。对比P-PSO算法和AP-PSO算法，两者在测试用例集规模上无明显差距，由此得出，本发明提出的优先级度量函数对缩减测试用例集规模有一定的效果。

从时间性能上看，AP-PSO算法略优于PSO算法，P-PSO算法相较于PSO算法和P-PSO算法，除CA1、VSCA11和VSCA14外，均具有较为显著的优势，其节约的时间达到16％～63％。由此可见，本发明提出的自适应策略可有效缩减算法执行时间。

综上所述，本发明提出的改进算法相较于原始粒子群算法，在生成测试用例集规模和算法执行时间上具有一定的优势。