语音增强算法分析与FPGA实现

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 test is a complex process , it nee

3、ds 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 software development cost . And then

4、，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 software testing and genetic algorithm

5、, 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 framework includes three parts w

6、hice.KEY WORDS: software test , test case , genetic algorithm目录摘要2ABSTRACT3目录4第一章 绪论61.1 问题的提出61.2 国内外研究现状71.3 论文研究内容9第二章 软件测试及算法基本概念102.1 软件测试基本概念102.1.1 软件测试的目的102.1.2 软件测试的原则102.2 软件测试的难点112.3 算法122.3.1 算法的思想及流程122.3.2 算法的特点142.4本章小结15第三章 基于算法的测试用例生成163.1基于算法的测试用例生成基本内涵163.1.1 软件测试用例的基本内涵163.1.2

7、基于算法的测试用例生成的基本内涵173.2 基于算法的测试用例生成框架173.3 基于算法的测试用例生成算法实现193.3.1 编码策略193.3.2 适应度函数及程序插桩203.3.3 策略213.3.4 参数控制233.4 本章小结23第四章 实验及结果分析244.1 待测程序分析244.1.1 待测程序引入244.1.2 程序流程分析244.1.3 路径分析254.2 程序插桩254.3 参数设定及程序实现264.3.1 参数设定264.3.2 部分程序实现264.4 结果分析294.5 本章小结31第五章 总结与展望32致谢语33参考文献34第一章 绪论1.1 问题的提出在信息化普及的

8、今天，计算机在人们的生活和工作中占据着重要地位，使人们的工作效率提高，也使生活更丰富多彩。而作为计算机的重要组成部分，软件的重要性不言而喻。随着计算机技术的日益发展，计算机软件的规模越来越庞大，复杂性越来越高，这就为软件质量的保证带来了困难。因为软件的开发过程大部分是由人的智力活动构成，不可能完美无缺。而软件缺陷如果不能及时发现，带来的损失可能是巨大的，有的甚至会危及人的生命。在历史上臭名昭著的软件缺陷案例有1：1999年12月3日，美国航天局的火星基地登陆飞船在试图登陆火星表面时失踪，原因仅仅是一个数据位的意外更改；美国爱国者导弹防御系统曾在几次对抗导弹战役中失利，其中一次竟然误使28名美国

9、士兵丧生，原因是一个很小的系统时钟错误导致系统累计拖延了100多个小时使跟踪系统失去准确度；还有就是大名鼎鼎的“千年虫”问题，起因是在20世纪70年代，为了节省硬盘空间，美国某位程序员在编写工资系统时将4位数日期（如1975）改成了2位数日期（如75），该缺陷一直拖到1995年都没有修复，最终给全球带来了高达数亿美元的损失等等。作为提高软件质量的重要手段，软件测试越来越受到重视。在美国的微软公司，测试人员和开发人员的比例达到了2：12。软件测试伴随着整个开发过程，是一个非常复杂的过程，其消耗的人力和资金一般占整个项目的一半左右。而在某些特别重要的软件开发过程中，为保证软件的质量，测试的费用甚至

10、是其它各阶段之和的3到5倍3。测试过程中，测试人员通常需要分析、设计和执行大量的测试用例，从而耗费了大量资源，因此找出合理的测试用例生成方法可以有效缩短测试时间，减少损耗，一般可以有效降低整个项目的4%费用4。然而，目前生成测试用例的方法主要是向前核查法和逆向回溯法，测试人员根据自己的项目经验手工为指定的程序路径生成测试数据5。向前核查法是指沿预期的路径向前检查，确定到每一个判断点时变量所能提供的最宽数值区间，然后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。逆向回溯法正好相反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整

11、各变量取值，直到退到程序入口，即获得所需的输入数据。向前核查法和逆向回溯法的局限性是，对某些条件要求苛刻的路径使用时非常困难，同时由于大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。由于测试的工作量大、测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。很多测试工具的使用大大提高了测试人员的工作效率，有效减少了项目开支。然而这些工具主要为测试的执行、管理和度量工具，在测试用例自动生成方面还不完善。而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生成问题。因此，寻找一种有效的测试用例生成方法是提高测试自动化的重中

