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

• 作者: 吴化尧 徐家喜 王燕 聂长海 钮鑫涛
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 基于搜索的软件工程 组合测试 覆盖表 禁忌搜索 并行化
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 系统软件与软件工程
• 页码范围: 3665-3691
• 页数: 27页
• 分类号: TP311
• 字数: 21851字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005369

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐家喜	南京晓庄学院信息工程学院	20	19	3.0	3.0
2	王燕	南京晓庄学院信息工程学院	10	33	3.0	5.0