分数布朗运动时间序列的基于递归图的网络分析.pdf

《分数布朗运动时间序列的基于递归图的网络分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第29卷第4期工程数学学报Vol.29No.42012年08月CHINESEJOURNALOFENGINEERINGMATHEMATICSAug.2012文章编号:1005-3085(2012)04-0486-07基于遗传蚁群算法的测试用例集约简¤华丽,王成勇,谷琼,程虹(襄樊学院数学与计算机科学学院，湖北襄阳441053)摘要:为提高软件测试效率，节省回归测试成本，本文提出了一种新的约简测试用例集的算法．该算法是遗传算法和蚁群算法两种算法的结合，首先利用遗传算法的快速随机全局搜索能力，生成蚁群算法的初始信息素，然后利用蚁群算法的正反馈性，快速得到约简测试用例集的

2、近似最优解．最后通过仿真实验验证了该算法的有效性．关键词:遗传算法；蚁群算法；测试用例集约减；测试运行代价分类号:AMS(2000)05C85中图分类号:TP312文献标识码:A1引引引言言言由于需求的变更使得软件系统的更新速度越来越快．每次变更之后，为确保修改的正确性必须对系统进行回归测试．因此，在原始测试用例集的基础上要补充新的测试用例来测试被修改了的模块．随着系统不断地更新，原始测试用例集中所包含的用例个数越来越多，导致回归测试的成本也急剧增加．因此，约简测试用例集问题成为软件测试领域中的一项关键课题．首先，在对原始测试用例集进行约简时，必须要满足跟原始用例

3、集相同的覆盖度．另外，为了尽可能减少回归测试的费用，在进行测试用例集约简时，不只是减少用例的个数，还要考虑每个测试用例的运行代价，并且每个测试用例的运行代价是不相等的．近年来，提出了很多算法用来解决测试用例集的约简问题[1]．如遗传算法、蚁群算法、贪心算法等．但这些方法都相对存在着一些不足，如遗传算法存在局部搜索能力差及收敛速度慢的现象；蚁群算法收敛速度快，但容易陷入局部最优解；而贪心算法存在求解结果精度低的问题．本文将遗传算法和蚁群算法相互融合，提出了一种基于遗传蚁群算法解决测试用例集约简问题，取得了不错的效果．实验分析结果表明，提出的约简算法在满足测试需求的条

4、件下，能够有效减小原始测试用例集的大小，并且大幅度降低测试运行代价，从而大大节省了软件测试成本．2测测测试试试用用用例例例集集集约约约简简简问问问题题题描描描述述述2.1问题定义对测试用例集约简问题定义为[2]：给出测试需求集为Rfr;r;¢¢¢;rg，测试用例集Tft;12m1t;¢¢¢;tg，且每个测试用例t都有相应的测试运行代价Cos(t)，找到一个T的子集T0满2nii足：T0的测试运行代价Cos(T0)为最小，并且T0能够用来充分测试给定的测试需求集R．这是一个NP-Complete问题．收稿日期:2011-12-20.作者简介:华丽(1975年6月生)

5、，女，硕士，讲师.研究方向：软件工程与软件测试.¤基金项目:教育部人文社会科学青年项目(10YJC790247)；湖北省教育厅中青年项目(Q20112604)；襄樊学院科研青年项目(2009YB025).第4期华丽，等：基于遗传蚁群算法的测试用例集约简487为进行测试用例集的约简，以下数据是实现的基础[3]：测试用例库：保存了软件系统在各个阶段使用过的所有测试用例．测试需求库：记录了每个测试用例与测试需求之间满足的关系．测试运行代价信息：记录了每个测试用例在测试时的运行代价．2.2问题模型设测试需求集R与原始测试用例集T之间的关系如表1所示．表1:测试需求集R与测

6、试用例集T满足的关系表TRt1t2t3t4t5t6r1100000r2011000r3010110r4011101r5010101如表1所示，测试需求集R=fr1;r2;r3;r4;r5g，测试用例集T=ft1;t2;t3;;t4;t5;t6g．其中值为“1”的表示对应的测试用例能覆盖对应的测试需求，值为“0”则表示对应的测试用例不能覆盖对应的测试需求．定义一个矩阵X，具有m行n列，用来表示m个测试需求与n个测试用例之间的关系，该矩阵所有元素值为0或1．定义一个一维向量Cos(Cos1;Cos2;¢¢¢;Cosn)，Cosi用来表示测试用例ti的测试运行代价．则该

7、问题的模型可以表示为：目标函数：Xnminf(S1;S2;¢¢¢;Sn)=CosiSi;i=18

8、盖；若矩阵