软件测试是对软件应用程序进行评估，以确定其是否存在缺陷的过程，这个过程确保了软件产品的质量。但是软件测试是一个相当昂贵的过程，其占据了软件开发成本的50%^[1]。在软件测试过程中，测试用例的生成是最为关键的一步。测试用例以前以手工生成为主，但后来为了提高测试用例的质量以及节省时间和资源，手工生成测试用例的方法逐步被自动化生成测试用例所取代^[2]。一般情况，新的测试用例生成可以通过原测试用例进行变异形成。因此，只需要在原测试用例的基础上自动变异便可以实现自动化生成测试用例^[3]。

软件行业的自动化测试已经将测试效率从20%提高到80%^[4]。一般情况下，自动化测试采用启发式算法自动或半自动地生成测试用例，而且还可以提供测试的分支覆盖，以实现更快的测试速度、减少测试数据等^[5]。为了实现软件测试中测试用例生成的自动化，将启发式算法如智能仿生算法应用于自动化测试中以生成和优化测试用例^[6]。例如，采用蚁群算法(ant clony optimization，ACO)对测试用例进行生成和优化后，测试用例减少了62%^[7]。

除了蚁群算法，遗传算法(genetic algorithm，GA)、萤火虫算法(firefly algorithm，FA)、人工蜂群算法(artificial bee colony algorithm，ABC)和粒子群算法(particle swarm optimization，PSO)等基于启发式技术的智能仿生算法也被用于软件自动化测试中^[8]。Bueno等^[9]提出了一种基于遗传算法和模拟退火的随机测试用例生成方法，该方法利用了测试集的差异，成功地提高了测试用例的变异效率和覆盖率。Srivatsava等^[10]引入了萤火虫算法，结合萤火虫的行为，利用图归约方法产生最佳测试数据序列，该方法提供了测试路径，可用于昂贵的测试过程。Lam等^[11]提出了利用人工蜂群算法进行测试数据集优化的方法，该方法适用于小规模程序。为了减少测试用例的数量，粒子群优化算法也被用于软件自动化测试中^[12]。针对软件测试用例自动化生成的效率问题，本文提出了一种改进的乌鸦搜索算法(improved crow search algorithm，ICSA)，利用其变异算子生成有效且优质的测试用例以实现自动化软件测试。该算法引入变异敏感度测试的概念^[13]，用相对误差作为变异敏感度的度量，克服传统软件测试的缺点。然后采用相对误差作为算法的适应度函数，利用柯西变异算子避免局部搜索最优。最后，将该算法与其他启发式算法(遗传算法、粒子群算法、蚁群算法和乌鸦搜索算法)进行了实验比较。

1 乌鸦搜索算法

乌鸦以其聪明才智而闻名，乌鸦可以观察到其他鸟类的食物隐藏方式。乌鸦由于记忆力很好，在观察了其他鸟的活动后，可以偷吃其他鸟的食物。乌鸦也知道如何利用其盗窃经验来避免食物被偷。利用乌鸦觅食的行为，Askarzadeh^[14]提出了乌鸦搜索算法。

设一个d维空间可以容纳乌鸦的总数为N。第i只乌鸦的位置用向量 ${{{x}}^{i,{i_{\rm{t}}}}}$ (i=1, 2,…, N；i_t=1, 2, …, i_t,m)表示，其中 ${{{x}}^{i,{i_{\rm{t}}}}}{\rm{=}}\left[ {x_1^{i,{i_{\rm{t}}}},x_2^{i,{i_{\rm{t}}}}, \cdots ,x_d^{i,{i_{\rm{t}}}}} \right]$ ，i_t,m是最大迭代次数。

假设乌鸦藏匿食物的位置为 $m_{}^{i,{i_{\rm{t}}}}$ 。这个位置被认为是乌鸦的最佳位置。在第i次迭代中，乌鸦i访问其隐藏的食物源。现在乌鸦i决定跟随乌鸦j去获取食物，根据感知概率(用变量P表示)，则可能出现2种情况：

1)乌鸦j不知道后面跟着乌鸦i，在这种情况下，乌鸦i会找到乌鸦j的食物隐藏位置。因此乌鸦i将得到一个新的位置，这个位置由以下等式给出

${x^{i,{i_{\rm{t}}} + 1}}={x^{i,{i_{\rm{t}}}}} + {r_i} \times f_{\rm{l}}^{i,{i_{\rm{t}}}} \times ({m^{j,{i_{\rm{t}}}}} - {x^{i,{i_{\rm{t}}}}})$

(1)

式中：r_i是均匀分布在0和1之间的随机数； ${m^{j,{i_{\rm{t}}}}}$ 是乌鸦j隐藏位置； $f_{\rm{l}}^{i,{i_{\rm{t}}}}$ 为局部变量，有助于跳出局部搜索， $f_{\rm{l}}^{i,{i_{\rm{t}}}}$ 的值越大，越容易进行全局搜索。

