一种基于Kalman滤波和粒子群优化的测试数据生成方法

doi:10.3969/j.issn.0372-2112.2017.10.023

电子学报 ›› 2017, Vol. 45 ›› Issue (10): 2473-2483.DOI: 10.3969/j.issn.0372-2112.2017.10.023

一种基于Kalman滤波和粒子群优化的测试数据生成方法

薛猛¹, 姜淑娟^1,2, 张争光¹, 钱俊彦², 张艳梅^1,3, 曹鹤玲⁴

1. 中国矿业大学计算机科学与技术学院, 江苏徐州 221116;
2. 桂林电子科技大学广西可信软件重点实验室, 广西桂林 541004;
3. 南京大学计算机软件新技术国家重点实验室, 江苏南京 210093;
4. 河南工业大学信息科学与工程学院, 河南郑州 450001

收稿日期:2016-08-07 修回日期:2017-04-23 出版日期:2017-10-25
- 通讯作者:
- 姜淑娟
- 作者简介:
- 薛猛,男.1979年4月出生,江苏邳州人.博士研究生,讲师,CCF会员,主要研究领域为软件测试、测试数据生成.E-mail:mgxue@cumt.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61502497，No.61562015，No.61673384，No.61602154）; 中国博士后科学基金 (No.2015M581887）; 广西可信软件重点实验室研究课题 (No.KX201530）; 南京大学计算机软件新技术国家重点实验室开放课题 (No.KFKT2014B19）; 徐州市科技计划项目 (No.KC15SM051）; 河南省高等学校重点科研项目计划资助 (No.16A520005）

A Test Data Generation Method Based on Kalman Filter and Particle Swarm Optimization Algorithm

XUE Meng¹, JIANG Shu-juan^1,2, ZHANG Zheng-guang¹, QIAN Jun-yan², ZHANG Yan-mei^1,3, CAO He-ling⁴

1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, Jiangsu 221116, China;
2. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China;
3. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu 210093, China;
4. College of Information Science and Engineering, Henan University of Technology, Zhengzhou, Henan 450001, China

Received:2016-08-07 Revised:2017-04-23 Online:2017-10-25 Published:2017-10-25
- Supported by:
- National Natural Science Foundation of China (No.61502497, No.61562015, No.61673384, No.61602154); China Postdoctoral Science Foundation (No.2015M581887); Research Project of Guangxi Key Laboratory of Trusted Software (No.KX201530); Open Project of State Key Laboratory for Novel Software Technology at Nanjing University (No.KFKT2014B19); Xuzhou Science and Technology planning Project (No.KC15SM051); Key Scientific Research Programs of colleges and universities of Henan Province (No.16A520005)

摘要/Abstract

摘要： 为减少进化代数，提高路径覆盖成功率，提出了多邻域Kalman滤波PSO测试数据生成方法.在该方法中将粒子固定划分到不同邻域中，各邻域内指定一个粒子向全局最优粒子学习，其余各粒子向所在邻域中最优粒子学习，而全局最优粒子利用无速度项的简化PSO进化.在此过程中，除全局最优粒子外的各粒子利用Kalman滤波方程更新粒子的位置.实验表明，相较于基本PSO和其他PSO方法，即使是覆盖困难的路径，本文方法也具有进化代数少、路径覆盖成功率高及性能稳定的特点.

关键词: 测试数据生成, 粒子群优化, Kalman滤波, 邻域拓扑

Abstract: A test data generation method named multi-neighborhood Kalman filter PSO(MNKFPSO) was proposed to reduce the evolution number and to improve the success rate of path coverage.Particles except the global best one update themselves' positions using Kalman filter.One of them is allotted to a fixed neighborhood.A designated particle learns from the global best particle,others learn from the best in one neighborhood.And the global best particle's position changes by a simple PSO which discards the particle velocity.The experimental results show that it can generate test data covering the specified path in the less evolutionary using MNKFPSO and has high success rate of path coverage even though the paths difficult to cover.The algorithm also exhibits a stable performance.

Key words: test data generation, particle swarm optimization (PSO), Kalman filter, neighborhood topology

中图分类号:

TP311.5

薛猛, 姜淑娟, 张争光, 等. 一种基于Kalman滤波和粒子群优化的测试数据生成方法[J]. 电子学报, 2017, 45(10): 2473-2483.

XUE Meng, JIANG Shu-juan, ZHANG Zheng-guang, et al. A Test Data Generation Method Based on Kalman Filter and Particle Swarm Optimization Algorithm[J]. Acta Electronica Sinica, 2017, 45(10): 2473-2483.

参考文献

[1] 单锦辉,王戟,齐治昌.面向路径的测试数据自动生成方法述评[J].电子学报,2004,32(1):109-113. SHAN Jin-Hui,WANG Ji,QI Zhi-Chang.Survey on path-wise automatic generation of test data[J].Acta Electronica Sinica,2004,32(1):109-113.(in Chinese)
[2] HARMAN M,JONES B F.Search-based software engineering[J].Information and software Technology,2001,43(14):833-839.
[3] MCMINN P.Search-based software test data generation:a survey[J].Software Testing Verification & Reliability,2004,14(2):105-156.
[4] MCMINN P.Search-based software testing:Past,present and future[A].Proceedings of IEEE Fourth International Conference on Software Testing,Verification and Validation Workshops[C].USA:IEEE,2011.153-163.
[5] HARMAN M,MANSOURI S A,ZHANG Y.Search-based software engineering:Trends,techniques and applications[J].ACM Computing Surveys (CSUR),2012,45(1):Article No.11.doi:10.1145/2379776.2379787.
[6] 中国计算机学会.CCF 2013-2014中国计算机科学技术发展报告[M].北京:机械工业出版社,2014.
[7] XANTHAKIS S,ELLIS C,SKOURLAS C,et al.Application of genetic algorithms to software testing[A].Proceedings of the 5th International Conference on Software Engineering and its Applications,Toulouse,France[C].USA:IGI Global,1992.625-636.
[8] PARGAS R,HARROLD M,PECK R.Test-data generation using genetic algorithms[J].Software Testing Verification and Reliability,1999,9(4):263-282.
[9] YAO Xiang-juan,GONG Dun-wei.Genetic algorithm-based test data generation for multiple paths via individual sharing[J].Computational Intelligence and Neuroscience,2014,38(6):1-12.
[10] YAO Xiang-juan,GONG Dun-wei,WANG Wen-liang.Test data generation for multiple paths based on local evolution[J].Chinese Journal of Electronics,2015,24(1):46-51.
[11] 巩敦卫,张岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报,2010,38(6):1299-1304. GONG Dun-wei,ZHANG Yan.Novel evolutionary generation approach to test data for multiple paths coverage[J].Acta Electronica Sinica,2010,38(6):1299-1304.(in Chinese)
[12] 张岩,巩敦卫.基于搜索空间自动缩减的路径覆盖测试数据进化生成[J].电子学报,2012,40(5):1011-1016. ZHANG Yan,GONG Dun-wei.Evolutionary generation of test data for path coverage based on automatic reduction of search space[J].Acta Electronica Sinica,2012,40(5):1011-1016.(in Chinese)
[13] TIAN Tian,GONG Dun-wei.Evolutionary generation approach of test data for multiple paths coverage of message-passing parallel programs[J].Chinese Journal of Electronics,2014,23(2):291-296.
[14] ALETI Aldeida,GRUNSKE Lars.Test data generation with a Kalman filter-based adaptive genetic algorithm[J].Journal of Systems and Software,2015,103(5):343-352.
[15] GUPTA M.Effective test data generation using genetic algorithms[J].Journal of Engineering Computers & Applied Sciences,2012,1(2):17-21.
[16] EL-SERAFY A,EL-SAYED G,SALAMA C,et al.Enhanced genetic algorithm for MC/DC test data generation[A].Proceedings of International Symposium on Innovations in Intelligent Systems and Applications[C].USA:IEEE,2015.1-8.
[17] WINDISCH A,WAPPLER S,WEGENER J.Applying particle swarm optimization to software testing[A].Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2007)[C].Berlin:Springer,2007.1121-1128.
[18] 毛澄映,喻新欣,薛云志.基于粒子群优化的测试数据生成及其实证分析[J].计算机研究与发展,2014,51(4):824-837. MAO Cheng-ying,YU Xin-xin,XUE Yun-zhi.Algorithm design and empirical analysis for particle swarm optimization-based test data generation[J].Journal of Computer Research and Development,2014,51(4):824-837.(in Chinese)
[19] MAO C.Generating test data for software structural testing based on particle swarm optimization[J].Arabian Journal Forence & Engineering,2014,39(6):4593-4607.
[20] JIANG S,SHI J,ZHANG Y,et al.Automatic test data generation based on reduced adaptive particle swarm optimization algorithm[J].Neurocomputing,2015,158:109-116.
[21] JIANG S,YI D,JU X,et al.An approach for test data generation using program slicing and particle swarm optimization[J].Neural Computing and Applications,2014,25(7-8):2047-2055.
[22] 王令赛,姜淑娟,张艳梅,于巧.基于正交搜索的粒子群优化测试用例生成方法[J].电子学报,2014,42(12):2345-2351. WANG Ling-sai,JIANG Shu-juan,ZHANG Yan-mei,YU Qiao.Test case generation based on orthogonal exploration and particle swarm optimization[J].Acta Electronica Sinica,2014,42(12):2345-2351.(in Chinese)
[23] 姜淑娟,王令赛,薛猛,张艳梅,于巧,姚慧冉.基于模式组合的粒子群优化测试用例生成方法[J].软件学报,2016,27(4):785-801. JIANG S J,WANG L S,XUE M,et al.Test case generation based on combination of schema using particle swarm optimization[J].Journal of Software,2016,27(4):785-801.(in Chinese)
[24] MONSON Chrstopher K,SEPPI Keven D.The Kalman swarm:a new approach to particle swarm motion in swarm optimization[A].Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004)[C].Berlin:Springer,2004,Vol.3102.140-150.
[25] KENNEDY J.EBERHART R C.Particle swarm optimization[A].Proceedings of IEEE International Conference on Neural Networks IV[C].Piscataway:IEEE,1995.1942-1948.
[26] SHI Y,EBERHART R.A modified particle swarm optimizer[A].Proceedings of IEEE International Conference on Evolutionary Computation[C].USA:IEEE World Congress on Computational Intelligence,1998.69-73.
[27] KALMAN R E.A new approach to linear filtering and prediction problems[J].Transactions of the ASME-Journal of Basic Engineering,1960,82:35-45.
[28] CLERC Maurice.Particle Swarm Optimization[M].USA:ISTE (International Scientific and Technical Encyclopedia),2006.
[29] KENNEDY J,MENDES R.Population structure and particle swarm performance[A].Proceedings of the Congress on Evolutionary Computation (CEC'02)[C].USA:IEEE Computer Society Washington,2002.1671-1676.
[30] SUGANTHAN P N.Particle swarm optimiser with neighbourhood operator[A].Proceedings of the Congress on Evolutionary Computation (CEC'99)[C].USA:IEEE Computer Society Washington,1999.1958-1962.
[31] KRINK T,VESTERSTROM J S,Riget J.Particle swam optimization with spatial particle extension[A].Proceedings of the Congress on Evolutionary Computation (CEC'02)[C].USA:IEEE Computer Society Washington,2002.1474-1479.
[32] 胡旺,李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报,2007,18(4):861-868. HU Wang,LI Zhi-Shu.A simpler and more effective particle swarm optimization algorithm[J].Journal of Software,2007,18(4):861-868.(in Chinese)
[33] JavaNCSS[OL].http://www.kclee.de/clemens/java/javancss/,2017-02-20.
[34] MCMINN P.An identification of program factors that impact crossover performance in evolutionary test input generation for the branch coverage of C programs[J].Information and Software Technology,2013,55(1):153-172.
[35] 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-239.
[36] KIFETEW F M,PANICHELLA A,LUCIA A D,et al.Orthogonal exploration of the search space in evolutionary test case generation[A].Proceedings of International Symposium in Software Testing and Analysis[C].USA:ACM,2013.257-267.
[37] KOREL B.Automated software test data generation[J].IEEE Transactions on Software Engineering,1990,16(8):870-879.
[38] 迟玉红,孙富春,王维军,喻春明.基于空间缩放和吸引子的粒子群优化算法[J].计算机学报,2011,34(1):115-130. CHI Yu-Hong,SUN Fu-Chun,WANG Wei-Jun,YU Chun-Ming.An improved particle swarm optimization algorithm with search space zoomed factor and attractor[J].Chinese Journal of Computers,2011,34(1):115-130.(in Chinese)

一种基于Kalman滤波和粒子群优化的测试数据生成方法

A Test Data Generation Method Based on Kalman Filter and Particle Swarm Optimization Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.
[2]	韩红桂, 阿音嘎, 张璐, 乔俊飞. 自适应分解式多目标粒子群优化算法[J]. 电子学报, 2020, 48(7): 1245-1254.
[3]	王海东, 刘云敬, 康琳, 武迎春. 射频能量捕获传感网移动能量源的布置策略研究[J]. 电子学报, 2020, 48(12): 2367-2375.
[4]	田甜, 巩敦卫. 并发程序变异测试研究综述[J]. 电子学报, 2020, 48(11): 2267-2277.
[5]	李泽, 田增山, 王中春, 王亚. 基于粒子群优化的多径辅助室内定位算法[J]. 电子学报, 2020, 48(10): 1952-1960.
[6]	孙辉, 邓志诚, 赵嘉, 王晖, 谢海华. 混合均值中心反向学习粒子群优化算法[J]. 电子学报, 2019, 47(9): 1809-1818.
[7]	黄锦旺, 吕善翔, 李广明, 袁华强. 基于增殖系数的混沌信号提取算法[J]. 电子学报, 2019, 47(4): 855-861.
[8]	张行, 常颖, 宋康, 李春国, 杨绿溪. 一种新颖的水声信道参数估计算法[J]. 电子学报, 2019, 47(2): 509-512.
[9]	龙文, 蔡绍洪, 焦建军, 伍铁斌. 一种改进的灰狼优化算法[J]. 电子学报, 2019, 47(1): 169-175.
[10]	韩红桂, 武淑君. 基于收敛速度和多样性的多目标粒子群种群规模优化设计[J]. 电子学报, 2018, 46(9): 2263-2269.
[11]	刘兆广, 纪秀花, 刘云霞. 一种快速收敛的非参数粒子群优化算法及其收敛性分析[J]. 电子学报, 2018, 46(7): 1669-1674.
[12]	韩红桂, 卢薇, 乔俊飞. 一种基于多样性信息和收敛度的多目标粒子群优化算法[J]. 电子学报, 2018, 46(2): 315-324.
[13]	闫涛, 刘凤娴, 陈斌. 基于量子混沌粒子群优化算法的分数阶超混沌系统参数估计[J]. 电子学报, 2018, 46(2): 333-340.
[14]	刘毅, 宋余庆, 刘哲. 基于有理四次Hermite插值和PSO的EMD包络线拟合算法[J]. 电子学报, 2018, 46(11): 2761-2767.
[15]	曹玉莲, 李文锋, 张煜. 基于拟熵自适应启动局部搜索策略的混合粒子群算法[J]. 电子学报, 2018, 46(1): 110-117.