遗传算法在黑盒测试中的应用

　　在软件测试中，黑盒测试主要是针对模块进行的功能测试。最普遍的方法是以软件的功能说明书为基础将软件的输入划分为若干个等价类，多次运行该软件来检验软件对于不同的等价类是否能满足要求。但是在实际应用中，有的模块太大或输入参数太多，等价类划分后需要进行的测试工作可能是一个极大的任务。这时，如何选择最优的测试用例就成为测试人员的一个重要任务。

　　遗传算法是模仿生物遗传和进化机制的一种最优化方法，它把类似于遗传基因的一些行为，如交叉重组、变异、选择和淘汰等引入到算法求解的改进过程中。遗传算法的特点之一是，它同时保留着若干局部最优解，通过交叉重组或者解的变异来寻求更好的解。与贪婪算法相比，遗传算法更可能找到全局最优解，而贪婪算法则容易限于局部最优而达不到全局最优。

　　如果能够将遗传算法有效地运用于黑盒测试中，帮助测试人员选择最优的测试用例，那么将给测试工作带来极大的帮助。

　　1 应用方法

　　在设计具体的算法之前，我们先介绍遗传算法的基本算法，其算法框架如下[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所示。

原文转自：http://www.uml.org.cn/Test/200901086.asp