Computer Science ›› 2018, Vol. 45 ›› Issue (8): 174-178.doi: 10.11896/j.issn.1002-137X.2018.08.031

• Software & Database Technology • Previous Articles     Next Articles

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

BAO Xiao-an1, XIONG Zi-jian1, ZHANG Wei1, WU Biao2, ZHANG Na1   

  1. School of Information Science and Technology,Zhejiang Sci-tech University,Hangzhou 310018,China1
    The Graduate School of East Asian Studies,Yamaguchi University,Yamaguchi 753-8513,Japan2
  • Received:2017-06-23 Online:2018-08-29 Published:2018-08-29

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: Software testing, Test cases generation, Genetic algorithm, Fitness function

CLC Number: 

  • TP311
[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.
[1] GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[2] SUN Chang-ai, ZHANG Shou-feng, ZHU Wei-zhong. Mutation Based Fault Localization Technique for BPEL Programs [J]. Computer Science, 2021, 48(1): 301-307.
[3] JI Shun-hui, ZHANG Peng-cheng. Test Case Generation Approach for Data Flow Based on Dominance Relations [J]. Computer Science, 2020, 47(9): 40-46.
[4] DONG Ming-gang, HUANG Yu-yang, JING Chao. K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection [J]. Computer Science, 2020, 47(8): 178-184.
[5] LIANG Zheng-you, HE Jing-lin, SUN Yu. Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition [J]. Computer Science, 2020, 47(8): 227-232.
[6] YANG De-cheng, LI Feng-qi, WANG Yi, WANG Sheng-fa, YIN Hui-shu. Intelligent 3D Printing Path Planning Algorithm [J]. Computer Science, 2020, 47(8): 267-271.
[7] FENG Bing-chao and WU Jing-li. Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System [J]. Computer Science, 2020, 47(6A): 114-118.
[8] YAO Min. Multi-population Genetic Algorithm for Multi-skill Resource-constrained ProJect Scheduling Problem [J]. Computer Science, 2020, 47(6A): 124-129.
[9] BAO Zhen-shan, GUO Jun-nan, XIE Yuan and ZHANG Wen-bo. Model for Stock Price Trend Prediction Based on LSTM and GA [J]. Computer Science, 2020, 47(6A): 467-473.
[10] MA Chuang, LV Xiao-fei and LIANG yan-ming. Agricultural Product Quality Classification Based on GA-SVM [J]. Computer Science, 2020, 47(6A): 517-520.
[11] XIA Chun-yan, WANG Xing-ya, ZHANG Yan. Test Case Prioritization Based on Multi-objective Optimization [J]. Computer Science, 2020, 47(6): 38-43.
[12] HU Shi-juan, LU Hai-yan, XIANG Lei, SHEN Wan-qiang. Fuzzy C-means Clustering Based Partheno-genetic Algorithm for Solving MMTSP [J]. Computer Science, 2020, 47(6): 219-224.
[13] ZHANG Ju, WANG Hao, LUO Shu-ting, GENG Hai-jun, YIN Xia. Hybrid Software Defined Network Energy Efficient Routing Algorithm Based on Genetic Algorithm [J]. Computer Science, 2020, 47(6): 236-241.
[14] JIN Xiao-min, HUA Wen-qiang. Energy Optimization Oriented Resource Management in Mobile Cloud Computing [J]. Computer Science, 2020, 47(6): 247-251.
[15] BAI Wei, PAN Zhi-song, XIA Shi-ming, CHENG Ang-xuan. Network Security Configuration Generation Framework Based on Genetic Algorithm Optimization [J]. Computer Science, 2020, 47(5): 306-312.
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .