一种基于改进遗传算法的路径测试用例生成方法

doi:10.11896/j.issn.1002-137X.2018.08.031

计算机科学 ›› 2018, Vol. 45 ›› Issue (8): 174-178.doi: 10.11896/j.issn.1002-137X.2018.08.031

一种基于改进遗传算法的路径测试用例生成方法

包晓安¹, 熊子健¹, 张唯¹, 吴彪², 张娜¹

浙江理工大学信息学院杭州310018¹
山口大学东亚研究所研究生院山口753-8513²

收稿日期:2017-06-23 出版日期:2018-08-29 发布日期:2018-08-29
作者简介:包晓安(1973-),男,硕士,教授,主要研究方向为自适应软件、软件测试与智能信息处理; 熊子健(1993-),男,硕士,主要研究方向为软件工程、软件测试; 张唯(1994-),女,硕士,主要研究方向为软件测试、软件形式化方法; 吴彪(1989-),男,博士,主要研究方向为软件工程、软件测试; 张娜(1977-),女,硕士,副教授,主要研究方向为软件工程、软件测试,E-mail:zhangna@zstu.edu.cn(通信作者)。
基金资助:
本文受国家自然科学基金(61502430,61379036,61562015),浙江理工大学521人才培养计划资助。

Approach for Path-oriented Test Cases Generation Based on Improved Genetic Algorithm

BAO Xiao-an¹, XIONG Zi-jian¹, ZHANG Wei¹, WU Biao², ZHANG Na¹

School of Information Science and Technology,Zhejiang Sci-tech University,Hangzhou 310018,China¹
The Graduate School of East Asian Studies,Yamaguchi University,Yamaguchi 753-8513,Japan²

Received:2017-06-23 Online:2018-08-29 Published:2018-08-29

摘要/Abstract

摘要： 采用遗传算法求解路径覆盖的测试用例生成问题是软件测试自动化的研究热点。针对传统标准遗传方法搜索测试用例易产生早熟收敛和收敛速度较慢的不足,设计了自适应的交叉算子和变异算子,提高了算法的全局寻优能力。基于动态生成算法框架,通过程序静态分析,考虑了分支嵌套深度的影响,结合层接近度和分支距离法,提出一种新的适应度函数。实验结果表明,该算法在面向路径的测试用例生成上优于传统方法,提高了测试效率。

关键词: 测试用例生成, 软件测试, 适应度函数, 遗传算法

Abstract: Using genetic algorithms to solve the problem of generating test cases for path coverage is a hot topic in software testing automation.In view of the problems in traditional standard genetic methods,such as premature convergence and slow search efficiency,this paper designed adaptive crossover operator and mutation operator,thus enhancing the global optimal capability of genetic algorithm.Meanwhile,a new fitness function was introduced to evaluate individuals based on dynamic generation algorithm framework,which combines approach level and branch distance and takes the nesting degree of branches into consideration to compute the fitness values of test data.The experimental results confirm that the proposed improved method is more efficient in generating test cases for path coverage compared with the traditional method.

Key words: Fitness function, Genetic algorithm, Software testing, Test cases generation

中图分类号:

TP311

包晓安, 熊子健, 张唯, 吴彪, 张娜. 一种基于改进遗传算法的路径测试用例生成方法[J]. 计算机科学, 2018, 45(8): 174-178. https://doi.org/10.11896/j.issn.1002-137X.2018.08.031

BAO Xiao-an, XIONG Zi-jian, ZHANG Wei, WU Biao, ZHANG Na. Approach for Path-oriented Test Cases Generation Based on Improved Genetic Algorithm[J]. Computer Science, 2018, 45(8): 174-178. https://doi.org/10.11896/j.issn.1002-137X.2018.08.031

参考文献

