2018年外文翻译--基于进化策略的模因蚁群优化结构测试数据生成

《2018年外文翻译--基于进化策略的模因蚁群优化结构测试数据生成》由会员分享，可在线阅读，更多相关《2018年外文翻译--基于进化策略的模因蚁群优化结构测试数据生成（35页珍藏版）》请在毕设资料网上搜索。

1、中文17949  字，PDF英文16页，下载该文件将得到word中文，PDF英文摘要测试数据生成影响软件测试的效率和有效性，是软件测试的关键活动之一。由于手动测试数据生成效率很低，甚至不实用，因此实现了自动测试数据生成，以生成适当的输入数据子集，以便在合理的时间内进行有效的软件测试。该方法结合了（1+1）进化策略，以改进局部移动中蚂蚁的搜索功能并增强搜索利用。此外，我们还引入了一个新的信息素功能定义，它阻止蚂蚁选择程序的大部分覆盖路径来加强搜索探索。以分支覆盖率为覆盖准则，分别采用了两个适应度函数。第一个适应度函数是一个布尔函数，它被特别定义为最大化分支覆盖率。如果给定的解决方案至少

2、成功遍历一个尚未发现的分支，则输出一个；否则，返回零。第二个适应度函数是根据所覆盖分支的复杂性来制定的。对于布尔函数值等于1的解，不考虑第二个适应度函数的值。对于这些解，蚂蚁的决策过程仅仅是基于第一适应度函数进行的。实验结果表明，相对于现有的测试数据生成技术，我们的记忆ACO算法在分支覆盖率和收敛速度方面都具有优势。 关键词：自动测试数据生成；分支覆盖率；蚁群优化；进化策略；信息素追踪；适应度函数；      1 引言软件测试是软件开发生命周期中的一项重要活动。软件测试中的挑战之一是生成一组称为测试套件的测试数据，以使其满足特定的测试标准1-3

3、。不幸的是，这个过程通常是乏味和昂贵的。根据4,5，近50%的软件开发成本与测试有关。另一方面，自动化测试数据生成有可能显著减少软件测试时间和成本6。由于表示程序输入空间的数据量可能接近无穷大，因此需要开发一些方法来生成一个覆盖程序大部分的适当测试套件7。更确切地说，假设一个程序P，P的输入向量表示为x（x1，x2，xn），其中n是输入的数目，而xi是第i个输入参数。如果输入xi的域等于di，程序输入空间等于d=d1*d2dn。很明显，对具有如此多输入的程序进行详尽的测试是负担不起的，需要在给定的域内生成一个有效的测试套件。尽管它在套件中包含的测试数据数量（作为效率的标准）方面的大小较低，以允

4、许较低的测试执行时间，但生成的测试套件应该覆盖程序的更多部分（作为有效性的标准）。测试数据生成方法通常可分为两个不同的类，功能测试数据生成和结构测试数据生成810。在前者中，测试数据的选择只参考被测软件（SUT）的功能规范，而后者的测试数据则是根据SUT源代码的结构元素（如语句、分支、定义使用对和路径）来选择的。与功能测试相比，结构测试数据的生成对于程序中的故障检测更具成本效益，因此得到了广泛的应用和研究6。各种覆盖标准来评估生成的测试套件已经提出了。一些重要的内容包括语句覆盖率11、分支覆盖率12,13、路径覆盖率14、程序中特定路径的覆盖率7和程序中特定路径中特定节点的覆盖率7。这些覆盖率

5、标准可以通过程序的控制流图（CFG）来计算。其中，分行覆盖率是最具成本效益的。与分支覆盖相比，完全路径覆盖是劳动密集型的，对于循环图来说不可行11。另一方面，与简单性相反，语句覆盖不能用来测试代码中的错误条件。因此，大多数研究采用分支覆盖率作为覆盖标准11。随着软件系统规模的不断扩大和复杂性的增加，使用传统的自动化测试数据生成方法，如符号执行15和随机测试数据生成10具有挑战性且成本高昂。或者，基于搜索的软件测试（SBST）在相关文中得到了广泛应用16。SBST背后的主要思想是使用元启发式算法生成满足特定测试标准的测试套件10,17。问题搜索空间定义为一个元启发式算法的SUT输入空间，它的目标

