基于组合优化技术的软件结构测试用例最小化方法

工程科学与技术，国际期刊19（2016）737全长文章基于故障检测和组合优化技术的结构测试用例最小化方法贝斯顿湾Ahmeda，b，*aIstituto“Dalle Molle”di Studi sull'Intelligenza Arti ficiale（IDSIA），USI/SUPSI，Manno（Lugano），Switzerlandb伊拉克埃尔比勒Salahaddin大学Hawler软件工程系A R T I C L E I N F OA B S不 R 一C T文章历史记录：收到日期：2015年6月21日收到日期：2015年10月22日2015年11月3日接受2015年12月14日在线发布关键词：组合测试测试用例设计错误播种软件变异测试软件结构测试布谷鸟搜索算法本文提出了一种技术，以减少配置感知结构测试中的测试用例的数量。组合优化首先用于通过对输入配置进行采样来生成优化的测试套件第二，为了进一步优化，生成的测试套件过滤的基础上，通过使用变异测试技术的自适应机制。初始化的测试集使用布谷鸟搜索（CS）和组合方法进行优化，变异测试用于将不同的故障种子到被测软件中，以及根据检测到的故障过滤测试用例。为了衡量该技术的有效性，进行了实证研究的软件系统。该技术证明了其有效性，通过进行的案例研究。本文还介绍了组合优化和CS在软件测试中的应用。© 2016，Karabuk University.出版社：Elsevier B.V.1. 介绍与任何其他工程过程类似，软件开发也受到成本的影响。目前，软件测试（作为软件开发生命周期的一个过程）消耗了软件开发的大部分时间和成本。随着测试时间的缩短，该成本可能会迅速降低。大多数情况下，由于市场压力以及节省时间和削减成本的意图，软件可能在没有经过充分测试的情况下发布。然而，向市场发布低质量的软件产品已不再被接受，因为这可能导致收入损失甚至生命损失。因此，软件测试人员应该设计高质量的测试用例，在不超过预定测试时间的情况下捕获软件中的大多数错误。因此，测试用例最小化机制在减少测试用例的数量而不影响其质量方面起着重要作用然而，减少测试用例的数量，特别是在可配置软件系统中，是一个主要问题。近年来，可配置软件系统在市场上获得了相当重要的地位，因为它们能够通过配置改变软件行为。传统的测试设计技术-* 联系电话：+41 779158530。电子邮件地址：bestoun@idsia.ch。由Karabuk大学负责进行同行审查http://dx.doi.org/10.1016/j.jestch.2015.11.0062215-0986/© 2016，Karabuk University.出版社：Elsevier B.V.由于输入元件和配置的组合，所以nique对于故障发现和预防是有用的，但是对于故障消除不是有用的[1]。我们认为所有配置组合都导致穷举测试，但由于时间和资源限制，这是不可能的[2，3]。测试用例的数量可以通过设计有效的测试用例来最小化，这些测试用例具有与穷举测试相同的在过去20年中，已经制定了解决上述问题的战略。在这些策略中，组合测试策略是最有效的设计测试用例的问题。这些策略有助于搜索和生成一组测试，从而形成一个完整的测试套件，根据组合的强度或程度覆盖所需的组合这个程度从两个开始（即，d=2，其中d是组合的程度）。我们认为最小化测试套件中的所有组合都是一个计算优化难题[4-因此，寻找一组最佳的测试用例可能是一项艰巨的任务，并且找到一个产生最佳结果的统一策略是具有挑战性的。可以遵循两个方向来有效地解决这个问题，并找到一个接近最优的解决方案。第一种使用具有数学排列的计算算法;另一种使用自然启发的元启发式算法[10]。使用自然启发的元启发式算法可以产生比计算算法更有效的结果，出版社：Karabuk University，PressUnit ISSN （印刷版）：1302-0056 ISSN（在线）：2215-0986 ISSN（电子邮件）：1308-2043主 办可 在 www.sciencedirect.com上 在 线ScienceDirect可在ScienceDirect上获得目录列表工程科学与技术国际期刊杂志主页：http://www.elsevier.com/locate/jestch738B.S. Ahmed/ Engineering Science and Technology，an International Journal 19（2016）737数学模型[10]。此外，由于该方法可以构造具有不同输入因子和水平的组合集，因此比其他方法具有更大的灵活性。因此，它的结果更适用，因为大多数现实世界的系统有不同的输入因素和水平。杜鹃鸟搜索（CS）算法是由Xin-She Yang和Suash Deb[12]开发的一种新算法，可用于有效地解决全局优化问题[13]。CS可以解决NP难问题，不能解决的精确解方法[14]。该算法在各种实际应用中是有效的最近的证据表明，CS优于其他解NP完全问题的元启发式算法[9，13，16，17]。虽然组合测试在文献中的许多研究中证明了其有效性，但证据表明这种测试技术存在弱点[18]。它假设输入因素对系统的影响是相同的。然而，实际上测试用例具有不同的影响，并且某些测试用例可能无法检测到(a)（b）（c）Fig. 1. 三个不同的例子来说明OA、CA和MCA。价值观一般来说，CA使用数学表达式CAλ（N;d，k，v）[24]。CAλ（N;d，k，v）是（0，.. 、.、v− 1）这样任何过错。换句话说，大多数故障可以由每一个B，B，B，是λ-覆盖的，且每个测试套件的一部分因此，应该有一个机制，0天1小时根据每个测试用例的故障检测强度过滤测试套件成功地做到这一点将导致进一步优化生成的测试套件的组合策略。本文提出了一种系统地解决这一问题的技术。应注意的是，在被测软件的输入配置中可能存在约束。这超出了本文的范围;但是，该方法也可以适用于此问题论文的其余部分组织如下：第2节介绍了组合测试背后的数学符号，定义和理论。第3节使用真实案例研究说明了问题的实用模型。第四节总结了最近的相关工作，并回顾了现有的文献。第5N× d子数组包含v个大小为d的值的至少λ次的所有有序子集[25]，其中列B ={b0，. . .， bd-1}{0，. . .，为了确保最优性，我们通常希望d-元组至少出现一次。因此，我们考虑λ=1的值，它经常被忽略。记法变成CA（N;d，k，v）[26]。我们假设数组的大小为N，组合度为d，因子为k，v水平和指数λ。给定d，k，v和λ，最小N，其中存在的CAλ（N; t，k，v）记为CANλ（d，k，v）。其中N = CAN λ（d，k，v）的CAλ（N; d，k，v）被认为是最优的，如等式（1）所示。1[27]。图1（b）示出了大小为9的CA，其具有4个因子，每个因子具有3个水平，组合度等于2。讨论了研究和实施的方法本节详细回顾了CS，并讨论了如何组合（一）使用这种算法生成测试套件。第6节包含评价结果。第七节给出了实验和案例研究的有效性威胁。最后，第8节对本文进行了总结。2. 组合优化及其数学表示未来向组合测试的发展涉及使用从称为覆盖阵列（CA）的数学对象导出的采样策略[19]。在组合测试中，CA可以简单地通过包含设计的测试用例的表表格的每一行代表一个测试用例，每一列是被测软件的输入因子这个数学对象本质上起源于另一个称为正交阵列（OA）的对象[20]。OAλ（N; d，k，v）是一个N × k数组，其中对于每个N × d子数组，每个d元组恰好出现λ次，其中λ = N/v d; d是组合强度; k是因子的数量（k ≥ d）; v是与每个因子相关的符号或级别的数量。在覆盖所有组合时，每个d元组必须在最终测试套件中至少出现一次[21]。当每个d元组只出现一次时，λ= 1，并且它可以在数学语法中未提及，即OA（N;d，k，v）。例如，OA（9; 2，4，3）包含三个水平的值（v），组合度（d）等于2，四个因子（k）可以由九行生成。图图1（a）示出了该阵列的布置。OA的主要缺点是其在此应用中的有限用途，因为它要求因子和水平是统一的，并且它更适合于小型测试套件[22，23]。为了解决这个限制，CA已被引入。CA是另一种数学符号，在表示具有较大大小的不同参数的测试套件时更灵活，当每个因子的水平数v相等时，CA是合适的在数组中。当因子具有不同的水平数时，使用混合覆盖阵列（MCA）。MCA表示为MCA（N，d，k，（v1，v2，v3vk ） ） 。它是一个N×k数组，有v个级别和k个因子，其中每个N×d子数组的行至少覆盖d列中所有d元组的值一次[2]。为了使符号更具灵活性，MCA可以表示为MCA（N; d，v k）），并且可以用于固定级别的CA，如CA（N; d，v k）[8]。图1（c）示出了具有4个因子的大小为9的MCA：其中2个因子各自具有3个水平，并且另外2个因子各自具有2个值。此外，图2示出了使用CA生成和覆盖d元组的方式的示例CA（4; 2，2，3）3. 通过一个实际例子随着通信系统的发展，移动电话是最新的行业创新之一，也是人类之间的常用通信方式。已经为这些设备开发了各种操作系统，作为执行基本任务的平台，例如识别输入、发送输出、跟踪文件和控制外围设备。这一发展为智能手机的出现铺平了道路。安装在移动平台上的智能手机应用程序或Android是一个重要的平台，包括一个特殊的操作系统和一个开源的开发环境。在控制智能手机的行为时，必须在Android单元中调整许多配置选项。在各种硬件和软件平台上执行正在运行的应用程序时，选项的这种调整起着重要的作用。例如，一些智能手机具有物理键盘，而另一些智能手机具有软键盘。 图 3显示了资源配置文件的示例01 -02 -03 -02 -09; （第2、4、3段）K1K2K3K41111222133311232231231221323CA（9; 2，4，3）K1K2K3K4133332311121121231132132332223112223MCA（9; 2，4，3222）K1K2K3K4211222213322131111211212321131112312B.S. Ahmed/Engineering Science and Technology，an International Journal 19（2016）737-753739图二. CA覆盖d元组的方式的说明Android的“configuration.java”源代码。代码中的许多配置因素被突出显示，必须对其进行调整。图 3 显 示 了 每 个 因 素 都 有 不 同 的 选 项 或 水 平 。 例 如 ，NAVIGATION 因 子 有 五 个 级 别 ， 分 别 是 DPAD 、 NONAV 、TRACKBALL、UNDEFINED和WHEEL。表1.确定这些参数及其可能的值。通过应用一组设计的测试用例来测试设备上的任何应用程序可能会暴露一组故障。然而，有证据表明，应用相同的测试用例集，但具有不同的配置可能会导致不同的故障[28，29]，这反过来又导致我们考虑相同的被测软件的不同配置（即，配置感知测试）。此外，有证据表明，考虑到配置之间的相互作用（即，配置的组合）也将引导我们检测新的故障[30]。在这种情况下，测试人员可以针对所有配置测试应用程序，这称为穷举测试。然而，这种测试导致了大量的测试用例，这使得测试过程变得棘手。在应用程序配置文件中必须设置大约35个选项。为了彻底测试整个配置，我们需要测试33 44 52，这意味着172，800个配置。然而，这个数量的测试用例需要大量的时间和资源。使用组合测试方法，测试人员可以测试配置的组合。除了测试单个因素中的意外组合的好处外，该技术是详尽测试的替代方案组合测试的使用基于组合度（d）来减少穷举测试用例，这主要取决于CA符号和数学模型。例如，d= 2表示两个因子的组合。在这里，不是172，800个测试用例，而是29个测试用例都有主了表2给出了一个例子，说明了这种技术如何减少基于d的穷举测试用例。证据表明，采取两种和三种的组合适用于许多应用。然而，对于许多其他应用，我们仍然需要更高的相互作用，特别是对于2 ≤d ≤6。4. 相关工作和文献虽然CA生成问题是一个NP难问题，但研究人员已经尝试使用各种方法来解决它。本节重点介绍研究人员开发的一般技术和工具。其中一些工具是免费提供的，而另一些只是作为文献中的证据4.1. 测试用例集生成策略迄今为止，许多软件工具和策略已经开发了测试套件生成。研究人员的第一次尝试从代数方法和从数学函数导出的OA开始。这种方法要求输入因素和水平由预定义的规则构建，而不需要任何组合细节。该方法直接通过计算值的数学目的来执行[8]。尽管OA很有用，但它限制性太强，因为它利用了数学属性，从而要求参数和值是统一的。为了克服这一限制，引入了互正交表（MOA）[31]来支持非均匀值。然而，MOA和OA存在一个主要缺点，即可行的解决方案仅适用于某些配置[8，31]。文献中的另一种方法是使用单因子（OFAT）和单次检验的计算方法740B.S. Ahmed/ Engineering Science and Technology，an International Journal 19（2016）737图三. Android资源配置文件。（OTAT）。在这种策略中，单个测试或一组已完成的测试用例是每次迭代的候选者，之后算法搜索覆盖最未覆盖的d-元组的测试用例以添加到最终测试套件中。基于这种方法，在以前的研究中已经开发了一些工具和策略不一样的井-表1Android资源配置因素和级别。在这种方法中开发了已知的策略，例如[32]的自动有效测试生成器（AETG），[33]开发的分类树编辑器扩展逻辑（CTE-XL），[34]的测试向量生成器（TVG）和[35]的测试配置（TCon fig）。后来，AETG被修改为mAETG[36]。此外，Jenny[37]、成对独立组合测试（PICT）[38]、约束数组测试系统（CATS）[39]和智能测试用例处理器（ITCH）[10]也被成功开发Tai和Lie[4]试图在这种方法中使用一种不同的更快的算法，因素编号的水平实际值oping in-parameter order（IPO）及其变体工具IPOG和IPOG-D[8，40]。屏幕布局_尺寸5大号、屏蔽、普通、小号、未定义屏幕布局_长4掩蔽，否，未定义，是触摸屏4手指，Notouch，触针，未定义键盘4 12键，NOKEYS，QWERTY，未定义键盘DHIDDEN 3否，未定义，是表2测试用例的数量及其与穷举测试相比的减少百分比d没有。减少%硬键盘3否，未定义，是导航5DPAD，NONAV，轨迹球，未定义，22999.98轮313999.91导航隐藏3否，未定义，是463299.63取向4景观，肖像，广场，5253398.53未定义6917194.69B.S. Ahmed/Engineering Science and Technology，an International Journal 19（2016）737-753741各种工具和策略仍在开发中，以生成最小的组合测试套件。他们中的一些人可以在互联网上免费获得[41]。每种策略都有其自身的特点和优势。对于所有输入配置，它们都不是最好的。有时，它们一起使用，然后选择最佳结果最近，已经做出了重要的努力来实现基于人工智能（AI）的组合测试套件生成策略到目前为止，遗传算法（GA）[42-一方面，在构造组合测试套件时，GA、SA和TS已经由[50]实现。该实现支持输入因子d= 2的小组合（即，成对地）。结果表明，与SA和TS相比，GA的效率最低。此外，TS是有效的小搜索空间，而SA执行更好的结果，大的搜索空间。当组合增加了3或更多时，Cohen[36]开发并实现了d= 3的SA，当这种情况下产生了大的搜索空间时。结果证实，SA执行了更好的结果，以找到最佳解决方案。另一方面，Shiba等人[51]开发了两种人工方法GA和ACA与压缩算法相结合结果表明，生成的CA通常是小的。然而，对于组合度，它们的大小并不总是最优的2 ≤d ≤ 3。构造CA的另一种技术是由[30]开发的基于粒子群的测试生成器（PSTG）。这种技术表明，粒子群算法支持输入因子之间的高度组合2 ≤d ≤ 6，这意味着它获得了大的搜索空间。结果表明，粒子群优化算法比其他算法具有更好的效果.然而，传统PSO的问题是收敛速度随着迭代次数的增加而降低，这会影响粒子达到最佳值[52]。粒子群算法也出现了参数调整的问题，因为不同的参数值的不同性能。事实上，大多数元启发式算法使用局部搜索和全局搜索，并生成随机初始种群[11]。由于组合测试集的NP完全性，每次获得最优组合测试集几乎是不可能的。4.2. 生成工具简介如前所述，生成组合测试套件的两个基本方向是计算和基于AI的策略。在本节中，将注意力集中在使用计算和基于AI的方法来概括这些工具计算方法的实现主要采用两个方向的算法：顺序实现算法和并行实现算法。顺序实现单独构建测试用例，直到完成。并行实现由多个处理单元组成，它们共同构成最终的测试套件。在这里，顺序算法的功能优于并行算法，因为顺序算法实现起来不那么困难然而，顺序算法往往比并行实现消耗更多的时间，特别是对于大的输入因子和配置[53]。如前所述，许多开发人员已经实现的一些工具现在可用于生成测试套件。在文献中已经开发了许多工具，例如AETG、mAETG、PICT、CTE-XL、TVG、Jenny、TCon fig、ITCH、IPO、IPOG和IPOG-D。AETG策略使用OTAT，仅支持统一程度的交互[32]。它通过生成一些候选测试来验证然后选择其中一个作为覆盖大多数元组的最终解决方案。此后，它从剩余的输入因素中随机选择另一个案例。对于每个剩余的输入因子，选择覆盖最未覆盖的d元组的值是必要的[32，53]。由于无法对该策略进行评估，Cohen[36]在一个名为mAETG的工具中再次对其进行了修改PICT策略使用贪婪算法和OTAT。PICT包含两个主要阶段：准备和生成。第一阶段计算第二阶段所需的所有信息生成过程首先从未覆盖元组列表中标记第一个未覆盖元组，然后用覆盖最多未覆盖元组的值迭代填充尽管PICT公式化了伪随机选择，但它总是使用相同的种子值初始化（除非用户另有指定）。因此，具有相同输入的两个执行构造相同的输出[53]。TVG算法使用OTAT并为每次执行生成测试用例，对于相同的输入具有不同的结果。TVG支持所有类型的交互程度。它已经被实现为一个Java程序，带有一个涵盖d-元组的GUI，其中d由测试人员指定[53]。Jenny策略使用OTAT，它从1元组开始生成，然后扩展到覆盖2元组，直到覆盖所有d元组（其中d由测试人员指定）。珍妮只支持统一的联合国学位。它覆盖了大多数组合，测试用例比其他策略少[37，53]。TCon fig是另一个使用OTAT和OPAT的测试套件生成策略它依赖于两种主要方法：递归块和IPO。第一种方法用于生成成对测试集，第二种方法用于生成更高一致度的测试集 的组合。递归分块方法采用代数方法生成基于OA的测试用例集它已被用作较大CA的初始块，包括可以通过从正交阵列构建CA生成的所有d组合[53]。IPO策略使用OFAT，它从2-组合开始生成过程，然后基于水平扩展每次添加一个参数进行为了确保覆盖所有d元组，可以根据垂直扩展不时添加新的测试用例[4]。基于这一思想，该技术将IPO策略从成对测试推广到多路测试，并由[40]产生了称为IPOG的现代策略。然而，多路测试具有时间和空间要求，因为组合的数量通常非常大。为此，在IPOG策略的基础上，提出了一种新的策略IPOG-D，它有时也被称为加倍构造。使用加倍构造算法提高初始测试用例集的规模。因此，与IPOG相比，IPOG-D策略所需的水平和垂直扩展的数量可以有效地减少，从而减少执行时间[53]。除了上述策略和算法之外，已经进行了几次尝试来开发基于AI的组合策略（即，AI程序）。到目前为止，基于GA、ACA、SA、TS和PSTG人工智能的技术已经成功地实现了组合测试集的生成一般而言，这些技术用于在有限数量的解决方案中找到最佳解决方案。每种技术都是从初始化随机种群开始，然后根据特定的算法和更新角色迭代更新种群。GA是一种启发式搜索技术，已广泛用于解决从优化到机器学习的问题[6]。它是用随机解初始化的，随机解表示染色体.此后，它通过交换和交换两个好的候选者来制定新的解决方案。过程交换已被应用于特定过程，如变异和交叉过程。最后，它从解决方案中选择最佳解决方案并添加到最终测试套件中。742B.S. Ahmed/ Engineering Science and Technology，an International Journal 19（2016）737在蚁群算法中，单个蚂蚁在第一轮中用空解生成候选解，然后迭代地添加解组件，直到生成的解完成。在构建完成的解决方案之后，蚂蚁提供关于解决方案的反馈，并且许多蚂蚁使用更好的解决方案[54]。搜索操作由多个蚂蚁执行最佳路径意味着测试用例的最佳值，因为蚂蚁从一个位置移动到另一个位置以找到最佳路径[53]。最近，SA在CASA工具中实现。SA中的搜索过程由两个主要部分组成，它们承担搜索过程。第一部分是当前解的接受概率，第二部分是当前解与相邻解之间的目标值差异。它允许在搜索空间中进行更少的受限移动，以及搜索吸引力陷入局部最优的概率[11]。该算法随机开始，然后根据概率方程应用于许多变换。概率方程在很大程度上取决于输入因子[53]。TS中的进程标识可能对给定解决方案有用的邻居或一组移动，以产生新的解决方案。它更准确地存储和移动的数据结构，被称为禁忌表。它记录了有关解决方案属性的信息，这些信息对于从一个解决方案到另一个解决方案的移动修改非常有用。通过使用有助于引入当前解决方案的适应性评估策略来选择良好的解决方案[54]。PSTG策略采用粒子群优化算法初始化随机种群，每个解都有其速度。整个种群称为swarm，每个解称为粒子群。拟合函数是基于这里的d元组当每个解覆盖大多数d元组组合时，它成为一个很好的候选者该算法根据粒子的更新角色和速度周期性地更新搜索空间。在这里，作用是根据参数来调整粒子的运动和它们的收敛速度这些参数必须仔细调整，以获得最佳解决方案，而不是陷入局部最小值[30，55]。5. 布谷鸟搜索组合测试如文献所示，与其他算法和方法相比，自然启发和基于AI的算法和策略可以获得更有效的结果。基于AI的算法需要更长的计算时间来生成最终的组合集，因为覆盖d-元组的搜索过程的计算量很大粒子群优化算法试图通过在更新和搜索过程中使用较轻的权重计算来解决这个问题。文献中的证据表明，与其他方法相比，PSO在大多数情况下的结果更好[30]。事实上，PSO并不是没有问题和弊端。粒子群优化算法的性能通常取决于优化参数的取值。换句话说，PSO结合了搜索机制的两个角色：探索和利用。在前一种机制中，PSO执行全局最优解搜索，而在后一种机制中，它通过将搜索收敛到有希望的候选者周围来寻求更精确的最优解。例如，为这些参数选择正确的值应该基于局部和全局探索之间的折衷，这将有助于更快的收敛。有证据表明，根据问题的复杂性，需要这些参数的不同值来实现所需的最佳解决方案[56，57]。此外，该算法的搜索过程陷入局部最优。因此，在一定数量的迭代之后，找到最佳解决方案变得困难。在解决这个问题，新的算法，包含很少的参数调整，没有缺点是更有效的。CS由Yang和Deb在2009年开发[58]。它是最新的自然启发式元启发式算法之一，用于解决全局优化问题[13]。最近，CSA被所谓的Lévy Right-method增强，而不是简单的随机游走[13，55]。该算法主要基于布谷鸟的自然行为。一种布谷鸟在别的巢里下蛋。如果一只宿主鸟确定这些蛋不是自己的，那么它要么把这些外来蛋扔掉，要么干脆放弃自己的巢，在其他地方建一个新巢。CSA的主要理想化角色是每只杜鹃每次产一个蛋，并将蛋倾倒在随机选择的巢中。拥有高质量蛋的最好的巢会传给下一代，可用的宿主巢的数量是固定的。因此，布谷鸟下的蛋被宿主鸟发现的概率在0和1之间。此外，CS可以处理NP难问题，并且可以在几个解决方案中获得最佳解决方案[9，14]。基于这些展望，本研究假设该算法能够很好地解决组合优化问题。本节提供了制定战略的必要细节第5.1节介绍了必要的背景，并说明了CS及其机制的基本细节。第5.2节介绍了“d元组生成”算法的细节。然后，第5.3节介绍了用于组合测试的CS及其优化过程和实现。5.1. 布谷鸟搜索（CS）CS是一种最新、最现代化的求解优化问题的策略。该算法主要用于解决需要全局搜索技术的NP难题[13，58]。图 4示出了说明该算法的一般步骤的伪代码。CSA的规则如下。（1）每只布谷鸟随机选择一个巢，在里面下一个蛋，蛋代表一个解， 一套解决方案。(2)巢的一部分包含最好的解决方案（鸡蛋），将为下一代生存。(3)宿主鸟在固定数量的巢中找到外星蛋的概率为pa ∈ [0，1][59]。 如果宿主鸟以这种概率发现了一个外星蛋，那么它要么扔掉这个蛋，要么放弃这个巢去建造一个新的。因此，我们假设具有n个嵌套的部分pa被新的嵌套替换。CSA使用Lévy Question进行本地和全局搜索[60]。Lévy随机光规则已成功地应用于生物学和物理学等不同领域的随机模拟中。Lévy Righty是一种随机的行走路径，它需要一系列的跳跃，算法1：布谷鸟搜索1初始化n个宿主巢的种群xi，i = 1，2，.. . . ，n2 为所有x我做Fi= f（x i）4端5 while（Number of iterations最大迭代次数6或（满足停止标准）7通过从 RR R和DOMNEST中读取LEVYFLIGHT，获得CUCKOEG（XI）8Fj= f（x i）9选择一个随机的巢i如果Fi> F j，则11xi← x j12Fi←F j13端部14放弃一小部分最糟糕的巢穴15个Buil d nnewnestatnolocationsviaLevyflightstoreplac enestslost16评估新巢的适应度并对所有解决方案进行17端部见图4。 CS的伪代码[58]。我我B.S. Ahmed/Engineering Science and Technology，an International Journal 19（2016）737-753743其选自概率函数。对于布谷鸟i的解x（t+1），一个步长可以由以下方程表示：在d-元组列表中，该策略首先生成一个包含二进制数字的二进制数字（BD）列表;该BD列表从零开始到空间限制（SL）。SL由Eq.3.第三章。BD列表可以由二进制数字填充，并且总数x1Levy（二）BD列表的元素的数量等于（2k）。其中k是每一步的大小，其中k是0，并且取决于优化问题的规模。该产品的质量是入门级的多-2kk个输入因子（三）叠起来，然后Le'vistheL e vydis。算法Ckk！（四）如果目标函数找到更好的位置，则继续将蛋移动到另一位置这一点在图中可以清楚地看到。 当Fi被Fj替换时，其中j是更新后生成的新解决方案的指示。与其他随机优化算法（如PSO和GA）相比，CSA的另一个优点是它缺少许多用于调整的参数。唯一用于调优的参数是pa。Yang和Deb [15，58]从文献中获得的证据表明，生成的结果与该参数的值无关，并且可以拟合为pa= 0.25的建议值。在使用该算法进行组合测试集生成时，必须使算法适应生成策略在这里，拟合函数在CS的适应和应用中起着重要作用。在本文中，在初始化群体之后，CS将群体中每个巢中覆盖的d-元组的数量作为拟合函数。这个函数选择覆盖d元组列表中大多数组合的最佳行5.2. D元组生成算法生成所有组合列表（即， d-元组列表）在计算拟合函数Fi= f（xi）时是必不可少的。d-元组列表包含输入因子k的所有可能组合。该算法主要采用三个输入：输入因子数（k）、每个输入因子的水平（v）和组合度（d）。为了下一代-Dd！快去快去！当创建BD列表时，算法基于组合度来过滤BD列表该算法计算每个二进制数中1的数量，并仅传递那些满足开始时输入中指定的组合度的二进制数。图5示出了BD和IFC的创建。基于指定的组合度，检查点将BD列表中的每个元素与度数（d）进行比较。对于BD列表中具有相同度数的每个行元素（即，重复“1”例如，如果d= 2 ，则 每个二进制数字必须包含两个1 ，其 中（011 ），（101）和(110)通过过滤器。IFC是表示输入因子组合的列表。这里，对于每个包含0的位置，插入输入因子的“无关”值。但是，同一个二进制元素中的1被该特定输入因子的水平所取代。例如，（011）表示三个输入因子（k1、k2和k3）。在这种情况下，第一个输入因子（k1= 0）被视为“无关紧要”，而组合则介于第二个和第三个因子之间。这里，该算法忽略BD列表中不满足组合度条件的元素，并将其余元素添加到IFC列表。图6通过简单的图表示出了该算法的运行示例该图显示了d= 2和k= 3的示例。因此，SL =（（2 × 2 × 2）−1）= 7，这反过来又二进制数字（BD）..................................................................................................................................................................................................................................................................输入因子组合k =输入系数v =每个输入因子的水平（国际金融公司）.......................................................................................................................................................................................................................d =结合度k-1BD =二进制数字=2SL=空间限制= 02kIFC=投入要素组合数据检查计数“1”是否等于“d”创建二进制数字（BD）空间限制（SL）一代DVK图五. IFC算法图。2744B.S. Ahmed/ Engineering Science and Technology，an International Journal 19（2016）737该算法的输出列表可以在图7所示的策略的输出屏幕中清楚地显示，用于具有CA（4; 2，2 4）的系统。一个算法被用来评估搜索过程的组合有效。在本文中，d-元组列表中的行是分组存储的。每个组都分配有一个索引号，指示其在列表中的位置。这些组是根据因素的组合选择的。输入因子的数量等于4（k1、k2、k3和k4），并且当组合度等于2（d= 2）时，每个输入因子具有两个水平（vi= 2、2、2、根据等式4、输入因子组合的个数可以确定如下：见图6。 d = 2，k = 3时的IFC和BD。C4烃 四个！二号！2004年4月2日！432121212464计数二进制数从0到7。该算法的结果满足方程中的结果。4，其中（c）表示组合[61]，即组合的数量等于IFC中的三个元素。根据结果，六种组合是可能的，如图所示。8.第八条。对于每一条路径，可以将级别相乘[（k3，k4），（k2，k4），（k2，k3），（k1，k4），（k1，k3），（k1，k2）]，然后结果为等于[（2 × 2 = 4），（2 × 2 = 4），（2 × 2 = 4），（2 × 2 = 4），（2× 2 = 4），（2 × 2 = 4）]。见图7。 输出策略的屏幕截图。k k k123k，k23k，k13k，k0 1 11 0 11 1 012双梳7IFCBD123k k k0 0 000 0 110 1 02K0 1 13二-11 0 0431 0 152 - 1 =1 1 061 1 172k= 8B.S. Ahmed/Engineering Science and Technology，an International Journal 19（2016）737-753745654K1K2K31K432见图8。 组合路径。根据这些结果，将搜索空间划分为六个分区，并且通过考虑每个组合[（4），（4 + 4 = 8），（8 + 4 = 12），(12+ 4 = 16），（16 + 4 = 20），（20 + 4 = 24）]。因此，该策略动态地创建了六个类别，例如[（1图图9详细说明了给定示例的这 种 机 制 。这种机制的优点是加速了搜索过程，因为该策略只搜索给定索引号中的相关元组。当找到最佳测试用例时，索引会动态地改变，因为搜索空间中的相关元组会立即被删除。5.3. CS优化流程在生成d-元组列表之后，CS开始。在本文中，CS修改，以解决当前的问题。拟合函数用于在一组解中导出更好的解在本文中，具有较高拟合权重的行被定义为可以覆盖d-元组列表中更多行的行。图10显示了组合测试套件生成的伪代码，其中CS为此目的进行了修改该策略首先考虑输入配置。然后，生成d元组列表. CS首先初始化一个随机种群，其中包含一些巢。假设每个输入因子的水平数是离散数，则初始化总体是离散的，而不是开区间。因此，种群初始化为0和v i之间的固定间隔。在本文中，一个系统有不同的因素，其中一个测试用例是一个复合的两个以上的因素，形成一行的最终测试套件。由于这样的安排，每个测试用例被视为一个向量xi，其维度等于系统的输入因子的数量。此外，每个输入因子的水平基本上是整数值。因此，向量初始化的总体中的每个维度必须是整数值。虽然初始种群是在离散区间内初始化的，但该算法可以产生输入因子的越界水平因此，向量必须受到上下界的限制。这一限制的理由是，杜鹃把蛋产在眼睛能识别的巢当CSA迭代时，它使用Lévy的光来走向最优解。Lévy分布是一种使用随机步长的行走在Lévy矩阵中随机步的生成包括两个步骤[62]，即生成步和选择随机方向。方向的产生通常遵循均匀分布。然而，在文献中，步骤的生成遵循几种方法。本文采用了最有效的步长生成方法Mantegna算法[62]。在该算法中，步长s可以定义如下：见图9。 搜索空间的索引。................................................................................................................................................1 - 4**2v1v65 - 8*3v*1v59 - 124v**1v413 - 16*3v2v*3十七、二十4v*2v*221 - 244v3v**1指数K4K3K2K1v1乌乌746B.S. Ahmed/ Engineering Science and Technology，an International Journal 19（2016）737锡乌（五）（步骤2）。从实际的角度来看，每个嵌套包含最终测试套件（FTS）的可扩展测试用例。此后，CSA通过评估每个巢的覆盖能力来评估每个巢。其中，u和v是从正态分布导出的，其中0，，0，2（6）1d-元组（步骤3-5）。例如，一个可以覆盖4元组的嵌套的覆盖权重为4。该策略使用前面描述的特殊机制（第5.2节）来确定覆盖元组的数量并验证权重。使用cov的结果搜索所有巢，该策略在搜索中再次对巢进行排序1