[1]SAGARNA R,LOZANO J A.Scatter search in software tes-ting,comparison and collaboration with estimation of distribution algorithms[J].European Journal of Operational Research,2006,169(2):392-412.
[2]FRASER G,ARCURI A.EvoSuite at the SBST 2015 Tool Competition[C]∥IEEE/ACM,International Workshop on Search-Based Software Testing.IEEE,2015:25-27.
[3]GALLER S J,AICHERNIG B K.Survey on test data generation tools[J].International Journal on Software Tools for Technology Transfer,2014,16(6):727-751.
[4]XUE Y Z,CHEN W,WANG Y J,et al.An automated approach for structural test data generation based on Messy GA[J].Journal of Software,2006,17(8):1688-1697.(in Chinese)薛云志,陈伟,王永吉,等.一种基于Messy GA的结构测试数据自动生成方法[J].软件学报,2006,17(8):1688-1697.
[5]AWEDIKIAN Z,AYARI K,ANTONIOL G.MC/DC automatic test input data generation[C]∥Genetic and Evolutionary Computation Conference(GECCO 2009).2009:1657-1664.
[6]MAHAJAN M,PORWAL R.Applying genetic algorithm to increase the efficiency of a data flow-based test data generation approach[J].Acm Sigsoft Software Engineering Notes,2012,37(5):1-5.
[7]GIRGIS M R,GHIDUK A S,ABDELKAWY E H.AutomaticGeneration of Data Flow Test Paths using a Genetic Algorithm[J].International Journal of Computer Applications,2014,89(12):29-36.
[8]GONG D W,ZHANG Y.Novel evolutionary generation ap-proach to test data for multiple paths coverage[J].Acta Electronica Sinica,2010,38(6):1299-1304.(in Chinese)巩敦卫,张岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报,2010,38(6):1299-1304.
[9]XIE X Y,XU B W,SHI L,et al.Genetic test case generation for path-oriented testing[J].Journal of Software,2009,20(12):3117-3136.(in Chinese)谢晓园,徐宝文,史亮,等.面向路径覆盖的演化测试用例生成技术[J].软件学报,2009,20(12):3117-3136.
[10]RAJKUMARI M R,GEETHA B G.Automatic test data gene-ration using genetic algorithm and program dependence graph[J].Journal of Computer Applications,2012,48(7):586-605.
[11]ALSHRAIDEH M A,MAHAFZAH B A,SALMAN H S E,et al.Using Genetic Algorithm as Test Data Generator for Stored PL/SQL Program Units[J].Journal of Software Engineering & Applications,2015,6(2):65-73.
[12]RAUF A,JAFFAR A,SHAHID A A.Fully automated gui testing and coverage analysis using genetic algorithms[J].International Journal of Innovative Computing Information & Control Ijicic,2011,7(6):3281-3294.
[13]SHI J J,JIANG S J.Automatic test data generation tool of dynamic variable parameters based on genetic algorithm[J].Computer Science,2012,39(5):124-127.(in Chinese)史娇娇,姜淑娟.基于遗传算法的动态可变参数的测试数据自动生成工具[J].计算机科学,2012,39(5):124-127.
[14]TRACEY N,CLARK J,MANDER K,et al.An AutomatedFramework for Structural Test-Data Generation[C]∥IEEE International Conference on Automated Software Engineering,1998.IEEE,1998:285-288.
[15]NIRPAL P B,KALE K V.Using Genetic Algorithm for Automated Efficient Software Test Case Generation for Path Testing[J].International Journal of Advanced Networking & Applications,2011,2(6):911-915.
[16]MCMINN P.Evolutionary Search for Test Data in the Presence of State Behaviour[J].University of Sheffield,2005,16(12):41-46.
[17]PACHAURI A,SRIVASTAVA G.Automated test data generation for branch testing using genetic algorithm:An improved approach using branch ordering,memory and elitism[J].Journal of Systems & Software,2013,86(5):1191-1208.
[18]DO H,ELBAUM S,ROTHERMEL G.Supporting ControlledExperimentation with Testing Techniques:An Infrastructure and its Potential Impact[J].Empirical Software Engineering,2005,10(4):405-435.
[19]ALETI A,GRUNSKE L.Test data generation with a Kalman filter-based adaptive genetic algorithm[J].Journal of Systems & Software,2015,103(C):343-352.
[20]SCHAFFER J D,CARUANA R A,ESHELMAN L J,et al.A study of control parameters affecting online performance of genetic algorithms for function optimization[C]∥International Conference on Genetic Algorithms,George Mason University,Fairfax,Virginia,USA.DBLP,1989:51-60.

相关文章 15

[1]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[2]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[3]	吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[4]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[5]	王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239
[6]	汪文轩, 胡军, 胡建成, 康介祥, 王辉, 高忠杰. 一种面向形式化表格需求模型的测试用例生成方法 Test Case Generation Method Oriented to Tabular Form Formal Requirement Model 计算机科学, 2021, 48(5): 16-24. https://doi.org/10.11896/jsjkx.201000048
[7]	左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053
[8]	文进, 张星宇, 沙朝锋, 刘艳君. 基于次模函数最大化的测试用例集约简 Test Suite Reduction via Submodular Function Maximization 计算机科学, 2021, 48(12): 75-84. https://doi.org/10.11896/jsjkx.210300086
[9]	滕俊元, 高猛, 郑小萌, 江云松. 噪声可容忍的软件缺陷预测特征选择方法 Noise Tolerable Feature Selection Method for Software Defect Prediction 计算机科学, 2021, 48(12): 131-139. https://doi.org/10.11896/jsjkx.201000168
[10]	高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同. 基于投影圆度和遗传算法的空间圆柱面拟合方法 Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm 计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057
[11]	姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191
[12]	孙昌爱, 张守峰, 朱维忠. 一种基于变异分析的BPEL程序故障定位技术 Mutation Based Fault Localization Technique for BPEL Programs 计算机科学, 2021, 48(1): 301-307. https://doi.org/10.11896/jsjkx.200900051
[13]	高基旭, 王珺. 一种基于遗传算法的多边缘协同计算卸载方案 Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm 计算机科学, 2021, 48(1): 72-80. https://doi.org/10.11896/jsjkx.200800088
[14]	吉顺慧, 张鹏程. 基于支配关系的数据流测试用例生成方法 Test Case Generation Approach for Data Flow Based on Dominance Relations 计算机科学, 2020, 47(9): 40-46. https://doi.org/10.11896/jsjkx.200700021
[15]	董明刚, 黄宇扬, 敬超. 基于遗传实例和特征选择的K近邻训练集优化方法 K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection 计算机科学, 2020, 47(8): 178-184. https://doi.org/10.11896/jsjkx.190700089

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种基于改进遗传算法的路径测试用例生成方法

Approach for Path-oriented Test Cases Generation Based on Improved Genetic Algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0