浙江工商大学有关保留使用学位论文的规定浙江工商大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印缩印或扫描等复制手段保存汇编学位论文，并且本人电子文档的内容和纸质论文的内容相致。保密的学位论文在解密后也遵守此规定。签名筮壹差导师签名盒经日期矽呀年月日第章绪论立题背景和选题意义随着社会的不断进步和计算机技术的飞速发展，计算机作为项重要的工具，已经在国防军事，市场经济和社会生活领域发挥着不可替代的作用。而软件作为计算机的灵魂，在其中起着举足轻重的作用。在软件开发的整个生命过程中，每个阶段都可能存在着潜在的危险，可能给社会带来巨大的经济损失，甚至危及人们的生命安全。年海湾战争中，美国爱国者导弹防御系统在对抗几枚导弹中失利，其中次在沙特阿拉伯的多哈击毙了名美国士兵，后来的分析发现该事故是系统时钟的个很小的计时所引起的，该累加起来到小时后，跟踪系统不再准确。年月日，美国航天局的火星极地登陆者号探测器试图在火星表面着陆时失踪的起因就是由于数据位被意外置位引起的。虽然软件质量是如此重要，软件工程领域也在不断地寻求更加安全的开发模式，但不论采用什么技术或方法，软件中仍然会有错。其根源就在于，软件开发是与人的智力活动紧密联系在起的，在软件开发的每个阶段，人的因素起着决定性作用。作为保证软件质量提高软件可靠性的重要手段，软件测试在软件开发过程中起着不可替代的作用，并伴随着软件开发的始终。然而，软件测试是个十分复杂的过程，需要花费巨大的人力，物力，财力和时间。在般情况下，测试所占的时间和费用约占整个开发过程的，或者更多。测试人员需要设计，执行，分析大量的测试用例，这在很大程度上还是依靠手工来实现的，效率非常低下，同时也导致了测试费用的居高不下。但是，由于测试工作的特殊性必须依赖于现有的产品说明书，代码和软件，不可能完全实现测试工作的自动化，因此如何最大程度上实现软件测试的自动化，提高测试效率，保证测试准确性，成为个迫切需要解决的问题。目前，软件测试的自动化已经取得了定的进展，已经有了些自动化工具来帮助测试人员进行测试。但是，这类测试工具基本上都是针对测试用例的执行和维护，以及对程序的覆盖情况的分析，在测试用例自动生成方面还很不完善。所以实现测试用例的自动生成，将大大地改善现在依靠经验和直觉来生成测试用例的现状提高测试效率节约测试成本。本文是在浙江省科技厅重点项目，基于主动数据仓库的中小企业商务智能系统项目编号的项目背景下进行研究和实施的。产生的测试数据用于本项目的测试提供了很好的服务，节约了项目成本。国内外研究现状软件测试数据自动生成可以包括功能测试数据自动生成和结构测试数据自动生成。前者属于黑盒测试，不需要知道程序代码，后者是在代码基础上的测试，本文所讨论的正是基于代码的测试数据自动生成。自从上世纪年代以来，国内外的学者们对于测试用例的自动生成进行了多方面的研究，提出了很多的方法和建议。提出采用随机法自动生成测试用例，可以不受限制地迅速随机生成大量的测试数据。只是生成的测试数据集，仍然是个庞大的集合，没有针对性，效率不高。目前很多测试工具所采用的就是这种随机法。等人和提出的都是符号执行法。该方法的主要思想是把符号值作为程序输入，静态执行指定路径上的语句，从而得到变量的值。这里的执行并没有真的动态运行被测程序，只是按照程序执行的顺序将相应的变量用符号表达式代换。因此随着程序规模的增大，符号表达式变得很长，甚至几乎无法求解，该方法的可用性也就随之变差。与之相对应的是动态法，动态法的基本思想是从输入空间中任取个假设解作为初始输入，通过实际运行程序不断调整输入，使得程序实际执行路径向指定路径不断逼近，直到与指定路径完全选择压力也将按指数增长。最佳个体在下代的生存机会将显著增加，而最差个体的生存机会将被剥夺。目前，轮盘赌是使用得比较广泛的策略之，本文也将轮盘赌算法作为选择操作的选取算法。本文中的选择操作是从父代中选取相对优良的个体进入中间代，使用轮盘赌法选取适应度高的个体，并复制进入中间代。对于种群中的个个体来说，具体操作如下顺序计算种群中各个个体的适应度，求得第个个体的适应度，累计值,在司，内随机生成个均匀分布的随机数⋯在第次，用与⋯进行比较，当第次出现时，选取第个个体进入中间代。若，则选取第个个体进入中间代。交叉算子交叉操作是进化算法中遗传算法具备的原始性的独有特征。中交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下代个体，并生成包含更复杂基因结构的新个体。交叉操作般分为下几个步骤从交配池中随机取出要交配的对个体根据位串长度，对要交配的对个体，随机选取，中个或多个的整数作为交叉位置根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的对个体。本文采用的交叉算子为点交叉，或称单点交叉。点交叉是由提出的最基础的种交叉方式。对于从交配池中随机选择的两个串⋯⋯,⋯⋯，随机选择个交叉位∈⋯，不妨设，对两个位串中该位置右侧部分的染色体位串进行交换，产生两个子位串个体为⋯⋯⋯⋯变异算子变异操作模拟自然界生物体进化中染色体上位基因发生的突变现象，从而改变染色体的结构和物理性状。在遗传算法中，变异算子通过按变异概率随机反转等位基因的二进制字符值来实现。对于给定的染色体为串⋯具体如下若否则，。其中∈⋯，是对应于每个基因位产生的均匀随机变量，∈，。这是对二进制编码而言，本文采取的是浮点数编码，所以变异是发生的并不是，之间的转换，而是实数间的替换，本文的具体方法是自动生成个满足条件的数，用它来替换。变异操作作用于个体位串的等位基因上，由于变异概率比较小，在实施过程中些个体可能不发生次变异，造成大量计算资源的浪费。因此，在具体应用中，我们可以采用种变通措施，首先进行个体层次的变异发生的概率判断，然后再实施基因层次上的变异操作。般包括两个基本步骤计算个体发生变异的概率以原始的变异概率为基础，可以计算出群体中个体发生变异的概率，⋯，给定均匀随机变量∈若，则对该个体进行变异，否则表示不发生变异。计算发生变异的个体上基因变异的概率由于变异操作方式发生了改变，被选择变异的个体上基因的变异概率也需要相应修改，以保证整个群体上基因发生变异的期望次数相等。传统变异方式下整个群体基因变异的期望次数为。设新的基因变异概率为，新的变异方式下整个群体基因变异的期望次数为。要求两者相等，即可以导出裔丽面。，位串越短，越比大。当位串长度趋于无穷大时两者相等，即。厶∞传统变异方式下的计算量为，新的变异方式下的计算量，计算量差异为，显然新的变异方式比传统方式计算量降低了，且随着位串长度的增大而下降。但是，这种新变异方式也在定程度上偏离了原来的变异基因位在全部群体个体基因位中的均匀分布的情况，当群体比较小时，可能会带来定的变异误差。为了保证个体变异后不会与其父体产生太大的差异，变异概率般取值较小，以保证种群发展的稳定性。当交叉操作产生的后代个体的适应值不再比它们的前辈更好，但又未达到全局最优解时，就会发生成熟前收敛或早熟收敛。这时引入变异算子往往能产生好的效果。方面，变异算子可以使群体进化过程中丢失的基因信息得以恢复，以保证群体中的个体差异性，防止发生成熟前收敛另方面，当种群规模较大时，在交叉操作基础上引入适度的变异，也能够提高遗传算法的局部搜索效率。在群体进化的整个过程中，交叉操作是主要的基因重组和群体更迭的手段，变异操作的作用是第二位的，变异算子仅仅充当背景性的角色。终止条件的确定关于迭代过程如何终止，由于实际问题的复杂性和遗传算法本身的随机性，在实际应用中常根据经验采用固定的进化迭代次数作为遗传算法的终止条件。其次，遗传算法的终止条件也可以是基于种判定标准的，即在判定种群已收敛并不再有进化趋势后终止计算。例如，根据连续几代个体的平均适应度值之差小于个较小的正数值，或者根据群体中最佳个体适应度值与平均适应度值之差小于个较小的正值作为终止条件。本文在采用遗传算法进行搜索计算的过程中，通过采用设定最大代数的方法来控制遗传算法的终止，但是本文的目的是要产生大量的符合要求的测试数据，而并非是遗传算法的般应用寻求最优解。所以本文采取的具体思路是，旦有符合适应度函数要求的个体，就先输出个体，再对整个群体进行迭代，生成新的代，然后再对新的代个体计算适应度函数值，输出符合要求的个体⋯⋯，这样重复下去直到到达限定的最大迭代次数为止。算法实现步骤算法流程本文中提到的算法的实现过程如下砌始化个体计算个体的适应度函数值，丧取当前种群中的最优个体选择复制操作腋叉操作腋异操作计算个体的适应度函数值肠莛取当前种群中的最优和最差个体初始化个体随机生成符合要求的数据作为初始基因，并根据多参数级联编码原则，将数据串成个体。同时初始化适应度函数值都为，累积适应度函数值也都为。计算适应度函数值根据构造的适应度函数，分别计算每个个体的适应度函数值。若值为，则对该个体进行拆分，解码，然后输出符合要求的测试数据。获取当前种群中的最优个体利用已经取得的适应度函数值，获取当前代种群中的最优个体。选择复制操作按之前得到的适值函数值，运用轮盘赌算法，选择进入下代的个体。交叉操作从产生的个体中按照交叉概率对每个个体进行选择，使两个个体进行单点交叉包括个基因位的交叉和段基因区间的交叉，得到新的个体。变异操作在交叉后的个体中随机加入些变异，这些变异基因是重新随机生成的，替代被变异概率选中的基因，产生新的个体获取当前种群的最优和最差个体获取当前代种群的最优个体和最差个体，如果当前代的最佳个体比上代的最佳个体要差的话，那么用这个上代的最佳个体代替当前代的最差个体，否则用当前代的最佳个体替代最佳个体。这个过程可以用流程图来表示更加清晰，如图所示图本文算法的基本流程实现过程测试数据生成过程本文所采取的测试程序是个常见的简单程序近凹蚤皿，这里根据两个语句可以生成条路径，假设我们要测试的是路径，也就是当时的情况，根据上节中介绍的适应度函数的构造方法，本文的适应度函数可以构造如下种