12、之重。1.2 国内外研究现状自上世纪60年代起，国内外的学者专家对测试用例的自动生成提出了很多方法，应用较为广泛的有随机法、静态法、动态法以及试探法5 6 7 8 9 10 11 12。D.Bird13等提出了采用随机法生成测试用例，其思想是不受限制地随机产生大量的测试用例。该方法产生测试用例的成本很低，在某些抽样测试中效果较好，但是该方法的针对性较弱，在输入空间为无穷大时产生的测试用例集非常庞大，测试效率低，现在的很多工具都是采用的该方法。静态法的典型代表是符号执行法，由14和C.Ramanmoorthy 15 16等人提出。该方法的主要思想是把符号值作为程序输入，静态“执行”指定路径的语句

13、，从而得到变量的值。这里所谓的执行，是指按照程序执行的顺序将相应的变量用符号表达式代换。该方法的缺点为需要进行复杂的代数运算，难以处理依赖于输入变量的循环条件、数组元素下标和模块调用的情况，特别对于动态的面向对象程序不适合使用。与静态法相对应的是动态法，该方法的基本思想是从输入空间中任取一个假设解作为初始输入，通过实际运行程序不断调整输入，使得程序实际执行路径向指定路径不断逼近，直到与指定路径完全一致。Korel17法是动态法的典型代表：其采用的是步进的方式执行程序，即一次只前进一个分支谓词；Korel还提出了“谓词函数”的概念，用来度量分支谓词的接近满足程度。然而，由于Korel法一次只考虑

14、一个分支谓词，使用回溯技术，所以要进行大量的迭代，浪费了大量的资源。而且由于对于非线性路径约束，该方法只能找到局部极小值，当谓词函数有多个局部极小值时显然将难以找到目标路径的解。除此之外，动态法还包括程序插装的方法和迭代松弛法，M.Gallagher和Neelam Guptal18分别对这两种方法进行了全面的阐述。第四种算法是试探法，该方法的基本思想是从输入数据空间中选择输入数据，运行程序，将运行结果结合概率论的思想产生新的数据继续进行试探。其受搜索空间限制条件的约束小，且不需要其它辅助性信息，对于很多高复杂度问题（如大空间、多峰、非线性、全局优化等）具有独特的优势和高效性。试探法主要包括算法

15、、模拟退火算法、禁忌搜索算法、混合策略的算法等。自20世纪90年代起，算法因其独特的优点而开始被广泛的用于测试用例的生成领域，并取得了良好的研究成果。算法模拟生物学中的变异原理，采用编码技术将待求数据映射到基因空间，并通过选择、交叉、变异等操作和优胜劣汰的自然选择确定搜索方向，从而找到最优解。实验证明，该算法具有隐性并行性和全局寻优能力，可以自动获取搜索过程中的有关信息并用于指导优化。Jones 等人19的实验表明，为使三角形分类等程序达到分支覆盖，算法生成的测试数据比随机法小一到两个数量级。Jin-Cherng Lin等人 20 等人对适应度函数进行了研究，提出了使用广义海明距离来构建适应度

16、函数。荚伟21分析了算法在测试用例产生这一问题上的可行性，提出了要有效解决该问题，必须从以下几个角度进行研究：参数的编码方法、适应度函数的构造、算子的设计以及算法参数的选择等。Berndt等人 22将输入空间划分成多个区间，根据待选输入的多种特性创建了一个最小化函数,使用简单算法进行求解,并使用了求解过程中的化石记录来指导求解过程。景志远23则从数学的角度分析了将MGA和K均值等改进的算法应用于测试用例的自动生成。蔡立志等人24提出了一种基于算法的成对测试生成方法,该方法用于选择当前局部优化覆盖的测试用例，以此构建满足成对测试基准的测试用例套，有效降低了相同覆盖率下的测试用例数量。陈雨等人25

