基于遗传操作的多故障定位方法在沙特国王大学学报

沙特国王大学学报基于遗传操作曹鹤玲a，b，c，王飞a，邓妙磊a，王先勇a，朱永和a河南工业大学粮食信息处理与控制教育部重点实验室，郑州450001b河南工业大学粮食光电检测与控制河南省重点实验室，郑州450001c河南工业大学信息科学与工程学院，郑州450001阿提奇莱因福奥文章历史记录：2022年11月23日收到2023年2月19日修订2023年2月25日接受2023年3月2日在线发布保留字：基于搜索的软件工程多故障定位粒子群算法A B S T R A C T近年来，基于谱的故障定位方法以其快速性和对单一故障程序的有效性而得到广泛应用，但现有的方法大多没有考虑程序具有多故障的特点为了解决上述问题，我们提出了一种基于遗传操作的粒子群优化多故障定位（PSOMFL）。该方法将软件多故障定位过程建模为粒子群算法的搜索过程，能够在多维超体积中快速找到最优解，最后对最优解集进行分析，得到多故障的位置。我们已经实现了一个原型，并进行了几个实验，比较PSOMFL对现有的故障定位方法。实验结果表明，PSOMFL方法的性能优于对比方法，平均可以降低5%-25%的成本。版权所有2023作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍在软件调试期间，软件维护需要大量的时间和资源。开发人员经常花费大量时间跟踪程序中的错误并确定错误的位置（Vessey，1985）。被称为故障定位，这一步可能是非常耗时和昂贵的。许多基于谱的故障定位（SBFL）方法收集测试用例的执行轨迹和结果，并分析不同结果对应的执行轨迹中包含的语句信息。最后，对所有的可执行语句进行可疑度评分，并给出一个由高到低的可疑度排序列表来检查可疑语句。使用这种方法的故障定位技术在文献（Mayer和Stumptner，2008;Jones等人，2002;Jones等人，2007; Abreu等人，2007; Zou等人，2019年）。然而，大多数SBFL方法只适用于单一断层。在多故障情况下，这些方法的排序列表不是*通讯作者。沙特国王大学负责同行审查对故障定位具有指导意义。在这些大型的多故障程序中，一些故障语句只被少数失败的执行跟踪所覆盖.根据识别值公式，即使可疑报表是真实错误，也可以赋予其低可疑度值。 此外，一些非错误语句可能被分配高可疑值，因为它们在执行跟踪中很常见.可疑报表的不正确识别可能导致报表的不正确排名（Hao等人，2005年）。多故障间的相互干扰导致现有故障定位方法的有效性降低。为了克服这一困难，Jones等人（2007）通过分析得到了故障局部化效应与故障故障个数越多DiGiuseppe和Jones（2011）进行了大量实验，发现故障数量对故障定位效果的影响可以忽略。 Abreu等人（2009）使用了DStar技术和基于贝叶斯推理框架的故障定位技术。然而，大多数基于贝叶斯推理的技术都假设程序组件独立失败，忽略了多个错误之间的干扰本文旨在通过将多故障定位问题转换为一个假设分布，以包含在单个粒子位置中的二进制向量的形式来Wenetal.https://doi.org/10.1016/j.jksuci.2023.02.0231319-1578/©2023作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comH. Cao，F.Wang，M.Deng等人沙特国王大学学报22ðω¼; ：;···（2013）提出了一种基于切片技术的多故障定位方法，减少了不同故障之间的相互影响然而，这种方法更适合于小规模的程序。本文提出了一种带遗传操作的粒子群优化算法来定位缺陷，该算法搜索范围更广，适用于更广泛的程序。Ghosh和Singh（2021）提出了一种基于 SBFL 技 术 的 基 于 混 沌 遗 传 算 法 的 多 故 障 定 位 自 动 化 框 架PSOMFL具有更少的参数和更简单的参数设置。 Lin等人（2021）提出了一种基于粒子群优化的微网故障定位与恢复方法。Xiaobo etal.（2021）提出了一种基于遗传算法的测试恢复方法，用于多故障程序中的有效故障定位，开发了一种搜索潜在耦合测试用例的遗传算法Gao和Wong（2018）提出了一种先进的故障定位技术，用于并行定位多个错误，通过将由同一错误引起的失败测试分组到相同的集群中来生成以最相关的工作由Wang等人提出。（2016），Zheng等人。（2018）提出了一种基于遗传算法的多故障定位软件（GAM-Fal）。该方法将故障定位问题转化为搜索优化问题，提高了多故障定位精度。但是遗传算法的实现比较复杂，除了编码/解码问题外，对参数的选取也要求较高。为了克服上述问题，在软件中多次出现故障场景，我们提出了一种多故障定位方法，通过遗传操作的粒子群优化算法。我们的方法可以搜索问题的解空间，并产生一组最优解，其中之一是一个序列的程序实体包含可疑的实体。通过对最优解集合中包含的程序实体进行分析，可以得到实体出现时间的降序，真正的故障实体可以排列在序列的最前面。最后，在该队列的指导下，开发人员可以用较少的代码快速定位程序中的错误条目。4个大型程序的验证表明，与其他方法相比，PSOMFL平均降低了5%~ 25%的定位成本，提高了真实故障实体在可疑实体队列中的排序值。我们的工作有两个新的方面首先，在PSOMFL中，多故障定位问题的解决方案首先被转换成一个假设分布的形式的二进制向量中包含的各个部件的位置为了提高算法的寻优速度和质量，在粒子位置更新后，采用遗传操作对粒子位置进行优化这用通过遗传算法获得的具有更高适应度值的新位置替换了在速度影响下已经改变的个体的当前位置，从而改善了群体其次，在PSOMFL中，引入了实体执行次数作为适应度函数的权重，增加了实体间的差距，使得失效的实体较多借鉴可疑度计算公式的形式，设计了一种新的适应度函数。该适应度公式能够正确评价种群中个体的优劣，保证PSOMFL正确定位故障。实验结果表明，该方法与其他方法相比，多故障定位代价平均降低5%~ 25%，单故障定位代价平均降低5%~ 20%.本文的其余部分组织如下。第二节介绍了故障定位的相关工作和基本定义第3节介绍了拟议方法的框架和实施情况。第四部分对实证研究进行了描述，并对相关工作进行了总结。最后，第5节给出了结论。2. 背景2.1. 基于频谱的故障定位基于频谱的故障定位方法需要分析通过和失败测试用例的频谱信息以提供排序列表。程序中的每个实体都被赋予一个适当的可疑值，并根据可疑值的大小为开发人员提供一个实体的可疑列表 Reps等人（2000）在研究千年虫缺陷时首次提出了程序谱的概念。随后，已经提出了许多基于光谱的计算公式（Jones等人，2002; Abreu等人，2007; Naish等人，2011; Wong等人，2007; Wong等人，2013;Jones和Harrold，2005; Abreu等人，2006年）。程序实体的覆盖统计可以分为以下几类：通过测试用例数nep sn，覆盖实体的失败测试用例数np，未覆盖实体的失败测试用例数nef sn和失败测试用例数nf其中，s是程序的语句。表1给出了基于频谱的故障定位中使用的6个可疑度公式。特别地，狼蛛（Jones 等人，2002 ），Ochiai（Abreu等人，2007）、Jaccard（Abreu等人， 2006）和Dstar（Wong等人， 2007）是式GP13（Yoo，2012）和Op2（Naish等人， 2011）是理论上的最优公式，Xuan和Monperrus（2014）从理论上证明了这一点。开发人员通过这些可疑性公式提供的排名列表来检查可疑状态。在表1中，nf和np分别表示失败和通过测试用例的数量。nnfs和nnps表示未覆盖实体的失败和通过测试用例的数量。nefs和neps表示失败和通过的测试用例的数量，这些测试用例是被覆盖的实体。实体的覆盖信息，我们可以通过可疑度公式得到实体对应的可疑度。表1基于频谱的故障定位公式。名称分子式Tarantulanefs=nfnefs=nfneps=nf痕迹和更多的处决有更高的可疑值比其他实体。新的适应度函数在4.2节中解释。Ochiaip本文的主要贡献可概括如下。JaccardnefjacksnfnepsDstarnefsω2 2 5nefsnep sGP13n有效值？提出了一种基于遗传操作的粒子群优化算法的EF萨普Op2nefs-nepsnp1●●n×n斯库台P.F.EF●H. Cao，F.Wang，M.Deng等人沙特国王大学学报23¼ ðÞ¼ ðÞ82 21我我þP2.2. 粒子群优化粒子群优化（PSO）是启发式算法之一（Shi等人，2001），被认为是一种进化计算算法，具有简单、高效、收敛速度快的特点。它模拟了自然界中鸟类的捕食行为群体中任何个体的行为都受到自身经验和邻居经验的该算法通过非智能个体之间的信息交流和正反馈，算法经过多次迭代得到问题的最优解。在PSO算法（Abreu等人， 2007），群体中的粒子数为N，搜索空间的维度为D，第i个粒子的位置xi 1 ; xi 2 ;. ;xiD，速度v i1;v i2;. . ;v iD，粒子历史中发现的最佳位置是p ip i1;p i2;... 这是局部最优解。全种群历史搜索的最优位置为g_1;g_2;…这是全局最优解。当种群进化到第t代时，更新粒子速度和位置的公式vt1¼wvtc1r1pt-xtc2r2gt-xt1定义5（gbest）。它指的是整个蜂群找到的最佳位置。它是整个群体找到的最佳位置，并用作粒子比较其当前位置的参考点。定义6（pbest）。它是指粒子在搜索空间中迄今为止pbest用于引导粒子3. 动机在本节中，我们将通过一个示例介绍我们的动机图1中的第一列给出了一个Java applet程序，它可以确定与三个输入对应的三角形。在第8行（bug 1）和第18行（bug 2）有两个错误语句。在接下来的十列中，本文设计了以下十个测试用例：t1={3，2，3}，t2={1，1，9}，t3={3，2，8}，t4={5，1，3}，t5={5，2，2}，t6={1，0，6}，t7={1，1，7}，t8={9，4，9}，t9={3，3，7}，t10={2，2，8}。标记1表示语句被测试用例覆盖，否则0表示声明不包括在内。在最后四列中，根据可疑值使用suspi给出排名列表xt1¼vt 1xtð2ÞTarantula、Ochiai、Jaccard和PSOMFL的计算公式（The我我我其中，学习因子c1和c2都是常数，r1和r2都是0-1之间的随机数这些方法将问题转化为搜索优化问题，可以通过搜索算法来处理，从而为解决软件工程中的问题提供了新的方法。在软件测试领域，启发式算法也得到了有效的应用。在软件测试领域，基于搜索的软件工程已经成功地解决了各种各样的测试问题（Wegener等，1997; Bühler和Wegener ， 2008; Masud 等 人 ， 2005; Li 等 人 ， 2007; Ghazi 和Ahmed，2003;Deb等人，2004; Briand等人，2002年）。一些重要的PSO术语定义如下（Shi等人，2001年）。定义1（适应度函数）。根据问题的需要构造适应度函数，有效地评价种群中的个体，指导种群的进化。一般来说，粒子越接近问题的解，粒子的适应度就越高。定义2（候选分布）。对于一个假设的故障分布c1，如果它满足指标（ac1）Ff，则c1称为候选分布.其中，index（x）表示下标Ff是缺陷分布中所获取的元素x的集合，并且Ff是故障轨迹中的元素下标的集合。定义3（换向器）。换向器d=（x，y）运算基于假设故障分布，其中x和y表示假设故障分布中的元素下标当换向器d作用于一个假设故障分布时，对应于该假设故障分布的二进制串中的两个指定下标位置x和y可以交换，以形成一个新的假设故障分布。定义4（换向器序列）。对于一个有序序列D，如果它满足n<$c i<$d<$c i1，则D<$fd1;d2;. 其中ci和ci+1是两个有前件关系的亏损分布，dj是交换序列D中的交换子.排名是从我们在第4节中描述的建议方法中得出的。最后一行，符号F表示程序运行失败，符号P表示程序运行通过。我们将简要地展示PSOMFL定位故障的过程，如图所示。1.一、首先，初始化的粒子c1，c2和c3通过随机和贪婪策略生成。粒子的元素的位置重合意味着对应于下标位置的两个二进制字符串的元素的值都是1。c1/4 f0;0;1;0;1;0;0;1;0;0;1;0;1;0;1;0;0;0gc2/4 f0; 0; 1; 1; 0; 0; 0; 1; 1; 0; 0; 0; 1; 0; 0; 0; 1; 0; 0; 1gc3/4 f1;1;0;0;1;0;0;1;0;0;0;0;0;1;0;0;1g然后，通过适应度函数计算适应度值，并且c1、c2和c3分别为0.707、0.843和0.948。具有最高适应值的C3被设置为gbest。然后，根据4.3节中的速度公式计算速度，v1=（1，14），（2，3），v2=（1，3），（2，4），v3=（11，12），（16，21）。通过计算粒子在给定时间段内的位置变化，可以将速度信息应用于粒子，并获得新的位置。c01/4f1;1;0;0;1;0;0;1;0;0;0;1;0;1;0;0;0;0gc02/4f1;1;0;0;0;0;1;1;0;0;0;1;0; 0; 0;1;0;0;1gc03/4f1;1;0;0;1;0;0;1;0;0;0;1;0;1;0;0;0;0g再次计算适应度函数的值，并且重复上述过程，直到适应度函数的值不再增加。然后，得到输出粒子群的粒子位置。最终结果如下：f0;0;1;0;0;0;0;1;1;1;0;0;0;0;0;0;1;1;0;0gf0; 0; 0; 1; 1; 0; 0 ; 0; 1; 1; 0; 0; 0 ; 0; 1; 0; 0 ; 0; 0gf0;0;0;0;0;1;0;1;1;0;0;0;0;0;1;0;1;0;0g根据故障的数量和分布，得到实体的排序列表如下：f8;9;18;10;19;3;4;5;11;14;16;15g：在由PSOMFL生成的故障实体的最终可疑性序列中，真实故障位置8和18分别在排序列表中排名第一和第三H. Cao，F.Wang，M.Deng等人沙特国王大学学报24Fig. 1.一个有两个错误的程序及其排序表。至于第8行的bug 1，可以从图中看出。 1、Tarantula、Ochiai和Jaccard公式分别检查1个语句、5个语句和1个状态来定位程序中的bug1。但是对于第18行的bug 2，Tarantula、Ochiai和Jaccard公式都需要检查13个语句来定位bug 2。结果表明，现有的方法对多故障的效果较差，因为这些方法没有考虑多故障的影响总之，现有的方法对第8行的bug 1表现良好。对于第18行的bug 2，Tarantula，Ochiai和Jaccard公式检查了13个语句来定位错误，但我们的方法只检查了3个语句。PSOMFL对多故障问题的定位能力明显优于其他方法。4. 我们的方法所提出的多故障定位方法PSOMFL如图2所示。首先，在预处理阶段，我们通过执行错误程序和测试用例来生成覆盖矩阵。 在假设的故障分布下构造包含故障程序的所有可执行语句的二进制串其次，选择一个策略，并对候选种群进行评估。通过适应度函数来评估，以测量假设故障分布与实际故障分布之间的差距。最后，利用粒子群算法在解空间中搜索最优粒子，生成下一个种群。生成最优种群，直到找不到更好的后代，然后将最优解集中的元素转换为程序实体的可疑性排名。4.1. 种群初始化结合贪婪和随机方法来初始化parti- cles。空粒子通过贪婪方法填充在这种方法中，粒子的元素的位置与失败的迹线重合。重合意味着下标位置对应的两个二进制字符串的元素的值都是1。然后，用随机方法改变颗粒内部元素的值调整后的粒子位置不仅基于实际故障位置，而且基于可控的随机因素。这种方法在一定程度上反映了程序的真实故障分布状态，被认为是二进制串的假设故障分布粒子在算法中不断进化，而真正的故障图二. PSOMFL的框架H. Cao，F.Wang，M.Deng等人沙特国王大学学报25KKKKKKG我我我我我我G我我Max我我我我G我我我我我G我我通过该方法的完整操作最终获得分布4.2. 候选评价是的。个体在速度的控制下更新。种群在所有个体完成位置更新操作时完成一次进化，其中速度是个体在位置更新之前运动的关键。经典粒子群算法中的速度和位置更新公式如下：我们引入实体的执行次数作为权重vk1½w×va×r×pxb×r×p-x7在适应度函数中，这增加了iki之间的适应度差距，实体，并使实体具有更多的失败跟踪和更多的执行，1我我2G icutions有高度怀疑价值观高于其他实体。xk1¼xkvk1ð8Þ在引入适应度函数之前，我们提供一些必要的定义。首先，公式3根据执行次数k和执行次数k计算实体s的权重，覆盖率为nep和nef。由方程式 7、x是惯性权重，用于控制原始速度的继承。v k表示粒子i在第k次迭代时的速度重量单位nefs 卢塞恩州卢塞恩3公里粒子相对于pbest和gbest的学习速度，r1和r2是区间[0，1]中的随机数，nfn ep s第k次迭代时粒子i的p最佳， 代表gBest其中S表示缺陷程序中的实体;NEF和NEP分别表示实体S的失败执行跟踪和通过执行跟踪的数目;K表示实体S被执行的次数。当一个实体s被执行多次并被许多失败的执行跟踪所覆盖时，它应该具有很大的权重通过组合权重，我们可以构建两个重合度公式：jTf jn在第k次迭代中。整个公式可以分为三个部分：第一部分是xk×v k，表示之前粒子速度的总和;第二部分是a×（v k-v k），表示粒子从pbest学习;第三部分是b×（v i-vk），表示粒子从当前gbest学习。这三部分共同构成了完整的质点速度。当量8是位置更新公式。xk<$1是新形成粒子的位置。xxXxf怀特E我4在PSOMFL中，速度更新公式的形式相同ð Þ¼1/4jTpjððj¼0ni×ij×ðjÞÞ ð Þ作为标准粒子群算法中更新公式的结构，它也由三部分组成，确定个人的下一个移动位置然而，在这方面，wCXXCi×fij×wightej51/4j¼0单个粒子的位置呈现出二元的形式PSOMFL中的矢量，原始速度公式无法计算其中，C表示故障分布（群体中的个体），cj是C中下标j的元素值。fij是元素值，i是迹线的下标，j是迹线中元素的下标。Weight（ej）表示第j个实体的权重，有缺陷的程序。Tf和Tp表示失败的跟踪集，以二进制向量的形式表示速度PSOMFL通过引入新的算子改进了速度更新公式。新的速度更新公式如下：vk1wk×vka×r1×pkxkb×r2×pk-xk9分别传递的跟踪集。r（C）计算符合性具有所有失败测试迹线的粒子位置c（故障分布）的度。故障分布c的一个值是1。对于该值，失败的执行跟踪中的对应位置的位置也是1，故障分布被称为与跟踪一致，并且r（C）的值相应地增加。w（C）计算粒子位置c（故障分布）与所有通过的执行轨迹的重合。当故障分布c与通过的执行跟踪一致时，w（C）的值相应地增加。最后，基于前面的公式，用于计算粒子位置c（故障分布）的公式Fitness（C）构造如下：由方程式（9），xk×v k 表示个体第k次迭代时生成的速度总和。它是影响个体运动的三个要素之一然而，该元素对个体向最优位置的移动并不是一个明显的引导，如果个体的初始速度较差，偏离了种群的总体进化方向，则会增加个体进化的数量，从而影响算法的效率。因此，我们设计了一个双因素影响的速度更新公式，该公式去除了原始公式中对前一次迭代中产生的速度的继承部分。同时，采用了速度更新和位置更新公式新的位置更新公式如下：FintessCrC ×TfwC-16健身功能也可以指其他形式的怀疑xk1¼xkxk×.r1×a ×。pk- xkr2×b×.pk- xkð10Þ计算公式，如Tarantula和Ochiai公式，它们与Jaccard公式相同，并基于本文前面提到的两个假设。经检验发现，在大多数故障程序中，参照三种可疑度计算构造的适应度函数，由方程式（10），值x将随着算法的变化而连续变化。rithm运行，提高了算法初期的解空间探索能力和执行后期的收敛速度，并推导了随次数调整的x迭代次数如下：Mulas的表现类似。此外，Jaccard公式具有结构简单，并且比xk¼K-1？？因此，我们选择PSOMFL的参考Jaccard公式来构造适应度函数。4.3. 粒子位置和速度更新在粒子群算法中，粒子群的速度决定了粒子群的进化方向和进化幅度其中kmax是最大迭代次数xmax和xmin是最大固定权重和最小固定权重;k是当前迭代次数;Dx=xmax-xmim是权重的增量。由方程式10、参数a用于控制学习速度基于粒子的历史最佳粒子位置pbest来计算粒子的最佳位置。粒子具有很强的探索解空间的能力H. Cao，F.Wang，M.Deng等人沙特国王大学学报26如果a值很大。值b基于当前种群中的最佳粒子位置gbest控制粒子较大的b值可以加快种群的收敛速度，但会降低粒子探索解空间的能力。因此，有必要在种群演化的不同阶段设置动态参数在种群进化的早期阶段，个体应积极探索算法的搜索空间，因此，要提高找到最优解位置的概率，应取大b值，取小b值。随着迭代次数的增加，个体逐渐收敛到最优解附近，算法进入收敛阶段。此时，应该设置小的a值和大的b值以增加个体的聚合能力。为了满足上述要求，以以下形式提出了随算法迭代次数变化的学习率计算公式：杂交，从而更好地结合两个亲本内的信息。交叉将产生两个新的个体，其中二进制向量相对于父个体改变为了进一步增加个体之间的变异性，需要通过突变步骤来调整个体，给定突变概率Cm，在该突变步骤下，个体的每个元素在该概率的控制下突变变异概率 Cm在PSOMFL中被设置为一个小值，因为变异增加了个体的多样性，同时导致个体内良好信息此外，为了防止更强的突变操作导致二进制向量形式的假设分布偏离缺陷的真实分布的情况，阈值x被设置为使得如果突变后二进制向量包含1的个体的数量通过此设置，其向量包含1的indi-vietronsa¼a最大值-a最大值-a最小值1- KKMax3×2-1mm1萨格勒布线。也就是说，包含在对应于该矢量的分布中的假设缺陷的数量处于稳定水平。遗传操作的最后一步是从优化群体中选择性地插入个体到原始群体中，K3b/b最大值-b/b最大值-b/min最大值1 -2 - 1 mm最大值×2- 1mm1是的。在插入步骤中，首先通过轮盘赌从优化群体中选择一个新的个体，然后将具有最低适应值的个体从最差顺序中依次移除其中， 是最小值，最大值 是最大a值，bmin是最小b值，bmax是最大b值。K是当前迭代次数，并且kmax是为算法设置的最大迭代次数。算法初始阶段a值明显高于b值。随着迭代次数k的增加，b的值逐渐超过a，并且在后期b显著高于a4.4. 遗传操作改进粒子群算法PSOMFL将多故障定位问题的解转换为包含在单个粒子位置中的二进制向量形式的假设分布，这使得问题的解与单个粒子位置的适应度值直接相关。为了提高获得最优解的方法的速度和质量，需要在通过遗传操作进行位置更新之后再次针对位置优化个体粒子，该遗传操作通过遗传算法获得具有更高适应值的新位置来替换在速度影响下已经改变的个体的当前位置，从而提高总体的适应性能。遗传操作的步骤包括选择、交叉、变异和插入，并在随后详细描述在遗传操作的预处理阶段，以当前种群的平均适应度值为水平线，将种群分为两组个体：第一组为适应度值大于水平线的较好个体集，第二组为适应度值小于水平线的较差个体集当队列被构造时，预处理阶段完成。遗传操作的选择阶段是从两个队列中的每一个中选择一个要杂交的亲本，使用不同的策略来选择两个队列中的个体：基于适应度值通过轮盘赌选择最好的个体，而从具有最低适应度值的个体中选择最差的个体两个被选中的个体作为父母开始交叉这里选择的交叉是二进制向量形式的粒子位置的洗牌交叉，这允许每个位置中的元素有机会比较两个个体的适应度值，并使用贪婪策略接受新个体，即仅允许具有更好适应度值的新个体被插入以替换原始个体，并且当最差阶中的所有个体都被替换时，操作终止。经过几次遗传操作后，种群的平均适应度值得到提高，但遗传操作是一种改进工具，应该在不影响PSOMFL方法整体性能的前提下对种群进行优化和改进，PSOMFL在平衡收益和消耗后，通过将种群的平均适应度值提高5%-10%来终止遗传操作.4.5. 终止准则与最优解该算法继续进行，直到在预定义的阈值内没有产生更好的后代或种群的平均适应度满足要求。如果满足终止标准，则算法立即停止，并且当前解作为最佳种群输出。由于单个粒子被设计为二进制向量中的假设分布，这直接代表问题的解决方案，因此最优种群直接作为问题的最佳解决方案的集合，而无需转换。4.6. 多故障定位在本节中，我们的目标是将最优解集中的元素转换为程序实体的可疑性排名。 最优解集中的元素在添加时已排序。当解的适应度值越高，相应假设分布中的元素越有可能是错误语句。这是因为将根据解决方案的顺序提取元素以形成可疑性排名。如果第一个解决方案中包含更多元素，则会根据其他的解决方案。我们通过下面的例子来解释从最优解集获得可疑性排名的过程。例如，存在以下最优解集：C1=（1，1，0，0，0），C2=（1，0，1，0，0），C3=（0，0，1，1，0）。其中最优分布C1具有H. Cao，F.Wang，M.Deng等人沙特国王大学学报27ðÞC3的适应度值最小，C1中的实体最有可能是故障实体。因此，对应于元素1和2的实体s1和s2在剩余的假设分布中，实体s1的出现次数大于实体s2，因此，实体s1在可疑性排序中应位于实体s2之前。也就是说，通常，实体 s1 比 s2 具有更高的可疑性。我们生成的最终可疑性排名为：{s1;s2;s3;s4}。一个状态- ment被检查，以定位在最好的错误，而四个语句被检查在最坏的。4.7. 算法算法1. PSOMFL算法5. 实证研究在本节中，我们从以下两个研究问题开始进行实验。RQ 1. PSOMFL是否优于所比较的方法？针对这一研究问题，我们将PSOMFL方法的结果与六个单故障定位的结果（即，Taran-tula（Jones等人，2002），Ochiai（Abreu等人，2007）、Jaccard（Abreu等人，2006）、Dstar（Wong等人，2007），Op2（Naish等人，2011 ），GP13（Yoo，2012）），GAMFal（Wang等人，2016; Abreu等人，2009）和MSeer（Gao和Wong，2018）。选择GAMFal是因为它类似于我们的种群选择解决方案。MSeer（Gao和Wong，2018）是一种并行定位多个bug的先进技术。RQ 2. 通 过 统 计 假 设 检 验 方 法 ， PSOMFL 是 否 显 著 优 于 com-candidate方法？PSOMFL是主要使用在秩序到解决多故障需要pupulation size1;学习因子a和b;时变惯性权重x;全局最优粒子位置gBest;故障测试数据执行轨迹集faildePath;历史最优粒子位置pBest确保种群包含最优候选解1：func初始化随机和贪婪填充;失败路径路径填充; 2：对于e2填充做3：对于路径2失败路径做4：如果e：localization\path^，则5：flag←path：getRandomLocalizationFlag6：e：localization：changeFlagValue标志7：如果结束8：结束9：结束10：回返人口11：func Evolutionpopulation;x;a;b;pBest;gBestpopulation12：对于e2人口做13：e：UpdateSpeed更新a;b;pBest;gBest更新14：e：UpdateLocalization更新本地化速度;e：本地化速度15：e：UpdateFitness16：结束17：func可终止的数量;k最大值18：对于k中的k max，19：如果k> k_max，则20：返回人口21：如果结束22：对于e2人口做23：如果e：健身足够，那么24：返回人口25：如果结束26：结束27：结束我们使用算法1来解释PSOMFL的故障定位第1至9行给出了种群初始化的描述第10到15行显示了种群更新的过程。第12、13和14行分别是速度更新、位置更新和适应度计算步骤。算法的终止基于第17至24行，其包括两个条件：是否达到最大迭代次数和输出最优解是否满足适应度值的要求。当满足其中一个条件时，算法终止。定位问题。通过对PSOMFL与其他方法的数据分析，验证了它们之间存在显著性差异。我们采用方差分析（ANOVA）和最小显著性差异（LSD）来衡量PSOMFL与其他比较方法的差异。5.1. 科目在我们的实证研究中，我们使用了四个大规模的程序，其中包含许多故障位置和丰富的故障类别，以评估所提出的方法的性能这些计划的ðÞH. Cao，F.Wang，M.Deng等人沙特国王大学学报28-从 SIR （ https://sir.csc.ncsu.edu ） 库 下 载 这 四 个 程 序 是 Flex 、Gzip、Sed和Grep，如表2所示。代码行（Line Of Code，简写为CODE）表示程序中可执行语句的数量。在四个程序中，我们总共保留了368个错误版本这些断层组合包括单断层、二断层、三断层和五断层等。5.2. 评价标准EXAM度量定义为在定位故障之前需要检查的可执行语句的百分比，通常用于评估单个故障定位的有效性。对于一个程序，当EXAM值较小时，故障定位的效果较好然而，EXAM度量不能应用于考虑同时定位多个故障位置的多个故障定位问题。因此，在文献（Yoo，2012）中提出了基于EXAM度量的两个改进的度量，如下所述。(1) 检查F：该指示符是在检测到第一个错误之前必须检查的语句的百分比。(2) 检查L：该指示符是在检测到最后一个错误之前必须检查的语句的百分比。在这些度量中，检查F反映故障定位方法定位多故障程序中的第一故障的能力，并且检查L反映故障定位方法定位多故障程序中的最后故障的能力。因此，我们将使用这两个指标来评估PSOMFL和其他方法在单故障和多故障定位问题中的性能。5.3. 实验装置(1) 实验环境实验环境分为两部分。第一部分用于缺陷程序的频谱信息的收集，第二部分用于接近方法的操作。在第一部分中，对越野车的运行情况进行了分析，在Linux操作系统上，采用E52600V5系列CPU和128G RAM，实现了频谱信息的提取和频谱信息的构建。gcov用于收集代码覆盖率信息，其覆盖了程序语句、函数和分支在不同粒度上的覆盖率，并且最终结果将包括程序完整执行所消耗的时间。第二部分是多故障定位PSOMFL方法的实验环境设置，该方法用Java编写，运行在Eclipse中 ， 使 用 64 位 Windows 10 操 作 系 统 ， 在 Intel i5 9400 CPU2.90Ghz和16G运行内存的笔记本电脑上运行(2) 参数设置在PSOMFL中，参数设置分为两部分：与种群相关的设置和与进化相关的设置。在与种群相关的设置中，有两个参数需要确定：种群进化的最大迭代次数和初始种群规模。为了得到最优的参数设置，我们将种群规模的初始值设为50，进化数的初始值设为100，并将两个参数的增量分别设置为50和100，并将增加的值设置回该方法，并观察该方法在该参数设置下的性能。每个参数递增五次，并对每个递增的参数组合进行性能评估，如表3所示。其中，人口规模用Popu表示。大小;演化时间用Evo表示。次通过分析表3中的数据可以发现，当种群规模参数设置为100，算法的进化代数设置为400时，该方法在本实验中获得最优性能在与进化相关的参数设置部分，有三个参数需要set：惯性权重x，学习因子a和b。 x控件粒子全局最优位置。参数的具体设置见表4。表2主题程序。程序故障版本LOC测试用例Flex三十五（六十）10459379Gzip四十四（六十）5680213Sed三十二（六十）14427300Grep十七（六十）10068450表3种群规模与进化时间的关系波波大小埃沃倍100200300400500600500.640.710.600.560.540.531000.540.610.680.760.650.591500.560.570.660.590.470.442000.450.480.470.470.420.392500.230.250.290.280.270.263000.220.240.270.260.260.24表4参数设置。XMaxXmin的最大阿敏b最大bmin0.50.10.50.10.70.2H. Cao，F.Wang，M.Deng等人沙特国王大学学报295.4. 多故障实验结果分析为了分析实验结果，使用了EXAMF和EXAML指示器。在5.2节中给出了指标的定义和计算形式。差异的比较通过箱形图中的六个数据呈现，即上边缘、下边缘、上四分位数、中位数、下四分位数和离群值，其中能够突出数据之间差异的关键值为上限、中位数和下限。5.4.1. 使用EXAML度量的图3显示了多故障定位能力，我们的方法相比，比较方法下的EXAML度量不同的故障程序。在图3（a）中，PSOMFL数据的平均值为0.13，数据波动范围为0.01- 0.21，波动范围的宽度为0.2。GAMFal数据的平均值为0.2，数据波动范围为0.13波动范围的宽度为0.22。MSeer数据的平均值为0.1，数据波动范围为0.08-0.38，波动范围的宽度为0.3。PSOMFL相对于GAMFal和MSeer具有较小的优势。其他故障定位方法，包括Tarantula、Jaccard、Dstar、Op2和Gp13方法，从两个方面与PSOMFL相比显示出很大的性能差距。Ochiai和Gp13基于样本数据的平均值与PSOMFL相似，但数据的波动程度相对较大，波动范围的宽度为0.5，远大于PSOMFL。在图3（b）中，PSOMFL的两个比较值分别为0.09和0.18，并且GAMFal产生值为0.15和0.17。两种方法的数据波动结果相似，但是PSOMFL样本数据的平均值优于GAMFal的平均与其他方法相比在图3（c）中，可以直观地得出结论，PSOMFL、GAMFal和MSeer的性能比其他方法好得多，并且这些方法图三. EXAML度量下的多故障定位。H. Cao，F.Wang，M.Deng等人沙特国王大学学报30三种方法的性能相似，但PSOMFL在样本数据的平均值方面稍有优势。在图3（d）中，PSOMFL的性能下降，主要体现在数据波动性的增加，值得注意的是，波动范围从0.2增加到0.3，但样本数据的平均值保持在0.05附近。这一结果表明，虽然所提出的方法显示出一些波动，但引起波动的数据量很小，对总体性能的影响并不显著。PSOMFL在除GAMFal和MSeer外的所有方法中仍具有显著的优势。5.4.2. 使用EXAMF度量的图4显示了该方法针对不同缺陷程序的多故障定位能力，并考虑了EXAMF矩阵。一般来说，PSOMFL产生的性能改善5%- 25%相比，在比较中涉及的其他方法仍然根据样本数据的平均值和数据波动程度进行详细比较。在图4（a）中，PSOMFL样本数据的平均值约为0.13，数据波动间隔宽度为0.21。这些GAMFal的值约为0.21和0.23，它们基本相同。MSeer的这些值约为0.12和0.26，它们基本相