论文研究-基于改进粒子群算法的变异体选择优化.pdf

所需积分/C币:9 2019-07-22 18:10:19 978KB .PDF
51
收藏 收藏
举报

变异测试是常用的测试方法之一,变异测试分析的过程中计算开销会比较大,问题主要集中于测试过程中会产生大量的变异体。为了减少变异体的数量,提出用标准粒子群聚类算法进行选择优化,但标准粒子群算法在被测数据量增加到一定数量的时候,它的迭代次数就会增加、收敛速度就会下降。针对以上问题提出基于改进的粒子群算法对变异体进行选择优化。通过对变异体集合进行聚类分区,增强变异体集合的多态性,从而对粒子群算法进行改进优化。实验结果表明,在不影响测试充分度的前提下,使变异体的数量大幅度减少,同时与K-means算法以及标准粒子群算法相比之下,改进后的方法具有更好的优化效果。
·754 计算机应用研究 第34卷 择优化的目的。针对一个测试用例,可以杀死多个同类型的变冗余度,则结束;否则返回d)。 早体。但如果测试用例和变异体已经生成那么如何在一定数3.2实例分析 量的变异休中选择出较少的变异休达到较高的测试充分度就 本节以一个小程序来说明本方法实验的步骤和有效性。 是粒子群算法要解决的问题。 程序是两个整数相乘的运算结果。通过 Mujava工具生成了13 2.3.2粒子的定义 个变异体,用具 Junit广生4个测试用例。运行测试用例,获 粒子群算法中的粒子是指所求解的目标位置,在标准的粒 得被测程序变异体的存活状况,观察测试用例充分度,查看是 子群算法屮,粒子是根据速度的更新而更新的,速度又要通过 否需要添加新的测试用例集,最终得到测试用例集。然后需要 各个维度的权重来更新。 手工完成测试用例和变异体的存活关系表,如表2所示。 在变异休选择优化的问题里,粒子的位置在每一维的值只 出表2列出的关系可知,变异体m1~m13的杀死度为 有两种选择,1或0ε1代表被选中,反之0则被裁减。因为变 K[订=[3,3,0,0,2,2,0,0,2,1,1,3,3。通过式(1)测试用例 异体对測试用例杀死程度不同(一个变异体可以同时被多少 个测试用例杀死,称为杀死度),杀死度越高的应该选中的概 充分度公式计算出的结果是38.46%。粒子数是13,粒子的维 率就比较高,从而加快变异体诜择优化的速度 数是4。设置终止条件最大迭代次数为50次,或者达到期望 表1变异体和测试用例关系结构(部分) 的杀死度和期望的冗余度。相关的实验参数设定由表3所示。 表3实验参数设置 测试用例; 变异体m 粒子数量 粒了维数 位置范同 0,1 t3 1 杀死度 3,3,0,0,2,2,0.0,2,1.1,3,3 各维度取110.75,0.75,0,0,0.5,0.5,0,0.0.5,0.25,0.25,0.75,0.75 4 最大代 2.3.3自适应函数 期望杀死度 自适应函数在标准粒子群算法中是评价粒子位置优劣的 表2实例测试用例和变异体关系 在变异体诜择优化的问题中,如果要用一个合适的自适应函 变异体 数,必须需要考虑到变异体的杀死度和冗余度作为参考指标,通测试用例:, mI /m2 7, 4 ms 6 m7 mgmg m10 7 11 12 m13 过加权来得到一个自适应函数。所以在木算法中自适应函数用 的是二维函数,一维是变异体的杀死度,另一维则是冗余度。粒 110011001 子的优劣就表现于杀死度是否足够大,而冗余度是杏足够小 1100000000011 3实验结果与分析 聚类过程屮可以明显看到13个变异体被分为7关,分别 3.1实验步骤 是{m1,m2},m2,m4,m2,m3,m5,m},{mo},|mo},m1 m12,m13。通过自适应函数计算出每个粒子最好位置,经过 实验总体流程如图2所示。 实验输出最后的结果:{m1,m3,ms,m2,m3,m1,m1,m12},测试 源程序 产生变异体仁类算法充分度为375%。通过实验结果可以看出变异体山原来的13 个经过选择优化得到了8个。而测试充分度也是减少了不到 Jm<测用使([购简后变体」1%,基本没有影响。 测试充分度((约简后的测试用例(额的贪心算法 3.3实验结果与分析 本实验选择的三个被测程序分别是判断三角形形状程序 图2实验总体流程图 Triangle、循环队列操作程序 Cireu Queue和北卡莱罗纳州立大 a)初始化粒子,其中包含测试用例和变异体的关系,通过 学研究团队在 Eclipse平台开发的插件 Muclipse附带的测试程 此关系获取测试用例和变异体的杀死度 序R 实验用3.1节的实验步骤进行实验,所得到的 b)设置算法的相关参数,例如粒」的数量,各个维度的取 值、迭代次数等 实验结果如表4所示。 c)对粒子群中的粒子进行编码,初始化各个维度为1的概 表4基丁改进粒了群算法的聚类技术实验丁三个被测程序的结果 优化前优化后 率 被测程序变异体测试用测试变异体测试用测试 d)二维自适应函数计算评价每一个粒子,即粒子对应的 数日例数日充分度数日例数日充分度 变异体对应测试用例的杀死度和冗余度; Triangle 95.6% e)将计算出来的适应值与其经过的最好位置 pResl进行 对比,若当前位置优于经历的最好位置則将当前位置记为最好 Re 93.5% 93.1% 位置 pBest; 由表1给出本文提出的方法对三个被测程序进行变异体 f)将计算出来的自适应值和全局最佳位冒 gbest进行对选择优化得到的实验结果,通过10次重复操作综合每次结果 比,若当前位置较好,则替换当前 gBest 值取平均值得到实验结果数据。实验结果表明,基于改进后 g)根据公式更新粒子的速度和位置; 的粒子群算法的变异体选择优化的聚类效果还是比较明显 h)如达到设置的最大迭代次数或者期望的杀死度和最小的,通过选择后的变异体而产生的约简后的测试用例集,在 第3期 王曙燕,等:基于改进粒子群算法的变异体选择优化 755 杀死变异体能力的方面并没有明显的下降,和选择优化前的 测试用例集的杀死能力比较没有任何变化或只是非常小的 4结束语 变化,如在测试程序 Triangle和测试程序 Cireu Queue,选择优 本文提出用改进的粒子群算法对变异体进行选择优化,成 化前和选择优化后测试用例充分度没有任何变化,这说明在功地对造成变异测试成本过高的卡要原因之一的庞大交异体 大唱度减少」变异体的数量后,并没有影响到测试用例集的数目进行了优化。在不改变测试用例集测试充分度的前提下 纠错能力,对扌测试程序 Recipe,虽然测试充分度下降了使变异体的数目大幅度下降,从而降低了变异测试的测试成 0.4%,这个下降的影响是非常小的,在测试的工程中是在可本:通过实验分析并与其他的聚类算法进行比较,改进的粒子 以接受的范围的。实验结果表明,本文提出的方法在两方面群算法在聚类的过程中可以改进因为数据量增大而造成的迭 降低了变异测试的消耗:a)在没有影响或者影响非常小的情代次数增加和收敛速度减小的问题。实验结果证明,其优化效 况下,使变异休的数日得到缩减;b)通过优化后的变异休产果相比于其他算法更好、更稳定。本文选取的测试程序是常用 生了相应缩减的测试用例集。 但规模较小的。下步I作,主要是在于实现自动获取变异体 3.4和其他聚类方法的比较 和测试用例集之间的对应关系的方法,从而可以对大规模程序 文献4]提出用聚类算法来对变异体进行选择优化,并用的变异体进行选择优化。 K- means和 agglomerative clustering算法进行了实验,实验的结参考文献 果表明了这两种方法对变异体的数量有明显的缩减作用,具有[1陈翔,顾庆。变异测试:原理、优化和应用[J计算机科学与探索 定的优化效果。但是K- means算法对K值有很强的依赖性, 012(12):1057-1075 聚类的效果容易被初始的聚类中心影响。 Agglomerative cluste [2 Acree A T On mutation. D. Atlanta: Georgia Institute of Technology mig算法中的簇如果结合了就不能被修改,这就限制了聚类的[31 Mathur A P. Performance, effectiveness, and reliability issues in soft- 质量。还有传统的粒子群算法在数据量增大的时候迭代次数 ware testing C//Proc of the 5 th International Computer, Software 就会增加,同时收敛速度也会下降。节将新提出的基于改进 and Applications Conference. 1991: 604-605 粒子群算法的变异体选择优化技术与K- means算法、 agglomera-[4] hamana. Mutation clustering[]. London; Kingg College,208 tive clustering算法以及标准粒子群算法进行对比。由图3可5. Ii Changbin, ChenZhenyu, XuBaowen,ctat. A novel method of mu 看出,本文提出的基丁改进的粒」样算法的变异体优化有着吏 ation clustering based on domain analysisL C//Proe of the 21 st In ternational Conference on Software Engineering and Knowledge engi 好的效果,且结果都比较稳定。 2009:1-3 ]邵楠,周雁舟,惠文涛,等,基于自适应变异粒子彩优化算法的測 试数据生成[J].计算杌应用研究,2015,32(3):786-789 [7]张功杰,现敦卫,姚香娟,基于变异分析和集合进化的测试用例 93.9 93.193.1 生成方法[J].计算机学报,2015,38(11):2318-2331 92.3 916 91.2 [8』冯霞,王曙燕,孙家泽.基于K- means聚类的組合测试月例生成优 化算法「J.西安邮电大学学报,2015,20(1):44-48 [9 Umar M. An evaluation of mutation operators for equivalent mutants [D]. London: King,s College, 2006 [10]潘烁,王躇燕,孙家泽,基于K-均伍聚类粒子群优化算法的组合 Triangle 测试数据生成LJ」.计算机应用,2012,32(4):1165-1167,11 ■改进粒子群算法标准粒子群算法■K- means■Agg算法 [11 Smith B H. Muclipse: an open sourre mutation testing plug-in for E 图3不同方法的实验对比图 lipset EB/OL.-[2010-09-29.hItp: //muclipse soureeforyenet/ (上接第729页) 2010:265-278 [31 Dean J, Chemawal S. Map Reduce: simplified data processing on lager 10] Zhang Xiaohong, Zhong Zh L. Improt clusters[J1. Communications of the ACM, 2008, 51(1): 1U7-113 data locality of Map Reduce by scheduling in homogeneous computin [4]于倩,蔚承建,王开,等.基于机器学习的 Mapreduce资源调度算 environment[C// Proc of the 9th IEEE International Symposium on 法[冂].计算机应用研究,2016,33(1):111-114. Parallel and Distributed Processing with Applications. 2011: 120 L5」李春艳,何一舟,戴彬. [Hadoop平台的多队列作业调度伏化方法 研完J].计算机应用研完,2014.31(3):705-707,738 [1]顾宇,周良,丁秋林,基于优先级的Thre-ueue调度算法硏究 [6 Rao B T, Reddy L S S. Survey on improved scheduling in Hadoop [J].计算机科学,2011,38(51):253-256 nap reduce in cloud environment[ J. International Journal of L 12 Suresh S, Gopalan N P. An optimal task selection scheme for ladoo Computer Applications, 2012, 34(9): 29-33 scheduling c/ /Proc of International Conference on Future Informa [7] Fischer M J, Su Xueyuan, Yin Yitong. Assigning tasks for efficiency in Hadoop extended abstract[ C]//Proc of the 22nd ACM Sympo- tion Engineering. 2014: 70-75 sium on Parallelism in algorithms and Architectures. 2010: 30-39 L13」徐焕良,翟璐,莽卫,等. hadoop平台中 MapReduce调度算法研究 [8 Jin Jiahui, Luo Junzhou, Song Aibo, et aL. BAR: an efficient data [J].计算初应用与软件,2015,32(5):1-6,16. locality driven task scheduling algorithm for cloud computing[ c/[14】余正秤,基于学习方式对 Hadoop作业调度的改进研究[J,计算 Proc of the 11th IEEE/ACM International Symposium on Cluster 机科学,2012,39(6):220-222,256 Cloud and Grid Computing. 2011: 295-304 [I5]施朝健,张明铭, Logistic回归模型分祈[J].计算札辅助工程, [9 Zaharia M, Borthakur D, Sarma JS, et u/ Delay sc heduling: H simple 2005,14(3):7478 technique for achieving locality and fairness in eluter scheduling L16」谢花林基于 logistic回归模型的农牧交错区土地利用变化驱动 [C]//Proc of the 5th European Conference on Computer System 力分析[J].地理研究,2008,27(2):294-304

...展开详情
试读 4P 论文研究-基于改进粒子群算法的变异体选择优化.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-基于改进粒子群算法的变异体选择优化.pdf 9积分/C币 立即下载
1/4
论文研究-基于改进粒子群算法的变异体选择优化.pdf第1页

试读结束, 可继续读1页

9积分/C币 立即下载 >