17、将自适应算子和禁忌搜索思想融入到算法中， 充分发挥算法的全局搜索和禁忌搜索算法局部搜索优势, 提高了测试数据的生成能力。全君林等人26提出了一种应用于软件回归测试过程中的基于算法的最小化测试用例集算法模型，该算法较一般的优化算法具有更高算法性能与效率。1.3 论文研究内容本文主要做了以下方面的研究：（1）广泛阅读了国内外相关文献资料，对软件测试和算法的应用现状进行了概述，认为使用算法进行测试用例生成可行。（2）分析了使用算法进行测试用例生成的基本内涵，提出了算法框架及对算法进行实现的具体策略。（3）以三角形分类程序为例进行试验，分析了试验结果，证实了算法的优越性。第二章 软件测试及算法基本概念

18、2.1 软件测试基本概念2.1.1 软件测试的目的1983年IEEE在“软件工程标准术语”中将软件测试定义为：“使用人工或自动手段来运行或测定某个软件系统的过程，其目的在于检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差别。”定义中指出软件测试的目的是“检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差别”Grenford. J. Myers在其著作The Art Of Software Testing中提出了与软件测试相关的三个重要观点，指明了软件测试的目的为：软件测试是程序的执行过程，目的在于发现错误；一个好的测试用例是指很可能找到迄今为止尚未发现的错误的

19、用例;一个成功的测试是指发现了迄今为止尚未发现的错误的测试。由此可见，软件测试的目的可以概括为：首先，软件测试要以最少的人力、物力，尽快找出软件中潜在的各种缺陷，通过修正这些缺陷，提高软件产品质量，尽量减少软件产品发布后由潜在的软件缺陷带来的可能的商业风险。其次，通过分析软件缺陷产生的原因，可以帮助发现当前开发开发过程中的软件过程缺陷，以便进行软件过程的改进。同时，通过对测试结果的分析整理，还可以修正软件开发规则，并为软件可靠性分析提供依据。 软件测试的原则软件测试作为一门独立的计算机软件技术，在执行过程中必须遵守一定的原则，以保证测试效果。软件测试的专家们经过长期的实践，总结出了软件测试的原

20、则应如下：应把“尽早和不断地进行软件测试”作为软件开发者的座右铭。实践证明单元测试能够尽早发现问题,减少后期测试的错误量。单元测试过程中可以使用相应白盒测试工具（如Junit，Jtest等）进行辅助测试，以提高测试效率。测试用例应由测试输入数据、测试执行步骤和与之对应的预期输出结果三部分组成。应当避免由程序员检查自己的程序。特别在后期的性能测试及系统测试中，应避免程序员测试自己的程序。这其中除了某些心理因素外，该原则还可避免由于程序员个人的惯性思维而导致的某些理解错误。测试用例的设计要确保能覆盖所有可能路径。在设计测试用例时，应当包括合理的输入条件和不合理的输入条件。不合理的输入条件是指异常的

21、、临界的、可能引起问题的输入条件。充分注意测试中的群集现象。经验表明，测试后程序残存的错误数目与该程序中已发现的错误数目或检错率成正比。应该对错误群集的程序段进行重点测试。严格执行测试计划，排除测试的随意性。软件测试是有组织、有计划、有步骤的活动。测试计划应包括：所测软件的功能，输入和输出，测试内容，各项测试的进度安排，资源要求，测试资料，测试工具，测试用例的选择，测试的控制方法和过程，系统的配置方式，跟踪规则，调试规则，以及回归测试的规定等等以及评价标准。应当对每一个测试结果做全面的检查。妥善保存测试计划，测试用例，出错统计和最终分析报告，为维护提供方便。2.2 软件测试的难点（1）测试用例

22、设计测试用例及测试例程是其设计者对被测对象实现原理和外部需求的理解，能否正确反映对被测对象的质量要求，很大程度上取决于其设计者的分析、理解和设计能力。这是一种缺乏指导性方法的、不易制订标准或规范的、需要“技巧”的设计活动。（2）测试管理目前缺乏测试管理方面的资料，几乎没有可供参考的、已实现的、完整的测试管理与测试实施模式。（3）测试的组织软件测试的有效实施需要开发组织与测试组织充分配合。虽然测试活动看似是对开发人员劳动成果的不断“挑剔”，但测试工作的出发点是：确保开发人员的劳动成果成为可被接收的、更高品质的软件产品。因此，测试人员应向开发人员谦虚求教，在测试工作中真正发挥作用，为保证软件产品的

