基于粒子群优化算法的测试用例生成方法
|
摘要
针对标准粒子群算法(Particle Swarm Optimization,PSO)中存在的早熟收敛、易于陷入局部极值的问题,提出了一种基于反向学习与再次搜索的粒子群优化算法(Reverse-Learning and Search-Again PSO,RSAPSO)用于测试用例生成。首先,通过非线性递减的惯性权重函数对学习因子进行改进,实现对种群的初步搜索,并采用梯度下降法完成对最优解与次优解的再次搜索;其次,以极值点为中心设定禁忌区域,对禁忌区域外的粒子进行反向学习,改善种群多样性;最后,采用分支距离法构造适应度函数,评判测试用例的优劣程度。实验结果表明,提出的改进方法在覆盖率、迭代次数和缺陷检测率指标上均有优势。
In order to solve the problem of premature convergence and being easy to fall into local extremum in standard particle swarm optimization,this paper put forward a particle swarm optimization based on reverse-learning and search-again for test case generation.Firstly,the learning factor is improved by the nonlinear decreasing inertia weight function,realizing the preliminary search for the population,and the gradient descent method is used to complete the search-again of the optimal solution and the suboptimal solution.Secondly,setting taboo areas with extreme points as the center,the population diversity is improved by the reverse learning of the particles outside the taboo region.Finally,the branch distance method is used to construct fitness function to evaluate the quality of test cases.Experiment results show that the proposed method has advantages in coverage,iteration times and defect detection rate.
In order to solve the problem of premature convergence and being easy to fall into local extremum in standard particle swarm optimization,this paper put forward a particle swarm optimization based on reverse-learning and search-again for test case generation.Firstly,the learning factor is improved by the nonlinear decreasing inertia weight function,realizing the preliminary search for the population,and the gradient descent method is used to complete the search-again of the optimal solution and the suboptimal solution.Secondly,setting taboo areas with extreme points as the center,the population diversity is improved by the reverse learning of the particles outside the taboo region.Finally,the branch distance method is used to construct fitness function to evaluate the quality of test cases.Experiment results show that the proposed method has advantages in coverage,iteration times and defect detection rate.
引文
[1] CHEN H Y,TSE T H,CHEN T Y.TACCLE:a methodology for object-oriented software testing at the class and cluster le-vels[J].ACM Transactions on Software Engineering & Metho-dology,2001,10(1):56-109.
[2] GALLAGHER M N,ARASIMHAN V L.ADT EST:A Test Data Generation Suite for A da Software Systems[J].IEEE Transactions on Software Engineering,1997,23(8):473-484.
[3] SHI Y,EBERHART R C.Fuzzy adaptive particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutio-nary Computation.Seoul,Korea,2001:101-106.
[4] XIA X W,LIU J N,GAO K F,et al.An improved particle swarm optimizer based on tabu detecting and local learning strategy in a shrunk search space[J].Applied Soft Computing,2014,23(1):76-90.(in Chinese)夏学文,刘经南,高柯夫,等.具备反向学习和局部学习能力的粒子群算法[J].计算机学报,2015,38(7):1397-1407.
[5] MENDES R,KENNEDY J,NEVES J.The fully informed particle swarm:Simpler,maybe better[J].IEEE Transactions on Evolutionary Computation,2004,8(3):204-210.
[6] ZHANG Y,GONG D W,SUN X Y,et al.Adaptive barebones particle swarm optimization algorithm and its convergence analysis[J].Soft Computing,2014,18(7):1337-1352.
[7] BAO X A,YANG Y J,ZHANG N,et al.Composite test case generation method based on Adaptive Particle Swarm Optimization[J].Computer Science,2017,44(6):177-181.(in Chinese)包晓安,杨亚娟,张娜,等.基于自适应粒子群优化的组合测试用例生成方法[J].计算机科学,2017,44(6):177-181.
[8] SHI J J,JIANG S J,HAN H,et al.Adaptive particle swarm optimization algorithm and its application in test data generation[J].Chinese Journal of Electronics,2013,41(8):1555-1559.(in Chinese)史娇娇,姜淑娟,韩寒,等.自适应粒子群优化算法及其在测试数据生成中的应用研究[J].电子学报,2013,41(8):1555-1559.
[9] LI G,SUN L,SUN H H,et al.String type test data generation based on mutation particle swarm optimization algorithm[J].Computer Science,2016,43(11):252-256,279.(in Chinese)李刚,于磊,孙回回,等.基于变异粒子群算法的字符串型测试数据生成[J].计算机科学,2016,43(11):252-256,279.
[10] BUENO P M S,JINO M,WONG W E.Diversity oriented test data generation using metaheuristic search techniques [J].Information Science,2014,25(9):490-509.
[11] MAO C Y,YU X X,XUE Y Z.Algorithm Design and Empirical Analysis for Particle Swarm Optimization Based Test Data Ge-neration[J].Journal of Computer Research and Development,2014,51(4):824-837.(in Chinese)毛澄映,喻新欣,薛云志.基于粒子群优化的测试数据生成及其实证分析[J].计算机研究与发展,2014,51(4):824-837.
[12] CHEN X,GU Q,WANG Z Y,et al.Framework of Particle Swarm Optimization Based Pairwise Testing[J].Journal of Software,2011,22(12):2879-2893.(in Chinese)陈翔,顾庆,王子元,等.一种基于粒子群优化的成对组合测试算法框架[J].软件学报,2011 22(12):2879-2893.
[13] LU C,SHENG W,HAN Y,et al.Phase-only pattern synthesis based on gradient-descent optimization[J].Journal of Northeast Petroleum University,2016,38(4):297-307.
[14] KOREL B.Automated software test data generation[C]//IEEE Trans on Software Engineering,1990,16(8):870-879.
[15] KIFETEW M F,PANICHELLA A,DE LUCIA A,et al.Orthogonal exploration of the search space in evolutionary test case generation[C]//Proceedings of the 2013 International Symposium on Software Testing and Analysis.Lugano:ACM,2013:257-267.
[16] XIAO M,EL-ATTAR M,REFORMAT M,et al.Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques[J].Empirical Software Engineering,2007,12(2):183-223.
[2] GALLAGHER M N,ARASIMHAN V L.ADT EST:A Test Data Generation Suite for A da Software Systems[J].IEEE Transactions on Software Engineering,1997,23(8):473-484.
[3] SHI Y,EBERHART R C.Fuzzy adaptive particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutio-nary Computation.Seoul,Korea,2001:101-106.
[4] XIA X W,LIU J N,GAO K F,et al.An improved particle swarm optimizer based on tabu detecting and local learning strategy in a shrunk search space[J].Applied Soft Computing,2014,23(1):76-90.(in Chinese)夏学文,刘经南,高柯夫,等.具备反向学习和局部学习能力的粒子群算法[J].计算机学报,2015,38(7):1397-1407.
[5] MENDES R,KENNEDY J,NEVES J.The fully informed particle swarm:Simpler,maybe better[J].IEEE Transactions on Evolutionary Computation,2004,8(3):204-210.
[6] ZHANG Y,GONG D W,SUN X Y,et al.Adaptive barebones particle swarm optimization algorithm and its convergence analysis[J].Soft Computing,2014,18(7):1337-1352.
[7] BAO X A,YANG Y J,ZHANG N,et al.Composite test case generation method based on Adaptive Particle Swarm Optimization[J].Computer Science,2017,44(6):177-181.(in Chinese)包晓安,杨亚娟,张娜,等.基于自适应粒子群优化的组合测试用例生成方法[J].计算机科学,2017,44(6):177-181.
[8] SHI J J,JIANG S J,HAN H,et al.Adaptive particle swarm optimization algorithm and its application in test data generation[J].Chinese Journal of Electronics,2013,41(8):1555-1559.(in Chinese)史娇娇,姜淑娟,韩寒,等.自适应粒子群优化算法及其在测试数据生成中的应用研究[J].电子学报,2013,41(8):1555-1559.
[9] LI G,SUN L,SUN H H,et al.String type test data generation based on mutation particle swarm optimization algorithm[J].Computer Science,2016,43(11):252-256,279.(in Chinese)李刚,于磊,孙回回,等.基于变异粒子群算法的字符串型测试数据生成[J].计算机科学,2016,43(11):252-256,279.
[10] BUENO P M S,JINO M,WONG W E.Diversity oriented test data generation using metaheuristic search techniques [J].Information Science,2014,25(9):490-509.
[11] MAO C Y,YU X X,XUE Y Z.Algorithm Design and Empirical Analysis for Particle Swarm Optimization Based Test Data Ge-neration[J].Journal of Computer Research and Development,2014,51(4):824-837.(in Chinese)毛澄映,喻新欣,薛云志.基于粒子群优化的测试数据生成及其实证分析[J].计算机研究与发展,2014,51(4):824-837.
[12] CHEN X,GU Q,WANG Z Y,et al.Framework of Particle Swarm Optimization Based Pairwise Testing[J].Journal of Software,2011,22(12):2879-2893.(in Chinese)陈翔,顾庆,王子元,等.一种基于粒子群优化的成对组合测试算法框架[J].软件学报,2011 22(12):2879-2893.
[13] LU C,SHENG W,HAN Y,et al.Phase-only pattern synthesis based on gradient-descent optimization[J].Journal of Northeast Petroleum University,2016,38(4):297-307.
[14] KOREL B.Automated software test data generation[C]//IEEE Trans on Software Engineering,1990,16(8):870-879.
[15] KIFETEW M F,PANICHELLA A,DE LUCIA A,et al.Orthogonal exploration of the search space in evolutionary test case generation[C]//Proceedings of the 2013 International Symposium on Software Testing and Analysis.Lugano:ACM,2013:257-267.
[16] XIAO M,EL-ATTAR M,REFORMAT M,et al.Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques[J].Empirical Software Engineering,2007,12(2):183-223.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |