配对组合测试用例集生成的一种新策略

丁怀宝

摘  要： 基于人工蜂群（ABC）算法与粒子群优化（PSO）算法，提出了一种新的配对混合人工蜂群（PHABC）策略，用于求解含约束条件的配对组合测试中测试用例集的生成问题.实验结果表明，即使在带有参数约束的情况下，PHABC输出的最佳组合测试集结果正确性更高，相较于其他现有的策略，性能更优.

关键词： 配对组合测试; 人工蜂群（ABC）算法; 粒子群优化（PSO）算法; 配对混合人工蜂群算法（PHABC）; 约束

文献标志码： TP 312    文献标志码： A    文章编号： 1000-5137（2020）04-0472-06

Abstract： A new pairwise hybrid artificial bee colony （PHABC） strategy based on artificial bee colony （ABC） algorithm and particle swarm optimization （PSO） algorithm was proposed in this paper.The novel algorithm could be used to resolve the generation of pairwise test suite with existing constraint factors.The results of the experiment showed that the accuracy of the PHABC output was more higher and the performance was more excellent than the existing research strategies，even with existing constraint factors.

Key words： pairwise testing; artificial bee colony（ABC） algorithm; particle swarm optimization（PSO） algorithm; pairwise hybrid artificial bee colony （PHABC） strategy; constraint

0  引  言

组合测试充分考虑了系统中各种因素以及因素间相互作用可能产生的影响，根据实际需要，用尽可能少的测试数据，尽可能多地覆盖一些影响系统的因素.这种测试方法对于由系统中某些因素相互作用而导致的软件故障具有较强的检测能力.根据覆盖程度的不同，组合测试方法可以分为：单因素覆盖、两两组合覆盖和三三组合覆盖等.

两两组合覆盖的组合测试，即配对组合测试，要求系统的任何一对输入参数都必须被至少一个测试用例所覆盖.研究发现，许多软件系统的故障由测试参数及其之间的相互作用引起，因此，配对组合测试方法具有较高的理论研究价值和现实意义[1].

配对组合测试用例集可表示为2维覆盖数组，参数之间存在约束条件的配对组合测试用例集可表示为2维约束覆盖数组.为了提高测试的效率，2维约束覆盖数组的规模应尽可能小.为此，很多搜索算法被应用到寻找规模最小或近似最小的2维约束覆盖数组中.主要包括HSS[2]，SA_SAT[3]，mAETG_SAT[4]，PICT[5]，BTS[6]和LAHC[7]等.这些研究策略都是基于不同算法的改进策略，在解决配对组合测试用例集生成问题方面各有优势.但是，生成最佳测试用例集仍然是一个多项式复杂程度的非确定性（NP）难题，尚待进一步探索.因此，本文提出了一种新的优化算法——混合人工蜂群（HABC）算法，该算法有效解决了ABC[8]算法中存在的初始参数随机化问题和易陷入局部最优解等问题.此算法具体实施在带有约束条件的配对组合测试用例集生成问题中，故称为配对混合人工蜂群（PHABC）策略.

1  相关知识

1.1 测试用例集的表示方式

1.1.1 覆盖矩阵（CA）[9]

组合测试用例集的测试用例列表CA（N;t，vp）包含4个基本参数：N，t，p和v，其中N表示测试用例的个数;t表示维数;p表示参数个数;v表示参数值的个数.例如，CA（25;2，56）表示该系统的测试用例集为2维矩阵（即两两组合），有25个测试用例（矩阵的行數），6个参数（矩阵的列数），每个参数可能的值的个数为5.CA要求所有参数值的类型要保持一致.

1.1.2 混合覆盖矩阵（MCA）[9]

MCA（N;t，v_1^（p_1 ），v_2^（p_2 ），…，v_n^（p_n ））具有与CA参数相同的含义，但支持允许参数具有不同类型的值，其中，n表示参数总数.例如，MCA（36;2，536427）表示该混合覆盖矩阵中有36个测试用例，该系统的测试用例集为2维矩阵，共有14个参数，包括3个具有5个值的参数，4个具有6个值的参数，7个具有2个值的参数.

