混合测试用例自动生成算法

曹小鹏，张 莹，唐 煜

(西安邮电大学 计算机学院，陕西 西安 710121)

0 引 言

在软件开发过程中，为了确保软件质量，利用测试用例自动生成技术，以达到用最少的测试用例找到尽可能多的错误。目前遗传算法、禁忌搜索算法、正交算法、粒子群算法、蚁群算法等启发式搜索算法在测试用例自动生成技术得到广泛应用，该技术将测试用例生成过程转换为使用智能算法求解最优值问题[1-2]。胡文欢等[3]在遗传算法测试用例自动生成中引进突变控制策略和优化解控制策略，有效提高了算法的搜索能力和获取最优解的性能。贾冀婷[4]针对粒子群算法容易陷入局部最优问题，对算法增加了“邻居”最优位置，进而提高了算法的局部搜索能力，证明该算法所需的迭代次数和平均运行时间，明显优于遗传算法等测试用例自动生成算法，提高了生成测试用例的自动化程度。董跃华等[5]引进一种新的启发式搜索算法—花朵授粉算法应用于测试数据自动生成，证明该算法比改进的遗传算法和粒子群算法在测试用例自动生成上的可行性高。对以上文献分析可知，在测试用例自动生成方面采用智能优化算法有较强优势，但同时随着算法的迭代，种群样本数越来越少，空间搜索能力下降，导致算法易陷入局部最优值。

为了解决花朵授粉算法早熟的缺陷，文中借鉴蛙跳算法(SFLA)的思想，对花粉配子种群个体先计算适应度值，并按照适应度值从大到小顺序进行排序，再划分种群为多个子族群，更新各个子族群中的最差个体位置，提高算法局部收敛速度，再将混合算法应用于测试用例的自动生成。

1 相关概念

1.1 花朵授粉

花朵授粉算法[6]是YANG X S教授受自然界中显花植物花朵授粉过程的启发而提出的一种新型群体智能优化算法。其授粉过程分为异花授粉和自花授粉。异花授粉是利用自然界的蝴蝶、蜜蜂、苍蝇等传播者，进行花朵间长距离传播授粉，因此又称为全局授粉；自花授粉是花朵的花粉传播到自身，相当于近距离传播，因此也称为自花授粉。算法还提供转换概率p来解决花朵授粉过程的全局搜索和局部搜索的切换问题。同时由于昆虫等传播者的长距离传播遵循莱维飞行机制，所以全局授粉能力较强。现在，花朵授粉算法已在函数优化[7]、无线传感网[8]、电力系统[9]等领域中应用广泛。该算法实现简单、参数少、易调节，且综合了布谷鸟算法和蝙蝠算法的优点，是一种优秀的智能优化算法。

在FPA算法求解最优化问题时，还需假设条件：每株开花的植物只开一朵花，且只会有一个花粉配子，此时一朵花的配子就是求解过程的一个解。经过这样简化，一个配子或一朵花就相当于优化问题的解。

该算法实现的具体步骤为：

(1)初始化所有参数，设定转换概率p∈[0,1]切换全局搜索和局部搜索，花朵种群数为n，再计算出每个解的适应度值，求出当前的最优解及最优值。

(2)全局授粉过程如式1所示，此时转换概率p>rand。

(1)

若求解最小优化问题，目标搜索空间为D维，种群规模为N。其中第i个花粉粒子位置向量表示为Xi=(Xi1,Xi2,…,XiD)，i=1,2,…,N。整个种群的最优位置为g*=(g*1,g*2,…,g*D)(全局最优解)。参数L是步长，L的计算公式为：

(2)

其中，λ=3/2，Γ(λ)是标准的伽马函数。

(3)局部授粉过程如式3所示，此时转换概率p

(3)

(4)计算式1或式3获得新解，如果新解的适应度值比当前解的适应度值优，就用新解替换当前解。

(5)如果在步骤2获得的解中有适应度值优于全局最优值，则用新解替换当前全局最优解。

(6)如果算法达到终止条件，则输出最优值和最优解，结束迭代，否则，返回步骤2继续进行位置更新。

1.2 蛙跳算法(SFLA)

蛙跳算法是一种解决组合优化问题的新型智能优化算法。该算法模拟自然界青蛙捕食的过程，并在求解优化问题时将解当作种群的青蛙，通过模仿青蛙在寻找食物过程中的合作与竞争实现对最优解的搜索。

SFLA算法描述如下：对于求解D维空间的优化问题，随机生成F只青蛙群体Q=(X1,X2,…,XF)作为初始种群。第i只青蛙的位置记为Xi=(Xi1,Xi2,…,XiD)，计算种群中全部青蛙的适应值f(Xi)，并依照适应值的大小对个体进行降序排列，记录当前全局最优个体Xg。将整个青蛙群体分割成m个子族群，且每个子族群包含n只青蛙，即满足F=m×n。族群分割公式为：

Mi={Xi+m(h-1)∈Q|1≤h≤n}

(4)