23、高质量起尽可能大的作用。测试的组织者应在促进上级组织协调各组织工作方面发挥作用。（4）测试的估计有效的测试工作需要投入足够的人力和物力，需要对工作的难度和消耗有充分的估计。测试的组织者也应在促进上级组织对资源的统一调度方面发挥作用。2.3 算法 算法的思想及流程算法（genetic algorithm）是模拟达尔文的选择和自然淘汰的生物进化过程的计算模型。该算法最先于1975年由美国的J.Holland教授提出。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不

24、需要确定的规则。算法作为一种不依赖具体问题的直接搜索方法受到广泛关注，它是现代有关智能计算的关键技术之一。算法的思想源于生物学和适者生存的自然选择规律，因此是具有“生存+检测”的迭代过程的搜索算法。它以一个群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。算法将问题的解空间映射为空间，对解空间进行编码，即将每个可能的解用一串二进制或十进制数字串表示，称为一个染色体，解的每个分量称为一个基因。算法开始时先随机给出一群染色体，即候选解，由预先设定的某个评价指标计算每个染色体的适应值，将适应度低的染色体淘汰掉，而保留适应度高的优良染色体，然后对这些染色体进行选择复制、交

25、叉和变异等操作，从而产生新的一代染色体群体。这样一代一代的“进化”，直至找到算法的最优解，即适应值满足条件的解。由于算法产生的“后代”是由优秀的“父代”和“母代”产生的，因此继承了上代的优良性态而优于上代，从而使算法向着最优解的方向进行，直到满足预先设定的条件。算法过程包括了编码、产生初始群体、计算适应值、选择、交叉、变异等操作。其一般流程图如图2-1所示：j:=0选择变异个体执行变异将变异结果添加到新群体中j:=j+1j=PmM？YN执行交换j:=j+1根据适应度选择两个交换个体j:=0将交换后的两个新个体添加到新群体中j=PcM？NYj:=0根据适应度选择复制个体执行复制将复制结果添加到新

26、群体中j:=j+1j=PsM？Y开始Gen:=0自左向右执行一次遗传算子计算群体中各个体适应度终止输出结果随机产生M个初始群体确定字符串长度L满足终止条件？YNNPsPcPmGen:=Gen+1图2-1 算法流程图 算法的特点算法是一类可用于复杂系统优化计算的搜索算法，与其他一些优化算法相比，它的主要特点有如下几点27：（1）算法以决策变量的编码作为运算对象，而传统优化算法往往直接利用变量的实际值来进行优化计算。这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念以及和进化机理。特别是对些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显

27、示出了其独待的优越性。（2）算法直接以目标函数值作为搜索信息，而不需要目标函数的导数值等其他辅助信息。这个特性对很多目标函数难以求导的优化问题，以及组合优化问题等，应用算法时就显得比较方便。而且，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。（3）算法同时使用多个搜索点的搜索信息，而传统的优化算法往往是从解空间中的一个初始点开始最优解的迭代搜索过程。单个搜索点的搜索效率不高，甚至可能使搜索过程陷于局部最优解而停滞不前。算法通过对个体组成的群体进行操作运算，产生新的群体，其中包含的群体信息可以避免搜索一些不必搜索的点，所以实际上相

28、当于搜索了更多的点，这是算法所特有的一种隐性并行性。（4）算法使用概率搜索技术，而很多传统的优化算法往往使用的是确定性的搜索方法。确定性的方法由于固定了点与点之间的转移方法和转移关系，往往可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。而算法属于一种自适应的概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了算法搜索过程的灵活性和搜索效率。2.4本章小结本章首先介绍了软件测试的一些基本概念，对软件测试的知识做了系统的介绍，包括软件测试的目的、原则、过程，介绍了了软件测试的主要技术难点，其中包括了测试用例的设计。本章后半部分介绍了算法的基本概念，包括算法的思想

