基于Memetic的多路径测试在网络课程平台中的应用

王晴

（徐州开放大学电子信息工程学院，徐州221006）

基于Memetic的多路径测试在网络课程平台中的应用

王晴

（徐州开放大学电子信息工程学院，徐州221006）

Memetic Algorithm（MA）是一种以遗传算法为基础的智能优化算法。以某高职院校网络课程的平台为应用基础，将MA应用于该平台的多路径测试数据生成方面，对多路径代码的测试数据生成技术进行深入的研究。

0 引言

MA算法以遗传算法为基础，集合了遗传算法中的全局搜索法和局部启发式搜索算法，在单路径测试数据生成方面已获得了优异的研究成果。本文在现有的研究成果上，结合某高职校网络课程平台的开发，运用MA算法，对多路径代码的测试数据生成技术进行了深入的研究，有效地避免了该网络课程平台相关代码的重复迭代时间，从而实现了路径间的资源共享，提高了该平台测试数据生成的效率，为平台的代码优化提供了强有力的支持。

1 测试环境

测试平台：Apach操作系统，PHP语言及MySQL数据库。

2 测试数据生成步骤和方法

测试数据的生成步骤如图1所示。

（1）设置各项参数，包括种群规模n，值域，交叉因子和变异因子，邻域搜索时的增量δ，最大迭代次数以及终止条件等等。并选定m条不同的路径，组成目标路径集Road。然后根据设定的参数对种群进行初始化，如 D0={d1,d2,...,dn}。

（2）进化种群：利用之前设置的交叉因子和变异因子实现个体的变异和个体间的交叉操作，从而进化种群，得到新个体。针对新个体采用适当的方法求解初始种群个体的适应度函数值，将结果所对应的路径记录下来，并对每个个体分别进行局部搜索。

图1 测试数据的生成步骤

（3）所有种群按适应度函数值的大小进行排序，淘汰较差的个体，从而优化种群，最后恢复种群规模仍为n。

（4）迭代找寻最优解。在优化后的种群中找出最优解，判断是否满足终止条件，若是，则从Road中剔除其对应的路径，然后检查Road是否为空，若为空就终止迭代，否则就继续进化种群。

3 多路径测试数据生成的适应度值求解方法

在测试数据的生成过程中，适应度函数的计算起着重要的作用，因为适应度函数的作用是在种群迭代过程中来引领种群更新方向的。对于单路径中的测试数据生成，计算一次适应度函数值即可。但在多路径测试数据生成中，适应度函数值的计算要相对复杂些，最常用的针对多路径测试数据生成的适应度函数有均值法和min值法。

（1）均值法。均值法是最早提出的面向多路径测试数据生成的方法之一。这种思想最为直接，是指将种群中的每个个体代入每一条目标路径，并逐个计算出各个路径的适应度函数值，然后计算它们的平均值，以此作为该个体最终的适应度值。

如式（1）所示一个程序中的多条路径：

个体d={d1,d2,...,ds}是初始种群中的一个，经过计算，d对m条路径的适应度值为{vd1,vd2,...,vdm}，取平均值，得最终的适应度值 vˉd，公式如式（2）所示。

然后，根据给定的阈值T，以式（3）所示的公式进行迭代，从种群中逐步找到合适的个体，作为测试数据。

该函数能使适应度值更好地反映该个体对多条路径整体的适应度，确保计算出的适应度值在有效范围内。当找到的数据满足其中一条路径时，就从目标路径集中删除这条路径，继续用函数公式迭代，在这个过程中不改变种群结构，判断迭代结束的条件是：目标路径集为空。

均值法是根据基于路径相似性提出的。只有相似的路径，才会产生相似的数据，对相似的数据取均值才能有效地代表整体。但当路径数目过大，且路径间的差异较大时，均值法的优势就不明显了。

例如：阈值为10，个体d对某两条路径的适应度值若分别为vd1=9，vd2=69，代入适应度值迭代函数，得到Ffitness(d)=( )vd1+vd2/2=39；个体p对某两条路径的适应度值若为 vp1=16，vp2=48，得出Ffitness(p)=(vp1+vp2)/2=32，由于 Ffitness(p)＜Ffitness(d)，因此 d被淘汰，但实际上vd1已非常接近阈值10，若用d迭代，很快就可以成功。

（2）min值法。min值法是一种采用适应度值集合中的最小值来作为某个体的整体适应度值，并以该值参与进化过程的方法。用min值法计算个体适应度值的方法如下：

还是以式（1）中所示的路径集为例，依照min值法，个体d的适应度函数如式（4）所示：

其中，Ffitness(d)同样表示个体d的适应度值求解函数，且结果是与执行路径最相近的那条目标路径的适应度值。此处再用上述平均值法中的例子来看，个体d对某两条路径的适应度值分别为vd1=9，vd2=69，用min值 法 得 到Ffitness(d)=min(9,69)，结 果Ffitness(d)=9；个体p对某两条路径的适应度值若为vp1=16，vp2=48，用min值法得到Ffitness(p)=min(16,48)，结 果Ffitness(p)=16，因 为Ffitness(d)＜Ffitness(d)，所以虽然个体d离第二条路径比较远，但由于它距离第一条路径的适应度值十分小而被保留了下来，而p被淘汰。

所以，当路径数目过多，且之间存在较大差异时，使用min值法能够保证那些较接近某一条路径的种群个体被保留下来，而不会因为它距离另外一条路较远而被淘汰。因为在进化的过程中，始终保留的都是那个适应度值较小的个体，且这个个体至少接近某一个路径。

