《毕业论文基于遗传算法的测试用例生成方法》由会员分享，可在线阅读，更多相关《毕业论文基于遗传算法的测试用例生成方法（21页珍藏版）》请在金锄头文库上搜索。
1、 沈阳理工大学高等职业技术学院论文摘要软件测试是保证软件质量和可靠性重要手段，在这方面发挥着其它方法不可替代的作用。然而，软件测试是一个复杂的过程，需要耗费巨大的人力、物力和时间，约占整个软件开发成本的40%50%。因此，提高软件测试工具的自动化程度对于确保软件开发质量、降低软件开发成本非常重要。而提高测试用例生成的自动化程度又是提高测试工具乃至整个测试过程自动化程度的关键所在，本文主要针对这一问题进行了研究和设计。本文在分析软件测试和遗传算法基本概念的基础上，提出软件测试用例的设计是软件测试的难点之一。论文提出了基于遗传算法的测试用例生成的内含是应用遗传算法来求解一组优化的测试用例，其框架包
2、括了测试环境构造、遗传算法及测试运行环境三部分，论文给出了基于遗传算法的测试用例生成的模型。最后以三角形分类程序为例应用遗传算法进行测试用例生成的模拟，结果显示，应用遗传算法进行测试用例生成可行。关键词：软件测试 测试用例 遗传算法ABSTRACTSoftware test is the important means that guarantee software quality and reliability， and in this respect，it plays the role that other method cannot replace. However software t
3、est is a complex process , it needs to consume huge manpower，material resources and time，which takes the 40%50% of entire software development cost approximately . Therefore，raising the automation level of software test tool is very important for ensure software development quality and reduction sof
4、tware development cost . And then，the most important is raising the automation level of the test case generation for raising the automation level of test tool and even entire test process，so this paper study and design mainly according to this problem.Based on the analysis of basic concepts of softw
5、are testing and genetic algorithm, this article proposes that software test case design is one of the difficulties of software testing. Paper presents the inherent in software test case designing based on genetic algorithm is using genetic algorithm to solve a set of optimization test cases, and the
6、 framework includes three parts which are test environment construction, genetic algorithm and the environment for test . Paper presents the model of software test case generation based on genetic algorithm. Finally, we take the triangle categorizer as an example, simulate software test case generat
7、ion based on genetic algorithm. The results display that software test case generation basing on genetic algorithm is possible.KEY WORDS: software test , test case , genetic algorithm目录摘要1ABSTRACT2目录3第一章 绪论51.1 问题的提出5第二章 遗传算法基本概念62.1 遗传算法62.1.1 遗传算法的思想及流程62.1.2 遗传算法的特点72.2本章小结8第三章 基于遗传算法的测试用例生成93.1基
8、于遗传算法的测试用例生成基本内涵93.1.1 软件测试用例的基本内涵93.1.2 基于遗传算法的测试用例生成的基本内涵93.2 基于遗传算法的测试用例生成框架103.3 基于遗传算法的测试用例生成算法实现113.3.1 编码策略113.3.2 适应度函数及程序插桩113.3.3 遗传策略123.3.4 参数控制133.4 本章小结14第四章 实验及结果分析154.1 待测程序分析154.1.1 待测程序引入154.1.2 程序流程分析154.1.3 路径分析164.2 程序插桩164.3 参数设定及程序实现174.3.1 参数设定174.4 本章小结18第五章 总结与展望19致谢语20参考文献
9、211第一章 绪论1.1 问题的提出在信息化普及的今天，计算机在人们的生活和工作中占据着重要地位，使人们的工作效率提高，也使生活更丰富多彩。而作为计算机的重要组成部分，软件的重要性不言而喻。随着计算机技术的日益发展，计算机软件的规模越来越庞大，复杂性越来越高，这就为软件质量的保证带来了困难。因为软件的开发过程大部分是由人的智力活动构成，不可能完美无缺。而软件缺陷如果不能及时发现，带来的损失可能是巨大的，有的甚至会危及人的生命。然而，目前生成测试用例的方法主要是向前核查法和逆向回溯法，测试人员根据自己的项目经验手工为指定的程序路径生成测试数据5。向前核查法是指沿预期的路径向前检查，确定到每一个判
10、断点时变量所能提供的最宽数值区间，然后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。逆向回溯法正好相反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整各变量取值，直到退到程序入口，即获得所需的输入数据。向前核查法和逆向回溯法的局限性是，对某些条件要求苛刻的路径使用时非常困难，同时由于大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。由于测试的工作量大、测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。很多测试工具的使用大大提高了测试人员的工作效率，有效减少了项目开支。然而这些工具主
11、要为测试的执行、管理和度量工具，在测试用例自动生成方面还不完善。而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生成问题。因此，寻找一种有效的测试用例生成方法是提高测试自动化的重中之重。第二章 遗传算法基本概念2.1 遗传算法2.1.1 遗传算法的思想及流程遗传算法（genetic algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法作为一种不依赖具体问题的直接搜索方法受到广泛关注，它是现代有关智能计算的关键技术之一。遗传算法的思想源于生物遗传学和适者生存的自然选择规律，因此是具有“生存+检测”的迭代过程的搜索算法。它以
12、一个群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。遗传算法将问题的解空间映射为遗传空间，对解空间进行编码，即将每个可能的解用一串二进制或十进制数字串表示，称为一个染色体，解的每个分量称为一个基因。算法开始时先随机给出一群染色体，即候选解，由预先设定的某个评价指标计算每个染色体的适应值，将适应度低的染色体淘汰掉，而保留适应度高的优良染色体，然后对这些染色体进行选择复制、交叉和变异等遗传操作，从而产生新的一代染色体群体。这样一代一代的“进化”，直至找到算法的最优解，即适应值满足条件的解。由于算法产生的“后代”是由优秀的“父代”和“母代”产生的，因此继承了上代的优良
13、性态而优于上代，从而使算法向着最优解的方向进行，直到满足预先设定的条件。遗传算法过程包括了编码、产生初始群体、计算适应值、选择、交叉、变异等操作。其一般流程图如图2-1所示：j:=0选择变异个体执行变异将变异结果添加到新群体中j:=j+1j=PmM？YN执行交换j:=j+1根据适应度选择两个交换个体j:=0将交换后的两个新个体添加到新群体中j=PcM？NYj:=0根据适应度选择复制个体执行复制将复制结果添加到新群体中j:=j+1j=PsM？Y开始Gen:=0自左向右执行一次遗传算子计算群体中各个体适应度终止输出结果随机产生M个初始群体确定字符串长度L满足终止条件？YNNPsPcPmGen:=G
14、en+1图2-1 遗传算法流程图2.1.2 遗传算法的特点遗传算法是一类可用于复杂系统优化计算的搜索算法，与其他一些优化算法相比，它的主要特点有如下几点27：（1）遗传算法以决策变量的编码作为运算对象，而传统优化算法往往直接利用变量的实际值来进行优化计算。这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念以及遗传和进化机理。特别是对些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独待的优越性。（2）遗传算法直接以目标函数值作为搜索信息，而不需要目标函数的导数值等其他辅助信息。这个特性对很多目标函数难以求导的优化问题，以及组合
15、优化问题等，应用遗传算法时就显得比较方便。而且，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。（3）遗传算法同时使用多个搜索点的搜索信息，而传统的优化算法往往是从解空间中的一个初始点开始最优解的迭代搜索过程。单个搜索点的搜索效率不高，甚至可能使搜索过程陷于局部最优解而停滞不前。遗传算法通过对个体组成的群体进行操作运算，产生新的群体，其中包含的群体信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的一种隐性并行性。（4）遗传算法使用概率搜索技术，而很多传统的优化算法往往使用的是确定性的搜索方法。确定性的方法由于固定了点与点之间的转移方法和转移关系，往往可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。而遗传算法属于一种自适应的概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了算法搜索过程的灵活性和搜索效率。2.2本章小结本章首先介绍了软件测试的一些基本概念，介绍了遗传算法的基本概念，包括遗传算法的思想、流程及特点。第三章 基于遗传算法的测试用例生成3.1基于遗传算法的测试用例生成基本内涵3.1
