论文部分内容阅读
覆盖表生成是组合测试研究的热点之一,其中贪心算法因为生成速度快,生成的覆盖表规模小而得到人们青睐。目前研究人员已经提出了很多基于不同策略的贪心算法,如AETG、TCG、DDA等,Bryce等将这类算法归结到一个统一的算法框架,这些已有方法不仅被包含在该框架中,而且从该框架又可以衍生出很多新的算法。Bryce等通过ANOVA工具来分析每个决策点对覆盖表规模的影响,但他们并没有给出具体有用的框架配置。因此怎样科学地配置和优化受六个决策点影响的算法框架,从而有效生成覆盖表仍是一个新的挑战。 本文针对影响该贪心算法框架的六个决策点,采用三种抽样方法,设计了pair-wise实验、Base Choice实验和爬山实验,形成一个增强型贪心算法来探索框架的最优配置,主要研究以下问题:1)算法框架下各个决策点的配置是否对其生成的覆盖表规模具有明显的影响?2)如果影响明显,是否存在最优配置,对于某些实例使用该配置总能生成规模较小的覆盖表?3)最优配置是否具有一定的普遍性,即利用该配置对其他实例能够生成较小规模的覆盖表?4)最优配置下的贪心算法和已有的AETG、DDA、TCG方法比较是否具有竞争力? 实验结果表明:1)算法框架下各个决策点的配置对其生成的覆盖表具有明显的影响;2)通过实验在某些实例中找出了最优配置,它能够生成较小规模的覆盖表;3)这些最优配置在多数情况下具有普遍性,能够生成规模较小的覆盖表,不过不是对所有实例都能生成最小覆盖表,要寻求框架的更优配置,可以针对某个待测系统,按照本文给出的增强型贪心算法进行探索;4)实验还将最优配置和已有算法AETG、TCG及DDA进行了比较,结果显示找出的最优配置是有优势的,在一些实例中略优于已有算法。