其中，Mi为第i个子族群。每个子族群中最优个体为XS，最差个体为XW。局部子族群最差个体XW按如下规则更新。

更新策略为：

Lj=γ(XS-XW)

(5)

(6)

(2)向全局最优个体学习。如若规则1中新个体适应度值劣于原来最差个体适应值，则用全局最优个体Xg替代XS，再依据式5和式6进行更新。

(3)随机更新。若经过规则1与规则2生成的新适应值劣于原来的适应值，则在搜索空间范围内依照XW随机生成一个新解替换原来式中的XW。

重复以上操作，直到满足终止条件。其中，γ为[0，1]内的均匀分布随机数；j=1,2,…,m；Lj为青蛙更新步长；Lmax为最大更新步长，Lmin为最小更新步长。

2 FPA算法的改进以及在测试用例生成中的应用

2.1 改进算法

通过对SFLA算法和FPA算法的分析，发现蛙跳算法可以弥补花朵授粉算法的不足。针对花朵授粉算法局部搜索能力低下、易陷入早熟现象等问题，根据SFLA对花粉位置进行更新。首先，将花朵种群分割成不同的子族群，每个子族群按照蛙跳算法的规则进行更新。花朵个体向子族群之间最优个体XS学习，若更新失败，再向全局最优个体Xg学习，如若2次都更新失败，则在可行域内随机产生一个新解替换局部最差个体XW。其次，每个子族群达到最大演化代数后，再将所有的子族群打乱重新混合，让花粉种群信息互换，以免种群汇集，保持多样性。由此可知，文中将两种算法结合，得到一种混合优化算法，即混合群体爬山策略的FPA(hybrid FPA of colony mountain climbing strategy，CMSFPA)。

为了加强算法局部寻优能力，维持种群多样性，防止种群花粉粒子向全局最优值处汇聚，对子族群的进化过程中只采用XS，而没有采用g*(或Xg)。混合算法流程如图1所示。

做为中建人的一员，全年在外施工是常态，对于家里自是无暇顾及，数次搬家、两次装修，抚养孩子，孝敬老人统统甩给了妻子，偶尔回到总部开会，也是匆匆来匆匆走，老人曾说他就是一个“野人”。然而，电话的那一头，却总是“儿子的胃病好点没，爹的假牙换了没……”他对家人的惦念一直留在心里，随着年龄的增长，他越来越注意抽出时间与父母唠家常，倔强的父亲也逐渐理解了这个“不孝”的儿子。

图1 CMSFPA算法流程

2.2 CMSFPA算法在测试用例生成中的应用

根据CMSFPA混合算法流程及测试用例生成的基本理论，创建了混合测试用例自动生成算法的系统模型框架，包含3个模块，如图2所示。

模块一为测试环境的搭建模块。该模块是建立框架的基准，对被测程序进行静态分析，然后根据选择的目标路径进行参数选择及分支函数插桩；模块二为CMSFPA算法模块。该算法是核心部分，首先对CMSFPA进行参数设置以及随机初始化一组解，然后对产生的解评估适应度，如果满足终止条件就输出最优解，如果不满足最优解就利用CMSFPA算法对初始解进行迭代操作，以此来对解进行更新，直到寻得足够优的位置或算法达到终止条件；模块三为测试执行模块。CMSFPA测试执行模块在测试用例生成框架中起到了实时调用并运行的作用，它主要完成对插桩后的被测测序的实时调用和运行，再将得到的适应度值传递给CMSFPA算法模块使用。

图2 CMSFPA算法测试用例自动生成框架

2.3 适应度函数的构造

适应度函数构造直接影响FPA效率。一般情况下，适应度函数由目标函数转化而来。设计时要满足以下条件：(1)单值，连续，非负，最大化；(2)合理，一致；(3)计算量小；(4)通用性强。

优良的适应度函数能够快速求出最优解。因此，能否合理并成功地构造适应度函数，是提高算法效率的关键点。换而言之，其适应度值反映了种群个体测试用例的测试效率，对应的值越高表明测试效率越高，因而测试用例能够在较短时间覆盖更多的目标路径，就能找到更多的程序错误。

基于文中测试用例生成模型框架的特性，综合考虑各方因素，选取“分支函数”[10]插装法来构造适应度函数，定义如下：假设被测程序中指定的某条路径有m个分支点，即Path=n1,n2,…,nm。首先，在每个分支点前插入适当的分支函数f1,f2,…,fm；其次，把这m个分支函数叠加：F=f1+f2+…+fm，并将叠加后的F作为适应度函数，其中fi∈[1,m]的值表示当前实际测试路径与指定逻辑路径的偏差距离。

文中假设的全部分支谓词都是形如MopN的简单关系表达式。M、N均为运算对象(包括运算表达式)，op为运算符[11](包括<，<=，==，！=，>，>=)。适应度函数值判断分析见表1。

表1 适应度函数值判断分析