1.1.3 约束覆盖矩阵（CCA）[9]

除了CA和MCA，组合测试用例集中由于约束条件的限制，禁止出现的测试用例以CCA（N;t，vp，F{}）表示，其中，F{}表示被禁止的组合.例如，CCA（N;2，24，F{}），当F={（1，-1，0，-1），（-1，1，0，-1）}时，其中，-1表示非参数值，该系统的测试用例集为2维矩阵，且测试用例数量为16（24）个，（1，-1，0，-1）和（-1，1，0，-1）被禁止出现在最后的测试用例集中.

1.2 人工蜂群（ABC）算法

ABC算法将人工蜂群置于搜索空间中，寻找花蜜量高（适应度值）的蜜源的位置（可行解），得到最高蜂蜜量的蜜源的位置（最优解）.

ABC算法中，蜂群由受雇蜂、跟随蜂和侦察蜂三类组成，其中一半的蜜蜂作为受雇蜂，剩余的一半作为跟随蜂.受雇蜂寻找较高花蜜量的蜜源，并将蜜源信息（路线、位置和周边潜在的蜜源）传达给跟随蜂;跟随蜂根据受雇蜂提供的信息对蜜源进行搜索选择.侦察蜂从受雇蜂中衍生而来，在原有蜜源被抛弃后，寻找新的、更好的蜜源.人工蜂群的行为方式可分为4个阶段：蜜源初始化阶段、受雇蜂阶段、跟随蜂阶段及侦察蜂阶段.通过不同阶段的搜索操作，不断执行循环迭代，直至找到蜂群的最优解或达到指定的迭代次数.

ABC算法主要步骤如下：

Step 1  初始化设置，产生初始蜂群;

Step 2  每只受雇蜂在其对应的蜜源及其邻域进行搜索，并计算新搜索到的蜜源的适应度值，选择保存适应度更高的蜜源的位置;

Step 3  跟随蜂会根据受雇蜂带回来的蜜源信息（适应度值）计算蜜源被选择的概率，从而选择一个蜜源位置，并在其邻域进行搜索，若新搜索到的蜜源的适应度值优于原蜜源，则将新蜜源位置取代原蜜源位置;

Step 4  若某蜜源位置被搜索次数超过阈值，仍没有找到具有更高適应度值的蜜源，则放弃该蜜源位置，同时受雇蜂转化为侦察蜂，随机搜索新的蜜源;

Step 5  记录迄今为止最优的蜜源;

Step 6  如果满足算法结束条件，则输出最优解;否则，转到Step 2.

1.3 粒子群优化（PSO）算法

PSO[10]算法通过群体中个体之间的协作和信息共享寻找最优解，其优点在于能求出多个粒子并存或合作时的最优解.假设种群中存在m个粒子，n个粒子群，第i个粒子的个体最优解为pid，i=1，2，…，m，d=1，2，…，n，所在整体粒子群的最优解为全局最优解gid，用d维速度vi=（vi1，vi2，…，vid）与位置xi=（xi1，xi2，…，xid）改变粒子的状态，通过不断变化速度与位置，产生新一代粒子群

v_i （d+1）=w×v_id+c_1×r_1×（p_id-x_id）+c_2×r_2×（g_id-x_id）， （1）

x_（i（d+1））=x_id+v_id， （2）

其中，r1，r2是[0，1]的均匀分布随机数;w为权重因子，用于平衡全局搜索和局部搜索;c1，c2是加速常数或学习因子，用于调节该粒子向自身已寻找的最优位置和同伴已寻找的最优位置方向飞行的最大步长，取值[0，2].vid是粒子先前的速度;c_1×r_1×（p_id-x_id）为“自身认知”部分，是从当前点指向粒子自身最好点的一个矢量，表示粒子自身的经验或记忆;c_2×r_2×（g_id-x_id）为“群体认知”部分，是从当前点指向种群最好点的一个矢量，表示粒子间的信息共享和相互合作.粒子通过自身的经验和同伴中最好的经验决定下一步的运动，从而有效地搜索到最好的位置.

