覆盖表生成的禁忌搜索算法

来源：软件学报杂志2018年第12期北京时间：

作者：王燕,聂长海,钮鑫涛,吴化尧,徐家喜

单位：王燕，南京晓庄学院 信息工程学院, 江苏 南京 21117111,聂长海，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21002302,钮鑫涛，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21002303,吴化尧，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21002304,徐家喜，南京晓庄学院 信息工程学院, 江苏 南京 21117105

摘要：组合测试可以有效检测待测系统中由参数间交互作用而引发的故障.在其30多年的发展过程中，覆盖表生成一直是关键问题之一，相关研究文献已达200多篇.作为一种有效的覆盖表生成算法，已有的禁忌搜索算法在所生成的覆盖表规模上具备一定的优势，但其解的质量和运算速度仍有提升空间；同时，这些算法实际应用能力较差，既不支持约束处理，也无法生成可变力度覆盖表.针对以上问题，提出了一种禁忌搜索算法.该算法从3个方面对已有的算法进行了改进：1）算法参数配置调优分pair-wise和爬山两阶段进行，确保使用较少配置条数最大程度击中最优配置，进一步提高算法生成覆盖表的规模；2）进行算法并行化，加速算法生成覆盖表的速度；3）增加约束处理和变力度处理，使算法可适应多种测试场景.实验结果表明，该算法在固定力度、变力度、带约束等多种类型覆盖表的规模上都具有一定优势，同时，并行化使算法平均加速2.6倍左右.

关键词：基于搜索的软件工程;组合测试;覆盖表;禁忌搜索;并行化

基金资助：国家自然科学基金（61272079，61321491，91318301）；教育部博士点基金（20130091110032）