基于遗传算法的测试用例生成方法
图3-2是一个简单的赌轮的例子：
13% 35% 15% 0.67 37%
|---------|--------------------------|-----------|-*-------------------------|
个体1 个体2 个体3 个体4
图3-2 轮盘赌转法示意
图3-2中随机数为0.67落在了个体4的段内，本次选择了个体4。 （2）交叉策略
交叉运算是算法中产生新个体的主要手段，其模拟的是生物学中的杂交现象。交叉运算通过使两个体的局部交换而使双方的优点有可能结合产生更好的新个体。一般控制产生交叉运算的概率Pc 为0.5至0.8 。
在二进制编码中，根据交叉点的不同可以分为单点交叉、两点交叉、均匀交叉等。在本文中采用的是单点交叉的方法，即首先在亲代中随机选取一个交叉点（染色体的某个码位），然后将两个亲代在该点及之后的染色体部分进行交换。
（3）变异策略
变异运算模拟的是生物中的基因突变现象。通过变异操作可以增强算法中群体的多样性，防止未成熟收敛现象，同时也使算法具备了局部随机搜索能力，是实现全局优化性能的重要算子之一。通常，变异的控制概率较小，Pm 一般取值为0.001至0. 1。
在二进制编码方式中，变异运算即是将某些基因位上的基因值取反，即0变1或1变0。一般变异个体的选择及变异位置都是随机确定的。二进制编码中的变异方法有基本位变异、均匀变异、高斯变异和二元变异等。
本文采用的是基本位变异方法，即先随机选择某变异个体，再随机确定染色体的一个变异点将该码位置反。
3.3.4 参数控制
除了上面提到的选择、交叉、变异的概率外，在算法中还有一些参数主要如下：
1种群规模 ○
群体规模较大可以增加算法的多样性，提高GA搜索的质量，防止算法未成
21
基于遗传算法的测试用例生成方法
熟收敛。但是群体规模大使个体适应度的计算量大大增加，影响了算法的效率。因此应根据不同的实际情况确定不同的种群规模。Goldberg证明了在二进制编码的前提下，若个体长度为L，则种群规模的最优值为2L/2。
2染色体长度 ○
染色体长度即是编码长度，也即是表示个体的字符串的长度。染色体的长度由具体问题决定，当解的取值范围越大、求值精度越大则染色体长度越大，带来的计算时间也相应越长。
3算法终止条件 ○
一般来说，算法的终止条件为预先设定的最大进化代数，通常取100到500 。也可以为某一特定条件，事具体问题而定。
以上参数为通常情况下的取值，当然并非是固定不变的。在不同的算法中可以根据实际情况作相应的调整，只要能提高算法的运行效率就是可行的。
3.4 本章小结
本章是论文的核心章节，对算法应用于测试用例的生产方法进行了系统的介绍。首先介绍了算法生成测试用例的基本内含，然后提出了基本框架，最后对本文中算法实现的相关操作进行了描述，包括编码策略、适应度函数构造、选择策略、交叉策略、变异策略等。
22
基于遗传算法的测试用例生成方法
第四章 实验及结果分析
4.1 待测程序分析 4.1.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>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.2 程序流程分析
该程序流程图如图4-1所示，程序分为两部分，先将输入值由小到大排序，再将三角形进行分类。
23
基于遗传算法的测试用例生成方法
输入a,b,c a>b? Y 交换a,b Y Y 交换a,c N a>c? N b>c? 交换b,c N a+b>c? 1 Y ○N 2 ○不是三角形 a==b||b==c? 3 Y ○N 普通三角形 4 ○N 5 ○等腰三角形 a==c? Y ○6 等边三角形 图4-1 三角形分类程序流程图
结束 4.1.3 路径分析 通过对
根据3.3.2，对待测程序插桩：
String tri_type(int a,int b,int c)
F=1/(1+f1)+1/(1+f2)+1/(1+f3); //适应度函数
return F; }
4.3 参数设定及程序实现 4.3.1 参数设定
（1）编码
在本例子中，由于程序输入为三角形的三条边的长度，因此设定输入值类型为0~63的整数，采用二进制级联编码方法，每个参数编码长度为6位，精度为1，并将三个参数进行级联（如参数000000、111111、101010级联后为
24
基于遗传算法的测试用例生成方法
000000111111101010），级联后染色体长度为18位。
（2）操作参数
在本实验中，设定操作的参数如表4-2所示：
表4-2 操作参数设定 种群大小 100 选择策略及概率 轮盘赌转法，0.1 交叉策略及概率 单点交叉，0.8 变异策略及概率 基本位变异，0.1 最大进化代数 100 （3）算法终止条件
本实验中设定算法终止条件为满足以下两个条件之一：
1找到最优解，即适应度为100的解； ○
2达到最大进化代数，○当程序进化满100代后，不管有没找到最优解都将退
出。
4.3.2 部分程序实现
本文中的三角形分类程序是在Microsoft Visual Studio2005的环境下采用C++语言实现的。以下为该程序的主要算法模块：
（1）染色体定义模块，该模块完成了染色体的编码：
struct sides
{ int a; int b;
int c; //测试的三个数据
bitset<3*BIT> chromosome; //该组的染色体 int sufficiency; //该组数的适应度 bool isOp ; } //标记是否操作过
（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
//if(a==c) type=“等边三角形”; //else type=“等腰三角形”;
25