王曙燕, 张海清, 孙家泽

(西安邮电大学 计算机学院， 陕西 西安 710121)

组合测试[1]作为一种可以降低软件成本并提高其可靠性的测试方法，旨在从庞大的组合空间中选取少量而有效的测试用例集，使这些用例集覆盖所有组合集，从而完成软件测试任务[2]。

两两组合测试作为组合测试的一种，近年来已成为很多学者研究的热点，且已被证明是一种能有效解决组合用例爆炸问题的方法[3]。组合测试生成最小用例集是一个NP-hard问题[4]，主要研究方法有遗传算法(genetic algorithm, GA)[5]、蚁群算法(ant colony algorithm, ACA)[6]、粒子群算法(particle swarm optimization, PSO)[7]和模拟退火(simulated annealing-based, SA)[8]等启发式算法，以及K-均值聚类算法(K-means clustering algorithm，K-means)和K-medoids聚类算法(K-medoids clustering algorithm，K-medoids)等聚类算法。目前，粒子群算法、遗传算法和K-均值聚类算法应用较为广泛。基于K-均值聚类的组合测试用例生成优化算法[9]、基于粒子群优化和交叉熵(cross entropy, CE)生成组合测试用例的方法[10]和基于岛模型并行化的遗传算法(island parallel genetic algorithm based on Spark, IPGAS )[11]生成组合测试用例时，虽然可以生成更小规模的测试用例集，但随着软件系统输入参数的不断增加，消耗时长也会成倍增长[12]。

为了改善粒子群算法生成测试用例消耗时间过长的问题，本文提出一种并行化粒子群算法用于生成两两组合测试用例的方法。该方法主要基于大数据平台Spark[13]，采用one-test-at-a-time策略和自适应粒子群算法相结合的方式，将需要覆盖的所有两两组合测试用例集进行分组，并分发到集群中不同的节点上进行寻优操作；待所有节点寻优结束后，利用Spark的Collect()函数进行测试用例集的收集，并对收集后的测试用例集进行约简操作。……