如表1所示，根据分支函数fi=N-M可知，f越大表明测试用例距离指定路径越远，f越小表明测试用例距离指定路径越近。选取分支路径有以下2种情况：(1)分支判断语句为真，则fi<0，其对应的适应度函数值等于0；(2)分支判断语句为假，则fi>0，其对应的适应度函数值等于N-M的值。因此，为了产生某目标路径测试用例，需要获取目标函数值为0的F。

3 实验结果与分析

3.1 实验方案

选取三个开源程序为被测对象，程序的详细信息如表2所示。

表2 测试程序

程序1的目标路径为等边三角形；程序2的目标路径为输入的10个字符均为16进制的字符，且其转化为10进制之后的总和在50～100之间；程序3的目标路径是判断数组中全部变量是否为0

实验将标准的FPA和PSO、CMSFPA分别应用于自动生成模型测，再对三者进行对比分析。算法涉及的参数为：PSO的学习因子c1、c2=2，惯性权重系数ω随迭代次数的增加由0.9线性减小到0.4，FPA与CMSFPA的转换概率p=0.8。随后利用迭代次数和运行时间作为实验成果的评价指标[14]。最后产生的全部目标路径测试用例的用时越短、进化代数越少，说明算法改进效率越高。

3.2 最优解迭代次数和最优解迭代时间对比

在实现CMSFPA、FPA、PSO三种算法分别产生实验程序的测试用例中，引用文献[15]数据，规模分别设置为140，180，220，260和300，设置最大进化代数为800。基于以上设置，将基本的PSO和混合的CMSFPA、基本的FPA作为核心算法应用于系统模型，其次，每个种群都互相独立地进行10组测试实验，对10次实验产生的运行时间(运行时间为10次找到最优迭代时间的平均值)和最优解所需的迭代次数进行了对比分析。

表3是以上3种算法分别对程序1、2、3进行测试生成最优解所需的最迭代次数。

表3 CMSFPA、FPA、PSO找到最优解迭代次数对比

从表3可以看出，随着种群规模的增加，三个测试程序对象采用混合的测试用例自动生成算法所需的迭代数普遍少于标准的花朵授粉算法和粒子群算法。说明文中算法明显优于标准的FPA、PSO。当种群规模达到300时，PSO、FPA、CMSFPA找到最优解的效率比较显著，但是随着后期种群搜索空间减小，种群规模越来越少，导致种群多样性下降，普通的PSO算法和FPA算法渐渐显现缺陷。在被测程序运行期间有时会快速地找到好的测试数据，但在多次迭代演化后，测试数据一成不变，表明该算法已陷入了早熟状态。可以看出当种群规模由300减少到140时，PSO算法和FPA算法找到最优解迭代次数增加较多，比较容易陷入局部最优解，而混合的FPA算法的迭代次数明显比PSO算法和FPA算法少，说明混合的FPA算法成功地解决了早熟问题，并且提高了收敛速度。

对3种测试程序分别进行测试，记录当种群的规模由140递增到300时，CMSFPA 、 FPA 、PSO算法生成最优解迭代时间的平均值，如实验结果图3～图5。

图3 程序1找到最优解运行时间

从图3可知，应用PSO、FPA、CMSFPA算法进行实验，其中PSO、FPA产生最优解迭代所需时间显著大于CMSFPA所需时间，在迭代次数良好的条件下，CMSFPA平均运行时间比基本FPA减少在 40ms 以上，比基本PSO减少在60ms 以上。

图4 程序编号程序2找到最优解运行时间

从图4可知，应用PSO、FPA、CMSFPA算法进行实验，其中PSO、FPA产生最优解迭代所需时间显著大于CMSFPA所需时间，在迭代次数良好的条件下，CMSFPA平均运行时间比基本FPA减少在 170ms 以上，比基本PSO减少在180ms 以上。

图5 程序3找到最优解运行时间

从图5可知应用PSO、FPA、CMSFPA算法进行实验，其中PSO、FPA产生最优解迭代所需时间显著大于CMSFPA所需时间，在迭代次数良好的条件下，其平均运行时间比标准FPA减少在 240ms 以上，比标准PSO减少在370ms 以上。通过对以上三个图的对比，可知混合的算法优越性明显。

综上所述，与标准FPA、PSO算法相比，本文研究的CMSFPA算法测试用例自动生成框架不仅收敛速度快、平均运行时间短，还能有效解决局部最优解缺陷，可以高效、精确地生成所需的测试用例。因而应用本文研究的CMSFPA 算法与标准算法相比生成测试用例的效果显著。

4 结束语

为了提高测试用例自动生算法局部搜索能力，改善易于陷入早熟状态的等问题。本文通过将花朵授粉算法融合蛙跳算法思想应用于测试用例自动生成，将花朵种群分成若干子族群，并根据SLFA规则学习并运行，不仅增强了FPA的局部搜索精度，而且改善了FPA陷入局部最优值误区状况。最后实验部分通过3个测试程序对算法进行了对比验证，实验证明CMSFPA有较强的寻优能力，对测试用例生成效率有了较大提高。