欢迎来到利索能及~ 联系电话:18621327849
利索能及
我要发布
收藏
专利号: 2021100516706
申请人: 徐州工程学院
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-09-12
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

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:输出测试数据集。