6、是在合理的短时间内尽可能多的程序结构内找到能够覆盖的最小测试套件。这种方法首先从一个小的测试套件开始，然后在算法执行期间逐渐扩大，直到达到100%的覆盖率（相对于选定的测试标准）或达到最大迭代限制。包括遗传算法在内的各种元启发式算法（ga）1,13,1921，模拟退火算法（sa）22，Tabu禁忌搜索（ts）17,23、粒子群优化（PSO）24和蚁群优化（ACO）25已被用于测试数据生成。此外，基于遗传算法等全局搜索策略与局部搜索算子相结合的混合元启发式算法（MA）对测试数据的生成也很有效5,2629。本文针对结构测试数据的大部分分支，提出了一种基于记忆ACO的结构测试数据生成算法。该方法通过

7、在蚂蚁的局部行动中加入（1+1）进化策略，增强了蚂蚁的搜索利用。此外，一种新的信息素功能定义已经被引入，它阻止蚂蚁选择程序的大部分覆盖路径来帮助搜索探索。对于我们提出的算法，我们考虑了两个可靠函数。第一个函数是一种布尔函数，旨在最大化分支覆盖率。如果给定的解决方案成功地遍历至少一个尚未发现的分支，则该函数输出一个；否则，它返回零。第二个充分性函数是根据所覆盖分支的复杂性而形成的。复杂度是根据分支的嵌套级别和谓词类型来确定的，这两种类型都是分支可达性的良好指标25。对于布尔函数值等于一的解，我们不考虑二次函数的值。在这种情况下，蚂蚁对其相应解决方案的决策过程仅基于第一性函数进行。终止标准要么达到

8、全部分支覆盖范围，要么超过预先指定的迭代次数。实验结果表明，所提出的模因算法具有较高的覆盖率，同时在全局和局部移动之间进行平衡，有利于收敛速度的提高。我们可以从以下三个方面总结我们工作的主要贡献：将（1+1）-ES并入蚂蚁的局部移动中，而不是随机追踪它们以加强搜索利用。引入信息素追踪的新功能，以增强搜索探索。为了最大限度地扩大分支机构的覆盖面以及加快收敛到完全覆盖。论文的其余部分组织如下。第2节介绍了相关工作。第3节回顾了25用于测试数据生成，基于此我们开发了记忆算法。建议的方法在第4节中描述。第5节介绍了实验结果以及经验和统计分析和讨论。四个评价标准用于评价分支覆盖率和收敛速度。最后，第六部

9、分对本文进行了总结，并指出了今后的研究方向。2 相关工作有许多研究提出了元启发式优化算法的结构测试数据生成。Michael等人1开发了一种基于GA的测试工具，称为自动测试数据生成小工具。两种不同的遗传算法实现标准，其中每个输入都表示为一个位串和差分，这是基于实值输入表示。两种实现的目标都是确定一组满足条件决策覆盖范围的测试。要获得100%的决策覆盖率，计划中的每个决策必须至少获得一次所有可能的结果，而要获得100%的条件覆盖率，计划中决策中的每个条件必须至少获得一次所有可能的结果。由于这两种类型的覆盖都很重要，并且一种类型不能保证满足另一种类型，因此在实践中，通常将它们组合起来形成条件决策覆盖

10、9。将这两种算法分别与随机下降法和梯度下降法进行了比较。随机测试数据生成只包括随机生成输入，直到找到有用的输入。梯度下降基本上是通过对一个输入值进行连续的小改变来确定进行较大移动的良好方向。当找到适当的方向时，在该方向上采取越来越大的步骤，直到没有进一步的改善。在这种情况下，会修改不同的输入值，并且当无法对任何输入值进行更多的处理时，流程将终止。实验结果表明，标准遗传算法的实现优于其他三种算法（即差分遗传算法、随机算法和梯度下降法）。考虑到分支覆盖准则，Fraser和ARCURI（21）利用GA自动生成Java代码编写的类测试数据，开发了EvoSuxe测试工具。作为其他使用遗传算法自动生成测试

11、数据的研究，我们可以参考13,19,20,22。一些研究集中在开发基于单一解决方案的元启发式自动测试数据生成。Masnour和Salame14采用了SA，目的是最大化路径覆盖。为了定义适应度函数，首先将每个分支谓词重新定义为由两个操作数组成的相等关系。两个操作数的值之间的紧密性然后通过它们之间的汉明距离加权来测量。实验结果表明，以牺牲较长的执行时间为代价，SA的覆盖率略高于GA。D.I.Az等人17考虑到条件决策覆盖范围的限制，采用TS自动生成测试数据。将所提出的TS与随机测试数据生成技术进行了比较。结果表明，TS在覆盖率和测试数据生成时间方面均具有优势。哈曼和麦克明30使用爬山算法（HC）通

12、过考虑分支覆盖标准生成测试数据。适应度函数定义是两个度量的组合，包括接近级别和分支距离。接近级别是从测试数据覆盖的路径到达目标分支所需的最小分支数，并且给定分支谓词的分支距离是在将输入值分配给变量时与其真实性的偏差。为了避免陷入局部最优，在新的随机选择的起始点定期重新启动爬山算法，直到达到指定数量的可靠评估。最近一些研究使用计算群智能算法来自动生成测试数据。Windisch等人24提出了一种综合学习粒子群算法（cl-pso），其中每个粒子分别从不同的邻域中学习每个维度，具体取决于其分配的学习速率。如果对特定的迭代次数没有进一步的改进，则通过重新分配粒子重新启动算法。通过将分支距离与渐进高度相结

13、合，确定了与Harman和McMinn30相同的适应度函数。从分支覆盖的角度，对粒子群算法的优越性进行了实证研究。辛加尔等31提出了一种基于PSO和GA的混合方法，通过考虑两个数据流覆盖标准来自动生成测试数据，包括“定义计算使用”和“定义谓词使用”。为了在相应的数据流图中确定测试数据与目标节点的接近程度，他们在测试数据的确定值中添加了一个称为接近程度（cl）的值。提出的混合方法结合了粒子群算法和遗传算法的优点，使得分支覆盖率更高。MOA3通过最大化分支覆盖率，开发了一种协调搜索（hs）算法。通过考虑分支距离和分支权重来构造适应度函数，后者由每个分支的嵌套级别及其谓词类型确定。确定了每类谓词的分

14、支距离，并将其包含在适应度函数公式中（见第3.1节的表1）。根据谓词类型，我们指的是待评估的谓词类型，它由布尔谓词和算术谓词两种类型组成32。实验结果表明，HS的覆盖率高于SA和GA。各种研究都从经验和理论上研究了记忆算法在测试数据生成中的作用。Wang和Jeng26是第一个将遗传算法与爬山算法相结合，生成程序函数测试数据的人。研究表明，MA在个体应用时的表现优于GA和HC。Arcuri和Yao27采用与参考文献26相同的算法生成面向对象软件的测试数据，并通过实验得出了类似的结论。Liaskos和Roper28将遗传算法与人工免疫系统（ais）算法结合，作为局部搜索运算符。作者从经验上证明了混

15、合方法优于遗传算法；甚至在某些情况下，与更复杂的人工智能算法相比，与简单的局部搜索算子相结合更有效。Torres Jimenez和Rodriguez Tello29将遗传算法与基于SA的算法结合，作为组合测试的局部搜索运算符。Harman和McMinn33基于荷兰著名的模式理论34进行了理论分析，以确定哪种搜索类型（全局或局部）最适合给定类型的测试数据生成问题。他们还进行了大规模的实证研究，以验证他们的理论预测。他们的发现导致了对全局和局部混合技术的考虑。Fraser等人5指出，为了形成有效的测试套件，应该对原始值（如整数或双精度值）进行小的局部更改，以便执行某些目标结构。因此，他们通过使用几

