本发明公开了一种基于遗传算法的MC/DC测试数据自动生成方法，包括：对被测程序进行静态分析，产生控制流图、数据流图、抽象语法树和抽象分析树；生成MC/DC测试用例预期结果集；对被测程序进行代码插桩；构造适应度函数；随机产生测试数据，检验是否满足预期执行的路径；使用遗传算法的选择、交叉、变异等遗传操作，得到合适的测试数据。本发明在适应度函数的构造上，结合链接法思想，以传统适应度函数为基础，提出以获取直接或者通过数据依赖间接影响问题节点遍历的控制节点的方法来优化接近水平适应评价。本发明对逻辑关系复杂的系统进行测试时具有很大的实用价值。
1.一种基于遗传算法的MC/DC测试数据自动生成方法，其特征在于：包括以下几个步骤：步骤一：对被测程序进行静态分析，产生控制流图、数据流图、抽象语法树和抽象分析树；
步骤2.1：从抽象分析树中提出条件节点，这些条件节点构成了抽象分析树的叶子，每一个叶子就是一个变量，用N表示提取的叶子变量的个数；
步骤2.2：构建真值表，对N个叶子变量，有2 种排列组合；
步骤2.4.1：将真值表当前行中的布尔值对应分配给抽象分析树的每一个叶子变量；
步骤2.4.2：自底向上评价各个条件节点的布尔值，直到抽象分析树的顶端，最终所得的抽象分析树的顶端的条件节点的布尔值就是这个判定语句的输出结果值；
步骤2.5：针对每一个叶子变量，寻找其测试用例，并添加到每个叶子变量的MC/DC测试用例集中：步骤2.5.1：为每一个叶子变量建立一对空的MC/DC测试用例集；
步骤2.5.2：在真值表中，寻找其他叶子变量值固定，只有目标叶子变量改变的两行；
步骤2.5.3：比较步骤2.5.2中的两行的输出结果值，如果两行的输出结果值不同，则这两行就是目标叶子变量的一对测试用例，将这两行以成对的形式添加到步骤2.5.1中建立的MC/DC测试用例集中；
步骤2.6：将每一个叶子变量的MC/DC测试用例集合并，得到测试用例集，并最小化测试用例集；
首先遍历抽象语法树找到插桩的位置，判断是否是插桩点，如果不是插桩点，返回继续遍历抽象语法树寻找找到插桩位置；如果是插桩点，则植入检查语句，然后直接在抽象语法树上以子树的形式植入代码的语法树片段，判断插桩是否完成，如已完成，则被测程序编译运行；如未完成，返回继续遍历抽象语法树找到插桩的位置，直至完成插桩；
步骤4.1.1：通过被测程序的控制流图，获得每一个判定的控制依赖关系集合；控制依赖用来描述一个目标节点y的执行关于其前面分支节点输出的依赖性，当每一条从目标节点y到出口节点e的路径都包含节点z时，称节点z被目标节点y后置控制；任意节点x，两个节点（y，x）之间可以构成一个分支路径，当每一条从目标节点y到出口节点e的通过（y，x）分支路径都包括节点z时，称节点z后置控制一个分支（y，x）；当节点z后置控制y的一个分支，且节点z不后置控制节点y，称节点z控制依赖于目标节点y，控制依赖关系是从结构关系角度衡量当前输入测试数据距离抵达目标的逼近程度，通过控制流图中目标与执行偏离条件节点间的关键节点计算得到；
控制依赖关系适应度函数包含了控制依赖关系集合中各分支节点的目标函数，建立控制依赖关系适应度函数为：ControlDepFittestdata＝dependentdecisions-executeddecisions （1）其中，dependentdecisions为目标的控制依赖关系集合中的控制节点数；executeddecisions表示以当前测试数据为输入；ControlDepFittestdata表示控制依赖关系适应度函数；
如果控制依赖关系适应度函数值为0，则测试数据能够到达目标判定；如果控制依赖关系适应度函数值大于0，则测试数据在某处偏离了目标节点，通过控制依赖关系适应度函数的值，得到偏离节点divergednode；
定义pn为问题节点，S为用来储存一个给定节点的依赖关系的集合，以pn和S作为获取数据依赖关系适应度函数方法的输入，DepSets用来储存当前搜集到的存在依赖关系的节点集合，PV用来存储问题节点使用的变量，S和DepSets被初始化为空集，获取一个节点的依赖关系适应度函数的方法为：步骤4.2.1：获取问题节点pn的控制依赖关系集合ControlDep（pn）赋给S，并将pn使用的变量UsedVariables（pn）加到PV中；
步骤4.2.2：对于PV中的每一个变量pv，获取pv的最后定义集合lastDefs；
（a）对于lastDefs中每一个最后定义ld，获取ld的控制依赖关系集合ControlDep（ld），并将其与S合并，得到扩展的S，然后将ld使用的变量UsedVariables（ld）添加到一个新建的PVnew中；
（b）对于ControlDep（ld）中的每一个控制节点cd，获取它使用的变量UsedVariables（ld），并添加到步骤4.2.2（a）建立的PVnew集合中；
步骤4.2.3：对于PV中的每一个变量pv，迭代获取PV依赖关系集S(ld)，首先获得PV中的第一个变量，获取其依赖关系集S(ld)，返回步骤4.2.2，然后获取PV中的下一个变量，直至完成PV中所有的变量，结束迭代，并将S(ld)添加到DepSets中；
步骤4.2.4：建立用于定义适应度函数的依赖关系集合：
定义DepFit为适应度函数依赖关系集合，对于DepSets中的每一个子集si：（a）添加si到DepFit中；
（b）判断DepSets中每一个非si的子集sj，与si是否存在then、else的分支冲突，如果不存在，则合并两个子集si、sj，得到新的子集Si,j，并将Si,j添加到DepFit中；如果存在then、else的分支冲突则不能合并，将si、sj都添加到DepFit中；
建立数据依赖关系集合后，用计算控制依赖关系适应度函数的方法得到数据依赖关系适应度函数；
当测试数据抵达目标时，用分支距离来度量测试数据是否满足期望测试用例，通过计算分支距离度量测试数据距离期望测试用例的逼近程度，如果测试数据到达目标判定，但是不满足任一个MC/DC测试用例，那么每一个测试数据的接近水平都为0，但分支距离不为
0；如果测试抵达目标并实现一个测试用例，那么它的分支距离和接近水平都为0；计算出来的分支距离的大小用来评价哪一个测试数据更接近于满足期望的分支测试用例；
步骤五：在MC/DC测试用例、适应度函数公式和执行插桩代码的基础上，随机产生测试数据，并在这些测试数据上执行插桩后的被测程序，获得适应度值，同时检验是否满足预期执行的路径；如果满足，则进入步骤七；否则进入步骤六；
计算接近水平适应度函数ApproachLevelFitness，如果ApproachLevelFitness为0，则测试数据到达目标；然后在目标判定处，计算分支距离BranchFitness，如果ApproachLevelFitness和BranchFitness都为0，则测试数据达到MC/DC测试目标，否则，测试数据的适应度函数值等于ApproachLevelFitness+normalized(BranchFitness)，normalized(BranchFitness)表示对分支距离BranchFitness的标准化，具体的计算过程为：步骤5.1：按照步骤二的方法生成MC/DC测试用例预期结果集；
步骤5.2：按照步骤4.1和步骤4.2的方法获得依赖关系集合，包括控制依赖集和数据依赖集；
步骤5.3：针对每一个目标判定，随机生成测试数据Ta和测试数据Tb；
步骤5.4：按照步骤4.1中的计算方法，根据依赖关系集合，分别计算测试数据Ta和测试数据Tb的控制依赖适应度函数和数据依赖适应度函数；
步骤5.5：按照步骤4.3中的计算方法，分别计算测试数据Ta和测试数据Tb的分支距离；
步骤5.6：进行分支距离的标准化BranchFitness(Ta)normalised，计算公式为：其中，BranchFitness(Ta)表示测试数据Ta的分支距离，BranchFitness(Tb)表示测试数据Tb的分支距离；
步骤5.7：总适应度函数值Fitness(T)为：
Fitness(T)＝ApproachLevelFitness(T)+BranchFitness(T)normalized其中，ApproachLevelFitness(T)表示测试数据T的接近水平适应度函数；
BranchFitness(T)normalized表示测试数据T的分支距离的标准化值；
步骤5.8：根据总适应度函数值比较这两个测试数据哪个更接近于达到判定目标；
若ApproachLevelFitness和BranchFitness都为0，则测试数据达到MC/DC测试目标，进入步骤七，否则，进入步骤六；
步骤六：根据得到的适应度值，使用遗传算法的选择、交叉、变异等遗传操作，生成新的测试数据，并返回步骤五，计算新生成的测试数据的适应度值；
步骤6.1：选择编码策略，把参数集合X和域转换为位串结构空间S；
采用整型和实型混合的方式编码染色体，问题的参数直接转换为染色体上的基因，参数的个数转换为染色体长度，各参数的取值区间映射为各基因的取值范围，具体过程如下：设求解问题包含n个输入变量X1,X2,...,Xn，首先，用等价类划分和边界值分析方法处理参数的值域，其中Yi(1≤i≤n)表示参数Xi(1≤i≤n)可以取值的有限离散点的集合，|Yi|表示集合的大小，建立问题解空间和染色体空间的映射关系，染色体表示为：X＝(X1,X2,...,Xn)→C＝(C1,C2,...,Cn) （2）其中，C为染色体空间解空间中的解，X为问题空间的解；
步骤6.2：设计和选择遗传操作，包括种群大小，选择、交叉、变异方法，以及确定交叉概率pc和变异概率pm等遗传参数；
（a）根据适应值的大小，降序排列种群中的所有个体；
（b）设计概率分配表，根据适应值大小，升序分配每个个体的概率值；
（c）每个个体被遗传到下一代的概率由步骤（b）中分配的概率值决定，再基于这些概率值，用轮盘赌选择法选择被淘汰和被复制的染色体；经过一轮排序选择策略后，会得到一个新的种群，然后在这个新的种群基础上再执行精英保留策略，具体过程为：（a）根据适应度函数值的大小从经过排序选择策略后得到的新种群即当前种群中获取最佳个体和最差个体；
（b）如果当前种群的最佳个体的适应度高于此前获得的出现的最佳个体的适应度，则用当前群体的最佳个体替换此前出现的最佳个体；
（c）保持迄今出现的最佳个体状态不变，将其完整的遗传到下一代种群中；
采用自适应的交叉概率pc和变异概率pm，根据群体平均适应值及当前群体最优个体适应值来自动调整交叉概率pc和变异概率pm；fmax表示某一代种群中最优个体的适应度，Favg表示该代群体的平均适应度，最优个体的适应度与该代群体的平均适应度的差值Δ＝fmax-Favg，则当Δ越小，表示种群个体之间的适应度差别越小，说明种群此时达到局部最优的可能性较大，过早收敛的可能性也越大；当Δ越大，表示个体之间的适应度差别越大，交叉概率pc和变异概率pm由Δ来决定，pc和pm的计算公式为：pc＝k1/Δ （3）
其中，k1和k2分别为交叉概率调整系数和变异概率调整系数；
步骤6.4：计算种群P中个体位串解码后的适应度值；
步骤6.5：按照遗传策略，将步骤6.2中设计的各遗传操作作用于种群，经过选择、交叉和变异后，形成了新一代种群；
步骤6.6：带着新产生的染色体即测试数据返回步骤五，计算其适应度值，判断其性能是否满足指标，或者是否已完成预定迭代次数，若不满足并且没有完成迭代次数，则进入步骤6.1，遗传算法从编码操作开始，对新产生的种群重新进行选择复制、交叉和变异，不断迭代；若满足指标或已完成迭代次数则直接进入步骤七；
一种基于遗传算法的MC/DC测试数据自动生成方法
技术领域
[0001] 本发明属于软件测试技术领域，具体涉及一种基于遗传算法的MC/DC测试数据自动生成方法，特别涉及工程测试中满足MC/DC覆盖（修正条件判定覆盖）的测试数据自动生成方法。
背景技术
[0002] 测试数据自动生成技术是指通过特定的算法依据软件的规约或者程序结构自动构造测试输入数据，其目的在于减轻测试人员所必须付出的大量劳动，降低手工测试的高额成本，同时提高测试过程的可信赖程度。遗传算法是一种模拟生物进化过程和机制求解极值问题的自适应人工智能技术，在解决大空间、非线性等高复杂度问题时具有独特的优势。
[0003] 动态执行程序生成测试数据的思想最初由Miller和Spooner提出，后来的学者做了大量的进一步研究。1992年，Xanthakis首先将遗传算法应用于测试用例生成，它采用编码技术将D映射到基因空间G，并通过选择、交叉、变异等遗传操作和优胜劣汰的自然选择确定搜索方向。交叉和变异操作为种群引入新的信息，从而更有利于找到全局最优解，避免了以往算法往往容易陷入局部极值的问题，能够生成满足所有分支判定准则的测试数据。在国内，1996到1998年，荚伟、高仲仪等发表多篇论文，讨论将遗传算法应用于基于路径覆盖的Ada软件结构测试数据的自动生成，并得出遗传算法比爬山法和随机法生成测试数据的效率高的结论。2001年，汪浩等给出了遗传算法的形式化的表示和一个基于此算法的测试数据生成系统原型。2003年，景志远从数学的角度分析了将MGA和遗传K均值等改进的算法应用于测试用例的自动生成。2006年，程烨在学位论文将遗传算法用于路径覆盖测试数据自动生成，并开发了相应的工具模型。2008年，吕珊珊在她的学位论文中使用神经网络和遗传算法生成基于输入域的测试数据。总的来说，现在国内外的研究学者多采用遗传算法或者遗传算法的改进算法作为核心算法来生成测试数据。但上述均是选择逻辑结构相对简单的语句覆盖或分支覆盖生成测试用例，使其在实际的工程领域无法得到广泛的应用。
发明内容
[0004] 针对现有技术中存在的问题，本发明提出一种基于遗传算法的MC/DC测试数据自动生成方法。针对遗传算法中传统适应度函数仅依靠控制流图中节点间的控制依赖关系，没有考虑被测程序内部的数据依赖关系的缺陷，提出使用链接法思想收集直接或者通过数据依赖间接影响问题节点遍历的控制节点，并将其与表征控制依赖关系见长的传统适应度函数相结合，构造一个新的适应度函数，以此来克服传统的适应度函数因忽略程序内部的数据依赖关系而造成的引导信息缺乏、搜索退化的问题。在此基础上设计实现了基于遗传算法的满足MC/DC准则的测试数据自动生成方法。MC/DC准则强调单个变量对于最后表达式真假的影响的能力，要求每一个条件都要独立的影响判定表达式的结果，对逻辑关系复杂且安全性要求较高的软件系统进行测试时具有很大的实用价值。
[0005] 本发明提出一种基于遗传算法的MC/DC测试数据自动生成方法，具体包括以下几个步骤：
[0006] 步骤一：对被测程序进行静态分析，产生控制流图、数据流图、抽象语法树和抽象分析树。
[0007] 步骤二：生成MC/DC测试用例预期结果集。
[0008] 步骤2.1：从抽象分析树中提出条件节点，这些条件节点构成了抽象分析树的叶子，每一个叶子就是一个变量，用N表示提取的叶子变量的个数。
[0009] 步骤2.2：构建真值表，对N个叶子变量，有2N种排列组合。
[0010] 步骤2.3：用数字0和1填充真值表。
[0011] 步骤2.4：针对真值表中的每一行：
[0012] 步骤2.4.1：将真值表当前行中的布尔值对应分配给抽象分析树的每一个叶子变量；
[0013] 步骤2.4.2：自底向上评价各个条件节点的布尔值，直到抽象分析树的顶端，最终所得的抽象分析树的顶端的条件节点的布尔值就是这个判定语句的输出结果值；
[0014] 步骤2.4.3：用输出结果值填充真值表的输出列。
[0015] 步骤2.5：针对每一个叶子变量，寻找其测试用例，并添加到每个叶子变量的MC/DC测试用例集中：
[0016] 步骤2.5.1：为每一个叶子变量建立一对空的MC/DC测试用例集；
[0017] 步骤2.5.2：在真值表中，寻找其他叶子变量值固定，只有目标叶子变量改变的两行；
[0018] 步骤2.5.3：比较步骤2.5.2中的两行的输出结果值，如果两行的输出结果值不同，则这两行就是目标叶子变量的一对测试用例，将这两行以成对的形式添加到步骤2.5.1中建立的MC/DC测试用例集中。
[0019] 步骤2.6：将每一个叶子变量的MC/DC测试用例集合并，得到测试用例集，并最小化测试用例集。
[0020] 步骤三：对被测程序进行代码插桩。
[0021] 首先遍历抽象语法树找到插桩的位置，判断是否是插桩点，如果不是插桩点，返回继续遍历抽象语法树寻找找到插桩位置；如果是插桩点，则植入检查语句，然后直接在抽象语法树上以子树的形式植入代码的语法树片段，判断插桩是否完成，如已完成，则被测程序编译运行；如未完成，返回继续遍历抽象语法树找到插桩的位置，直至完成插桩。
[0022] 步骤四：构造适应度函数。
[0023] 步骤4.1：建立控制依赖关系适应度函数：
[0024] 步骤4.1.1：通过被测程序的控制流图，获得每一个判定的控制依赖关系集合；控制依赖用来描述一个目标节点y的执行关于其前面分支节点输出的依赖性，当每一条从目标节点y到出口节点e的路径都包含节点z时，称节点z被目标节点y后置控制；任意节点x，两个节点（y，x）之间可以构成一个分支路径，当每一条从目标节点y到出口节点e的通过（y，x）分支路径都包括节点z时，称节点z后置控制一个分支（y，x）；当节点z后置控制y的一个分支，且节点z不后置控制节点y，称节点z控制依赖于目标节点y，控制依赖关系是从结构关系角度衡量当前输入测试数据距离抵达目标的逼近程度，通过控制流图中目标与执行偏离条件节点间的关键节点计算得到。
[0025] 步骤4.1.2：建立控制依赖关系适应度函数：
[0026] 控制依赖关系适应度函数包含了控制依赖关系集合中各分支节点的目标函数，建立控制依赖关系适应度函数为：
[0027] ControlDepFittestdata＝dependentdecisions-executeddecisions （1）[0028] 其中，dependentdecisions为目标的控制依赖关系集合中的控制节点数；executeddecisions表示以当前测试数据为输入；ControlDepFittestdata表示控制依赖关系适应度函数；
[0029] 如果控制依赖关系适应度函数值为0，则测试数据能够到达目标判定；如果控制依赖关系适应度函数值大于0，则测试数据在某处偏离了目标节点，通过控制依赖关系适应度函数的值，得到偏离节点divergednode；
[0030] 步骤4.2：建立数据依赖关系适应度函数：
[0031] 定义pn为问题节点，S为用来储存一个给定节点的依赖关系的集合，以pn和S作为获取数据依赖关系适应度函数方法的输入，DepSets用来储存当前搜集到的存在依赖关系的节点集合，PV用来存储问题节点使用的变量，S和DepSets被初始化为空集，获取一个节点的依赖关系适应度函数的方法为：
[0032] 步骤4.2.1：获取问题节点pn的控制依赖关系集合ControlDep（pn）赋给S，并将pn使用的变量UsedVariables（pn）加到PV中；
[0033] 步骤4.2.2：对于PV中的每一个变量pv，获取pv的最后定义集合lastDefs；
[0034] （a）对于lastDefs中每一个最后定义ld，获取ld的控制依赖关系集合ControlDep（ld），并将其与S合并，得到扩展的S，然后将ld使用的变量UsedVariables（ld）添加到一个新建的PVnew中；
[0035] （b）对于ControlDep（ld）中的每一个控制节点cd，获取它使用的变量UsedVariables（ld），并添加到步骤4.2.2（a）建立的PVnew集合中；
[0036] 步骤4.2.3：对于PV中的每一个变量pv，迭代获取PV依赖关系集S(ld)，首先获得PV中的第一个变量，获取其依赖关系集S(ld)，返回步骤4.2.2，然后获取PV中的下一个变量，直至完成PV中所有的变量，结束迭代，并将S(ld)添加到DepSets中；
[0037] 步骤4.2.4：建立用于定义适应度函数的依赖关系集合：
[0038] 定义DepFit为适应度函数依赖关系集合，对于DepSets中的每一个子集si：
[0039] （a）添加si到DepFit中；
[0040] （b）判断DepSets中每一个非si的子集sj，与si是否存在then、else的分支冲突，如果不存在，则合并两个子集si、sj，得到新的子集Si,j，并将Si,j添加到DepFit中；如果存在then、else的分支冲突则不能合并，将si、sj都添加到DepFit中；
[0041] 步骤4.2.5：建立数据依赖关系适应度函数：
[0042] 建立数据依赖关系集合后，用计算控制依赖关系适应度函数的方法得到数据依赖关系适应度函数。
[0043] 步骤4.3：建立分支适应度函数：
[0044] 当测试数据抵达目标时，用分支距离来度量测试数据是否满足期望测试用例，通过计算分支距离度量测试数据距离期望测试用例的逼近程度，如果测试数据到达目标判定，但是不满足任一个MC/DC测试用例，那么每一个测试数据的接近水平都为0，但分支距离不为0；如果测试抵达目标并实现一个测试用例，那么它的分支距离和接近水平都为0；计算出来的分支距离的大小用来评价哪一个测试数据更接近于满足期望的分支测试用例。
[0045] 步骤五：在MC/DC测试用例、适应度函数公式和执行插桩代码的基础上，随机产生测试数据，并在这些测试数据上执行插桩后的被测程序，获得适应度值，同时检验是否满足预期执行的路径；如果满足，则进入步骤七；否则进入步骤六。
[0046] 计算接近水平适应度函数ApproachLevelFitness，如果ApproachLevelFitness为0，则测试数据到达目标；然后在目标判定处，计算分支距离BranchFitness，如果ApproachLevelFitness和BranchFitness都为0，则测试数据达到MC/DC测试目标，否则，测试数据的适应度函数值等于ApproachLevelFitness+normalized(BranchFitness)，normalized(BranchFitness)表示对分支距离BranchFitness的标准化，具体的计算过程为：
[0047] 步骤5.1：按照步骤二的方法生成MC/DC测试用例预期结果集。
[0048] 步骤5.2：按照步骤4.1和步骤4.2的方法获得依赖关系集合，包括控制依赖集和数据依赖集。
[0049] 步骤5.3：针对每一个目标判定，随机生成测试数据Ta和测试数据Tb。
[0050] 步骤5.4：按照步骤4.1中的计算方法，根据依赖关系集合，分别计算测试数据Ta和测试数据Tb的控制依赖适应度函数和数据依赖适应度函数。
[0051] 步骤5.5：按照步骤4.3中的计算方法，分别计算测试数据Ta和测试数据Tb的分支距离；
[0052] 步骤5.6：进行分支距离的标准化BranchFitness(Ta)normalised，计算公式为：
[0053]
[0054] 其中，BranchFitness(Ta)表示测试数据Ta的分支距离，BranchFitness(Tb)表示测试数据Tb的分支距离。
[0055] 步骤5.7：总适应度函数值Fitness(T)为：
[0056] Fitness(T)＝ApproachLevelFitness(T)+BranchFitness(T)normalized[0057] 其中，ApproachLevelFitness(T)表示测试数据T的接近水平适应度函数；
[0058] BranchFitness(T)normalized表示测试数据T的分支距离的标准化值。
[0059] 步骤5.8：根据总适应度函数值比较这两个测试数据哪个更接近于达到判定目标。
[0060] 步骤5.9：
[0061] 若ApproachLevelFitness和BranchFitness都为0，则测试数据达到MC/DC测试目标，进入步骤七，否则，进入步骤六。
[0062] 步骤六：根据得到的适应度值，使用遗传算法的选择、交叉、变异等遗传操作，生成新的测试数据，并返回步骤五，计算新生成的测试数据的适应度值。
[0063] 步骤6.1：选择编码策略，把参数集合X和域转换为位串结构空间S。
[0064] 采用整型和实型混合的方式编码染色体，问题的参数直接转换为染色体上的基因，参数的个数转换为染色体长度，各参数的取值区间映射为各基因的取值范围，具体过程如下：
[0065] 设求解问题包含n个输入变量X1,X2,...,Xn，首先，用等价类划分和边界值分析方法处理参数的值域，其中Yi(1≤i≤n)表示参数Xi(1≤i≤n)可以取值的有限离散点的集合，|Yi|表示集合的大小，建立问题解空间和染色体空间的映射关系，染色体表示为：
[0066] X＝(X1,X2,...,Xn)→C＝(C1,C2,...,Cn) （2）
[0067] 其中，C为染色体空间解空间中的解，X为问题空间的解；
[0068] 步骤6.2：设计和选择遗传操作，包括种群大小，选择、交叉、变异方法，以及确定交叉概率pc和变异概率pm等遗传参数。
[0069] 步骤6.2.1：执行排序选择策略和精英保留策略：
[0070] 执行排序选择策略的具体过程为：
[0071] （a）根据适应值的大小，降序排列种群中的所有个体；
[0072] （b）设计概率分配表，根据适应值大小，升序分配每个个体的概率值；
[0073] （c）每个个体被遗传到下一代的概率由步骤（b）中分配的概率值决定，再基于这些概率值，用轮盘赌选择法选择被淘汰和被复制的染色体；经过一轮排序选择策略后，会得到一个新的种群，然后在这个新的种群基础上再执行精英保留策略，具体过程为：
[0074] （a）根据适应度函数值的大小从经过排序选择策略后得到的新种群即当前种群中获取最佳个体和最差个体；
[0075] （b）如果当前种群的最佳个体的适应度高于此前获得的出现的最佳个体的适应度，则用当前群体的最佳个体替换此前出现的最佳个体；
[0076] （c）保持迄今出现的最佳个体状态不变，将其完整的遗传到下一代种群中。
[0077] 步骤6.2.2：交叉操作和变异操作：
[0078] 采用自适应的交叉概率pc和变异概率pm，根据群体平均适应值及当前群体最优个体适应值来自动调整交叉概率pc和变异概率pm；fmax表示某一代种群中最优个体的适应度，Favg表示该代群体的平均适应度，最优个体的适应度与该代群体的平均适应度的差值Δ＝fmax-Favg，则当Δ越小，表示种群个体之间的适应度差别越小，说明种群此时达到局部最优的可能性较大，过早收敛的可能性也越大；当Δ越大，表示个体之间的适应度差别越大，交叉概率pc和变异概率pm由Δ来决定，pc和pm的计算公式为：
[0079] pc＝k1/Δ （3）
[0080] pm＝k2/Δ （4）
[0081] 其中，k1和k2分别为交叉概率调整系数和变异概率调整系数。
[0082] 步骤6.3：随机初始化生成种群P。
[0083] 步骤6.4：计算种群P中个体位串解码后的适应度值。
[0084] 步骤6.5：按照遗传策略，将步骤6.2中设计的各遗传操作作用于种群，经过选择、交叉和变异后，形成了新一代种群。
[0085] 步骤6.6：带着新产生的染色体即测试数据返回步骤五，计算其适应度值，判断其性能是否满足指标，或者是否已完成预定迭代次数，若不满足并且没有完成迭代次数，则进入步骤6.1，遗传算法从编码操作开始，对新产生的种群重新进行选择复制、交叉和变异，不断迭代；若满足指标或已完成迭代次数则直接进入步骤七。
[0086] 步骤七：运行结束，得到合适的测试数据。
[0087] 本发明具有的优点在于：
[0088] 1、本发明提出一种基于遗传算法的MC/DC测试数据自动生成方法，针对遗传算法中传统适应度函数仅依靠控制流图中节点间的控制依赖关系，没有考虑被测程序内部的数据依赖关系的缺陷，提出使用链接法思想收集直接或者通过数据依赖间接影响问题节点遍历的控制节点，并将其与表征控制依赖关系见长的传统适应度函数相结合，构造一个新的适应度函数，以此来克服传统的适应度函数因忽略程序内部的数据依赖关系而造成的引导信息缺乏、搜索退化的问题。
[0089] 2、本发明提出一种基于遗传算法的MC/DC测试数据自动生成方法，实现了基于遗传算法的满足MC/DC准则的测试数据自动生成方法，对逻辑关系复杂且安全性要求较高的软件系统进行测试时具有很大的实用价值。
附图说明
[0090] 图1：本发明提出的基于遗传算法的MC/DC测试数据自动生成方法的流程图；
[0091] 图2：本发明中抽象语法树的生成过程流程图；
[0092] 图3：本发明中抽象分析树的生成过程流程图；
[0093] 图4：本发明中MC/DC测试用例预期结果集生成流程图；
[0094] 图5：本发明中代码插桩流程图；
[0095] 图6：本发明中建立控制依赖关系适应度函数所应用的某一程序片段；
[0096] 图7：本发明中遗传算法基本流程图。
具体实施方式
[0097] 下面将结合附图对本发明进行详细说明。
[0098] 本发明提出一种基于遗传算法的MC/DC测试数据自动生成方法，该包括抽象语法树的生成、抽象分析树的生成、MC/DC测试用例预期结果集的生成、代码插桩、适应度函数的构造、遗传算法设计等关键内容，具体流程如图1所示，具体包括以下几个步骤：
[0099] 步骤一：对被测程序进行静态分析，产生控制流图、数据流图、抽象语法树和抽象分析树等信息；被测程序是指将要执行测试的软件代码。
[0100] 借助解析工具（如测试工具Testbed）对被测程序进行词法分析、语法分析和语义分析，生成抽象语法树。抽象语法树是编译程序在经过语法分析以后得到的源程序的另外一种表示。每一个语法规则对应一个相应的处理函数，并作为抽象语法树的一个节点挂在抽象语法树上，提供对外的接口，它能够为下一步的代码插桩工作做准备。
[0101] 抽象语法树的生成过程如图2所示,首先对被测程序代码进行词法分析和语法分析。词法分析提供了抽象语法树所需要的符号结点，如常量和名字；语法分析则提供了含有代表相应语法结构的中间结点的抽象语法树；然后对被测程序代码进行语义分析，对名字、符号等进行的处理，将语法树转变为一种包括表示类型信息和符号表的标准形式，并将它们连接成树形结构，最终得到抽象语法树。在代码解析过程中，借助于工具Flex和Bison完成被测程序代码的抽象语法树的建立过程。
[0102] 通过访问已建立的抽象语法树，收集判定语句子树，同时，用大写字母表示关系表达式，新生成的子树被称为抽象分析树。每一个判定都有一个表示其逻辑结构的抽象分析树。解析工具在生成抽象分析树后自动生成控制流图和数据流图。
[0103] 被测程序片段为“if（x>y&&x>z||x>y+z）”；图2为被测程序片段生成的抽象语法树；图3表示从抽象语法树中提取出来的抽象分析树，其中，AND和OR为条件节点，A、B、C称为抽象分析树的叶子。
[0104] 步骤二：生成MC/DC测试用例预期结果集；
[0105] 抽象分析树构成了生成MC/DC测试用例预期结果集的输入。抽象分析树中的每一个节点都会被分配一个布尔值和一个布尔变量评价，用布尔变量评价来识别是否已经计算过该节点的布尔值。以被测程序片段“if（x>y&&x>z||x>y+z）”为范例，介绍MC/DC测试用例预期结果集的生成过程，如图4。具体步骤如下：
[0106] 步骤2.1：从抽象分析树中提出条件节点，这些条件节点构成了抽象分析树的叶子。每一个叶子就是一个变量，用N表示提取的叶子变量的个数；如图5，程序片段if（x>y&&x>z||x>y+z）叶子变量为3，即N=3。
[0107] 步骤2.2：构建真值表，对N个叶子变量，有2N种排列组合；如图5，被测程序片段“if（x>y&&x>z||x>y+z）”的真值表有8种组合方式。
[0108] 步骤2.3：用数字0和1填充真值表；
[0109] 步骤2.4：针对真值表中的每一行：
[0110] 步骤2.4.1：将真值表当前行中的布尔值对应分配给抽象分析树的每一个叶子变量；如图5中，真值表中第四行A=0，B=1、C=1，将其分别分配给抽象分析树的叶子变量。
[0111] 步骤2.4.2：自底向上评价各个条件节点的布尔值，直到抽象分析树的顶端。最终所得的抽象分析树的顶端的条件节点的布尔值就是这个判定语句的输出结果值；如图5，真值表中第五行A=0，B=1、C=1，则A&&B为真，A&&B||C为真，因此，该行判定的最终输出为真。
[0112] （3）用输出结果值填充真值表的输出列。
[0113] 通过以上步骤，完成某一给定判定语句（被测程序）的真值表的建立。然后开始提取测试用例。考虑到MC/DC的特点，针对每一个叶子变量，需要寻找能体现叶子变量独立影响判定结果的两行。
[0114] 步骤2.5：针对每一个叶子变量，寻找其测试用例，并添加到每个叶子变量的MC/DC测试用例集中：
[0115] 步骤2.5.1：为每一个叶子变量建立一对空的MC/DC测试用例集；
[0116] 步骤2.5.2：在真值表中，寻找其他叶子变量值固定，只有目标叶子变量改变的两个行，如图5，当目标叶子变量为A时，取叶子变量B和C变量值固定的两行，可取第三行和第七行，其中叶子变量B和C固定，只有目标叶子变量A改变；
[0117] 步骤2.5.3：比较步骤2.5.2中的两行的输出结果值（由各自行的条件节点的输出结果值组成），如果两行的输出结果值不同，则这两行就是目标叶子变量的一对测试用例，并且该测试用例是有效的，因为它们显示了目标叶子变量的影响作用，将这两行以成对的形式添加到步骤（1）中建立的MC/DC测试用例集中。
[0118] 如图4，目标变量为A时，第三行为（010），第七行为（110），由真值表可知，第三行的输出为0，第七行的输出为1，比较这两行的输出值，不相同，则（010）和（110）就是变量A的一对测试用例，并且该测试用例是有效的，已成对的形式，添加到叶子变量A的测试用例集中。其他叶子变量作为目标叶子变量，寻找其测试用例的方法与上述的叶子变量A作为目标叶子变量的寻找方法相同，并添加到每个叶子变量的MC/DC测试用例集中。
[0119] 步骤2.6：将每一个叶子变量的MC/DC测试用例集合并，得到测试用例集，并最小化测试用例集。该测试用例集就是使用遗传算法搜索所要实现的目标用例集。
[0120] 如图4，叶子变量A、B、C的测试用例集分别为（010，110），（100，110），（000，001，010，011，100，101），最小化该测试用例集，得到（010，100，110，101），这组测试用例集满足每一个叶子变量的MC/DC测试用例集覆盖要求。
[0121] 步骤三：对被测程序进行代码插桩；
[0122] 程序插桩是测试数据自动生成过程的步骤之一。在测试过程中，测试结果数据的获取和记录都是通过程序插桩完成的。主要过程是在保持被测程序原有逻辑完整性的基础上插入检查语句，当被测程序运行时，通过检查语句的执行采集程序的运行特征数据。分析这些特征数据，可以获得程序的逻辑覆盖等动态信息，并由此完成个体适应值的计算。其具体过程如图5，抽象语法树（AST）生成后，首先遍历抽象语法树（AST）找到插桩的位置，判断是否是插桩点，如果不是插桩点，返回继续遍历抽象语法树寻找找到插桩位置；如果是插桩点，则植入检查语句（探针），然后直接在抽象语法树上以子树的形式植入代码的语法树片段，判断插桩是否完成，如已完成，则被测程序编译运行；如未完成，返回继续遍历抽象语法树（AST）找到插桩的位置，直至完成插桩。
[0123] 步骤四：构造适应度函数；
[0124] 适应度函数是遗传算法与实际问题的唯一接口，是种群中个体优劣的一种量化反映，它的构造直接影响问题求解的效率。传统的适应度函数f（x）由两个部分组成：
[0125] f（x）＝approachlevel+branchdistance
[0126] 第一部分approachlevel体现的是控制依赖关系，通常被称为接近水平。第二部分branchdistance被称为分支距离，它克服了只使用接近水平进行适应评价的局限性，分支距离衡量了在当前输入测试数据的基础上距离满足目标或是满足偏离分支的逼近程度。
[0127] 在MC/DC测试数据的生成这一实际问题上，本发明的目标是最终找到满足指定目标的MC/DC的测试数据。本发明充分利用链接法在表征测试数据依赖关系方面的优势，使用链接法思想收集直接或者通过测试数据依赖间接影响问题条件节点遍历的控制节点，并将其与表征控制依赖关系见长的传统适应度函数相结合，构造新的适应度函数，以此来克服传统的适应度函数因忽略程序内部的数据依赖关系而造成的引导信息缺乏、搜索退化的问题。
[0128] 具体来说，构造适应度函数从建立控制依赖关系适应度函数、数据依赖关系适应度和分支适应度三点因素对适应度函数三个方面进行设计。
[0129] 步骤4.1：建立控制依赖关系适应度函数
[0130] 步骤4.1.1：通过被测程序的控制流图，获得每一个判定的控制依赖关系集合；控制依赖用来描述一个目标节点y的执行关于其前面分支节点输出的依赖性，当每一条从目标节点y到出口节点e的路径都包含节点z时，称节点z被目标节点y后置控制；设x为一个任意节点，两个节点（y，x）之间可以构成一个分支路径，当每一条从目标节点y到出口节点e的通过分支（y，x）的路径都包括节点z时，称节点z后置控制一个分支（y，x）；当节点z后置控制y的一个分支，并且z不后置控制y，则称节点z控制依赖于目标节点y。控制依赖关系是从结构关系角度衡量当前输入测试数据距离抵达目标的逼近程度，它是通过控制流图中目标与执行偏离条件节点间的关键节点计算得到。
[0131] 如某被测程序片段的控制流图如图6所示。从图中可以看出，第16行的判定依赖于第12行的判定取真和第13行的判定取假，由此认为16行的目标判定依赖于经过12、13行的控制流，这些节点被称为临界分支，因为他们决定控制流流向或者远离目标。因此，第16行判定的控制依赖关系集包含第12、13行的判定，也就是说，为达到目标节点，必须依次执行这些分支节点，并且这些节点的输出必须是特定的。可以得到控制依赖关系集ControlDep(16)＝{12,-13}，正数表示需要执行真分支，负数表示需要执行假分支。
[0132] 步骤4.1.2：建立控制依赖关系适应度函数。
[0133] 建立起控制依赖关系集合后，搜索判断哪一个测试用例执行了最多的控制节点数目，例如图6中，一个在13行偏离的测试数据比一个在12行偏离的测试数据更接近于目标。这时就需要一个评价函数用来判断哪一个测试数据能使执行流更接近于目标，这样就建立控制依赖关系适应度函数。
[0134] 控制依赖关系适应度函数包含了控制依赖关系集合中各分支节点的目标函数。建立控制依赖关系适应度函数如下式所示。
[0135] ControlDepFittestdata＝dependentdecisions-executeddecisions （1）[0136] 其中，dependentdecisions为目标的控制依赖关系集合中的控制节点数；executeddecisions表示以当前测试数据为输入；ControlDepFittestdata表示控制依赖关系适应度函数。
[0137] 如果控制依赖关系适应度函数值为0，则说明测试数据能够到达目标判定；如果控制依赖关系适应度函数值大于0，就说明测试数据在某处偏离了目标节点，可以通过控制依赖关系适应度函数的值，精确地得到是在目标判定前的哪一个控制节点偏离出去的，称该点为偏离节点divergednode。以图6为例，某输入数据使执行流在12行偏离，则有控制依赖关系适应度函数值为2–0=2；但如果在12行执行真分支，而在13行偏离，那么控制依赖关系适应度函数值就为2–1=1。这样，根据测试数据各自相对于目标判定的接近水平，就能够对其进行区分，并且将搜索引导向最为接近的测试数据。
[0138] 步骤4.2：建立数据依赖关系适应度函数
[0139] 在计算依赖关系上，本发明的重点在于通过插入控制依赖关系和数据依赖关系来改进由接近水平适应度向搜索提供的引导。这种对接近水平的扩展，包含了数据依赖关系，将搜索向更有希望的搜索区域的搜索引导。本发明旨在克服谓词中使用flag变量或者代码谓词间有强烈的数据依赖关系时存在的引导缺乏和平面搜索的问题。
[0140] 获取数据依赖关系适应度函数方法步骤如下：
[0141] 定义pn为问题节点，S为用来储存一个给定节点的依赖关系的集合，以pn和S作为获取数据依赖关系适应度函数方法的输入。DepSets用来储存当前搜集到的存在依赖关系的节点集合，PV用来存储问题节点使用的变量。S和DepSets被初始化为空集。获取一个节点的依赖关系适应度函数的方法如下：
[0142] 步骤4.2.1：获取问题节点pn的控制依赖关系集合ControlDep（pn）赋给S，并将pn使用的变量UsedVariables（pn）加到PV中；
[0143] 步骤4.2.2：对于PV中的每一个变量pv，获取pv的最后定义集合lastDefs；
[0144] （a）对于lastDefs中每一个最后定义ld，获取ld的控制依赖关系集合ControlDep（ld），并将其与S合并，得到扩展的S，然后将ld使用的变量UsedVariables（ld）添加到一个新建的PVnew中；
[0145] （b）对于ControlDep（ld）中的每一个控制节点cd，获取它使用的变量UsedVariables（ld），并添加到步骤（a）中建立的PVnew集合中。
[0146] 步骤4.2.3：对于PV中的每一个变量pv，迭代获取PV依赖关系集S(ld)。首先获得PV中的第一个变量，获取其依赖关系集S(ld)，返回步骤4.2.2，然后获取PV中的下一个变量，直至完成PV中所有的变量，结束迭代，并将S(ld)添加到DepSets中。
[0147] 步骤4.2.4：建立一个用于定义适应度函数的依赖关系集合：
[0148] 定义DepFit为适应度函数依赖关系集合，对于DepSets中的每一个子集si：
[0149] （a）添加si到DepFit中；
[0150] （b）判断DepSets中每一个非si的子集sj，与si是否存在then、else的分支冲突，如果不存在则合并两个子集si、sj，得到新的子集Si,j，并将Si,j添加到DepFit中；如果存在then、else的分支冲突则不能合并，将si、sj都添加到DepFit中。
[0151] 步骤4.2.5：建立数据依赖关系适应度函数
[0152] 建立起数据依赖关系集合后，用计算控制依赖关系适应度函数的方法得到数据依赖关系适应度函数，其计算方法与计算控制依赖关系适应度函数的方法相同。
[0153] 步骤4.3：计算分支距离
[0154] 当测试数据抵达目标时，用分支距离来度量测试数据是否满足测试用例，即通过计算分支距离度量测试数据距离期望测试用例的逼近程度。如果测试数据到达目标判定，但是不满足任一个MC/DC测试用例，那么每一个测试数据的接近水平都为0，但分支距离不为0；如果测试抵达目标并实现一个测试用例，那么它的分支距离和接近水平都为0；计算出来的分支距离的大小用来评价哪一个测试数据更接近于满足期望的分支测试用例。
[0155] 一个判定的分支距离是基于这个判定的结构来计算的：
[0156] （1）若判定的结构中含有a==b表达式，当a==b为真时，分支距离的计算公式为abs(a-b)；当a==b为假时，分支距离的计算公式为a==b?k:0；
[0157] （2）若判定的结构中含有a≠b表达式，当a≠b为真时，分支距离的计算公式为a!=b?k:0；当a≠b为假时，分支距离的计算公式为a!=b?abs(a-b):0；
[0158] （3）若判定的结构中含有a
[0159] （4）若判定的结构中含有a<=b表达式，当a<=b为真时，分支距离的计算公式为a<=b?0:a-b；当a<=b为假时，分支距离的计算公式为a<=b?a–b+k:0；
[0160] （5）若判定的结构中含有a>b表达式，当a>b为真时，分支距离的计算公式为a>b?0:a-b；当a>b为假时，分支距离的计算公式为a>b?a–b+k:0；
[0161] （6）若判定的结构中含有a>=b表达式，当a>=b为真时，分支距离的计算公式为a>=b?0:a-b；当a>=b为假时，分支距离的计算公式为a>=b?a–b+k:0；
[0162] （7）若判定的结构中含有a||b表达式，当a||b为真时，分支距离的计算公式为min[fit(a),fit(b)]；当a||b为假时，分支距离的计算公式为fit(a)+fit(b)；
[0163] （8）若判定的结构中含有a&&b表达式，当a&&b为真时，分支距离的计算公式为fit(a)+fit(b)；当a&&b为假时，分支距离的计算公式为max[fit(a),fit(b)]；
[0164] 在尝试达到测试用例时，需要比较接近于完成测试用例的测试数据的逼近程度，而不是测试数据本身，所以分支距离经常是一个正值。在尝试达到测试用例时，比较接近于完成测试用例的测试数据的逼近程度，而不是测试数据本身。因此，一个负的适应的函数值不会给搜索增加任何有价值的信息，所以返回一个函数值的绝对值。总的分支距离为判定中每一个条件的分支距离的累加。
[0165] 步骤五：在有效的MC/DC测试用例、适应度函数公式和执行插桩代码的基础上，随机产生测试数据，并在这些测试数据上执行插桩后的被测程序，获得适应度值，同时检验是否满足预期执行的目标路径（即指测试数据是否到达目标）；如果是，则进入步骤七；否则进入步骤六；
[0166] 计算接近水平适应度函数ApproachLevelFitness，如果ApproachLevelFitness为0，则测试数据到达目标；然后在目标判定处，计算分支距离BranchFitness。如果ApproachLevelFitness和BranchFitness都为0，则测试数据达到MC/DC测试目标。否则，测试数据的适应度函数值等于ApproachLevelFitness+normalized(BranchFitness)，normalized(BranchFitness)表示对分支距离BranchFitness的标准化，它的值在0到1之间。具体的计算过程包括以下几个步骤：
[0167] 步骤5.1：按照步骤二的方法生成MC/DC测试用例预期结果集；
[0168] 步骤5.2：按照步骤4.1和步骤4.2的方法获得依赖关系集合，包括控制依赖集和数据依赖集；
[0169] 步骤5.3：针对每一个目标判定，随机生成2个测试数据Ta和Tb；
[0170] 步骤5.4：按照步骤4.1中的计算方法，根据依赖关系集合，分别计算2个测试数据的控制依赖适应度函数和数据依赖适应度函数；
[0171] 步骤5.5：按照步骤4.3中的计算方法，分别计算2个测试数据的分支距离；
[0172] 步骤5.6：进行分支距离的标准化BranchFitness(Ta)normalised，计算公式为：
[0173]
[0174] BranchFitness(Ta)表示测试数据Ta的分支距离，BranchFitness(Tb)表示测试数据Tb的分支距离；
[0175] 步骤5.7：总适应度函数值Fitness(T)为：
[0176] Fitness(T)＝ApproachLevelFitness(T)+BranchFitness(T)normalized[0177] 其中，ApproachLevelFitness(T)表示测试数据T的接近水平适应度函数；
[0178] BranchFitness(T)normalized表示测试数据T的分支距离的标准化值。
[0179] 步骤5.8：根据总适应度函数值比较这两个测试数据哪个更接近于达到判定目标。
[0180] 步骤5.9：
[0181] 若ApproachLevelFitness和BranchFitness都为0，则测试数据达到MC/DC测试目标，进入步骤7，否则，进入步骤6；
[0182] 这个步骤之后是否也应该对应有一个步骤5.9判断是否进入步骤六或七的步骤？这样才能与上面的表述一致！
[0183] 下面仍以图6中的被测程序片段为例介绍适应度函数值的获取。假设目标是第16行。前期活动：
[0184] （1）获得的依赖关系集合为{ ，{2，12，-13}，{2，3，4，8，12，-13},{2，3，-4，8，12，-13}}；
[0185] （2）从MC/DC测试用例生成模块中提取第16行目标判定的MC/DC测试用例：{(010),(110),(100),(011。例如，我们计划达到测试用例(010)。
[0186] 计算：
[0187] 假设现在运行时，测试数据生成器为参数x、y、z输出两组测试数据：(12，-2，3)和(1，2，0)。为鉴别是否满足或者接近满足测试用例(010)，分别评估每一个测试数据的适应度函数。
[0188] （1）T1＝(12，-2，3)
[0189] 目标是穿过4行判定的假分支，因此有：
[0190] ApproachLevelFitness(T1，16)＝Count({2，3，-4，8，12，-13}-{2，3，4})[0191] ＝Count({-4，8，12，-13})＝4
[0192] BranchFitness(T1，-4)＝(Fit(x＞0)+Fit(x＞0)+Fit(x＞0))T1＝0+2+0＝2[0193] （2）T2＝(1，2，0)
[0194] 目标是穿过第13行判定的假分支，给出假分支公式。我们选择k＝0.1。
[0195] ApproachLevelFitness(T2，16) ＝ Count({2，3，-4，8，12，-13}-{2，3，-4，8，12，13})
[0196] ＝Count({13}=)
[0197] BranchFitness(T2，-13)＝(Fit(z＝＝0))T2＝k＝0.1
[0198] （3）分支适应的的标准化：
[0199]
[0200]
[0201] （4）测试数据的比较：
[0202] Fitness(T,d)＝ApproachLevelFitness(T,d)+BranchFitness(T)normalized[0203] Fitness(T1，16)＝4+0.9＝4.9
[0204] Fitness(T2，16)＝1+0.045＝1.045
[0205] 相比之下得到T2更接近于达到判定目标。
[0206] 步骤六：根据得到的适应度值，使用遗传算法的选择、交叉、变异等遗传操作，生成新的测试数据，并返回步骤五，计算新生成的测试数据的适应度值。
[0207] 遗传算法中生物进化的术语同软件测试用例生成过程的术语对应关系为：染色体：遗传算法中的每一个测试数据，带有特征的染色体也称个体；种群：随机生成的测试数据的集合；进化：使用遗传算法从旧的测试数据迭代生成新测试数据过程；编码：将染色体按一定的规则编码为计算机能够操作的字符的过程。
[0208] 遗传算法以编码空间代替问题的参数空间，以适应度函数为评价依据，以编码群体为进化基础，以对群体中个体位串的遗传操作实现选择和遗传机制，建立起一个迭代过程，具体包括以下几个步骤，如图7所示。
[0209] 步骤6.1：选择编码策略，把参数集合X和域转换为位串结构空间S；
[0210] 在测试数据自动生成问题中，遗传算法染色体的每个基因，可能属于不同的测试数据类型。因此，在本发明中采用整型和实型混合的方式编码染色体，问题的参数直接转换为染色体上的基因，参数的个数转换为染色体长度，各参数的取值区间映射为各基因的取值范围。这也就表明，染色体和问题的解具有相同的空间。具体过程如下：
[0211] 设求解问题包含n个输入变量X1,X2,...,Xn，首先，用等价类划分和边界值分析方法处理参数的值域，其中Yi(1≤i≤n)表示参数Xi(1≤i≤n)可以取值的有限离散点的集合，|Yi|表示集合的大小。建立问题解空间和染色体空间的映射关系，染色体表示为：
[0212] X＝(X1,X2,...,Xn)→C＝(C1,C2,...,Cn) （2）
[0213] 其中，C为染色体空间解空间中的解，X为问题空间的解。
[0214] 步骤6.2：设计和选择遗传操作，包括种群大小，选择、交叉、变异方法，以及确定交叉概率pc和变异概率pm等遗传参数；
[0215] 步骤6.2.1：执行排序选择策略和精英保留策略：
[0216] 精英保留策略可以保证交叉、变异操作不会破坏迄今为止所得到的最好个体，有效提高收敛速度，它是保证遗传算法收敛性的有力前提。另一方面，虽然其计算结果较好，但一般很难得到最优解。本发明采用排序选择和精英保留策略结合的方式对种群进行复制，在采取精英保留策略前，先采用排序选择策略，用于选择合适的个体进行交叉、变异操作。
[0217] 其中执行排序选择策略的具体过程为：根据适应度函数值的大小，按升序或降序排列种群中的所有个体，则个体被选中的概率在升序或降序排序的基础上分配，具体为：
[0218] （a）根据适应值的大小，降序或升序排列种群中的所有个体；
[0219] （b）设计概率分配表，根据适应值大小，升序分配每个个体的概率值，即在表中，每个个体的适应度值是由大至小，概率值是由小至大的；
[0220] （c）每个个体被遗传到下一代的概率由步骤（b）中分配的概率值决定，再基于这些概率值，用轮盘赌选择法选择被淘汰和被复制的染色体。
[0221] 经过一轮排序选择策略后，会得到一个新的种群，然后在这个新的种群基础上再执行精英保留策略。
[0222] 执行精英保留策略的具体过程为：
[0223] （a）根据适应度函数值的大小从经过排序选择策略后得到的新种群（称为“当前种群”）中获取最佳个体和最差个体；
[0224] （b）如果当前种群的最佳个体的适应度高于此前获得的出现的最佳个体的适应度，则用当前群体的最佳个体替换此前出现的最佳个体；
[0225] （c）保持迄今出现的最佳个体状态不变，将其完整的遗传到下一代种群中。
[0226] 经过这两种策略对种群进行复制，形成最终的种群。
[0227] 步骤6.2.2：交叉操作和变异操作
[0228] 基于Srinivas思想，采用自适应的交叉概率pc和变异概率pm，根据群体平均适应值及当前群体最优个体适应值来自动调整交叉概率pc和变异概率pm。
[0229] fmax表示某一代种群中最优个体的适应度，Favg表示该代群体的平均适应度，最优个体的适应度与该代群体的平均适应度的差值Δ＝fmax-Favg，则当Δ越小，表示种群个体之间的适应度差别越小，说明种群此时达到局部最优的可能性较大，过早收敛的可能性也越大；当Δ越大，表示个体之间的适应度差别越大。因此，交叉概率pc和变异概率pm可以由Δ来决定。为使得pc和pm在进化的过程中能够根据种群的实际情况调整其值，当种群趋于收敛时，提高pc和pm，增加交叉和变异的频率，破坏当前的稳定性，使得遗传算法具有更强的探测能力，克服过早收敛；反之，当种群个体发散时，降低交叉和变异频率，增加开发能力，使得个体趋于收敛。pc和pm的计算公式为：
[0230] pc＝k1/Δ （3）
[0231] pm＝k2/Δ （4）
[0232] 其中，k1和k2分别为交叉概率调整系数和变异概率调整系数。为避免k1和k2取值不当，设计了交叉和变异校正概率：当交叉概率pc大于交叉概率校正上值kc1时，将kc1的值赋予pc，当交叉概率pc小于交叉概率校正下值kc2时，将kc2的值赋予pc，当变异概率pm大于变异概率校正上值km1时，将km1的值赋予pm，当变异概率pm小于变异概率校正上值km2时，将km2的值赋予pm。
[0233] 步骤6.3.随机初始化生成种群P；
[0234] 步骤6.4.计算种群P中个体位串解码后的适应度值；
[0235] 步骤6.5.按照遗传策略，将步骤6.2中设计的各遗传操作作用于种群，经过选择、交叉和变异后，形成了新一代种群；
[0236] 步骤6.6.带着新产生的染色体（即测试数据）返回步骤五，计算其适应度值，判断其性能是否满足指标，或者是否已完成预定迭代次数，若不满足并且没有完成迭代次数，则进入步骤6.1，遗传算法从编码操作开始，对新产生的种群重新进行选择复制、交叉和变异，不断迭代；若满足指标或已完成迭代次数则直接进入步骤七。
[0237] 步骤七：运行结束，得到合适的测试数据。
