适应度为前的个体情况表究，提出了使用广义海明距离来构建适应度函数。荚伟分析了算法在测试用例产生这问题上的可行性，提出了要有效解决该问题，必须从以下几个角度进行研究参数的编码方法适应度函数的构造算子的设计以及算法索过程中的有关信息并用于指导优化。等人的实验表明，为使三角形分类等程序达到分支覆盖，算法生成的测试数据比随机法小到两个数量级。等人等人对适应度函数进行了研模拟生物学中的变异原理，采用编码技术将待求数据映射到基因空间，并通过选择交叉变异等操作和优胜劣汰的自然选择确定搜索方向，从而找到最优解。实验证明，该算法具有隐性并行性和全局寻优能力，可以自动获取搜全局优化等具有独特的优势和高效性。试探法主要包括算法模拟退火算法禁忌搜索算法混合策略的算法等。自世纪年代起，算法因其独特的优点而开始被广泛的用于测试用例的生成领域，并取得了良好的研究成果。算法本思想是从输入数据空间中选择输入数据，运行程序，将运行结果结合概率论的思想产生新的数据继续进行试探。其受搜索空间限制条件的约束小，且不需要其它辅助性信息，对于很多高复杂度问题如大空间多峰非线性极小值时显然将难以找到目标路径的解。除此之外，动态法还包括程序插装的方法和迭代松弛法，和分别对这两种方法进行了全面的阐述。第四种算法是试探法，该方法的基量分支谓词的接近满足程度。然而，由于法次只考虑个分支谓词，使用回溯技术，所以要进行大量的迭代，浪费了大量的资源。而且由于对于非线性路径约束，该方法只能找到局部极小值，当谓词函数有多个局部使得程序实际执行路径向指定路径不断逼近，直到与指定路径完全致。法是动态法的典型代表其采用的是步进的方式执行程序，即次只前进个分支谓词还提出了谓词函数的概念，用来度入变量的循环条件数组元素下标和模块调用的情况，特别对于动态的面向对象程序不适合使用。与静态法相对应的是动态法，该方法的基本思想是从输入空间中任取个假设解作为初始输入，通过实际运行程序不断调整输入，主要思想是把符号值作为程序输入，静态执行指定路径的语句，从而得到变量的值。这里所谓的执行，是指按照程序执行的顺序将相应的变量用符号表达式代换。该方法的缺点为需要进行复杂的代数运算，难以处理依赖于输弱，在输入空间为无穷大时产生的测试用例集非常庞大，测试效率低，现在的很多工具都是采用的该方法。静态法的典型代表是符号执行法，由和等人提出。该方法的法。等提出了采用随机法生成测试用例，其思想是不受限制地随机产生大量的测试用例。该方法产生测试用例的成本很低，在些抽样测试中效果较好，但是该方法的针对性较成问题。因此，寻找种有效的测试用例生成方法是提高测试自动化的重中之重。国内外研究现状自上世纪年代起，国内外的学者专家对测试用例的自动生成提出了很多方法，应用较为广泛的有随机法静态法动态法以及试探的工作效率，有效减少了项目开支。然而这些工具主要为测试的执行管理和度量工具，在测试用例自动生成方面还不完善。而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。由于测试的工作量大测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。很多测试工具的使用大大提高了测试人员反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整各变量取值，直到退到程序入口，即获得所需的输入数据。向前核查法和逆向回溯法的局限性是，对些条件要求苛刻的路径使用时非常困难，同时由于查法是指沿预期的路径向前检查，确定到每个判断点时变量所能提供的最宽数值区间，然后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。逆向回溯法正好相反查法是指沿预期的路径向前检查，确定到每个判断点时变量所能提供的最宽数值区间，然后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。逆向回溯法正好相反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整各变量取值，直到退到程序入口，即获得所需的输入数据。向前核查法和逆向回溯法的局限性是，对些条件要求苛刻的路径使用时非常困难，同时由于大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。由于测试的工作量大测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。很多测试工具的使用大大提高了测试人员的工作效率，有效减少了项目开支。然而这些工具主要为测试的执行管理和度量工具，在测试用例自动生成方面还不完善。而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生成问题。因此，寻找种有效的测试用例生成方法是提高测试自动化的重中之重。国内外研究现状自上世纪年代起，国内外的学者专家对测试用例的自动生成提出了很多方法，应用较为广泛的有随机法静态法动态法以及试探法。等提出了采用随机法生成测试用例，其思想是不受限制地随机产生大量的测试用例。该方法产生测试用例的成本很低，在些抽样测试中效果较好，但是该方法的针对性较弱，在输入空间为无穷大时产生的测试用例集非常庞大，测试效率低，现在的很多工具都是采用的该方法。静态法的典型代表是符号执行法，由和等人提出。该方法的主要思想是把符号值作为程序输入，静态执行指定路径的语句，从而得到变量的值。这里所谓的执行，是指按照程序执行的顺序将相应的变量用符号表达式代换。该方法的缺点为需要进行复杂的代数运算，难以处理依赖于输入变量的循环条件数组元素下标和模块调用的情况，特别对于动态的面向对象程序不适合使用。与静态法相对应的是动态法，该方法的基本思想是从输入空间中任取个假设解作为初始输入，通过实际运行程序不断调整输入，使得程序实际执行路径向指定路径不断逼近，直到与指定路径完全致。法是动态法的典型代表其采用的是步进的方式执行程序，即次只前进个分支谓词还提出了谓词函数的概念，用来度量分支谓词的接近满足程度。然而，由于法次只考虑个分支谓词，使用回溯技术，所以要进行大量的迭代，浪费了大量的资源。而且由于对于非线性路径约束，该方法只能找到局部极小值，当谓词函数有多个局部极小值时显然将难以找到目标路径的解。除此之外，动态法还包括程序插装的方法和迭代松弛法，和分别对这两种方法进行了全面的阐述。第四种算法是试探法，该方法的基本思想是从输入数据空间中选择输入数据，运行程序，将运行结果结合概率论的思想产生新的数据继续进行试探。其受搜索空间限制条件的约束小，且不需要其它辅助性信息，对于很多高复杂度问题如大空间多峰非线性全局优化等具有独特的优势和高效性。试探法主要包括算法模拟退火算法禁忌搜索算法混合策略的算法等。自世纪年代起，算法因其独特的优点而开始被广泛的用于测试用例的生成领域，并取得了良好的研究成果。算法模拟生物学中的变异原理，采用编码技术将待求数据映射到基因空间，并通过选择交叉变异等操作和优胜劣汰的自然选择确定搜索方向，从而找到最优解。实验证明，该算法具有隐性并行性和全局寻优能力，可以自动获取搜索过程中的有关信息并用于指导优化。等人的实验表明，为使三角形分类等程序达到分支覆盖，算法生成的测试数据比随机法小到两个数量级。等人等人对适应度函数进行了研究，提出了使用广义海明距离来构建适应度函数。荚伟分析了算法在测试用例产生这问题上的可行性，提出了要有效解决该问题，必须从以下几个角度进行研究参数的编码方法适应度函数的构造算子的设计以及算法参数的选择等。等人将输入空间划分成多个区间，根据待选输入的多种特性创建了个最小化函数，使用简单算法进行求解，并使用了求解过程中的化石记录来指导求解过程。景志远则从数学的角度分析了将和均值等改进的算法应用于测试用例的自动生成。蔡立志等人提出了种基于算法的成对测试生成方法，该方法用于选择当前局部优化覆盖的测试用例，以此构建满足成对测试基准的测试用例套，有效降低了相同覆盖率下的测试用例数量。陈雨等人将自适应算子和禁忌搜索思想融入到算法中，充分发挥算法的全局搜索和禁忌搜索算法局部搜索优势，提高了测试数据的生成能力。全君林等人提出了种应用于软件回归测试过程中的基于算法的最小化测试用例集算法模型，该算法较般的优化算法具有更高算法性能与效率。论文研究内容本文主要做了以下方面的研究广泛阅读了国内外相关文献资料，对软件测试和算法的应用现状进行了概述，认为使用算法进行测试用例生成可行。分析了使用算法进行测试用例生成的基本内涵，提出了算法框架及对算法进行实现的具体策略。以三角形分类程序为例进行试验，分析了试验结果，证实了算法的优越性。第二章软件测试及算法基本概念软件测试基本概念软件测试的目的年在软件工程标准术语中将软件测试定义为使更新适应度变异操作，采用基本位变异方法随机产生变异位更新适应度结果分析对算法自身的进化能力分析以三角形分类程序的判为等边三角形的路径为例，运行程序，发现在代时找到了最优解，表分别为第代第代第代的适应度为前的个体情况表第代适应度前的个体个体编号染色体编码参数值适应度表第代适应度前的个体个体编号染色体编码参数值适应度表第代适应度前的个体个体编号染色体编码参数值适应度由这三张表可见，随着进化过程的继续，群体的总体适应度在增加，说明算法正朝着最优解的方向收敛，直至找到最优解。这说明算法在程序测试数据自动生成中是有定作用的，它能逐渐改善个体，使其越来越接近我们的标准路径，最终达到我们设定的标准路径。算法与随机法比较随机法是目前大多数测试工具生成测试用例所使用的算法，其思想已在本文第章中介绍过。为了显示算法的优越性，现分别使