基于模拟退火遗传算法的软件测试用例研究

张红敏 周凤

引言：本文在探讨模拟退火遗传算法的基础上，结合软件测试的基本过程，提出在软件测试中用模拟退火遗传算法寻求最佳测试用例，以便提高软件测试效率，并给出一般性的原理和算法。

一、遗传算法

遗传算法（Genetic Algorithm）是最初由美国Michigan大学J.Holland教授于1975年首先提出来的，是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法包含5个要素：初始化种群，选择，交叉，变异，更新初始群体，结束条件。

模拟退火算法是根据固体退火原理，将固体加热到充分高的温度，再让其徐徐冷却，加温时，固体内部的粒子随着温度上升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到到平衡态，最后在常温时达到基态，内能减为最小【1】。

由于遗传算法具有良好的全局搜索能力，但是对于局部空间搜索却不是很有效，容易产生早熟收敛现象，陷入局部最优【2】。为了解决这个问题，可以将模拟退火算法结合到遗传算法中，模拟退火算法的局部搜索能力可以解决遗传算法局部搜索能力差以及早熟现象，同时也解决了模拟退火算法全局搜索能力差和效率不高的问题。

二、软件测试

软件测试是运行程序并发现程序错误的过程。测试是为了发现程序中的错误，而不是证明程序中没有错误。而测试用例应该包括为测试某个程序路径或者确定是否满足某个特定需求而编制的一组测试输入、执行条件和与之对应的预期结果。一个好的测试用例是能够快速有效的发现程序中的错误。一般把测试分为两类：白盒测试也称为结构测试、透明盒测试、逻辑驱动测试或基于代码的测试，是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作；黑盒测试也称为功能测试或数据驱动测试，是通过测试来确认每个功能是否得到完整实现，检测每个功能是否都能正常使用。而黑盒测试的测试用例设计通常是用等价划分法。

用等价类划分法首先要划分等价类：输入规定了的取值范围或值的个数就可以确定一个有效等价类和两个无效等价类。输入规定了的输入值的集合或者一个布尔量可以确定一个有效等价类和一个无效等价类。输入规定的输入数据的一组值（假设m个）且对每一个输入值分别处理可以确定m个有效等价类和一个无效等价类。输入的数据必须遵守一定的规则可以确定一个有效等价类和若干个无效等价类。已划分的等价类中各元素处理方式不同时应将等价类再划分为更小的等价类。其次确定测试用例：给等价类编号设计一个重复使其尽可能多地覆盖尚未被覆盖过的合理等价类直到所有合理等价类被测试用例覆盖的测试用例。设计一个使其只覆盖一个不合理等价类的测试用例。

三、用模拟退火遗传算法需求最佳测试用例

（1）编码。模拟退火遗传算法需要将软件测试中的一个问题的可行解从解空间转换到遗传算法所能解决的搜索空间。初始化种群规模为100，编码方法可以选择浮点法、grey法则和二进制法，本文每个参数的编码方式采用二进制编码。

（2）选择退火算子

在软件测试中，测试的目的是发现程序中至今没有发现的错误，一个好的测试用例就相当于遗传算法中适应度值大的个体，本文将初始群体中的100个个体进行适应度评价，个体适应度值越大，该个体被遗传到下一代的概率也越大。

①随机选择初始群体两个个体A、B，计算其个体适应度值f（A）和f（B）。

②如果f（A）

③重复①、②操作直到新的一代群体中也包含100个个体。

（3）选择。染色体的选择方法可以采用锦标赛法和轮盘赌法，本文采用轮盘赌法，通常适应度大的被选择的几率较高。

（4）交叉。在遗传算法的遗传操作中，交叉运算决定了遗传算法的全局搜索能力【3】。将父代中的任意两个个体进行交叉产生最新染色体。进行退火操作，如果最佳适应度大于最新染色体适应度，就用最新染色体适应度取代之前的最佳适应度，否则以概率P（exp（（f（A）-f（B））/T））接受最新个体。重复操作，直至以概率0.7完成所有的交叉操作。

（5）变异。在遗传算法的遗传操作中，变异操作决定了遗传算法的局部搜索能力【3】。变异方法的选择浮点法和单点法。本文采用浮点法。随机选择一个的内部选择两个节点进行变异，如果新产生的个体适应度小于原个体适应度，就用最新个体取代原个体，否则以概率P（exp（（f（A）-f（B））/T））接受最新个体。重复此操作。直至以概率0.05完成所有的交叉操作。

（6）终止条件。当进化代数超过某个值而适应度不变时或者进化代数达到最大值时。最后留下的也即最优的软件测试用例。

四、结束语

综上所述，本文重在在软件测试中使用模拟退火遗传算法需找最好的软件测试用例。以一种高效率的方式完成软件中的黑盒测试，并找出最佳测试用例。

参考文献

[1]季海婧.基于模拟退火—量子遗传算法的路径测试数据自动生成方法研究[D].浙江：杭州师范大学，2012.

[2]杨清平.基于改进遗传算法的测试用例自动生成研究[D].广东：广东工业大学，311.

[3]李欣，基于贝叶斯网络和遗传算法的测试用例生成模型[D].重庆：重庆交通大学，2012.

（作者单位：贵州大学 计算机科学与技术学院）