本文就采用min值法来计算适应度函数值，从而生成多路径测试数据。

4 局部搜索过程中的个体比较方法

在测试数据的生成过程中，局部搜索的方法和过程设计是核心问题。而在局部搜索过程中，值得一提的是值域范围内的种群个体与其搜索到的邻域的种群个体的比较，有两种不同的方法：全局法和单一路径法。

例如：前提条件如下：

R={r1,r2,...,rk}——路径集。其中k为路径的数目。

D0={d1,d2,...,di,...dn}——种群规模集合。

V={v1,v2,...,vn}——种群中个体的适应度值集合。

Ffitnessi=min(vi1,vi2,...,vik)——采用最小值法迭代适应度函数，其中k为路径的数目，i为种群中的某个个体。

全局法：假设种群中的某个个体di，其邻域的一个种群个体，采用min值法计算的适应度函数值为，若Ffitness′i＜Ffitnessi，则di=d′i（保留 d′i），否则 di不变。

优点：针对所有的路径进行局部搜索，可以更快地发现最优解。

缺点：该方法需要消耗大量的时间去计算d′i对所有路径的适应度值，由于要在众多适应度值中选取min值来做最终结果，所以它更容易使种群中的个体趋向于某一条路径，从整体上看，丧失一定的多样性。而在求解过程中，若该条路径得出最优解且被剔除后，种群中的个体却都趋近这条已被剔除的路径，这样的话对其他路径的适应度就会较差。

单一路径法：对于同样的di和d′i，计算 d′i在路径Ri上 的 适 应 度 函 数 值 Ffitness′iPi，若Ffitness′iPi＜

优点：由于只针对特定的路径，在单一的方向上进行局部搜索，所以计算适应度值所耗费的时间较小，在一定程度上能够保持种群的多样性。

缺点：收敛速度较慢。

5 测试数据及分析

（1）测试1：结合以上测试数据的生成步骤与方法，以该网络课程平台的学生成绩排序为例，来验证使用MA，在计算适应度函数值时，min值法比均值法更具优势。

测试参数设值如表1：

表1 参数设置

100次测试后的结果如表2和表3：

上表中的数据显示，路径的数目越多，路径的差异越大，则min值法在迭代速度和迭代时间上相较均值法的优势就越明显。因此，min值法更具优势。

（2）测试2：分别使用局部搜索的两种比较方法，验证使用MA在生成多路径测试数据时，与遗传算法相比的有效性。

测试参数设置同表1。

100次测试后的结果如表4所示：

表2 选取5条路径测试后的结果

表3 选取10条路径测试后的结果

表4 生成多路径测试数据的实验结果

从测试结果可以看出，MA在多路径的测试数据生成方面要优于传统的遗传算法。且对比MA算法中局部搜索的两种方式，全局法的平均迭代时间较长，但搜索较全面，且平均迭代次数较少；单一路径法虽不如全局法全面，且平均迭代次数较多，但迭代时间较短。所以，综合看来，单一路径法较全局法，在时间上更具有优势。

6 结语

本文结合某高职院校网络课程平台的开发，对MA在多路径测试数据生成方面进行了深入的研究。首先提出基于MA的多路径测试数据的生成步骤，然后对生成过程中的重点方面——适应度函数的设计方法和局部搜索的方法进行了详细的理论分析。最后通过对网络课程平台中学生成绩排序的算法进行了实验，实验数据验证了理论：

（1）当路径数目增加时，在迭代速度和迭代时间方面，min值法更具优势；

（2）在多路径的测试数据生成方面，MA算法要优于遗传算法

（3）局部搜索的两种方法相较，全局法较全面，且迭代次数较少，而单一路径法的迭代时间却较短。

但MA在局部搜索中所耗费的时间仍然较多，所以对于MA在多路径测试数据生成方面的性能提升有待进一步的研究。

[1]程烨.遗传算法在路径覆盖测试数据生成中的研究与应用[D].上海师范大学，2013.

[2]王蓁蓁.软件测试理论初步框架[J].计算机科学，2014，41（3）:12-16.

[3]姜元鹏.基于遗传算法和分支覆盖的测试数据生成方法[J].计算机工程与设计，2016（1）：112-117.

[4]Chencyinc Mao，Xinxin Yu.Test Data Generation for Software Testing Based on Quantum-Inspired Genetic Algorithm[J].International Tournai of Computational Intelligence and Applications,2013,12（1）:1-19.

[5]林耿，关健.自适应Memetic算法求解集合覆盖问题[J].浙江大学学报（理学版），2016（2）：168-174.

王晴（1980-），女，江苏徐州人，硕士研究生，讲师，研究方向为软件工程

2017-08-10

2017-10-07

Memetic Algorithm;Online Course;Multipath Testing

Application of Multipath Testing Based on Memetic in Online Course Platform

WANG Qing

(School of Electronic Information Engineering,The Open University of Xuzhou,Xuzhou 221006)

Memetic Algorithm（MA）is an intelligent optimization algorithm based on genetic algorithm.Takes an online course platform of higher voca⁃tional colleges as the application foundation,applies MA to the multipath test data generation on the platform，and deeply studies the test data generation technology of multipath code.

Memetic算法；网络课程；多路径测试

1007-1423（2017）29-0035-04

10.3969/j.issn.1007-1423.2017.29.009