2)乌鸦j知道乌鸦i在跟踪它。因此，乌鸦j将通过欺骗乌鸦i来保护它的食物来源。为了躲避乌鸦i跟踪，乌鸦j将会随机进入搜索空间的位置来愚弄乌鸦i：

$ {x^{i,{i_{\rm{t}}} + 1}}={\rm{random}}\;p $

(2)

根据式(1)和(2)，乌鸦的位置会在搜索空间中更新。通过对新位置的适应度函数进行评价，如果新位置的适应度优于原来位置的适应度，则就用新的位置更新原来的位置。

在启发式算法中，为了获得最优结果，必须考虑2个相反的准则，即多样性和收敛性。如果搜索空间被限制在一个局部区域内，将无法得到最优结果。乌鸦搜索算法试图通过飞行长度 $f_{\rm{l}}^{i,{i_{\rm{t}}}}$ 和感知概率P在多样性和收敛性之间保持平衡。飞行长度 $f_{\rm{l}}^{i,{i_{\rm{t}}}}$ 的值越小就越容易导致局部搜索，相反 $f_{\rm{l}}^{i,{i_{\rm{t}}}}$ 的值越大就越容易导致全局搜索。感知概率P的值低就容易导致搜索空间局限于局部区域，相反较高的P值就容易导致全局搜索。这些参数是由用户在执行算法之前选择的，并且在选择这些参数时不用考虑执行过程中获得的解的状态，这就有可能导致最终的解很容易陷入局部最优。

为了解决上述问题，本文提出了一种改进的乌鸦搜索算法。该算法使用已被应用于许多启发式算法的柯西变异算子^[15]代替飞行长度，并将P设置为第i代迭代时每个群体可产生的最大相对误差。柯西变异算子的引入有效地提高了ICSA算法的搜索性能和效率。

2 改进的乌鸦搜索算法

改进的乌鸦搜索算法利用乌鸦的觅食行为，结合柯西算子和动态P值，利用变异操作来生成测试数据集。柯西算子在生成新位置时考虑乌鸦的初始位置，由于柯西的随机数有时可能很高，因此它可以防止解陷入局部最优。动态P的值有助于搜索到最优解，故柯西算子和动态P值方面的改进有助于探索全局最优解，并取得良好的效果。

2.1 适应度函数

在改进的乌鸦搜索算法中，利用柯西变异算子来对测试用例进行变异，而适应度函数的目标就是评价这些变异优劣。采用由Hook等^[13]提出的相对误差适应度函数来检验算法中是否存在变异。设P_o(t)和P_m(t)分别为变异前和变异后测试用例生成的结果，则

$\gamma ({P_{\rm{m}}},t)=\frac{{{P_{\rm{m}}}(t) - {P_{\rm{o}}}(t)}}{{{P_{\rm{o}}}(t)}}$

式中：γ是相对误差；t是测试用例。

最大相对误差可计算为

$\tau ({P_{\rm{m}}},t)={\max _{t \in T}}\{ \gamma ({P_{\rm{m}}},t)\} $

式中τ是最大相对误差，这有助于用更加广泛地使用测试用例来测试程序。

相对误差随着测试用例值的变化而增加，即当选择适当的测试用例时，相对误差会增加。

2.2 算法实现

本节讨论如何实现改进的乌鸦搜索算法以完成最佳测试用例生成和变异检测。设乌鸦对应于d维搜索空间中的测试用例，其中d对应于测试用例的维数，乌鸦种群的大小对应于测试用例的数量(N)。

测试用例在搜索空间中的位置按照前面的规则进行定义。测试用例的初始数据是随机初始化的，利用适应度函数对原始位置的测试用例进行评价，即适应度函数检验初始种群的测试用例是否能产生较高的相对误差。适应度函数在第i次迭代时检查与初始种群的最大相对误差，然后根据乌鸦搜索算法，选择随机测试用例，并根据式(3)更新其位置：

