Page 77 - 《软件学报》2021年第9期

钱忠胜 等:面向关键字流图的相似程序间测试用例的重用 2701

序,并被设定为下一节研究相似程序间测试用例重用选择的实验对象.

3 基于遗传算法的相似程序间测试用例的重用
本节利用遗传算法完成测试用例的生成,实现测试用例的重用.遗传算法作为一种基于自然选择原理和自
然遗传机制的通用搜索算法 [25,26] ,通过进化过程获得的信息自行组织搜索,适应度大的个体具有较高的生存概
率,并获得更适应环境的基因结构.在进化的遗传操作中,适应度较高的个体以更大概率将更优秀的基因遗传给
下一代.
遗传算法具有良好的可扩展性,容易与其他算法相结合,也可以调节遗传操作和适应度函数等方式提升算
法的效率.本节在种群进化过程上引入适应度较高的个体来提高测试用例生成的效率.其基本思路(重用模型如
图 9 所示)如下.
1) 假设一个程序适应度较高的测试用例已经生成,将这些测试用例应用到其相似程序的测试中.实验采
用遗传算法来完成测试用例的重用;
2) 利用遗传算法测试待测程序时,将重用的测试用例引用到遗传操作的种群进化中,种群的其他个体通
过向这些测试用例学习,目的是加快种群进化速度,提高测试用例的生成效率.

程序相似性的判定

判断待测程序能否实现 关键字流图子图的构建 相似度的判定
测试用例的重用

相似程序间测试用例的重用 算 算
法 法
程序A 2 3 程序A
遗传算法
遗传算法
初始化种群
（生成种群P） 种群P
程序A的相似
进行适应度计算、 程序B适应度
个体选择、交叉、 新种群 较高的测试数
变异等遗传操作 据
进行适应度计算、个
新种群 体选择、交叉、变异
等遗传操作

Fig.9 Reuse model of test cases for similar programs
图 9 相似程序间测试用例重用模型
3.1 适应度函数
遗传算法具有种群初始化、个体评价、选择运算、交叉运算、变异运算、进化终止条件判断等步骤.遗传
算法的初始种群通常采用随机的方式生成,个体评价通过相应的适应度函数计算种群中各个个体的适应度值,
选择运算就是将适应度较高的个体进行交叉变异操作,产生的个体组成下一代种群.重复选择进化的过程,直至
终止条件满足,算法结束.
适应度函数是衡量种群个体优劣的标准 [27] ,根据优胜劣汰的生存法则,通过淘汰生存能力低的个体实现种
群的选择、进化.因此,适应度函数决定了种群的进化速度.合理的适应度函数能够全面提高种群个体的质量,有
利于快速进化至最优解.适应度函数的设置是算法操作重要的一环.