《基于K-均值聚类粒子群优化算法的组合测试数据生成》由会员分享，可在线阅读，更多相关《基于K-均值聚类粒子群优化算法的组合测试数据生成（6页珍藏版）》请在金锄头文库上搜索。
1、 基于基于 K-K-均值聚类粒子群优化算法的组合测试数据生成均值聚类粒子群优化算法的组合测试数据生成摘要:在解决组合测试中的测试数据集生成问题时，粒子群优化算法(pso)在待测数据量增加达到一定程度以后，出现迭代次数增加、收敛速度减慢的缺点。针对该问题，提出了一种应用于组合测试数据集生成问题的基于 k .均值聚类的粒子群优化算法。通过对测试数据集合进行聚类分区域，增强测试数据集的多态性，从而对粒子群优化算法进行改进，增加各个区域内粒子之间的影响力。典型案例实验表明该方法在保证覆盖度的情况下具有一定的优势和特点。关键词:组合测试；粒子群优化算法； k .均值聚类算法；测试数据 test data
2、 generation based on k .means clustering and particle swarm optimizationpan shuo *, wang shu.yan, sun jia.zeschool of computer science and technology，xi an university of posts and telecommunications，xian shaanxi 710061, chinaabstract:to solve the problem of the test data set generation in combinator
3、ial testing, if the software under test has a great many factors and values, the traditional particle swarm optimization(pso)will have large iteration times and slow convergence velocity. a test data set generation method based on k .means clustering algorithm and pso has been proposed. the polymorp
4、hism of the test data set has been enhanced, though the clustering and partition the test data set. and it makes pso has been improved. the compact between the particles in each area has been promoted. the several typical cases show that this method has some merits with ensuring the coverage.to solv
5、e the problem of the test data set generation in combinatorial test, if the software under test has a great many factors and values, the traditional particle swarm optimization (pso)will have large iteration times and slow convergence velocity. a test data set generation method based on k .means clu
6、stering algorithm and pso has been proposed. the polymorphism of the test data set has been enhanced, though clustering and partitioning the test data set. and it makes pso has been improved. the compact between the particles in each area has been promoted. several typical cases show that this metho
7、d has some merits while ensuring the coverage.key words:combinatorial test; particle swarm optimization (pso) algorithm; k .means clustering algorithm; test data0 引言 软件测试作为软件质量保证的重要手段，在整个软件生命周期中占有重要的地位。而测试数据生成是软件测试过程中的重要环节，现代软件测试数据的数量庞大，若使用穷尽测试，则耗费大量的时间且效率低下。目前组合测试研究的焦点问题是生成数量少质量高的测试数据集合问题，即根据具体待测软件
8、，用尽量少的测试数据尽可能多地覆盖软件系统中的各个因素以及相应组合，以便在对软件系统的检测时发现系统中各个因素之间的相互作用对系统所产生的影响。 2002 年 kuhn 等 1研究了组合测试的可用性发现，大约 70%的软件故障是由一个或两个因素的相互作用引发的，因而研究两两组合覆盖测试具有重要的意义。近年来研究者使用贪心算法、代数分析法和启发式搜索算法解决组合测试数据生成问题。 2006年 microsoft 发布了工具 pict 是一种基于 one.test.at.a.time策略的，可以有效地按照两两组合测试的原理进行测试数据的设计；而后由 lei 等提出了逐因素扩展（in.paramet
9、er.order）的方式实现二维组合测试数据的生成，并且基于该方法开发了名为pairtest 的二维组合测试数据生成工具 2 ，该方法为以后的研究者进行多维的组合测试数据生成提供了新思路。 2009 年，mccaffrey 将遗传算法以及蚁群算法应用于组合测试数据集生成问题 3-4 ，将现代群体智能算法引入，对测试数据生成的时间效率和寻优能力上有了很大提高。2010 年查日军等 5提出组合测试数据生成的交叉熵与粒子群方法，该方法简单地使用了传统粒子群算法取得了一定的效果。近年来研究者将多种算法与粒子群优化算法相结合，对粒子群算法进行改进，例如将粒子群算法与遗传算法结合，粒子群算法与模拟退火算法
10、混合等等。这些算法对于传统粒子群优化算法的各个方面进行改进，以满足应用问题。本文将 k .均值聚类算法结合粒子群优化算法(particle swarm optimization, pso)应用于两两覆盖的组合测试数据集的生成，实验表明该方法对于组合测试数据集生成问题的迭代次数，以及收敛速度上具有优势和改善。 1 组合覆盖测试模型 假设影响待测软件（software under test, sut）的因素共有n 个,形成有限集合 f=(f 1, f 2, f n)，其中因素 f i在有限离散集合中包含 k 个可选取值，从而形成该因素的取值集合 x i(1in)，不妨设 x i=x i1,x i2
11、,x ik。称一个 n 元组 test=(x 1，x 2,x n)(x 1x 1,x 2x 1,x nx n)为 sut 的一条测试数据，相应的，称一个含有多个这样的 n 元组所构成的集合为sut 的一个测试数据集。 待测软件系统 sut 中任意两个因素对可以用二元关系矩阵a=(a i,j) kk 表示，其中，k 表示待测系统的 n 个因素的全部取值总个数，即因素集合 f 的各个因素取值个数相加和，对各个取值进行编号为 1,2,k，i,j 为各个取值的编号，a i,j 的值表示第 i 个离散值和第 j 个离散值覆盖对是否要覆盖，a i,j=1 表明第 i 个离散值和第 j 个离散值对需要覆盖，
12、a i,j=0 表明第 i 个值和第 j 个值对不需要覆盖，不需要覆盖的原因表示是同一因素内部的取值对，或者是组合对为已有组合对的逆转重复。 两两覆盖的组合测试数据集生成问题就是找到覆盖所有因素取值的两两组合对的规模最小的测试数据集, 在上述模型中找到覆盖二元关系矩阵 t=(t i,j) pp 所有两两组合对的规模最小的集合,以便在保证错误检测能力的前提下尽可能地降低测试成本。可以证明, 两两覆盖的组合测试数据集生成问题是一个 np.c 问题6 。在实际的测试中，人们一般都利用启发式算法、贪心算法和一些数学代数等方法近似求解。近几年，研究者将几种仿生物学的算法应用于生成两两组合测试数据集。本文在粒子群优化算法的基础上结合模糊 k.均 值聚类算法将算法应用于组合测试数据生成问题。算法在每次迭代过程中首先通过 k .均值算法把粒子群体分成若干个子群体，然后粒子群中的粒子根据其个体极值和子群中的最优粒子更新自己的速度和位置值。采用一次产生一个测试数据集的方法，从整体评价一个测试数据集的优劣来指导生成测试数据集。
