组合测试是一种系统检测软件中由参数间相互作用所引发故障的软件测试方法。经过三十多年的发展,组合测试研究在测试理论和测试方法上已取得了很多成果,组合测试实践在工业界也获得了广泛关注。然而,当前的组合测试方法仍存在一些需要解决的问题:一方面,组合测试的成功应用依赖于高效的测试用例生成和优化方法,而基于搜索算法的测试用例生成仍存在巨大的改进空间,同时在测试用例优先级排序上则缺乏对切换成本的考虑;另一方面,目前在对组合测试故障检测能力的理解和认识上也仍存在着一定的局限。这些都限制了组合测试的进一步推广和应用。为了在实践中更加科学有效地使用组合测试方法,本文在系统回顾和总结组合测试已有研究成果的基础上,首先研究了基于搜索的组合测试方法,旨在使用高效的搜索算法来解决组合测试中的测试用例生成和优先级排序问题。同时,本文在不同的测试场景下评估了组合测试方法的故障检测能力,旨在帮助测试实践者更好地理解组合测试的适用范围。本文的主要贡献总结如下:1.针对组合测试的测试用例(覆盖表)生成,提出了一种新的离散粒子群算法DPSO,并在覆盖表生成上对粒子群算法进行参数调优。DPSO基于集合和概率特征重新定义了粒子的速度表示,并设计了相应的粒子演化算子,从而使得候选种群在组合覆盖空间中进行搜索,克服了传统粒子群算法在连续空间中进行搜索的潜在不足。实验结果表明,参数调优的粒子群算法在57%的情况下能生成比已有粒子群算法规模更小的覆盖表,而DPSO则能在74%的情况下显著优于参数调优的粒子群算法;DPSO同时还能增强已有的粒子群变种算法,并优于其它搜索算法,因此是一种颇具潜力的覆盖表生成的方法。2.针对组合测试的测试用例优化,提出了测试用例间切换成本的概念,并研究了存在切换成本时的测试用例优先级排序问题。测试用例间切换成本刻画了相邻两条测试用例执行时所需的环境重配置开销,为了找到能最快检测出所有故障的测试执行序列,提出并比较了基于单目标、混合目标和多目标的六种不同优化方法。在400个模拟模型和8个真实模型上的实验显示,基于旅行商问题的搜索算法能找到具有最小总切换成本的测试执行序列;而综合考虑组合覆盖和测试成本的混合目标和多目标优化方法能更好地对两者进行平衡,从而在测试中达到最高的故障检测率。3.针对组合测试的有效性,在不同测试场景下比较了组合测试、随机测试和自适应随机测试的故障检测能力,首次考虑了不同完整程度的测试模型以及不同检测难度的故障对组合测试有效性带来的影响。通过在9个真实待测软件的1683个测试场景下进行实验,发现三种测试方法趋向于在故障率相对较低时表现出不同的故障检测能力。组合测试在98%的场景下不差于另外两种测试方法;自适应随机测试优于随机测试,且能在96%的场景下和组合测试性能相当,但其生成开销在约束高度限制的测试模型下会达到组合测试的3.5倍。当测试模型中没有识别任何约束时,随机测试则更具成本效益;但若测试模型较完整时,则应优先使用系统化设计的组合测试或自适应随机测试方法。