29、、流程及特点。第三章 基于算法的测试用例生成3.1基于算法的测试用例生成基本内涵 软件测试用例的基本内涵测试用例是为某个特殊目标而编制的一组测试输入、执行条件以及预期结果，以便测试某个程序路径或核实是否满足某个特定需求，包含输入和输出两部分。构造测试用例的目的是为了检查被测软件的操作结果是否与预期的需求相吻合，确定应用程序的某些特性是否正常的工作等。测试用例的质量可以用以下四个标准来描述:（1）有效性:是否能够发现缺陷，或者至少可能发现缺陷；（2）仿效性:可仿效的测试用例能够测试多项内容，从而减少测试用例的数量；（3）经济性:测试用例的执行、分析和调试是否经济；（4）修改性:软件修改后测试用例

30、的维护成本。实践中，设计测试用例需遵守一定的原则，这些原则主要有：（1）全面性包括：应尽可能覆盖程序的各种路径；应考虑存在跨年、跨月的数据；大量数据并发测试的准备等。 （2）正确性输入界面后的数据应与测试文档所记录的数据一致且预期结果应与测试数据发生的业务吻合。 （3）符合正常业务惯例测试数据应符合用户实际工作业务流程且兼顾各种业务变化的可能。 （4）仿真性 人名、地名、电话号码等应具有模拟功能，符合一般的命名惯例；不允许出现与知名人士、小说中人物名等雷同情况。 （5）可操作性 测试用例中应写清测试的操作步骤，不同的操作步骤相对应的操作结果。 基于算法的测试用例生成的基本内涵使用算法实现测试用

31、例的自动生成可描述为12：应用算法来求解一组优化的测试用例。在每一步进化计算过程中，测试用例自动生成器使用当前群体（测试用例）驱动被测试程序的执行，每一个测试用例的执行路径被跟踪和记录，以最大化程序执行路径的覆盖为适应性目标函数进行计算，产生出下一代群体。在多代进化之后，得到最优种群或超过特定的循环限制条件而结束。因为测试用例的自动生成是在一个数据域中寻找满足给定的测试标准的一组测试输入数据的过程，所以近年来出现了把测试用例的生成问题转化成路径搜索问题的思想。由于一般情况下，测试数据的产生是一个不可判定性问题，再加上被测程序的规模和复杂性，一般的搜索算法受到了极大的限制。算法在处理不确定搜索问

32、题时有着非常明显的优势。算法能针对程序路径生成大量有效测试用例，因此符合测试用例设计的全面性、正确性等原则。生成的测试用例符合上节中的测试用例设计标准，特别是有效性和经济性等，由此可见算法应用于测试用例生成是可行的。3.2 基于算法的测试用例生成框架本文基于算法的测试用例生成基本流程如下所示：（1）分析源程序代码，获得程序控制流程图；（2）由程序控制流程图得到程序分支路径集合，选择目标路径；（3）根据各谓词条件给程序插桩并制定适应度函数；（4）设定算法参数，包括群体大小、变异率等，随机产生初始测试数据集合；（5）使用测试数据执行经过插装的源代码，获得适应度值，根据适应度值判断，若满足程序终止条

33、件则输出结果并退出程序，若不满足条件则进入步骤（6）；（6）根据得到的适应度值，使用算法的选择、交叉、变异等操作，生成新的测试数据，并回到步骤（5），重复执行；Y静态分析路径选择程序插桩变异GA初始化测试环境构造选择交叉解码评估结束N遗传算法驱动模块待测程序桩模块测试运行环境程序框架如图3-1所示，包含测试环境构造、算法和测试运行环境三部分。图3-1 程序框架图测试环境构造部分是整个系统的基础，它主要利用静态分析提供的基本信息并借助于各种插装技术来构造相应的测试运行环境。算法部分是系统的核心，它主要按照第一部分生成的编码参数格式构造相应的染色体串，并生成初始种群，然后通过对该种群进行反复的GA

34、运算（选择、交叉和变异）从而引导种群不断地向目标值进化直到最终找到解或达到限定的运行代数为止。最后部分是测试运行环境。算法第二部分需要对种群中每一个个体的优劣进行评估，它主要是通过实时地调用并运行插装后的测试系统来返回适应度值，从而来指导算法的搜索。3.3 基于算法的测试用例生成算法实现 编码策略使用算法求解问题时，必须将目标问题的实际表示与算法的染色体位串结构之间建立映射关系，这一过程即为编码。编码就是将目标问题的解用一种特定字符串来表示，从而将问题的解空间（有效的候选解，即表现型个体）与算法的码空间（基因型个体）相对应。编码过程是算法的基础，编码方法除了决定了个体的染色体排列形式之外，还决

