Document Type : Methodologies
Authors
1 Department of Computer Engineering, K. N. Toosi University of Technology, Tehran, Iran.
2 Faculty of Computer Engineering, K. N. Toosi University of Technology, Tehran, Iran.
Abstract
In the structural software test, test data generation is essential. The problem of generating test data is a search problem, and for solving the problem, search algorithms can be used. Genetic algorithm is one of the most widely used algorithms in this field. Adjusting genetic algorithm parameters helps to increase the effectiveness of this algorithm. In this paper, the Adaptive Genetic Algorithm (AGA) is used to maintain the diversity of the population to test data generation based on path coverage criterion, which calculates the rate of recombination and mutation with the similarity between chromosomes and the amount of chromosome fitness during and around each algorithm. Experiments have shown that this method is faster for generating test data than other versions of the genetic algorithm used by others.
Keywords
[1] McMinn, Phil. "Search‐based software test data generation: a survey." Software testing, Verification and reliability 14, no. 2 (2004): 105-156.
[2] Lonetti, Francesca, and Eda Marchetti. "Emerging software testing technologies." In Advances in computers, vol. 108, pp. 91-143. Elsevier, 2018.
[3] Civicioglu, Pinar, and Erkan Besdok. "A conceptual comparison of the Cuckoo-search, particle swarm optimization, differential evolution and artificial bee colony algorithms." Artificial intelligence review 39, no. 4 (2013): 315-346.
[4] McGinley, Brian, John Maher, Colm O'Riordan, and Fearghal Morgan. "Maintaining healthy population diversity using adaptive crossover, mutation, and selection." IEEE Transactions on Evolutionary Computation 15, no. 5 (2011): 692-714.
[5] Kim, Su Yong, Sungdeok Cha, and Doo-Hwan Bae. "Automatic and lightweight grammar generation for fuzz testing." Computers & Security 36 (2013): 1-11.
[6] Khan, Rijwan, Mohd Amjad, and Akhilesh Kumar Srivastava. "Optimization of automatic generated test cases for path testing using genetic algorithm." In 2016 Second International Conference on Computational Intelligence & Communication Technology (CICT), pp. 32-36. IEEE, 2016.
[7] Damia, Amir Hossein, and Mohammad Mehdi Esnaashari. "Automated Test Data Generation Using a Combination of Firefly Algorithm and Asexual Reproduction Optimization Algorithm." International Journal of Web Research 3, no. 1 (2020): 19-28.
[8] Pachauri, Ankur, and Gaurav Mishra. "A path and branch based approach to fitness computation for program test data generation using genetic algorithm." In 2015 International Conference on Futuristic Trends on Computational Analysis and Knowledge Management (ABLAZE), pp. 49-55. IEEE, 2015.
[9] Jiang, Shujuan, Jiaojiao Shi, Yanmei Zhang, and Han Han. "Automatic test data generation based on reduced adaptive particle swarm optimization algorithm." Neurocomputing 158 (2015): 109-116.
[10] Kumar, Sumit, Dilip Kumar Yadav, and Danish Ali Khan. "A novel approach to automate test data generation for data flow testing based on hybrid adaptive PSO-GA algorithm." International Journal of Advanced Intelligence Paradigms 9, no. 2-3 (2017): 278-312.
[11] Khan, Rijwan, Mohd Amjad, and Akhlesh Kumar Srivastava. "Optimization of automatic test case generation with cuckoo search and genetic algorithm approaches." In Advances in Computer and Computational Sciences, pp. 413-423. Springer, Singapore, 2018.
[12] Gupta, Meenakshi, and Garima Gupta. "Effective test data generation using genetic algorithms." Journal of Engineering, Computers & Applied Sciences 1, no. 2 (2012): 17-21.
[13] Sharifipour, Hossein, Mojtaba Shakeri, and Hassan Haghighi. "Structural test data generation using a memetic ant colony optimization based on evolution strategies." Swarm and Evolutionary Computation 40 (2018): 76-91.
[14] Rao, K. Koteswara, G. S. V. P. Raju, and Srinivasan Nagaraj. "Optimizing the software testing efficiency by using a genetic algorithm: a design methodology." ACM SIGSOFT Software Engineering Notes 38, no. 3 (2013): 1-5.
[15] Singh, Bindhyachal Kumar. "Automatic efficient test data generation based on genetic algorithm for path testing." International Journal of Research in Engineering & Applied Sciences 2, no. 2 (2012): 1460-1472.
[16 Liu, Dan, Xuejun Wang, and Jianmin Wang. "Automatic Test Case Generation based on Genetic Algorithm." Journal of Theoretical & Applied Information Technology 48, no. 1 (2013).
[17] Latiu, Gentiana Ioana, Octavian Augustin Cret, and Lucia Vacariu. "Automatic test data generation for software path testing using evolutionary algorithms." In 2012 Third International Conference on Emerging Intelligent Data and Web Technologies, pp. 1-8. IEEE, 2012.
[18] Varshney, Sapna, and Monica Mehrotra. "Automated software test data generation for data flow dependencies using genetic algorithm." International Journal of Advanced Research in Computer Science and Software Engineering 4, no. 2 (2014): 472-479.
[19] Zhu, Xiao-mei, and Xian-feng Yang. "Software test data generation automatically based on improved adaptive particle swarm optimizer." In 2010 International Conference on Computational and Information Sciences, pp. 1300-1303. IEEE, 2010.
[20] Noei, Shirin, Mohammadreza Parvizimosaed, and Mohammadreza Noei. "Longitudinal Control for Connected and Automated Vehicles in Contested Environments." Electronics 10, no. 16 (2021): 1994.
[21] Aleti, Aldeida, and Lars Grunske. "Test data generation with a Kalman filter-based adaptive genetic algorithm." Journal of Systems and Software 103 (2015): 343-352.
[22] Yang, Shunkun, Tianlong Man, Jiaqi Xu, Fuping Zeng, and Ke Li. "RGA: A lightweight and effective regeneration genetic algorithm for coverage-oriented software test data generation." Information and Software Technology 76 (2016): 19-30.
[23] Yang, Shunkun, Tianlong Man, Jiaqi Xu, Fuping Zeng, and Ke Li. "RGA: A lightweight and effective regeneration genetic algorithm for coverage-oriented software test data generation." Information and Software Technology 76 (2016): 19-30.
[24] Pachauri, Ankur, and Gursaran Srivastava. "Automated test data generation for branch testing using genetic algorithm: An improved approach using branch ordering, memory and elitism." Journal of Systems and Software 86, no. 5 (2013): 1191-1208.
[25] Mann, Mukesh, Pradeep Tomar, and Om Prakash Sangwan. "Test Data Generation Using Optimization Algorithm: An Empirical Evaluation." In Soft Computing: Theories and Applications, pp. 679-686. Springer, Singapore, 2018.
[26] Myers, Glenford J., Corey Sandler, and Tom Badgett. The art of software testing. John Wiley & Sons, 2011.
[27] Sahoo, Rashmi Rekha, and Mitrabinda Ray. "PSO based test case generation for critical path using improved combined fitness function." Journal of King Saud University-Computer and Information Sciences 32, no. 4 (2020): 479-490.
[28] Mishra, Deepti Bala, Rajashree Mishra, Kedar Nath Das, and Arup Abhinna Acharya. "Test case generation and optimization for critical path testing using genetic algorithm." In Soft computing for problem solving, pp. 67-80. Springer, Singapore, 2019.
[29] Bao, Xiaoan, Zijian Xiong, Na Zhang, Junyan Qian, Biao Wu, and Wei Zhang. "Path-oriented test cases generation based adaptive genetic algorithm." PloS one 12, no. 11 (2017): e0187471.
[30] Surendran, Anupama, and Philip Samuel. "Evolution or revolution: the critical need in genetic algorithm based testing." Artificial Intelligence Review 48, no. 3 (2017): 349-395.
[31] Grefenstette, J., 2000. Rank-based selection. Evolutionary computation, 1, pp.187-194.
[32] Razali, Noraini Mohd, and John Geraghty. "Genetic algorithm performance with different selection strategies in solving TSP." In Proceedings of the world congress on engineering, vol. 2, no. 1, pp. 1-6. Hong Kong: International Association of Engineers, 2011.
[33] Bullnheimer, Bernd, Richard F. Hartl, and Christine Strauss. "A new rank based version of the Ant System. A computational study." (1997).
[34] Liang, Haibo, Jialing Zou, Kai Zuo, and Muhammad Junaid Khan. "An improved genetic algorithm optimization fuzzy controller applied to the wellhead back pressure control system." Mechanical Systems and Signal Processing 142 (2020): 106708.
[35] Noei, Mohammadreza, and Mohammad Saniee Abadeh. "A genetic asexual reproduction optimization algorithm for imputing missing values." In 2019 9th International Conference on Computer and Knowledge Engineering (ICCKE), pp. 214-218. IEEE, 2019.
[36] Kim, Chiho, Rohit Batra, Lihua Chen, Huan Tran, and Rampi Ramprasad. "Polymer design using genetic algorithm and machine learning." Computational Materials Science 186 (2021): 110067.
[37] Wei, Han, Hua Bao, and Xiulin Ruan. "Genetic algorithm-driven discovery of unexpected thermal conductivity enhancement by disorder." Nano Energy 71 (2020): 104619.
[38] Hamdia, Khader M., Xiaoying Zhuang, and Timon Rabczuk. "An efficient optimization approach for designing machine learning models based on genetic algorithm." Neural Computing and Applications 33, no. 6 (2021): 1923-1933.
[39] Suresh, Yeresime, and Santanu Ku Rath. "A genetic algorithm based approach for test data generation in basis path testing." arXiv preprint arXiv:1401.5165 (2014).
[41] Reddy, G. Thippa, M. Praveen Kumar Reddy, Kuruva Lakshmanna, Dharmendra Singh Rajput, Rajesh Kaluri, and Gautam Srivastava. "Hybrid genetic algorithm and a fuzzy logic classifier for heart disease diagnosis." Evolutionary Intelligence 13, no. 2 (2020): 185-196.
[42] Ghiduk, Ahmed S. "Automatic generation of basis test paths using variable length genetic algorithm." Information Processing Letters 114, no. 6 (2014): 304-316.
[43] Newman, Michael. "Software errors cost us economy $59.5 billion annually." NIST Assesses Technical Needs of Industry to Improve Software-Testing (2002).
[44] Ammann, Paul, and Jeff Offutt. Introduction to software testing. Cambridge University Press, 2016.
[45] Xiao, Man, Mohamed El-Attar, Marek Reformat, and James Miller. "Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques." Empirical Software Engineering 12, no. 2 (2007): 183-239.
[46] Hinterding, Robert, Zbigniew Michalewicz, and Agoston E. Eiben. "Adaptation in evolutionary computation: A survey." In Proceedings of 1997 Ieee International Conference on Evolutionary Computation (Icec'97), pp. 65-69. IEEE, 1997.
[47] Manikumar, T., A. John Sanjeev Kumar, and R. Maruthamuthu. "Automated test data generation for branch testing using incremental genetic algorithm." Sādhanā 41, no. 9 (2016): 959-976.
[48] Kumar, Sumit, Dilip Kumar Yadav, and Danish Ali Khan. "A novel approach to automate test data generation for data flow testing based on hybrid adaptive PSO-GA algorithm." International Journal of Advanced Intelligence Paradigms 9, no. 2-3 (2017): 278-312.
[49] Mansouri, Ardeshir, Mohammadreza Noei, and Mohammad Saniee Abadeh. "Predicting Hospital Length of Stay of Neonates Admitted to the NICU Using Data Mining Techniques." In 2020 10th International Conference on Computer and Knowledge Engineering (ICCKE), pp. 629-635. IEEE, 2020.
[50] Damia, Amirhosein, Mehdi Esnaashari, and Mohammadreza Parvizimosaed. "Adaptive Genetic Algorithm Based on Mutation and Crossover and Selection Probabilities." In 2021 7th International Conference on Web Research (ICWR), pp. 86-90. IEEE, 2021.
[51] Damia, Amirhosein, Mehdi Esnaashari, and Mohammadreza Parvizimosaed. "Automatic Web-Based Software Structural Testing Using an Adaptive Particle Swarm Optimization Algorithm for Test Data Generation." In 2021 7th International Conference on Web Research (ICWR), pp. 282-286. IEEE, 2021.
[52] Parvizimosaed, Mohammadreza, Mohammadreza Noei, Mohammadmostafa Yalpanian, and Javad Bahrami. "A Containerized Integrated Fast IoT Platform for Low Energy Power Management." In 2021 7th International Conference on Web Research (ICWR), pp. 318-322. IEEE, 2021.
[53] Esnaashari, Mehdi, and Amir Hossein Damia. "Automation of Software Test Data Generation Using Genetic Algorithm and Reinforcement Learning." Expert Systems with Applications (2021): 115446.
[54] McCabe, Thomas J. "A complexity measure." IEEE Transactions on software Engineering 4 (1976): 308-320.
[55] Saadtjoo, M. A., and S. M. Babamir. "Optimizing Cost Function in Imperialist Competitive Algorithm for Path Coverage Problem in Software Testing." Journal of AI and Data Mining 6, no. 2 (2018): 375-385.
)