16、个局部搜索操作符将进化测试扩展到一种记忆算法中。在12000个Java类上进行了广泛的实验，证明了他们提出的混合方法在最大化分支覆盖率方面的优越性。全局探索与当地开发相结合的效果不仅体现在软件测试数据生成中，还体现在各种应用中，包括机器学习及其相关问题35,36。例如，Qian等人35开发了一种结合局部搜索算子的进化双目标优化方法，用于集成剪枝，目的是最大限度地提高集成的泛化预测性能，最大限度地减少为预测选择的基础学习者的数量。从理论角度来看，分析表明，与单一的纯搜索策略相比，混合策略能够在更短的预期运行时间内接近全局最优37。Mao等人25最新的研究开发了一种记忆算法来自动生成测试数据，他开

17、发了一种基于ACO搜索的算法，该算法配备了一个随机的局部搜索操作符。这项工作是对参考文献3中作者先前工作的延伸，并与SA、GA和PSO三种元启发式方法进行了比较。实验结果表明，记忆ACO在生成测试数据方面明显优于SA和GA，与PSO具有可比性。3 测试数据生成的基本集群算法本研究的灵感来源于Mao等人基于ACO的方法25。重要的是要专门指定一个单独的部分来描述他们的工作。作者将基本ACO算法改为结构测试数据生成的连续版本，其中每个蚂蚁的位置代表一个测试数据。因此，与整个总体对应的解决方案形成一个测试套件。起初，蚂蚁随机分布在搜索空间中。对于每只蚂蚁，定义一个半径恒定的连续邻域。为了提高算法的搜

18、索能力，生成更为多样的测试输入，定义并应用了局部转移、全局转移和信息素更新三个步骤以及分支覆盖的可靠函数。在局部转移中，每只蚂蚁随机地在一个固定半径的相邻范围内移动，该固定半径是根据基准点的复杂性预先确定的。蚂蚁首先随机生成一个邻居解决方案，然后如果其性能优于旧的解决方案，或者保持在当前位置，则将其转移到此新位置。此程序将继续执行预先指定的次数。在全局转移中，如果满足一定的概率，那么相应的有效性低于平均值的蚂蚁将被随机转移到整个搜索空间中的一个新位置。否则，蚂蚁会经历一种称为偏颇探索的搜索过程。在这种类型的搜索中，信息素量较大的蚂蚁有较高的概率吸收其他蚂蚁在其周围进行搜索。作者将信息素结构定义

19、为与蚂蚁数量大小相同的实数数组。在每次迭代中，每个蚂蚁对应的信息素值与它产生的解的质量成正比，并相应地更新。最后，根据两个标准（包括分支距离和分支重量）定义了一个适应度函数，这两个标准将在下面描述。3.1适应性的定义给定分支谓词的所谓分支距离是当输入值分配给变量时偏离其真实性。Mao等人25根据参考文献中的定义测量分支距离3，8，10。表1显示了每种谓词的分支距离值。表中的值f（f>0）指的是一个常数，如果该项不是真的，则该常数总是加上。几种分支谓词的分支距离 3,8,10,25. 编号术语类型分支距离1Booleanif true then 0 else 2aif true

20、then 0 else f3a = bif abs(a  b) = 0 then 0 else abs(a  b) + f4a  bif abs(a b) 0 then 0 else f5a < bif (a b) < 0 then 0 else abs(a b) + f6a  bif (a b)   0 then 0 else abs(a b) + f7a > bif (a b) > 0 then 0 else abs(a b) + f8a  bif (a b)    0 then 0 else abs(a b) + f9a and bf (a) + f (b)10a or bMin(f (a), f (b)表1