Abstract: Test data generation is a key component of combination testing. However, the complexity of test case generation problem for combinatorial testing is NP-complete. A kind of optimal test suite generation mechanism is proposed. It makes use of the encoding mechanism to map the combinatorial testing problem domain to a binary code space. And then a Genetic Algorithm（GA） is used to search this binary code space to find the optimal individual and generate the optimal test suite based on a decoding mechanism. Experimental results show this mechanism is simple and effective, and it has the characteristics of less producing test data and time consumption.

Key words: software testing, pairwise combinatorial testing, test case generation, genetic algorithm

摘要： 测试数据生成是组合测试的一个关键问题，但是组合测试用例集的构造问题的复杂度是NP完全的。提出了一种成对组合测试用例集整体优化和生成的方法。该方法通过编码机制将测试用例数据的生成问题转换为一个基于二进制编码的最优化问题，同时使用遗传算法对此编码空间进行搜索，并对所发现的最优个体进行解码，构造产生最佳测试用例集。实验结果表明，该方法简单高效，且具有解的质量高、时间消耗小的特点。

关键词: 软件测试, 成对组合测试, 测试用例生成, 遗传算法