1.一种基于聚类和多种群遗传算法的软件测试数据生成方法，其特征在于：该方法包括以下步骤：

S1.1：确定变异体杀死难度；

S1.2：确定变异体纸件的相似度；

S2：聚类变异体；

S3：构建测试数据生成数学模型；

S4：基于多种群遗传算法生成测试数据。

2.根据权利要求1所述的基于聚类和多种群遗传算法的软件测试数据生成方法，其特征在于：步骤S1.1中，确定变异体杀死难度的方法为：设变异体的集合，记为M＝{M1,M2,…,Mn}，n为变异体的个数；将变异体对应的变异分支插入G中，形成的新被测程序，记为G'；X运行G'，如果Mi对应的变异分支被覆盖，那么基于弱变异准则Mi被杀死；

为了反映X杀死变异体Mi情况，定义一个随机变量μi(X)，为了计算μi(X)，采用数理统计的方法；首先，需要得到一个测试数据集，为此，在程序G输入域内随机生成R个样本，记为X1,X2,...,XR；将Xk,k＝1,2,…，R执行程序，考察在弱变异测试准则下它是否能杀死Mi，然后计算μi(Xk)的值；因此，Mi的杀死的难度Dif(Mi)，可以表示为：

所有变异体杀死难度，记为Dif(M1),Dif(M2),...,Dif(Mn)，将这些变异体基于杀死难度进行降序排序，排序之后对应的变异体序列，记为S。

3.根据权利要求2所述的基于聚类和多种群遗传算法的软件测试数据生成方法，其特征在于：步骤S1.2中确定变异体纸件的相似度的方法为：假设变异体Mi,Mj,i,j＝1,2,...,n,i≠j是两个不同的变异体；定义两个随机变量μi(Xk)和μj(Xk)，它们分别反映Mi,Mj被杀死的可能性；那么μj(Xk)＝1的概率表示为：Mi和Mj之间的相似度，记为αi,j，由上式可以表示为:由上式可知，αi,j∈[0,1]。

4.根据权利要求3所述的基于聚类和多种群遗传算法的软件测试数据生成方法，其特征在于：步骤S2中聚类变异体的方法为：对于所有变异体M1,M2,…,Mn之间的相似度，建立变异体了相似矩阵Λ，记为：设第i簇为Ci，开始时 设阈值为T∈(0,1)；

聚类变异体步骤如下，

A1：变量i＝1，

A2：从S中选出首元素作为聚类中心 更新簇为A3：将 分别从S和M中删除；

A4：考察Λ中 对应的行， 与Mj,Mj∈M,j＝1,2,...,n, 的αi,j值，如果αi,j≥T，可以把Mj放入Ci，由此得到，以 为中心的簇 其中|ci|为簇中元素的个数， 为第i个簇中第j个元素；

A5：将 从S中删除；

A6：i＝i+1；

A7：判断S是否还有变异体，如果还有变异体，转A2：；

A8：输出簇C1,C2，…Cm，其中m为簇的个数。

5.根据权利要求4所述的基于聚类和多种群遗传算法的软件测试数据生成方法，其特征在于：步骤S3中构建测试数据生成数学模型的方法为：对于 设目标函数为 其中X为决策变量，即为程序的输入；当决X能杀死否则 因此，当且仅当 取最小值0时， 被X杀死；通过这种方式，杀死 的问题转化为求 最小值问题，表示为：然而，由上式可知 的取值只有0和1两种，为了提供更多的信息指导种群进化，需要增加一个约束函数；

在杀死 之前，测试数据须先覆盖变异语句s′；因此，基于分支覆盖的约束函数，表示为:

其中Appr(s′,X)是X对于s′的层接近度，dist(s',X)为分支距离；由上式可知，当且仅当时 时，X能覆盖s′；

根据X， 和 建立杀死 的优化模型为：

6.根据权利要求5所述的基于聚类和多种群遗传算法的软件测试数据生成方法，其特征在于：步骤S4基于多种群遗传算法生成测试数据的方法为：对于上面的数学模型，基于强变异准则，采用多种群遗传算法生成测试数据；为了引导种群进化，需要计算进化个体的适应值；考虑到数学模型中包括一个目标函数和一个约束函数，适应值函数 表示为：

其中， 是很小的正整数，它的作用确保括号里的值大于0；由上式可知，当且仅当时，X能杀死了

在多种群遗传算法中，一个种群包含m个子种群，分别处理m个簇C1,C2,...,Cm中变异体的 测试数据生成，所有的子种群并行进化，第i个子种群的进化个体为其中Size为子种群中进化个体个数；算法的输出为生成的测试数据集；终止条件有两个，一个是对于m个簇的变异体，期望的测试数据全部找到；另一个是种群进化到最大进化代数g；

生成测试数据的步骤：

B1:初始化m个子种群和算法中的各种参数；

B2:设变量count＝1；

B3:判定终止条件是否满足，如果满足，转B13；

B4:设变量i＝1；

B5: 首先执行Ci中的聚类中心变异体 判断 是否被杀死，如果是，标记 被杀死，并保存杀死它的测试数据，转B6；否则，转B9；

B6: 继续执行Ci中未被杀死的变异体；判断 是否杀死Ci中所有变异体，如果是，转B7；否则转12；

B7:停止第i个子种群的进化；m＝m‑1；保存生成的测试数据；转B13；

B8: 执行其它簇中未杀死的变异体，保存杀死的变异体和测试数据；转B9；

B9:计算所有个体的适应值

B10:实施选择、交叉和变异操作；生成新进化个体，不引起混淆，仍记为B11:count＝count+1；转B5；

B12:在每一个簇中，从未杀死的变异体中，选择难杀死的变异体为新的聚类中心；转B1；

B13:输出测试数据集。