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

作     者：王燕 聂长海 钮鑫涛 吴化尧 徐家喜 WANG Yan;NIE Chang-Hai;NIU Xin-Tao;WU Hua-Yao;XU Jia-Xi

作者机构：南京晓庄学院信息工程学院江苏南京211171 计算机软件新技术国家重点实验室(南京大学)江苏南京210023 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2018年第29卷第12期

页      面：3665-3691页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(61272079 61321491 91318301) 教育部博士点基金(20130091110032) 

主　　题：基于搜索的软件工程 组合测试 覆盖表 禁忌搜索 并行化 

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