遗传算法结合黑盒测试实现全局最优解

　　遗传算法是把类似于遗传基因的一些行为(如交叉重组、变异、选择等引入到算法求解)。黑盒测试通常也被称为是功能测试，主要针对模块进行功能测试，检测每个功能是否能正常使用。最常见的方法便是以软件的功能说明书为基础，将软件的输入划分为若干个等价类，多次运行该软件来检验软件对于不同的等价类是否能满足要求。

　　但面对数据量较大的测试工作时，等价类划分后进行的测试工作可能是一个超大的任务。因而需要选择一个最优的测试方法。遗传算法的特点之一便是它同时保留着若干局部最优解，通过交叉重组或者解的变异来寻求更好的解。若将遗传算法运用到黑盒测试中，便能够极大的减轻工作量。

　　一、应用方法

　　在设计具体的算法之前，我们先介绍遗传算法的基本算法，其算法框架如下[1]：

　　第一步，初始化：选取p个候选解作为初始解，把其中最好的解作为暂定(最优)解。

　　第二步，解的改进：若满足终止条件，输出暂定解，算法终止。否则，进行以下的运算：

　　(1)解的交叉重组：从p个解中选出两个或两个以上的解进行交叉重组，得到新解，重复该运算若干次。

　　(2)解的变异：在候选解中随机加进一些变异，产生新解。

　　(3)局部搜索：对新产生的解用局部搜索法进行改良。若能得到比候选解更好的解，更新候选解。

　　(4)从全部解中按一定的准则选出p个解作为下一代的候选解，更新暂定解。

　　转第二步。

　　了解了遗传算法的算法框架后，进一步要做的就是在软件的黑盒测试中，如何将不同的等价类转变为遗传算法的候选解， 如何设定解的优劣标准，如何设置合适的终止条件。

　　我们假定一个软件模块的输入参数有5个：A、B、C、D、E，经过合理的等价类划分后，每个参数又有5个不同的等价类：A1～A5，......，E1～E5。我们采用一个广义的遗传算法候选解概念，一般的遗传算法往往将候选解形式定为二进制的数据串，比如：111010、010001等等，而在不同等价类输入作为候选解时我们将候选解形式定为(按照上面假定为基础)：A3B1C2D4E5、A2B2C4D1E3等等。这样我们解决了候选解的问题，在解的优劣标准以及终止条件的设定问题上，我们需要借助工具作为标准。

　　软件测试的目的是提高软件的可靠性，终止条件当然是软件达到了测试的目的及要求。而解的优劣标准正好与软件质量相反，即软件失效几率越大，这个测试用例(一个输入的解)越优。文献2中结合北大的青鸟黑盒测试环境提出了一种基于测试执行的失效数据模型JBFDM(Jade Bird failure data model)。利用该模型我们可以做到[2]：

　　(1)提供一致的失效数据建模、收集及管理的可靠性度量过程，从而支持可靠性度量;

　　(2)利用测试及软件现场收集的数据来评价测试计划、操作概图及测试方法的有效性。

　　软件测试的目的是发现错误，在黑盒测试中，错误表现的形式是软件失效。但是由于软件错误并不是软件失效的充分条件，换句话说，并不是所有错误都会在测试或运行时暴露，所以黑盒测试的目的就是尽可能的通过运行测试用例使软件失效而发现错误。在我们对测试用例的评价时，用以下的数据表示测试用例的优劣：

　　A=P+λ/M+μ×F

　　其中A表示遗传算法中的适应度Adaptation，P表示该测试用例在实际中发生的几率Probability，M表示平均失效时间(MTTF)，F表示失效等级。因为测试是针对使用的，所以发生几率高的测试用例适应度高就不难理解了;而M——平均失效时间越长，该测试用例应该不容易发现软件的错误，所以A越低;F则表示某些特殊情况发生使软件严重失效(比如造成死机、损坏仪器等等)，此时该测试用例以及其后代必须被重点关注，所以此时A越大。λ、μ是相应于各个具体的被测试软件模块而定的系数。在实际应用中，由于软件失效的可能性不是特别大，所以遗传结果往往是发生几率高的测试用例后代较多。所以我们应该针对具体被测试软件设计准确的发生概率产生算法。具体算法框架如图1所示。

　　二、黑盒测试

　　对于该算法的说明如下：

　　1.每一个输入参数往往有一个几率(可以事先定义)，可以简单相加来求得该测试用例的概率。但是在输入参数有较强相关性时，此方法并不能准确求得某个测试用例的发生概率，一个解决办法是设置输入参数的相关耦合度。在遗传算法的交叉、变异时其同时进行的几率与相关耦合度成正比，即对于相关耦合度高的输入参数，它们同时进行交叉、变异的几率高，反之则低。

　　2.检验是否满足测试要求时，需要先设置一个计数器。每运行一个新的测试用例，测试计数器加一。当发现第一次失效或故障时，计数器加二。若产生的遗传后代又使软件发生失效，则计数器加22。同理递推，当遗传算法产生的测试用例连续n次使软件失效，则计数器加2n。同时，记录所有的测试情况(此工作由外围的测试环境完成，比如北大的青鸟黑盒测试环境)。如果出现严重错误则终止测试，进行对程序的检查。如果连续k代测试用例的遗传后代都运行良好，计数器的值加2k。k的值由具体被测试软件的等价类数量、输入参数个数等决定。当测试计数器的值达到所有黑盒测试用例等价类的数值时(对于我们上面所举的例子，该值为55=3125)，结束测试。当生成的孙子代、子代与父母代三代完全相同时，算法也必须结束，因为此时测试不会有新的结果。所以我们还要设置一个结束条件。而且该条件强于计数器条件。

　　3.每一组测试用例可以生成多个测试用例，根据适应度函数大小决定留下哪些测试用例组成新的测试用例组。

　　从上面的算法框图和说明可以看出，如果某测试用例使软件的运行发生了问题(即某个软件错误发作)，它的后代也同样受困于该软件错误，算法很快能发现这些最佳测试用例并给出结果。测试人员就可以将它们交给开发人员解决这些问题。若软件本身确实质量优良，这些测试用例及其不同的后代无法发现失效，算法也能尽快结束，而不是完成所有测试用例(虽然从理论上，我们希望测试尽可能运行所有测试用例)。

　　三、效果

　　上节的算法，相对于运行所有测试用例，并没有比较明显的优点。尤其对于测试来说，算法并没有加速运行测试用例，好象还降低了运行速度。其实算法本身的确不是用来加速运行测试用例的，其目的是找到一组最佳测试用例。因为实际上对于很多模块运行所有测试用例或哪怕是所有等价类都是几乎不可能的。

　　以上一节举的例子做说明，其输入等价类大致有55=3125。如果一个模块有10个输入、每个输入有10种等价类，那么输入等价类为1010。按运行一个等价类需要1分钟计算(很多循环运行模块可能不止1分钟)，需要几个月才能运行一遍所有等价类。这时，运用遗传算法的优势就体现出来了。

　　综上所述，本文提出了一种利用遗传算法寻求最佳测试用例的测试方法原理。它能在较短时间内完成软件模块的黑盒测试并给出测试结果和好的测试用例。利用该算法原理，可以在测试集成环境中做一些设置或修改测试集成环境，这样可以大大提高测试工作的效率。