PSO算法主要步骤如下：

Step 1  初始化粒子群中各个参数;

Step 2  利用适应度值公式计算每一个粒子的适应度值;

Step 3  比较粒子的当前适应度值与历史最优适应度值，更新历史最优值;

Step 4  比较当前适应度与种群历史最优位置适应度值，更新历史最优值;

Step 5  若获得最优值，则输出最优值结果;否则，跳转Step 2继续进行迭代.

2  配对混合人工蜂群（PHABC）策略

为获得比PSO和ABC算法更出色的性能，结合两者的优点，针对带有约束条件的配对组合测试用例集的生成问题，提出了一种新的算法——混合人工蜂群（HABC）算法.HABC算法利用PSO算法中的各粒子之间的信息共享能力改进ABC算法中初始蜜源随机化的问题，同时利用其较强的全局搜索能力，缓解ABC算法易陷入局部最优解问题.

如果一个新粒子被选择的概率大于当前粒子被选择的概率，则更新粒子位置和速度，通过引入与蜂群共享的信息更新其速度

v_（i（d+1））=w×v_id+c_1×r_1×（p_id-x_id）+c_2×r_2×（g_id-x_id）+c_3×r_3×（pa_d-x_id）， （8）

其中，r3和r1，r2类似，是分布在[0，1]的均匀分布随机数，pa是HABC算法子种群中的随机蜜源（随机解）.与1.3节相同，适应度值（概率）较高的蜜源会被优先选择.

HABC算法主要步骤如下：

Step 1  分别初始化ABC和PSO子群;

Step 2  每只受雇蜂在其对应的蜜源邻域进行搜索，并计算新蜜源的适应度值，若其适应度值更高，则新蜜源位置取代原蜜源位置;

Step 3  跟随蜂根据受雇蜂带回来的蜜源信息（适应度值），计算该蜜源被选择的概率，定位概率最高的蜜源，并在该蜜源邻域进行搜索，若新蜜源的适应度值高于原蜜源，则新蜜源位置取代原蜜源位置;

Step 4  若新蜜源被选择的概率高于原蜜源，则新蜜源取代原蜜源位置;否则，受雇蜂（或跟随蜂）变成侦察蜂，随机选择一个蜜源，算法迭代次数增1;

Step 5  执行粒子群搜索阶段，如果一个新粒子被选择的概率大于当前概率，则更新粒子位置和速度;否则，继续搜索粒子，算法迭代次数增1;

Step 6  将各子种群的最优解作为全局最优解，如果2个子种群中任何一个算法满足终止条件，则算法终止，输出最优解;否则，算法转到Step 2.

HABC算法流程图如图1所示.

将混合人工蜂群算法（HABC）运用到配对组合测试（pairwise testing）用例生成的策略称为PHABC策略.

3  实验结果

将PHABC策略与目前比较流行的工具和策略BTS，mAETG_SAT，HSS，PICT，SA_SAT和LAHC相比较，基准数据从现有已发布结果的相关研究中获取[6-7，11-12].为了获得最佳结果，已将PHABC参数调整为c1=c2=c3=2.0，w=0.9，ABC算法最大迭代次数为100，PHABC算法最大迭代次数为1 000次，最优解个数为N=5.该实验是在Windows 7操作系统台式计算机上进行，Java版本JDK1.8.实验中含约束的待测系统CCA如下：

1） 待测系统1：CCA（N，2，33，F{}），其中，F={（-1，2，0），（-1，1，0），（0，-1，1），（2，2，-1），（2，-1，2），（1，2，2）};

2） 待测系统2：CCA（N，2，43，F{}），其中，F={（0，1，-1），（2，-1，3），（3，3，0），（2，1，-1）}.

