软件测试是保障被测软件质量的重要手段。但软件测试研究面临诸多挑战,例如被测软件制品的分析建模技术、测试充分性准则的设定、有效的测试用例生成技术、回归测试技术和变异测试等。组合测试作为一种重要的测试用例生成技术已经得到国内外学者的广泛关注。当完成对被测软件制品建模分析后,测试人员可以获得由因素和因素取值构成的实例,组合测试通过关注少数因素间取值组合的覆盖可以构造出小规模组合测试用例集,但最优组合测试用例集的构造已被证明为是一个NP难问题。本文系统回顾和总结了组合测试技术和应用的已有研究成果,针对组合测试中典型的成对组合测试和一些组合测试扩展问题进行了深入研究,提出了多种基于元启发式搜索技术的有效测试用例集构造算法。同时针对回归测试中的测试用例集约简问题,提出了一种基于测试需求间成对组合覆盖的约简算法。具体贡献可以概括为以下三个方面。(1)针对传统成对组合测试问题,本文提出一种基于粒子群优化的成对组合测试用例集构造算法。在生成单个测试用例时,尝试利用粒子群优化生成组合覆盖能力强的测试用例,并对搜索空间、适应值函数和启发式的合理设定进行了深入探讨。同时以上述单个测试用例生成算法为基础,提出两种不同的测试用例集构造算法,一种基于one-test-at-a-time策略,另一种基于类IPO策略。随后采用一个压缩算法对组合测试用例集做进一步的压缩。最后通过实证研究分析了算法框架内的不同设定对最终构造出的测试用例集规模的影响,并与已有的经典算法和工具进行比较来验证该算法的有效性。(2)针对组合测试扩展问题,本文将蚁群优化技术在传统成对组合测试问题上的应用进行扩展,使之可以有效构造基于优先级的组合测试用例集和可变强度组合测试用例集。具体来说,针对基于优先级的组合测试问题,本文采用one-test-at-a-time策略构造测试用例集,在构造单个测试用例时,提出四种不同的蚁群优化策略(AS、ASelite、ACS和MMAS)并针对该问题对其中的启发式设定进行了深入探讨,最后通过实例研究将这四种策略与经典的贪心策略WDA (Weighted Density Algorithm)进行了比较,同时也对这四种不同策略的具体执行效果进行了比较并验证了所提方法的有效性。针对可变强度组合测试问题,本文同样采用one-test-at-a-time策略来构造测试用例集,在构造单个测试用例时,采用ACS策略并针对该问题对其中的启发式设定进行了深入的探讨,随后采用一个压缩算法对组合测试用例集做进一步的压缩。最后通过实例研究与已有的经典方法和工具进行比较来验证该方法的有效性。(3)针对测试用例集约简问题,传统测试用例集约简算法仅考虑对单个测试需求的覆盖,这类方法一般会大幅度削弱约简后的测试用例集缺陷检测能力。本文通过考虑对测试需求间成对组合的覆盖,提出了一种轻量级的测试用例集约简方法PWIR。在实证研究中,采用Siemens套件中的实际C语言程序作为实验对象。最终结果显示该方法可以仅通过添加少量测试用例就可以有效提高约简后的测试用例集缺陷检测能力。