组合测试数据生成的交叉熵与粒子群算法及比较  

Test Data Generation Algorithms of Combinatorial Testing and Comparison Based on Cross-Entropy and Particle Swarm Optimization Method

作　　者：查日军[1,2] 张德平[3] 聂长海[2,4] 徐宝文[2,4] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]南京大学软件新技术国家重点实验室,南京210093 [3]南京航空航天大学信息科学与技术学院,南京210016 [4]南京大学计算机科学与技术系,南京210093

出　　处：《计算机学报》2010年第10期1896-1908,共13页Chinese Journal of Computers

基　　金：国家自然科学基金(90818027;60721002;60873050;60773104);国家"八六三"高技术研究发展计划项目基金(2008AA01Z143;2009AA01Z147);国家"九七三"重点基础研究发展规划项目基金(2009CB320703);上海市科委重点实验室基金(09DZ2272600)资助~~

摘　　要：测试数据生成是组合测试的一个关键问题.文中提出以数理统计为基础的交叉熵方法和以仿生学为基础的粒子群优化算法来生成两两组合测试数据,交叉熵方法采用最优选择概率产生测试数据,而粒子群算法则在可行解空间中搜索具有最优适应值的测试数据.文章给出了交叉熵方法最优选择概率的理论推导,并对两种算法所生成的测试数据集进行约简.将两种算法和现有的贪心方法、代数方法及其它启发式搜索方法进行比较,实验表明交叉熵方法和粒子群算法具有一定的优势和特点.Abstract The test suite generation is one of key issues of combinatorial testing. This paper uses Cross-Entropy method of statistics and Particle Swarm Optimization from bionics to generate pairwise test data of combinatorial testing. The cross-entropy method used the best selection probability to generate test data and the particle swarm optimization generates test data by searching one with best fitness in a feasible solution. A theoretical method is given for the opti- mal probability selection of the cross-entropy method and a reduction technique is proposed to re- duce the test suite generated by two methods. The empirical results show that the cross-entropy method and the particle swarm optimization have some merits compared with existing greedy al- gorithms, algebra methods and other heuristic search algorithms.

关 键 词：软件测试 组合测试 交叉熵 粒子群优化 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]