基于遗传算法的测试用例生成方法
（5）可操作性
测试用例中应写清测试的操作步骤，不同的操作步骤相对应的操作结果。
3.1.2 基于算法的测试用例生成的基本内涵
使用算法实现测试用例的自动生成可描述为[12]：应用算法来求解一组优化的测试用例。在每一步进化计算过程中，测试用例自动生成器使用当前群体（测试用例）驱动被测试程序的执行，每一个测试用例的执行路径被跟踪和记录，以最大化程序执行路径的覆盖为适应性目标函数进行计算，产生出下一代群体。在多代进化之后，得到最优种群或超过特定的循环限制条件而结束。
因为测试用例的自动生成是在一个数据域中寻找满足给定的测试标准的一组测试输入数据的过程，所以近年来出现了把测试用例的生成问题转化成路径搜索问题的思想。由于一般情况下，测试数据的产生是一个不可判定性问题，再加上被测程序的规模和复杂性，一般的搜索算法受到了极大的限制。算法在处理不确定搜索问题时有着非常明显的优势。
算法能针对程序路径生成大量有效测试用例，因此符合测试用例设计的全面性、正确性等原则。生成的测试用例符合上节中的测试用例设计标准，特别是有效性和经济性等，由此可见算法应用于测试用例生成是可行的。
3.2 基于算法的测试用例生成框架
本文基于算法的测试用例生成基本流程如下所示： （1）分析源程序代码，获得程序控制流程图；
（2）由程序控制流程图得到程序分支路径集合，选择目标路径； （3）根据各谓词条件给程序插桩并制定适应度函数；
（4）设定算法参数，包括群体大小、变异率等，随机产生初始测试数据集合；
（5）使用测试数据执行经过插装的源代码，获得适应度值，根据适应度值判断，若满足程序终止条件则输出结果并退出程序，若不满足条件则进入步骤（6）；
16
基于遗传算法的测试用例生成方法
（6）根据得到的适应度值，使用算法的选择、交叉、变异等操作，生成新的测试数据，并回到步骤（5），重复执行；
程序框架如图3-1所示，包含测试环境构造、算法和测试运行环境三部分。
图3-1 程序框架图
静态分析 路径选择 程序插桩 GA初始化 变异 交叉 选择 N 解码 评估 Y 结束 遗传算法 测试环境构造 测试运行环境 驱动模块 待测程序 桩模块
测试环境构造部分是整个系统的基础，它主要利用静态分析提供的基本信息并借助于各种插装技术来构造相应的测试运行环境。
算法部分是系统的核心，它主要按照第一部分生成的编码参数格式构造相应的染色体串，并生成初始种群，然后通过对该种群进行反复的GA运算（选择、交叉和变异）从而引导种群不断地向目标值进化直到最终找到解或达到限定的运行代数为止。
最后部分是测试运行环境。算法第二部分需要对种群中每一个个体的优劣进行评估，它主要是通过实时地调用并运行插装后的测试系统来返回适应度值，从而来指导算法的搜索。
17
基于遗传算法的测试用例生成方法
3.3 基于算法的测试用例生成算法实现 3.3.1 编码策略
使用算法求解问题时，必须将目标问题的实际表示与算法的染色体位串结构之间建立映射关系，这一过程即为编码。编码就是将目标问题的解用一种特定字符串来表示，从而将问题的解空间（有效的候选解，即表现型个体）与算法的码空间（基因型个体）相对应。编码过程是算法的基础，编码方法除了决定了个体的染色体排列形式之外，还决定了个体从GA空间的基因型变换到问题空间的表现型时的解码方法（即为编码方法的逆方法）。同时，编码方法也影响到交叉算子、变异算子等算子的运算方法。
由此可见，编码方法的好坏是影响算法性能及效率的重要因素。一个好的编码方法，有可能会使得交叉运算、变异运算等操作可以简单地实现和执行。相反，选择了不当的编码方法有可能会使得交叉运算、变异运算等操作难以实现，甚至可能会产生很多不属于可行解集合内的无效解。因此Goldberg提出了三条编码评估规范：
①完备性（Completeness）：问题空间中的所有点都能作为GA空间中的点(染色体)表现。
②健全性（Soundness）：GA空间中的染色体能对应所有问题空间中的候选解。
③非冗余性（Nonredundancy）：染色体和候选解一一对应。
常见的编码方法有二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法等，在应用中具体使用何种编码方法应根据问题的实际情况而定，这里我们使用二进制编码方法。
二进制编码方法是算法中使用最多的编码方法，不光是由于其编码解码操作简单，便于实现交叉、变异等操作，而且该编码方法符合最小字符集编码原则，能使染色体与候选解一一对应。
使用二进制编码方法进行编码时，先根据问题所要求的求解精度确定符号串的长度，假设某一参数的取值范围为[Xmin,Xmax]，可用长度为L的二进制编码符号
18
基于遗传算法的测试用例生成方法
来表示该参数，则能产生2L个不同的编码，设编码精度为δ，则： Xmin 表示为 0000...000=0 Xmax 表示为 1111...111=2L -1
δ=
Xmax?Xmin （3-1）
2L?1若某个体编码为X：aLaL-1aL-2...a2a1 ，则其解码公式为：
x= Xmin?(?ai?2i?1)?i?1LXmax?Xmin （3-2） L2?13.3.2 适应度函数及程序插桩
（1）适应度函数
在算法中，不需要用到搜索空间的知识，而使用适应度函数对染色体进行评价，一般来说，适应度高的染色体的评价较高，适应度低的染色体评价较低而可能被淘汰，因此，适应度函数直接决定了种群的进化方向，对算法的好坏具有很大影响。同时，适应度函数的复杂度是算法复杂度的主要组成部分，因此适应度函数要求尽可能简单。
适应度函数通常可以从目标函数转化而来。一般来说，要求适应度的取值越大越好。但在实际问题中，有的目标函数是求最大值（如利润问题），也有的目标函数是求最小值（如费用问题）。因此在很多场合需要将目标函数转换为最大值形式并且函数值为非负的适应度函数。
（2）程序插桩
在程序流程图中，每个分支都可以用一个判断表达式来表示，该判断表达式称为分支谓词，其作用是描述了程序遍历该分支的条件，如判断语句“if(a>b)...”中分支谓词为“a>b”。
分支谓词的一般形式为：E1 op E2，E1和E2是算数表达式，关系运算符
op???,??,?,??,??,!??。每个分支谓词都可以转换成等价形式为：F rel 0，其中F为分支函数，其构造方法如表3-1所示。
表3-1 分支函数的构造 分支谓词 E1>E2
分支函数 E2-E1 19 rel < 基于遗传算法的测试用例生成方法
E1>=E2 E1 fit(x)?111???..... （3-3） 1?f(x1)1?f(x2)1?f(x3)其中，f(xi)为各分支插桩后的分支函数值。 3.3.3 策略 （1）选择策略 选择运算也叫复制运算，模拟了生物界优胜劣汰的自然选择现象。通过选择将优胜的个体直接到下一代或通过配对交叉产生新一代个体再到下一代。选择运算的依据是个体的适应度，适应度高的个体被选择到下一代的概率就大，甚至可能被多次复制，而适应度低的个体则可能一次都没被选中而淘汰。选择的概率一般取Ps 为0.1至0.2 。 常用的选择运算的方法有轮盘赌转法、随机遍历抽样、锦标赛选择等，其中以轮盘赌转法最为常用。该算法将所有染色体的适应度总和看做一个轮子的圆周，而各染色体按其适应度占适应度总和的比例值大小占据一个扇区。每次进行选择时相当于轮盘的一次转动，转到哪个扇区则该扇区的染色体被选中。这样适应度越高的染色体被选中的概率就越大。若某染色体的适应度为f(xi)，则被选中的概率为： Ps?f(xi) （3-4） ?f(xi)20