改进组合适应度函数的测试用例自动生成技术在路径覆盖中的应用：APSO算法的实验验证.

沙特国王大学学报基于改进组合适应度函数Rashmi Rekha SahooSahoo，Mitrabinda Ray印度布巴内斯瓦尔，Siksha'O' Anusandhan大学ITER学院阿提奇莱因福奥文章历史记录：2018年12月29日收到2019年8月22日修订2019年9月17日接受在线预订2019年保留字：基于搜索的测试粒子群算法Apso关键路径分支距离改进的组合适应度函数A B S T R A C T测试用例生成是一个多目标问题，其目标是实现多个目标。在现有的工作中，重点是生成测试用例，以实现最大的路径覆盖。对于质量测试，关键路径的覆盖率比代码覆盖率更重要。本文的目的是生成测试用例，以实现最大的路径覆盖的挑战，覆盖关键路径，在可用的测试资源。在自动测试用例生成时，如果覆盖路径的概率低，则该路径是关键的。基于搜索的测试用例自动生成技术采用元启发式算法.适应度函数在搜索技术中起着重要的作用本文提出了一种适应度函数--改进的组合适应度函数（ICF），利用自适应粒子群优化算法（APSO）自动生成基于路径覆盖准则的测试用例。通过对三个著名的算例进行实验，发现粒子群优化算法（PSO）和APSO算法在已有的适应度函数、分支距离函数和分支距离与逼近水平相结合的情况下，虽然能给出最大路径覆盖率，但有时不能达到关键路径，而我们提出的ICF函数应用于APSO算法，在路径覆盖数方面有更好的效果©2019作者制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍测试用例生成在测试过程中有着重要的作用。手动测试过程消耗了软件开发过程的40为了克服手工测试耗时的缺陷，人们提出了各种自动化的测试用例生成方法。基于搜索的测试（SBT）是一种自动生成测试用例的方法它是基于搜索的软件工程（SBSE）的子领域使用搜索/元启发式技术的软件测试被称为基于搜索的测试（McMinn，2011）。各种Meta启发式技术，如遗传算法（GA）、粒子群优化、蚁群优化、禁忌搜索、布谷鸟搜索、爬山、模拟退火等，已成功应用于测试数据生成（Harman等人，2015; Roshan等人，2012年;Sahoo和Ray，2018年）。一个元启发式算法的搜索过程*通讯作者。电子邮件地址：rashmirekhasahoo@soa.ac.in（R.R. Sahoo）。沙特国王大学负责同行审查Rithm由适应度函数指导。适应度函数是一种数学函数，它为搜索空间中的每个解分配一个值以评估其质量（ Roshan 等人，2012;Harman等人，2015年）。在SBT中，适应度函数主要基于覆盖准则来制定。覆盖标准是用于测量被测软件被生成的测试用例执行得有多好的参数（Shahid等人， 2011年）。一些最常用的标准是语句覆盖率，分支覆盖率，决策覆盖率 -年龄和路径覆盖率（ Mall ，2018）。如果目标只是覆盖率的最大百分比，那么关键路径可能会被跳过，生成的测试用例是无效的。较少的覆盖率不会对测试用例生成质量产生太大影响，但关键路径的覆盖率会生成有效的测试用例。我们的目标是在可用的测试资源范围内覆盖关键路径在我们的方法中，我们定义的关键路径作为一个路径的覆盖率低的时候，自动生成测试用例 我们认为APSO用于自动测试用例生成，因为它平衡了探索和开发（Baresel等人，2002年），并避免过早收敛。为了覆盖目标分支/路径，大多数研究人员（Chen等人，2009; Gursaran，2012; thi等人， 2016）使用基于分支距离的适应度函数。分支距离是通过在目标节点缺失的分支节点中使用分支条件来计算的（Gursaran，2012）。仅分支距离值https://doi.org/10.1016/j.jksuci.2019.09.0101319-1578/©2019作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com480R.R. 萨胡，M。Ray/ Journal of King Saud University不足以实现目标路径。因此，启发式信息的近似程度与分支距离相结合，以更好地指导搜索空间。它告诉目标节点距离当前访问的节点有多远（Gursaran，2012）。这种组合拟合函数（CFF）在某些情况下也会失效，其中覆盖分支/路径的概率较低（Garg和Garg，2015 ）。从现有的工作（Chen et al ，2009; Garg and Garg，2015）中可以观察到，使用GA基于分支距离函数和组合函数的关键路径覆盖率没有给出良好的结果。本文提出了一种基于粒子群优化搜索的关键路径测试用例生成方法本文的搜索技术的新颖之处在于提出了改进的基于分支距离的适应度函数。第二部分介绍了关键路径及其分析的背景研究和基于分支距离的适应度函数。在第三节中，讨论了基于搜索的测试的相关工作，其中我们强调使用遗传算法和粒子群算法生成测试用例，并以表格形式给出了相关工作的聚类视图。第四节提出了实现目标路径的适应度函数，第五节解释了实现适应度函数的材料和方法。第6节讨论了使用粒子群算法和具有ICF函数的APSO算法对关键路径覆盖的实验结果，并与现有的拟合函数进行了比较。第7节介绍了对所提出方法有效性的各种威胁。结论和未来工作见第8。2. 背景针对三角形分类和余项计算问题，分析了关键路径及其关键程度。三大战略;并结合实例讨论了分支距离、逼近水平以及两者的结合作为适应度函数应用于粒子群优化算法中的问题。2.1. 关键路径分析在路径覆盖测试中，生成测试用例以执行每条路径至少一次，以发现路径内的故障。首先，通过使用圈复杂度（CC）度量确定线性独立路径的数量（Mall，2018）。为了生成CC，生成中间图，源代码的控制流图（CFG）。然后，通过应用以下McCabe CC公式（Mall，2018）从源代码的CFG计算CC。V= E- N= 2;其中，E = CFG中的边数N = CFG中的节点数在本文中，三个基准的案例研究被认为是和所选择的路径的测试用例生成进行了分析。虽然三角分类问题是一个小程序，但要实现100%的路径覆盖率是一个复杂的任务。下面解释具有路径关键性的三角形分类问题2.1.1. 三角形分类程序这个程序以三条边作为输入，并显示这是否是一个不等边，等腰，等边或不是三角形。图1（a）示出了TCP的源代码，图1（b）示出了其对应的用于生成线性独立路径的CFG。以下四条线性独立的路径是从三角形分类CFG中获得的。使用以下CC公式进行验证。V- 10图1a. Matlab中的TCP源代码。图1b. 图中的CFG。1（a）路径1：1路径3：1路径4：1在测试数据的三角形的每一边的范围[1，3]中，我们在范围[1，3]中生成a，b和c的测试数据的概率为零，这是最低的概率。虽然在指定的范围内得到不等边三角形的概率最小，但我们当值域的上界> 3时，得到不等边三角形的组合关键路径的概率低于其他路径，但应大于零。对于零概率，路径是不可行的。在这个例子中，图。图1（b）中，通向等边三角形的路径4被认为是关键路径，由于得到等边三角形的概率最低，等边三角形的概率（P）= |E|/|S| = 4/64 = 0.0625。TCP只需要选择结构。 在另一个案例研究中，其余部分计算（无使用司和模R.R. 萨胡，M。Ray/ Journal of King Saud University481除法运算符）程序（Sthamer，1995），我们考虑选择以及重复（循环）结构。2.1.2. 余值计算程序RCP程序的一个代码段及其CFG如图所示。 2a. 如图在图2（b）中，包含节点3和5的路径2和3具有被遍历的最低概率，因为这些节点仅在为输入a和b生成的测试数据值为零时被遍历。假设输入范围为[0，±20000]，覆盖路径2/路径3的概率为P = 1/40001 = 0.00002499因此，我们认为路径2和路径3是关键路径，因为它们比给定图中的其他路径具有最小的概率。2.1.3. 单源最短路径我们的第三个案例研究是Dijkstra的单源最短路径（Chen等人，2004）算法。这是一个线性复杂问题。这个程序包含六个条件语句和六个循环，有30条路径要覆盖。2.2. 适应度函数我们讨论了在我们的工作中使用的PSO和APSO的各种类型的适应度函数。研究人员（Baresel等人，2002; Chen等人，2009）提出了三种算法：（i）基于分支距离的适应度(ii)基于近似水平的适应度和（iii）组合适应度，以生成代码覆盖率的测试用例。2.2.1. 基于分支距离的适应度方法分支距离是根据条件节点的测试数据计算的（Korel，1990）。 它确定测试数据的距离或接近程度为了根据要求满足条件（真/假）（Chen等人， 2009年）。基于Korel的分支距离函数评估分支条件目标路径的分支距离是三个分支距离之和，如图所示。3 .第三章。2.2.2. 基于近似水平（AL）的适应度方法近似水平评估个人通过控制的执行部分达到目标的程度图2a. RCP在Matlab中的代码段。结构（Chen等人，2009; Thi等人，2016年）。它是通过计算在执行目标路径时测试用例未遍历的分支节点的数量来确定的。TCP的每个条件节点的AL如图4所示。因此，应尽量减少近似水平。2.2.3. 组合适应度函数Wegener等人（2001）提出了一种结合上述两种方法的组合方法。在组合适应度函数中将小的固定值添加到分支距离（Chen等人，2009年）。测试用例的适用性，t：适应度（t）=归一化分支距离（NBD）+近似水平（AL）NBD = 1-（1.001）-距离（Wegener等人，2001），NBD在范围[0，1]内。3. 相关工作研究基于搜索的测试数据生成。路径覆盖是基于代码的测试的主要标准在这里，我们专注于基于分支/路径的代码覆盖主要使用GA和PSO搜索算法，分支距离为基础的适应度函数。Pachauri和Mishra（2015）提出了一种基于相似性的分支距离适应度函数，使用GA进行分支覆盖。实验结果表明，在搜索过程中的覆盖率显着提高Chen等人（2009）比较了两种适应度函数，即分支距离和扩展汉明距离与GA覆盖目标路径，他们发现分支距离适应度比SIMILARITY更有效地生成目标路径的测试用例Garg和Garg（2015）提出了扩展水平分支（ExLB）适应度函数，用于使用简单遗传算法（SGA）和混合遗传算法（HGA）进行基本路径测试。虽然HGA使用ExLB函数提供了更好的覆盖，但它无法覆盖目标路径。Papadhopulli和Meçe（2016）使用GA和一个建议的适应度函数，该函数结合了分支距离，接近水平和对象状态来指导搜索过程以测试Java类。建议的适应度函数有相对增加的平均突变得分和平均测试套件的大小相比，原来的适应度函数。Jiang等人（2018）提出了一种使用GA生成数据流测试数据的进化方法他们首先减少定义使用对（DUP）应用约简算法，然后使用GA生成测试实验结果表明，该方法减少了测试用例，不影响覆盖率。所有这些方法在同一时间覆盖一个单一的目标。提出了一些方法来克服这个空白，使用搜索技术，以涵盖多个路径的时间。Liu等人（2019）提出了一种分散搜索策略，结合基于搜索的算法 （ GA ， PSO ， 差 分 进 化 （ DE ） ） ， 以 覆 盖 自 然 语 言 处 理（NLP）程序的所有可能路径。NLP需要特殊的值来覆盖路径，因为它将字符串作为输入。他们的测试结果表明，所提出的方法通过快速覆盖路径消耗更少的运行时间。Arcuri和Fraser（2014）提出了一种使用GA的整体套件（WS）生成方法，其中他们同时生成所有测试用例，Annibale Panichella et al. （2018）提出了多目标求解器，动态多目标排序算法（DynaMOSA），一次覆盖多个目标路径。在非决定性排序遗传算法（NSGA）中，以分支距离和接近度作为适应度结果表明，DynaMOSA在语句、分支和变异覆盖方面优于WSA和MOSA，但它们在覆盖时没有考虑执行时间和内存消耗。482R.R. 萨胡，M。Ray/ Journal of King Saud University图2b. 图中的CFG。2（a）.图三.图中三个条件节点的目标路径的分支距离。1（a）.一次有很多目标Lv等人（2018）提出了结合变形关系的PSO算法来生成多路径的测试用例。他们的目标是通过在一次运行中覆盖多条路径而不是几次运行来使自动生成过程具有成本效益 Zhu等人（2017）提出了一种改进的分组策略，通过在基于搜索的软件测试中贡献并行执行，使用GA覆盖多条路径。收集同一组中目标路径的共同约束，测试数据的搜索空间采用该策略，收敛速度加快，提高了搜索效率。这些工作主要集中在覆盖多条路径上，而不是关键路径上。在我们的方法中，我们专注于关键路径，并自动将多条路径覆盖到目标路径上，这是耗时较少的。表1显示了使用分支距离适应度函数的基于搜索的测试工作的比较研究。当我们提出一个R.R. 萨胡，M。Ray/ Journal of King Saud University483×见图4。图1的目标路径的近似水平1（b）.修改版本的分支距离函数，我们比较的工作与我们的工作。相关的工作分为两组，工作提出了改进的分支距离为基础的适应度函数和工作使用现有的分支距离函数与改进的元启发式算法。此外，它是由他们的工作类型，如测试用例生成单路径或多路径（见表2）。4. 测试用例生成提出了一种改进的组合适应度函数，并将其与粒子群算法和自适应粒子群算法相结合首先，通过对ICF函数的逐步评估，说明了基于适应度函数的粒子群优化算法.最后给出了算法在TCP的问题。我们提出的方法生成测试数据的步骤如图所示。 五、如图5所示，给定源代码的CFG和路径测试覆盖标准的概率是该方法的输入。从CC得到的线性无关路径集合中，根据概率论选择关键路径。ICF适应度函数是基于路径覆盖准则建立的。将该适应度函数应用于粒子群优化算法和自适应粒子群优化算法。初始测试数据是随机生成的，测试数据的适应度是通过执行仪表化程序来计算的。根据适应度值对生成的测试数据进行优化，最终得到覆盖关键路径的最佳测试数据。下面解释使用PSO算法和ICF的测试用例生成。4.1. 基于ICF函数的伪代码的的PSO与ICF如下：在图。 C1和C2是加速系数。至于APSO，在速度计算方程中只修改了惯性权重w为w = wMax-[（wMax-wMin）iter]/maxIter，其余算法与PSO相同。TCP案例研究中ICF功能的评价说明如下。4.2. 改进的组合适应度（ICF）函数测试用例自动生成的目标是为覆盖率很低的路径生成测试用例。在这种情况下，自动生成测试用例是非常困难的，因为这样的测试数据是非常少的，在一个广阔的范围内。这是非常需要指导搜索过程，以获得这样的解决方案（测试数据）。在我们的方法中，不是增加近似水平，表1比较研究（对相关工作的全面看法）。新奇作者（年份）目的搜索技术结果话改进的基于分支距离的适应度函数Lv等人（2018）Jiang等人（2018年）使用变形关系使用所有定义-PSOGA比现有分支距离函数更高的成功率和平均评估次数减少的DUP不影响覆盖率提出了一种改进的基于分支距离的适应度函数。分支距离和接近水平是共同的，在他们提出的适应度功能尽管他们的Papadhopulli和Meçe覆盖覆盖所有的树枝GA更好的结果显示，性能比（2016）; Arcuri和Fraser（2014）帕乔里和米什拉生成测试用例GA与现有分支距离功能虽然明显更好现有的功能，但有时无法覆盖目标路径。（2015）; Garg和Garg（2015）;Chen et al.（二零零九年）单目标路径覆盖覆盖范围比与现有的适应度函数，改进Liu等人（2019）; Zhu等人覆盖多条路径，GA但未能覆盖目标路径执行现有这些工作建议元启发式算法（2017）; Panichella etal. （2018年）一次运行方法，难以覆盖所有路径，消耗更多资源改进的元启发式算法，一次覆盖多条路径。所有的道路都被认为是同等重要的。它消耗更多的时间。至少我们建议的工作用…覆盖关键路径支助事务处、辅助支助事务处优于现有重要路径/分支可能需要更多次数的迭代来覆盖。强调的是一条路径（改善综合健身）功能）可用的测试资源项数分支距离适应度函数迭代次数和时间其覆盖概率较小。自动所有几乎所有的路径都是执行.有效覆盖关键路径（目标路径）由关键路径执行的时间覆盖。484R.R. 萨胡，M。Ray/ Journal of King Saud University公司简介01@AnPiCNjP表2速度矩阵，v.测试用例一BCTC10.30.10.4TC20.10.20.4TC30.20.30.4TC40.20.20.3TC50.30.10.3分支距离，我们结合了我们提出的启发式命名的路径距离和分支距离命名的ICF函数。基于近似水平的解析法存在一定的局限性在接近层，如果关键路径的所有节点都被遍历，则近似为零，但我们仍然不能保证测试用例能够遍历目标路径。由于CFG的最后一个条件节点也有两条向外的边，一条通向目标路径，另一条是刚发散的边。如果两条路径的所有分支节点都相同，则两条路径的近似水平都为零，如图所示。四、这两条道路之间没有明确它是分支距离（BD）和路径距离（PD）的线性组合。如果测试用例（t）遍历具有条件节点（CN）j= 1到n的路径（Pi），则适应度4.2.1. 路径距离计算构造具有图1（b）中所示的控制流图的所有路径的矩阵。行表示路径，列表示节点。通过添加尾随零来使所有路径相等长度，并且图1（b）中编号为8的最后一个节点被移除以使路径距离计算更简单，并在那里放置0。 由于所有路径中的最后一个节点相同，因此在距离计算中没有差异。1700 0P1230 01 2 4 5 01 2 4 6 0关键路径（Pc）=[1 2 4 6 0]路径的节点与关键路径节点相匹配。路径中不匹配节点的数量称为路径距离（PD）。电话：+86-10 - 6666666P1：17PD（P1，Pc）= 3 PD（P2，Pc ） = 2 PD（P3，Pc）= 1PD（P4，Pc）= 0分支距离的计算如图所示。7.第一次会议。联系我们PXiCNj BDij= PD i;其中，. n1所提出的适应度函数被公式化为，F（t）=n+ PDi，其中i = 1至n，j = 1至n。BDijBD被归一化以将值保持在[0，1]的范围时间复杂度是O（n）的，所以我们可以用O（n）的时间复杂度来计算。对于n个节点，时间复杂度为O（n2）。案例研究：TCP：Fig. 7解释了ICF功能的评价。在进一步的解释中，我们将路径缩写为P，关键路径缩写为Pc。如第2节所述，选择图1（b）中的路径4作为关键路径，其在图6中以粗实线示出。然后，按如下方式计算到关键路径4.3. 测试用例生成最后以TCP为例说明了粒子群算法的ICF实现。第一步：迭代0最初，矩阵X被认为是每个patricle的个人最佳值，即pBest。矩阵X表示随机生成的生成中间图被测试程序形变测试标准一组线性使用圈复杂度的CFG独立选择基于概率论的关键路径制定适应度函数（ProposedFunction）执行使用生成PSO算法生成最 终测试仪表化程序执行测试数据图五.拟议方法示意图。●R.R. 萨胡，M。Ray/ Journal of King Saud University485667722 367●×见图6。 基于粒子群算法的测试用例生成。见图7。 ICF对TCP问题的评估。A，B，C代表三角形的三条边。2314312 4最佳价格23 443135初始速度，v = 0.1 X（Alam，2018）。每个颗粒的初始速度示于表2中。第二步：体能评估使用建议的ICF函数评估每个测试数据的拟合度。在迭代1中，我们给出了分支距离拟合（BDF）函数和CFF的评估。TCP的条件节点的BD和AL如图2和3所示。分别为3和4。BD被归一化（Wegener等人，;2001）计算健身值。486R.R. 萨胡，M。Ray/ Journal of King Saud University32 3667767迭代1矩阵X的TC1覆盖TCP的CFG的路径1，这导致无效三角形。BDF评价：BD（TC 1）=-2*（a + b + c）=-2*（（3 + 1 + 4）=-16标准化分支距离（TC 1）= 1-（1.001）-BD= 1-（1.001）16= 1-CFF评价：如图4所示，TC 1的近似水平（AL）为2。适合度（TC 1）= BD +AL =-0.016 +2 = 1.984ICF评价：适合度（TC 1）= BD + PD =-0.016 +3 = 2.984TC2（1，2，4）也会导致无效三角形BDF，所有测试用例的CFF值如表3所示。在其余的实现，测试用例生成只使用ICF功能进行了说明。● TC 3（2，3，4）覆盖通向不等边三角形BD（TC 3）= BD 1 +BD 2BD（TC 3）= -2*（2 + 3 + 4）+min（abs（2abs（4-适合度（TC 3）= -0.017 +2 = 1.983TC 4（2，2，3）和TC 5（3，1，3）覆盖通向等腰三角形的路径3。BD（TC 4）= BD 1 + BD 2 + BD 3BD（TC 4）=-2*（2 + 2 + 3）+min（abs（2-abs（2-3）-abs（3-2）-适合度（TC 4）= -0.017 +1 = 0.983接下来，找到ICF值的最小值TC5具有最小值i.e.0.982（参见表3）。在迭代1中，TC 5是gBest（参见表3）。gBest = [31 3 0.982]然后，使用PSO算法更新速度（见图6）。(To仅实现APSOw被修改为w = wMax-[（wMax- wMin）×iter]/maxIter）(i) 然后使用以下公式计算新位置。X（i，j）= round（X（i，j）+v（i，j））;2314321 4X ¼33 243135(ii) 再次使用ICF计算更新的测试用例的适应度。如果更新后的粒子适应度小于其先前的pBest值，则pBest矩阵被其更新后的值替换。TC3和TC4更新的适应度值小于其先前的pBest值。表3使用BDF、CFF和ICF的测试数据的拟合值测试用例A B C BDF CFF ICF TC 1 3 1 4-0.016 1.9842.984沪ICP备16011501号-1电话：+86-021 - 8888888传真：+86-021 - 8888888Copyright © 2018-2019 www.tc4.com版权所有沪ICP备05005558号-1然后pBest的最小值取为gbest gBest=[ 3 3 2 0.982]（见表4）迭代2：在迭代2中，gBest =[333 - 0.018]（参见表5）。在这个例子中，我们解释了如何自动生成测试用例的所有路径使用PSO的目标覆盖关键路径的过程我们试图在两次迭代中达到目标，以使解释简短，但在小范围的实际该方法的优点是适应度函数ICF为不同路径的测试用例赋予不同的适应度值，指导搜索过程实现目标。它还需要最少的迭代次数和更少的执行时间来生成关键路径的测试用例。局限性在于路径覆盖概率是手动计算的，这纯粹是主观的。5. 材料和方法实验是在TCP、RCP和SSSP程序上完成的，如第2节所述。搜索算法在MATLAB中实现。表6显示了基于一些研究工作的PSO和APSO算法的参数设置（Alam，2018; Huang等人，2014; Lv等人，2018年）。最大总体大小被认为几乎等于样本空间大小，表4更新迭代1中的pBest矩阵。测试用例一BCICFTC13142.984TC21242.986TC33320.982TC43230.982TC53130.982gBest = [ 3 3 2 0.982]表5p最佳迭代2。测试用例一BCICFTC13142.984TC21242.986TC33320.982TC4和TC5333133-0.0180.982gBest = [ 3 3表6PSO APSO的参数设置。参数TCPRCPSPP人口规模一千，六万四千400,0011000惯性重量（w）0.90.90.9惯性重量（wmax）（APSO）0.90.90.9惯性重量（wmin）（APSO）0.40.40.4加速因子（c1，c2）222下界1-200001上界二十四十20,0001000最大迭代1001001000●●测试用例一BC健身TC13142.984TC21242.986TC33320.982R.R. 萨胡，M。Ray/ Journal of King Saud University487概率论上界和下界与问题相关，如第2节所述。针对TCP案例研究，分别在种群规模为1000和64,000，三角形各边的范围为[1-20]和[1-40]的情况下进行了两组实验 BDF和CFF在GA中应用于各种工作中的测试用例生成（Pachauri和Mishra，2015; Garg和Garg，2015;Chen等人，2009; Panichella等人，2018），在我们的工作中，我们使用PSO和APSO应用现有的功能。6. 结果和讨论对于TCP，3次运行（每次运行100次迭代）生成的测试用例的平均数量见表7（a）和表7（b），对于RCP，见表8对于SSSP，我们需要1000次迭代。表9显示了覆盖TCP、RCP和SSSP的关键路径在这些表中，迭代#列显示覆盖关键路径所需的最小迭代次数。实验结果与现有的适应度函数的性能进行了比较表7（a）显示，在迭代次数和执行时间方面，具有拟议ICF的表7（b）表明所有算法都覆盖了关键路径，迭代次数几乎相同，当采用大范围大种群规模进行实验时当填充大小为1000时，执行时间从0到2 s，但对于大小为64000的文件，执行时间从10 s到20 s不等。PSO和APSO与BDF和CFF给出了几乎相同的结果，这意味着近似水平值并没有增加任何意义的最终适应度函数。如表8所示，对于关键路径，路径2和路径3，生成的测试用例的平均数量低于其他路径。如表（第1行）所示，对于以下情况，测试用例的数量为零：表7a人口为# 1000的TCP。总体：1000范围：[1实现目标路径平均执行时间（秒）算法不是三角形斜角等腰等边PSO与现有BDF（Pachauri和Mishra，2015）447.333440.333109.6672.6667 31.3535APSO与现有BDF（Pachauri和Mishra，2015）451429.667116.6672 31.5002PSO与现有CFF（Garg和Garg等人，2015）464434100.6671.33333 31.3560具有现有CFF的APSO（Garg和Garg等人，2015）490407.667100.3332 20.4406PSO与拟议的ICF471.667417106.3335 20.2252APSO与拟议ICF461421.333112.6675 20.1836表7b人口为64，000人的TCP。Population：64，000范围[1实现关键路径平均执行时间（秒）算法不是三角形斜角等腰等边PSO与现有BDF（Pachauri和Mishra，2015）34,79027740.333144624 420.53586APSO与现有BDF（Pachauri和Mishra，2015）34,45128129.667139525.66 315.00276PSO与现有CFF（Garg和Garg等人，2015）34,21027,304246224.333 315.35605具有现有CFF的APSO（Garg和Garg等人，2015）35,38026417.667217825 312.44060PSO与拟议的ICF31014.3329373.33357438.66 210.97627APSO与拟议ICF30833.329,5673559.3340.33 210.10385表8RCP问题的实验结果。总体大小：迭代#生成的测试用例的平均数量平均执行范围：±20000秒算法路径1路径2路径3路径4路径5路径6路径7路径8路径9路径10PSO与BDF543000.333433.7456659823652856167511626 5520.39484APSO与BDF4298.30.330.333998498735214718788456454319 5219.65544带CFF的4349.20.3301587.345375633.6675631654154966268 5619.21336带CFF的4271.70.6670.332976493654613442521564237275.3365014.56982有ICF的4198215395574355634425507934483447 228.345984有ICF的5217.312.333578834627874468858893589.3373490 208.873965表9不同适应度函数在TCP、RCP和SSSP上的性能实现关键路径的算法迭代次数平均执行时间（秒）TCPRCPSSSPTCPRCPSSSPPSO与现有BDF（Pachauri和Mishra，2015）45510120.5358620.3948445.5535APSO与现有BDF（Pachauri和Mishra，2015）3529715.0027619.6554442.3002PSO与现有CFF（Garg和Garg等人，2015）3569515.3560519.2133640.2510具有现有CFF的APSO（Garg和Garg等人，2015）3509212.4406014.5698238.3406PSO与拟议的ICF2228210.976278.34598426.2252APSO与拟议ICF2217710.103858.87396524.1836488R.R. 萨胡，M。Ray/ Journal of King Saud University路径2，而路径8具有8561个测试用例。我们从这个实验结果中观察到，对于某些路径，自动测试用例生成器生成了一些测试用例，而对于某些路径，它可能无法生成一个单一的测试用例。还观察到具有BDF和CFF的PSO不能覆盖关键路径，如表8的第1行和第3行所示。如表7、表8和表9所示，与其他两个现有函数BDF和CFF相比，拟议ICF函数需要更少的执行时间。表9显示了覆盖关键路径所需的最小迭代次数和算法的平均执行时间这里示出了实现关键路径的最小迭代次数，因为具有较小覆盖概率的路径被视为关键路径，并且关键路径被覆盖意味着到那时几乎所有路径都被覆盖。第7列显示SSSP与其他两个程序相比需要更多的迭代次数和执行时间。用已有的适应度函数和提出的适应度函数得到的结果在迭代次数和计算时间上在这3个算例中，由于采用了有效的搜索机制，所以带ICF的APSO算法得到了较好的结果。在粒子群算法中，搜索速度在整个搜索过程中是相同的，所以有机会绕过全局最优值，但在APSO中，它降低了搜索速度，同时它越来越接近目标。APSO中提出的ICF由于其路径距离启发式，对搜索技术也给出了适当的指导。图8（a）和8（b）显示了PSO和APSO与ICF函数的收敛图，用于表7（a）中所示的3次运行。它表明，它得到的结果，在两个迭代。图9（a）和9（b）是使用PSO和APSO在1000个人口上为TCP问题生成的测试用例6.1. 与现有工作的虽然GA是自动测试中最常用的算法，但有时它无法实现目标路径（Garg and Garg，2015）。GA存在过早收敛和大量迭代的问题，这是使用PSO避免的（Lv et al.（2018））。与遗传算法相比，它产生质量的结果与更少的参数。粒子群算法没有遗传算法中的变异和交叉算子Garg和Garg（2015）提出了扩展水平分支（ExLB）拟合函数来覆盖目标路径。他们已经在GA和混合GA（GA和爬山法结合）中使用了建议的拟合函数在ExLB函数中，他们修改了基于接近水平的函数的值，其中目标路径的最后一个条件节点的AL值是前一个节点的AL值的一半图8a. 粒子群优化算法的收敛特性。图8b. 基于ICF的APSO算法的收敛特性。图9a. 使用PSO生成测试用例。图9b. 使用APSO生成测试用例。分歧的一个。虽然他们提出的方法在路径覆盖方面比分支和方法级组合适应度函数给出了更好的结果，但不能覆盖等边路径（关键路径），如图 所 示。 10、我们的R.R. 萨胡，M。Ray/ Journal of King Saud University489见图10。 使用随机初始种群进行40次实验后，数值上的测试数据平均数（覆盖四条路径）（Garg和Garg，2015）。APSO中使用的建议ICF在3次运行中覆盖等边路径，每次运行100次迭代，如实验结果表7和表8所示。Pachauri和Mishra（2015）提出了一种基于两步分支距离的适应度函数，使用GA进行分支覆盖。在第一步中，计算分支距离和接近水平。与我们的工作不同，在第二步中，他们使用Lin和Yeh（2001）提出的SIMILARITY适应度函数来找出路径相似性。考虑了关键路径与其它路径在节点数上的差异，使适应度评价在一个步骤中完成，具有较高的效率。他们在TCP上进行实验。实验结果表明，在搜索过程中的覆盖率显着提高，但等边分支没有覆盖，在我们的工作中，我们有效地覆盖了等边路径。Lv等人（2018）提出了一种改进的PSO算法，可以为多条路径生成测试用例。与我们的工作不同，他们认为所有的路径作为目标路径。他们的目标是使自动生成过程的成本效益，覆盖多个路径在一个运行，而不是几个运行。并以TCP和SSSP为例进行了分析。他们修改的方法水平，以避免相同的将变形关系与粒子群算法相结合，在一次运行中生成多条路径的测试虽然它覆盖了所有的路径，但评估的平均数量成比例地增加。但我们的目标是只覆盖测试资源中的重要路径Liu等人（2019）提出了一种分散搜索策略，结合基于搜索的算法（GA，PSO，差分进化（DE））来覆盖自然语言处理（NLP）程序的一些特定路径与我们的整数测试输入值不同，它们需要字符串值。它们使用现有的分支距离函数。共同点是，他们也选择了一些特定的路径，目的是覆盖所有可能的路径。他们的测试结果表明，与GA和PSO相比，DE消耗的运行时间更少，快速覆盖路径7. 对有效性的有效性威胁是实验研究设计和执行中可能存在的风险（MárcioBarros和Arilo Neto，2011）。在这里，我们讨论了可能对我们的研究工作构成威胁7.1. 对内部效度的内部效度威胁是指可能影响实验结果的因素。下面的因素是威胁测试用例生成覆盖我们的工作中的路径参数设置在执行成本和覆盖目标路径所需的迭代次数方面起着重要作用根据各种研究工作，我们设置了影响收敛速度的算法的惯性权重和加速因子的值（Alam，2018; Huang等人，2014; Lv等人，2018年）。我们还没有试验过可能提高性能的参数的其他值。对有效性的另一个威胁是关键路径选择。我们认为一条路径是关键的，它的概率是最低的，它是纯粹主观的。我们的测试用例生成器程序集中在关键路径的覆盖范围，但根据系统的操作配置文件（Musa，1993），路径的执行概率可能非常低。路径的执行概率取决于系统的操作配置文件的准确性。内部有效性的第三个威胁是PSO算法的随机性获得稳定结果所需的执行次数我