3） 待测系统3：CCA（N，2，53，F{}），其中，F={（1，1，-1），（4，-1，2），（4，-1，4），（4，3，1），（4，2，-1），（1，3，-1）}.

4） 待测系统4：CCA（N，2，63，F{}），其中，F={（3，5，-1），（-1，3，4），（2，0，-1），（-1，1，2），（3，-1，1），（-1，3，1），（5，4，4）}.

5） 待测系统5：CCA（N，2，73，F{}），其中，F={（-1，0，5），（5，5，3），（4，-1，0），（6，4，-1），（1，4，-1），（6，3，-1）}.

由于PHABC策略的随机性，使每个待测系统独立运行20次获取最优解，得到各策略对于带有约束的待测系统产生的测试用例数量，如表1所示.

由表1可以看出，PHABC算法比其他策略的运行结果更好，在1号待测系统和5号待测系统中产生了更少的测试用例数量，BTS，HSS，LAHC和SA_SAT次之，mATEG_SAT和PICT运行结果较差.

4  结  论

将ABC和PSO算法有机结合，提出PHABC策略，用于求解含约束条件的配对组合测试中测试用例集的求解问题.通过实验分析，证明该策略的可行性及高效性.在以后的研究工作中，将进一步改进PHABC策略，使其能够适用于所有交互强度的组合测试.

参考文献：

[1] 聂长海，徐文宝，史亮.一种新的二水平多因素系统两两组合覆盖测试数据生成算法 [J].计算机学报，2006，29（6）：841-848.

NI C H，XU W B，SHI L.A new pairwise covering test data generation algorithm for the system with many 2-level factors [J].Chinese Journal of Computers，2006，29（6）：841-848.

[2] ALSEWARI A R A，ZAMLI K Z.Design and implementation of a harmony-search-based variable-strength t-way testing strategy with constraints support [J].Information and Software Technology，2012，54（6）：553-568.

[3] COHEN M B，DWYERM B，SHI J.Constructing interaction test suites for highly-configurable systems in the presence of constraints：a greedy approach [J].IEEE Transactions on Software Engineering，2008，34（5）：633-650.

[4] COHEN M B，DWYER M B，SHI J.Exploiting constraint solving history to constructinteraction test suites [C]//Academic and Industrial Conference Practice and ResearchTechniques.Windsor：IEEE，2007：121-132.

[5] CZERWONKA J.Pairwise testing in real world [C/OL]//Proceedings of 24th Pacific Northwest Software Quality Conference，2006[2020-05-30].http：//msdn.microsoft.com/en-us/library/cc150619.

[6] ALSARIERA Y A，AHMED H A S，ALAMRI H S，et al.A bat-inspired testing strategy for generating constraints pairwise test suite [J].Advanced Science Letters，2018，24：7245-7250.

[7] ZAMLI K Z，ALSEWARI A R，AL-KAZEMI B.Comparative benchmarking of constraints t-way test generation strategy based on late acceptance hill climbing algorithm [J].International Journal of Software Engineering & Computer Sciences，2015，1：15-27.

[8] KARABOGA D.An idea based on honey bee swarm for numerical optimization [R].Kayseri：Erciyes University，2005.

[9] 王艷玲，李龙澍，胡哲.群体智能优化算法 [J].计算机技术与发展，2008，18（8）：114-117.

WANG Y L，LI L S，HU Z.Swarm intelligence optimization algorithm [J].Computer Technology and Development，2008，18（8）：114-117.

[10] KENNEDY J，EBERHART R.Particle swarm optimization[C]//International Conference on Neural Networks.Honolulu：IEEE，2002：1-23.

[11] ALSEWARI A A，ZAMLI K Z，ALKAZEMI B.Generating t-way test suite in the presence of constraints [J].Journal of Engineering and Technology，2015，6（2）：52-66.

[12] LI L S，CUI Y X，YANG Y.Combinatorial test cases with constraints in software systems [C]//International Conference on Computer Supported Cooperative Work in Design.Wuhan：IEEE，2012：195-199.

（责任编辑：包震宇）