作者：上海中科院上海小卫星工程部（２０００５０） 陈 浩 刘海涛 来源：《电子技术应用》

遗传算法在黑盒测试中的应用 摘要：提出了一种利用遗传算法帮助测试人员在较短时间内完成软件模块的黑盒测试，并给出测试结果和好的测试用例的方法。 关键词：遗传算法 测试用例 耦合度 在软件测试中，黑盒测试主要是针对模块进行的功能测试。最普遍的方法是以软件的功能说明书为基础将软件的输入划分为若干个等价类，多次运行该软件来检验软件对于不同的等价类是否能满足要求。但是在实际应用中，有的模块太大或输入参数太多，等价类划分后需要进行的测试工作可能是一个极大的任务。这时，如何选择最优的测试用例就成为测试人员的一个重要任务。

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

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

１ 应用方法

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

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

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

（１）解的交叉重组：从ｐ个解中选出两个或两个以上的解进行交叉重组，得到新解，重复该运算若干次。

（２）解的变异：在候选解中随机加进一些变异，产生新解。

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

（４）从全部解中按一定的准则选出ｐ个解作为下一代的候选解，更新暂定解。

转第二步。

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

我们假定一个软件模块的输入参数有５个：ａ、ｂ、ｃ、ｄ、ｅ，经过合理的等价类划分后，每个参数又有５个不同的等价类：ａ１～ａ５，．．．．．．，ｅ１～ｅ５。我们采用一个广义的遗传算法候选解概念，一般的遗传算法往往将候选解形式定为二进制的数据串，比如：１１１０１０、０１０００１等等，而在不同等价类输入作为候选解时我们将候选解形式定为（按照上面假定为基础）：ａ３ｂ１ｃ２ｄ４ｅ５、ａ２ｂ２ｃ４ｄ１ｅ３等等。这样我们解决了候选解的问题，在解的优劣标准以及终止条件的设定问题上，我们需要借助工具作为标准。

软件测试的目的是提高软件的可靠性，终止条