${x^{i,{i_{\rm{t}}} + 1}}=\left\{ {\begin{array}{*{20}{l}} {{x^{i,{i_{{\rm{t}}}}}}={x^{i,{i_{{\rm{t}}}}}} + {r_i} \times f_{\rm{l}}^{i,{i_{{\rm{t}}}}} \times ({m^{j,{i_{{\rm{t}}}}}} - {x^{i,{i_{{\rm{t}}}}}}),\quad {r_j} \geqslant P_{\rm{m}} ^{j,{i_{{\rm{t}}}}}} \\ {{\rm{a}}\;{\rm{random}}\;{\rm{position}},\quad {\rm{{\text{其他}}}}} \end{array}} \right.$

(3)

式中r_i和r_j是均匀分布在0和1之间的随机数。最大感知概率P_m对应于在第i次迭代时产生具有最高相对误差的测试用例，然后更新目前位置并存储起来。

使用式(4)生成测试用例的新位置：

${x^{i,{i_{\rm{t}}} + 1}}=\left\{ {\begin{array}{*{20}{l}} {{x^{i,{i_{\rm{t}}}}} + {r_i} \times C \times ({m^{j,{i_{\rm{t}}}}} - {x^{i,{i_{\rm{t}}}}}),\quad \quad {r_j} \geqslant P_{\rm{m}} ^{j,{i_{\rm{t}}}}} \\ {{\rm{a}}\;{\rm{random}}\;{\rm{position}},\quad {\rm{{\text{其他}}}}} \end{array}} \right.$

(4)

式中C是从柯西分布中抽取的随机数。柯西随机数有时非常大，从而帮助乌鸦跳出局部搜索空间。如果利用柯西分布确定乌鸦位置超过 ${m^{j,{i_{\rm{t}}}}}$ ，则利用缓存中优化后的测试用例对程序进行测试。

为了更好评价测试用例的变异效果，采用变异得分的概念来衡量算法应用于软件测试中的效果。变异得分可根据被终止的变异体个数q和变异体总数s计算得出，公式为

$ {{S}}\left( {Q,R} \right)=q/s $

(5)

式中：Q表示程序；R表示测试数据集。

图1为改进算法的流程，算法伪代码如下：

设置群大小和迭代次数，初始化乌鸦的位置和缓存。

while i_t<i_t,m

　for i=1 to N

　　评价初始缓存的适应度函数

　　产生柯西随机数

　　从缓存中随机选择一个测试用例，用式(4)更新乌鸦的位置

　end for

　　评估适应度函数并更新缓存

　　利用更新缓存中的测试用例通过式(5)计算变异分数

　　重复上述步骤，检查终止条件

end while

3 实验结果与分析

在软件环境为MATLAB 2018b，硬件环境为8 GB内存、64位Intel(R)I5 2.30 GHz处理器的条件下对该算法进行了仿真实验。然后将本文的算法与遗传算法、粒子群算法、蚁群算法和乌鸦搜索算法的仿真结果进行了比较。

3.1 基准程序

针对实验测试，使用了10个基准程序来验证所有对比算法的效果，这10个基准程序见表1。

3.2 评价标准

变异得分是一种性能度量，它提供了如何有效地检测或终止变异的数量。变异得分可以衡量启发式算法应用于软件测试中的效果，因此本文采用式(5)来计算变异得分作为比较算法应用于软件测试性能的评估指标。

3.3 参数设置

表2给出了实验测试参数，其中种群的个体成员是指GA中的染色体、PSO中的粒子、ACO中的蚂蚁、CSA和ICSA中的乌鸦。对于较小的程序，设置最大迭代次数i_t,m=300。对于较大的程序，由于其执行时间较长，所以对于其最大迭代次数i_t,m设置为100或50。

表3给出了每个算法的参数，其中一些参数取自于文献[16]。

3.4 结果分析

经过实验测试，表4和图2给出了各种对比算法的变异得分及得分分析。通过对比可以看出本文算法相对于其他算法在软件测试方面的改进。

从表4和图2得到的结果表明，对于程序binSearch、calDay和GCD，ICSA算法获得了大约98的高变异分数。然而，针对OdeRK4程序的最低得分92分也高于或等于其他算法对于所有程序的最高得分。从实验结果可以看出，遗传算法在所有算法中的变异得分都很低，即使是CSA算法的变异得分，也都高于GA、PSO和ACO。由于ICSA算法是针对CSA算法的改进，所以ICSA算法在所有算法中变异得分最高也属于正常。这是因为ICSA算法在柯西变异算子的帮助下防止乌鸦陷入局部最优搜索，而传统算法无法解决解陷入局部最优的问题。另外，适应度函数的强度以及乌鸦搜索算法的均衡搜索模式在很大程度上也有助于提高变异得分。

3.5 算法复杂度分析

循环复杂度是指程序的源代码中量测线性独立路径的个数。由于本文算法是应用于软件测试中，所以利用循环复杂度对所有对比算法的复杂度进行了评估。表5给出了所有对比算法的循环复杂度。

复杂度评估结果表明，与其他算法相比，ICSA算法具有最小的循环复杂度即最少的线性独立路径数，因而易于开发和测试。

4 结论

一个有效的优化算法能够提供最优的测试用例数，防止陷入局部最优。本文所提出的ICSA算法利用柯西变异算子自动生成最优的测试数据集，解决了解陷入局部优的问题。在ICSA算法中，采用了相对误差作为适应度函数，通过识别有效的测试用例来提高变异得分。实验结果表明，所提出的ICSA算法的变异得分大幅高于用于对比测试的GA、PSO、ACO和CSA算法。

与其他算法相比，ICSA算法具有更好的效果。因此，ICSA算法可以用于软件测试中有效测试用例的进化。