英语原文共 17 页，剩余内容已隐藏，支付完成后下载完整资料
一种用于生成覆盖阵列的离散粒子群优化方法
Huayao Wu, Changhai Nie, Member, IEEE, Fei-Ching Kuo, Member, IEEE,
Hareton Leung, Member, IEEE, and Charles J. Colbourn
摘要
软件的运行依赖于很多因素。组合测试(CT)的目的是生成小的测试用例集，以发现这些因素及其相互作用导致的缺陷。覆盖阵列生成问题是离散优化问题，是CT领域最热门的研究领域。粒子群算法是一种基于进化搜索的启发式算法，它成功地生成了具有规模优势的覆盖阵列。然而，目前的粒子群算法只是简单地将粒子的位置四舍五入到整数来处理离散搜索空间。此外，没有准则可以有效地为这个问题设置PSOs参数。本文将已有的离散粒子群算法(DPSO)——基于集合的粒子群算法(set-based PSO)推广到数组生成。提出了两种辅助策略(粒子重初始化和gbest的附加评估)来提高性能，开发了一种新的覆盖阵列生成DPSO。本文系统地给出了传统PSO(CPSO)和DPSO参数设置的准则。对现有的四种粒子群算法进行了离散扩展，以进一步研究粒子群算法在阵列生成中的有效性。实验表明，基于参数设置准则的CPSO能够获得更好的结果，而DPSO能够生成比CPSO以及其他进化算法更小的覆盖阵列。DPSO在覆盖阵列生成问题上是一种很有前途的PSO。
索引词：组合测试(CT)，覆盖阵列生成，粒子群优化(PSO)。
I．介绍
随着软件功能和运行环境越来越复杂，对于现代软件系统的测试也变得越来越昂贵。生成测试用例的关键问题是高效低成本地检测故障。
组合测试(CT)是一种常用的检测各种因素及其相互间作用而引起的故障的测试方法。CT方法以覆盖阵列为测试单元，在测试用例较少的大组合空间中进行采样，覆盖固定数量因素之间的不同交互作用。Kuhn和Reilly[2]的研究表明，对于某一软件，70%以上的故障是由一个或两个因素相互作用造成的，并且几乎所有的故障都可以通过检查六个因素之间的相互作用而检测出来。因此，CT在实践中是一种有效的方法。生成测试用例最少(最小规模)的覆盖阵列是CT中的一个主要问题。一般情况下，覆盖阵列的最小规模是未知的;因此，方法集中于以合理的搜索成本找到包含尽可能少的测试用例的覆盖数组。目前已有的许多方法可分为两类:1)数学方法 2)计算方法[1]。数学(代数或组合)方法通常利用一些已知的组合结构。根据搜索空间的大小，计算方法主要使用贪婪策略或启发式搜索技术来生成覆盖数组。在某些情况下，数学方法可以得到最好的覆盖阵列。例如，在实验设计中使用的正交阵列为覆盖阵列提供了大量可证明为最小规模的测试用例。然而，所有已知的数学方法只能应用于限制性因素集。这种限制也体现了计算方法的重要性。贪婪算法在生成覆盖阵列时是一种非常有效的算法，但其精度受到局部最优解的限制。近年来，基于搜索的软件工程(SBSE)一直致力于使用基于搜索的优化算法为软件工程问题寻找高质量的解决方案。受SBSE的启发，许多基于人工智能的启发式搜索技术被应用到软件测试中。例如，模拟退火(SA)[3] -[7]，遗传算法(GA)[8] -[10]，蚁群优化(ACO)[9]，[11]，[12]都被应用于覆盖阵列生成中。这些技术可以生成任何类型的覆盖阵列，并且可以轻松集成约束求解和优先级排序技术。它们的应用已被证明是有效的，在许多情况下能产生相对较小的覆盖阵列。粒子群算法是一种较新的进化算法，在[13]-[16]领域也得到了应用。该方法实现简单，初始化速度快。
传统的PSO (CPSO)算法最初是为了在连续空间中寻找最优解或近似最优解而设计的。然而，许多离散粒子群算法(DPSO)的算法和框架已经解决了[17]-[22]的离散问题。为了生成覆盖阵列，目前的离散方法[13]-[16]主要是简单地将粒子的位置四舍四入到整数，同时保持速度为实数。然而这些离散方法有两个主要的缺点。首先，PSO的性能受到其参数设置的显著影响。在[23]中，我们分析了一般参数选择和初始种群对PSO的影响，但是没有关于参数设置的准则来生成覆盖阵列。因此，需要清楚地了解如何设置这些执行参数。其次，简单的将位置四舍五入到整数会在搜索中产生大量错误。相反，需要一个专门的DPSO。由于目前的粒子群算法在生成覆盖阵列方面表现出了良好的效果，这两个主要缺点应该可以得到解决。
本文采用基于集合的PSO (S-PSO)[18]生成覆盖阵列。S-PSO利用集合论和概率论，提出了一种新的组合优化问题表示方案，并对演化算子进行了改进。我们在对S-PSO进行修改的过程中，提出了两种可以提高性能的辅助策略，并且提出了一种新的DPSO算法。DPSO具有与CPSO相同的概念基础，具有相似的搜索行为，参数扮演相似的角色。然后，我们探索CPSO和DPSO的最佳参数设置，以提高它们的性能，并确定推荐的设置。此外，由于许多CPSO变体[24]-[27]可以很容易地基于我们的DPSO扩展到离散情况，这些离散情况的性能也与它们的原始情况进行了比较。最后，我们将CPSO和DPSO与现有的GA和ACO[9]、[11]算法进行比较，生成覆盖阵列。
本文的主要内容如下。
1)基于集合表示，我们设计了一个S-PSO[18]版本，用于生成覆盖阵列。
2)提出粒子重初始化和gbest附加评价两种辅助策略，提高粒子群算法的性能。提出了一种生成覆盖阵列的分布式粒子群算法。
3)设计实验，探索生成覆盖阵列的CPSO和DPSO的最优参数设置。
4)我们对4个代表性PSO变体(TVAC[24]、CLPSO[25]、APSO[26]、DMS-PSO[27])的原始和离散模式进行了覆盖阵列生成效果的比较。
本文的其余部分组成如下。第二节给出了CT的背景，包括阵列生成和CPSO算法。第三节总结了有关工作。第四节给出了我们的DPSO算法，包括表示方案、相关算子和两种辅助策略。第五节评估了CPSO和DPSO的性能，并探讨了最优参数设置。第六节对CPSO、DPSO、原始变量和离散变量进行了比较。第七节将CPSO和DPSO与GA和ACO进行了比较。第八部分对本文进行了总结，并对今后的工作进行了展望。
II．背景
A．CT
假设被测软件(SUT)的行为由n个独立的因素控制，这些因素可以表示配置参数、内部或外部事件、用户输入等等。第i个因子具有个离散级别，从大小为的有限集Vi中选择一个n元组形式的测试用例,其中isin;对于所有的 1le;ile;n。
考虑一个简单的电子商务软件系统[15]。这个系统由五个不同的部分组成。这五个分量中的每一个都可以看作一个因子，其构造可以看作是若干个不同的层次。TABLE I显示了这五个因素及其对应的水平。在这个例子,n=5,
。
系统故障往往是由一些因素之间的相互作引起的，这些因素之间的相互作用可以用因素级别的组合来表示。为了检测这些故障，测试套件应该至少覆盖它们的组合一次。可以使用t-way模式来表示它们。
|
TABLE I E-COMMERCE SOFTWARE SYSTEM |
||||||||||
|
定义1(t-way模式):n元组(minus;,,hellip;,,hellip;)是t-way模式(tgt;0)当一些t因素固定水平和其他因素可以采取任何有效的水平,表示为“-”。
例如，假设factor Payment Server采用级别Master，而factor Web Server采用级别Apache，就会发生系统故障。要检测此故障，测试单元必须至少覆盖一次2-way模式(Master,-,Apache,-,-)。为了简化后面的讨论，我们使用每个因素的级别集中的索引来表示一个模式。例如，(0,-,1,-,-)用来表示(Master,-,Apache,-,-)。
穷举测试覆盖系统的所有n-way模式;在我们的示例中,它使用2times;2times;2times;3
times;3 = 72测试用例。随着因素和水平的增加，测试成本变得令人望而却步。此外，因为只有少数因素之间的交互才可能触发失败[2]，所以测试高速模式可能导致许多没有信息的测试用例。另一个极端是，如果我们只保证覆盖每个单向模式一次，那么只需要三个测试用例(一个测试用例最多可以覆盖五个单向模式)。但我们可能无法检测到一些涉及两个因素交互触发的故障。
相反，CT覆盖了所有t-way模式。这样的测试套件是t覆盖阵列，t为覆盖强度。t的值决定了覆盖的强度。这是CT的一个关键设置，应该由测试人员来决定。我们给出了一个精确的定义。
定义2(覆盖数组):如果一个Ntimes;N数组,其中N是测试用例的数量,具有以下特性:1)每一列i(1le;ile;n)仅包含集合中的元素并且=||；2)每个Ntimes;t子数组的行覆盖所有||times;||times;hellip;times;||的t列的组合至少一次,其中tle;n和1le;lt;hellip;lt;le;n,那么它就是一个t-way覆盖数组,用CA(N;t,n,(,
,hellip;,))。当==hellip;==，记为CA(N;t,n,)。
文献[2]表明，2覆盖阵列可以检测到70%以上的故障，而6覆盖阵列几乎可以检测到所有的故障。因此，利用CT，我们可以利用相对较低的强度覆盖阵列来检测系统的许多故障。换句话说，CT在保持较高的故障检测能力的同时，可以大大减小测试集的大小。
在表I的例子中，如果我们只考虑任意两个因素之间的交互，那么构建一个2覆盖数组只需要9个测试用例，而不是穷举测试所需的72个。表II显示了一个覆盖数组，其中每一行代表一个测试用例。此表涵盖与列对应的任意两个因素的所有可能的2覆盖。例如,考虑因素支付服务器和用户浏览器,所有2times;3 = 6模式, 表中可以找到(Master,-,-,Firefox,-),(Master,-,-,Explor-
er,-),(Master,-,-,Chrome,-),(VISA,-,-,Firefox,-),(VISA,-,-,Explorer,-),(VISA,-,-,Chrome,-)。
|
TABLE II COVERING ARRAY CA(9;2,) |
|||||||||||||||||||||||||||||||
|
