基于遗传算法的测试用例生成方法
后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。逆向回溯法正好相反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整各变量取值，直到退到程序入口，即获得所需的输入数据。向前核查法和逆向回溯法的局限性是，对某些条件要求苛刻的路径使用时非常困难，同时由于大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。
由于测试的工作量大、测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。很多测试工具的使用大大提高了测试人员的工作效率，有效减少了项目开支。然而这些工具主要为测试的执行、管理和度量工具，在测试用例自动生成方面还不完善。而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生成问题。因此，寻找一种有效的测试用例生成方法是提高测试自动化的重中之重。
1.2 国内外研究现状
自上世纪60年代起，国内外的学者专家对测试用例的自动生成提出了很多方法，应用较为广泛的有随机法、静态法、动态法以及试探法
[5] [6] [7] [8] [9] [10] [11] [12]
。
D.Bird[13]等提出了采用随机法生成测试用例，其思想是不受限制地随机产生大量的测试用例。该方法产生测试用例的成本很低，在某些抽样测试中效果较好，但是该方法的针对性较弱，在输入空间为无穷大时产生的测试用例集非常庞大，测试效率低，现在的很多工具都是采用的该方法。
[15] [16]
静态法的典型代表是符号执行法，由P.D.Coward[14]和C.Ramanmoorthy
等人提出。该方法的主要思想是把符号值作为程序输入，静态“执行”指定路径的语句，从而得到变量的值。这里所谓的执行，是指按照程序执行的顺序将相应的变量用符号表达式代换。该方法的缺点为需要进行复杂的代数运算，难以处理依赖于输入变量的循环条件、数组元素下标和模块调用的情况，特别对于动态的面向对象程序不适合使用。
与静态法相对应的是动态法，该方法的基本思想是从输入空间中任取一个假设解作为初始输入，通过实际运行程序不断调整输入，使得程序实际执行路径向指定路径不断逼近，直到与指定路径完全一致。Korel[17]法是动态法的典型代表：
6
基于遗传算法的测试用例生成方法
其采用的是步进的方式执行程序，即一次只前进一个分支谓词；Korel还提出了“谓词函数”的概念，用来度量分支谓词的接近满足程度。然而，由于Korel法一次只考虑一个分支谓词，使用回溯技术，所以要进行大量的迭代，浪费了大量的资源。而且由于对于非线性路径约束，该方法只能找到局部极小值，当谓词函数有多个局部极小值时显然将难以找到目标路径的解。除此之外，动态法还包括程序插装的方法和迭代松弛法，M.Gallagher和Neelam Guptal[18]分别对这两种方法进行了全面的阐述。
第四种算法是试探法，该方法的基本思想是从输入数据空间中选择输入数据，运行程序，将运行结果结合概率论的思想产生新的数据继续进行试探。其受搜索空间限制条件的约束小，且不需要其它辅助性信息，对于很多高复杂度问题（如大空间、多峰、非线性、全局优化等）具有独特的优势和高效性。试探法主要包括算法、模拟退火算法、禁忌搜索算法、混合策略的算法等。
自20世纪90年代起，算法因其独特的优点而开始被广泛的用于测试用例的生成领域，并取得了良好的研究成果。算法模拟生物学中的变异原理，采用编码技术将待求数据映射到基因空间，并通过选择、交叉、变异等操作和优胜劣汰的自然选择确定搜索方向，从而找到最优解。实验证明，该算法具有隐性并行性和全局寻优能力，可以自动获取搜索过程中的有关信息并用于指导优化。
Jones 等人[19]的实验表明，为使三角形分类等程序达到分支覆盖，算法生成的测试数据比随机法小一到两个数量级。
Jin-Cherng Lin等人 [20] 等人对适应度函数进行了研究，提出了使用广义海明距离来构建适应度函数。
荚伟[21]分析了算法在测试用例产生这一问题上的可行性，提出了要有效解决该问题，必须从以下几个角度进行研究：参数的编码方法、适应度函数的构造、算子的设计以及算法参数的选择等。
Berndt等人 [22]将输入空间划分成多个区间，根据待选输入的多种特性创建了一个最小化函数,使用简单算法进行求解,并使用了求解过程中的化石记录来指导求解过程。
景志远[23]则从数学的角度分析了将MGA和K均值等改进的算法应用于测试用例的自动生成。
7
基于遗传算法的测试用例生成方法
蔡立志等人[24]提出了一种基于算法的成对测试生成方法,该方法用于选择当前局部优化覆盖的测试用例，以此构建满足成对测试基准的测试用例套，有效降低了相同覆盖率下的测试用例数量。
陈雨等人[25]将自适应算子和禁忌搜索思想融入到算法中， 充分发挥算法的全局搜索和禁忌搜索算法局部搜索优势, 提高了测试数据的生成能力。
全君林等人[26]提出了一种应用于软件回归测试过程中的基于算法的最小化测试用例集算法模型，该算法较一般的优化算法具有更高算法性能与效率。
1.3 论文研究内容
本文主要做了以下方面的研究：
（1）广泛阅读了国内外相关文献资料，对软件测试和算法的应用现状进行了概述，认为使用算法进行测试用例生成可行。
（2）分析了使用算法进行测试用例生成的基本内涵，提出了算法框架及对算法进行实现的具体策略。
（3）以三角形分类程序为例进行试验，分析了试验结果，证实了算法的优越性。
8
基于遗传算法的测试用例生成方法
第二章 软件测试及算法基本概念
2.1 软件测试基本概念 2.1.1 软件测试的目的
1983年IEEE在“软件工程标准术语”中将软件测试定义为：“使用人工或自动手段来运行或测定某个软件系统的过程，其目的在于检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差别。”
定义中指出软件测试的目的是“检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差别”
Grenford. J. Myers在其著作《The Art Of Software Testing》中提出了与软件测试相关的三个重要观点，指明了软件测试的目的为：
1软件测试是程序的执行过程，目的在于发现错误； ○
2一个好的测试用例是指很可能找到迄今为止尚未发现的错误的用例; ○
3一个成功的测试是指发现了迄今为止尚未发现的错误的测试。 ○
由此可见，软件测试的目的可以概括为：
首先，软件测试要以最少的人力、物力，尽快找出软件中潜在的各种缺陷，通过修正这些缺陷，提高软件产品质量，尽量减少软件产品发布后由潜在的软件缺陷带来的可能的商业风险。其次，通过分析软件缺陷产生的原因，可以帮助发现当前开发开发过程中的软件过程缺陷，以便进行软件过程的改进。同时，通过对测试结果的分析整理，还可以修正软件开发规则，并为软件可靠性分析提供依据。
2.1.2 软件测试的原则
软件测试作为一门独立的计算机软件技术，在执行过程中必须遵守一定的原则，以保证测试效果。软件测试的专家们经过长期的实践，总结出了软件测试的原则应如下：
9
基于遗传算法的测试用例生成方法
1应把“尽早和不断地进行软件测试”作为软件开发者的座右铭。 ○
实践证明单元测试能够尽早发现问题,减少后期测试的错误量。单元测试过程中可以使用相应白盒测试工具（如Junit，Jtest等）进行辅助测试，以提高测试效率。
2测试用例应由测试输入数据、○测试执行步骤和与之对应的预期输出结果三
部分组成。
3应当避免由程序员检查自己的程序。 ○
特别在后期的性能测试及系统测试中，应避免程序员测试自己的程序。这其中除了某些心理因素外，该原则还可避免由于程序员个人的惯性思维而导致的某些理解错误。
4测试用例的设计要确保能覆盖所有可能路径。 ○
在设计测试用例时，应当包括合理的输入条件和不合理的输入条件。不合理的输入条件是指异常的、临界的、可能引起问题的输入条件。
5充分注意测试中的群集现象。 ○
经验表明，测试后程序残存的错误数目与该程序中已发现的错误数目或检错率成正比。应该对错误群集的程序段进行重点测试。
6严格执行测试计划，排除测试的随意性。 ○
软件测试是有组织、有计划、有步骤的活动。测试计划应包括：所测软件的功能，输入和输出，测试内容，各项测试的进度安排，资源要求，测试资料，测试工具，测试用例的选择，测试的控制方法和过程，系统的配置方式，跟踪规则，调试规则，以及回归测试的规定等等以及评价标准。
7应当对每一个测试结果做全面的检查。 ○
8妥善保存测试计划，测试用例，出错统计和最终分析报告，为维护提供方○
便。
2.2 软件测试的难点
（1）测试用例设计
测试用例及测试例程是其设计者对被测对象实现原理和外部需求的理解，能否正确反映对被测对象的质量要求，很大程度上取决于其设计者的分析、理解和
10