35、定了个体从GA空间的基因型变换到问题空间的表现型时的解码方法（即为编码方法的逆方法）。同时，编码方法也影响到交叉算子、变异算子等算子的运算方法。由此可见，编码方法的好坏是影响算法性能及效率的重要因素。一个好的编码方法，有可能会使得交叉运算、变异运算等操作可以简单地实现和执行。相反，选择了不当的编码方法有可能会使得交叉运算、变异运算等操作难以实现，甚至可能会产生很多不属于可行解集合内的无效解。因此Goldberg提出了三条编码评估规范：完备性（Completeness）：问题空间中的所有点都能作为GA空间中的点(染色体)表现。健全性（Soundness）：GA空间中的染色体能对应所有问题空间中的

36、候选解。非冗余性（Nonredundancy）：染色体和候选解一一对应。常见的编码方法有二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法等，在应用中具体使用何种编码方法应根据问题的实际情况而定，这里我们使用二进制编码方法。二进制编码方法是算法中使用最多的编码方法，不光是由于其编码解码操作简单，便于实现交叉、变异等操作，而且该编码方法符合最小字符集编码原则，能使染色体与候选解一一对应。使用二进制编码方法进行编码时，先根据问题所要求的求解精度确定符号串的长度，假设某一参数的取值范围为Xmin,Xmax，可用长度为L的二进制编码符号来表示该参数，则能产生2L个不同的编码，设编码精度为，则

37、：Xmin 表示为 0000.000=0 Xmax 表示为 1111.111=2L -1= （3-1）若某个体编码为X：aLaL-1aL-2.a2a1 ，则其解码公式为：x= （3-2） 适应度函数及程序插桩（1）适应度函数在算法中，不需要用到搜索空间的知识，而使用适应度函数对染色体进行评价，一般来说，适应度高的染色体的评价较高，适应度低的染色体评价较低而可能被淘汰，因此，适应度函数直接决定了种群的进化方向，对算法的好坏具有很大影响。同时，适应度函数的复杂度是算法复杂度的主要组成部分，因此适应度函数要求尽可能简单。适应度函数通常可以从目标函数转化而来。一般来说，要求适应度的取值越大越好。但在实

38、际问题中，有的目标函数是求最大值（如利润问题），也有的目标函数是求最小值（如费用问题）。因此在很多场合需要将目标函数转换为最大值形式并且函数值为非负的适应度函数。（2）程序插桩在程序流程图中，每个分支都可以用一个判断表达式来表示，该判断表达式称为分支谓词，其作用是描述了程序遍历该分支的条件，如判断语句“if(a>b).”中分支谓词为“a>b”。分支谓词的一般形式为：E1 op E2，E1和E2是算数表达式，关系运算符。每个分支谓词都可以转换成等价形式为：F rel 0，其中F为分支函数，其构造方法如表3-1所示。表3-1 分支函数的构造分支谓词分支函数relE1>E2E2-E

39、1<E1>=E2E2-E1<=E1<E2E1-E2<E1<=E2E1-E2<=E1=E2abs(E1-E2)=E1!=E2-abs(E1-E2)<由表可知，当分支谓词为假时，分支函数为正；当分支谓词为真时，分支函数为负。而要使某条路径被覆盖时，该路径上的所有分支谓词应取真值，则分支函数应为负。由于分支函数直接构成了适应度函数，不能为负值，故而将分支函数修改为：当分支谓词为真时，分支函数取0；当分支谓词取假时，分支函数依然取真值。因此如果某条路径的所有分支函数都为0时表示该路径被全部覆盖。在本文中，使用的适应度函数为： （3-3）其中，f(xi)为

