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

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

Tabu Search in Covering Array Generation

Combinatorial testing can effectively detect faults caused by the interaction among the parameters of the system under test. In its 30 years of the development, covering array generation has been one of the key research areas, and relevant research articles have reached more than 200. As effective algorithms to generate covering arrays, existing tabu search algorithms have some advantages on the size of covering array, but there is still much room for improving the solution quality and calculation speed. Furthermore, the practical application of the existing algorithms is poor, because they can neither take account of constrains nor generate variable strength covering arrays. To solve the above problems, this paper proposes a new tabu search algorithm. Three improved aspects are presented. 1) The process of parameter tuning is divided into two stages:pair-wise and climbing to ensure that the optimal configuration is hit with a minimum number of configurations so as to further improve the size of covering arrays. 2) In order to improve the speed, the algorithm is parallelized. 3) Constrains and variable strength handling are added to make the algorithm adapt to various test scenarios. Experimental results show that the proposed algorithm has the advantage on the size of various covering arrays, such as fixed strength covering arrays, variable strength covering arrays and covering arrays with constraints. At the same time, the parallelization results in the increase of average speed of the algorithm by about 2.6 times.