40、各分支插桩后的分支函数值。 策略（1）选择策略选择运算也叫复制运算，模拟了生物界优胜劣汰的自然选择现象。通过选择将优胜的个体直接到下一代或通过配对交叉产生新一代个体再到下一代。选择运算的依据是个体的适应度，适应度高的个体被选择到下一代的概率就大，甚至可能被多次复制，而适应度低的个体则可能一次都没被选中而淘汰。选择的概率一般取Ps 为0.1至0.2 。常用的选择运算的方法有轮盘赌转法、随机遍历抽样、锦标赛选择等，其中以轮盘赌转法最为常用。该算法将所有染色体的适应度总和看做一个轮子的圆周，而各染色体按其适应度占适应度总和的比例值大小占据一个扇区。每次进行选择时相当于轮盘的一次转动，转到哪个扇区则该

41、扇区的染色体被选中。这样适应度越高的染色体被选中的概率就越大。若某染色体的适应度为f(xi)，则被选中的概率为： （3-4）图3-2是一个简单的赌轮的例子：13%              35%         15%    0.67     37%|-|-|-|-*-|个体1    &

42、#160;        个体2              个体3         个体4图3-2 轮盘赌转法示意图3-2中随机数为0.67落在了个体4的段内，本次选择了个体4。（2）交叉策略交叉运算是算法中产生新个体的主要手段，其模拟的是生物学中的杂交现象。交叉运算通过使两个体的局部交换而使双方的优点有可能结合产生更好的新个体

43、。一般控制产生交叉运算的概率Pc 为0.5至0.8 。在二进制编码中，根据交叉点的不同可以分为单点交叉、两点交叉、均匀交叉等。在本文中采用的是单点交叉的方法，即首先在亲代中随机选取一个交叉点（染色体的某个码位），然后将两个亲代在该点及之后的染色体部分进行交换。（3）变异策略变异运算模拟的是生物中的基因突变现象。通过变异操作可以增强算法中群体的多样性，防止未成熟收敛现象，同时也使算法具备了局部随机搜索能力，是实现全局优化性能的重要算子之一。通常，变异的控制概率较小，Pm 一般取值为0.001至0. 1。在二进制编码方式中，变异运算即是将某些基因位上的基因值取反，即0变1或1变0。一般变异个体的选

44、择及变异位置都是随机确定的。二进制编码中的变异方法有基本位变异、均匀变异、高斯变异和二元变异等。本文采用的是基本位变异方法，即先随机选择某变异个体，再随机确定染色体的一个变异点将该码位置反。 参数控制除了上面提到的选择、交叉、变异的概率外，在算法中还有一些参数主要如下：种群规模 群体规模较大可以增加算法的多样性，提高GA搜索的质量，防止算法未成熟收敛。但是群体规模大使个体适应度的计算量大大增加，影响了算法的效率。因此应根据不同的实际情况确定不同的种群规模。Goldberg证明了在二进制编码的前提下，若个体长度为L，则种群规模的最优值为2L/2。染色体长度染色体长度即是编码长度，也即是表示个体的

45、字符串的长度。染色体的长度由具体问题决定，当解的取值范围越大、求值精度越大则染色体长度越大，带来的计算时间也相应越长。算法终止条件一般来说，算法的终止条件为预先设定的最大进化代数，通常取100到500 。也可以为某一特定条件，事具体问题而定。以上参数为通常情况下的取值，当然并非是固定不变的。在不同的算法中可以根据实际情况作相应的调整，只要能提高算法的运行效率就是可行的。3.4 本章小结本章是论文的核心章节，对算法应用于测试用例的生产方法进行了系统的介绍。首先介绍了算法生成测试用例的基本内含，然后提出了基本框架，最后对本文中算法实现的相关操作进行了描述，包括编码策略、适应度函数构造、选择策略、交

46、叉策略、变异策略等。第四章 实验及结果分析4.1 待测程序分析 待测程序引入本章中将以三角形分类程序为例来验证算法。三角形分类程序在许多软件测试研究中被作为基准程序来使用，因为其包含清晰而又复杂的逻辑，并且即使将一个较大范围的整数作为输入，也只有少量的输入组合能满足代码的某些特定分支。例如当输入为1到10 的整数时，1000组输入只有10组能满足判断为“等边三角形”的分支。三角形源程序为：String tri_type(int a,int b,int c) string type; if(a>b) change(a,b); if(a>c) change(a,c); if(b>

47、c) change(b,c); if(a+b>c) if(a=b|b=c) if(a=c) type=“等边三角形”; else type=“等腰三角形”; else type=“普通三角形”; else type=“不是三角形”; return type; 程序流程分析该程序流程图如图4-1所示，程序分为两部分，先将输入值由小到大排序，再将三角形进行分类。输入a,b,c交换a,b不是三角形a>b?a>c?b>c?a=b|b=c?a+b>c?交换a,c交换b,ca=c?等腰三角形普通三角形等边三角形结束YYYYYYNNNNNN图4-1 三角形分类程序流程图 路径分

48、析通过对程序流程分析可知，该程序对三角形进行分类的语句为图4-2中标有“”至“”号的分支，对这些分支进行路径分析如表4-1所示：表4-1 路径分析路径号分支结果w1不是三角形W2-普通三角形W3-等腰三角形W4-等边三角形4.2 程序插桩根据，对待测程序插桩：String tri_type(int a,int b,int c) string type; if(a>b) change(a,b); if(a>c) change(a,c); if(b>c) change(b,c); f1=c-(a+b) ; /插桩1 if(a+b>c) f2=min(abs(a-b),abs

49、(b-c); /插桩2 if(a=b|b=c) f3=abs(a-c); /插桩3 if(a=c) type=“等边三角形”; else type=“等腰三角形”; else type=“普通三角形”; else type=“不是三角形”; return type; F=1/(1+f1)+1/(1+f2)+1/(1+f3); /适应度函数 return F; 4.3 参数设定及程序实现 参数设定（1）编码（2）操作参数在本实验中，设定操作的参数如表4-2所示：表4-2 操作参数设定种群大小选择策略及概率交叉策略及概率变异策略及概率最大进化代数100轮盘赌转法，0.1单点交叉，0.8基本位变异，

50、0.1100（3）算法终止条件本实验中设定算法终止条件为满足以下两个条件之一：找到最优解，即适应度为100的解；达到最大进化代数，当程序进化满100代后，不管有没找到最优解都将退出。 部分程序实现本文中的三角形分类程序是在Microsoft Visual Studio2005的环境下采用C+语言实现的。以下为该程序的主要算法模块：（1）染色体定义模块，该模块完成了染色体的编码：struct sides int a;int b;int c; /测试的三个数据bitset<3*BIT> chromosome; /该组的染色体int sufficiency; /该组数的适应度bool i

51、sOp ; /标记是否操作过（2）计算适应度，采用插桩法：int getSufficiency(int a, int b, int c) int f, f1, f2, f3;if(a>b) change(a,b); if(a>c) change(a,c); if(b>c) change(b,c);f1 = c - (a + b); /if(a+b>c)f2 = min<int>(abs(a-b), abs(b-c); /if(a=b|b=c)f3 = abs(a-c); /if(a=c) type=“等边三角形”; /else type=“等腰三角形”; /

52、else type=“普通三角形”; /else type=“不是三角形”; /return type; if (f1 < 0) f1 = 0; f = ( 100/(1+f1) + 100/(1+f2)+ 100/(1+f3)/3;return f; （3）选择操作，使用了轮盘赌转法：void select(sides newGroup, sides oldGroup) resetFlag(oldGroup);int aPosGROUP; /存储每组数据在转盘中的位置aPos0 = oldGroup0.sufficiency;for (int i = 1; i < GROUP;

53、i+) aPosi = oldGroupi.sufficiency;aPosi += aPosi - 1; for(int i = 0; i < SELECTION; ) int random = rand()%aPosGROUP - 1; /产生随即数,0到群体中的最后一组数据所在的位置找到该随机数所在位置,如果位置重复了就重新选择for (int j = 0; j < GROUP; j+) if(random <= aPosj) if(!oldGroupj.isOp) newGroupi = oldGroupj; oldGroupj.isOp = true;i+;break; else break; （4）交叉操作，先用轮盘赌转法选择，再用单点交叉法进行交叉：void cross(sides newGroup, sides oldGroup) int aPosGROUP; aPos0 = oldGroup