تحلیل مقایسه ای بهبودهای اخیر الگوریتم بهینه سازی ازدحام ذرات در تولید خودکار داده های آزمون نرم افزار
محورهای موضوعی : مجله فناوری اطلاعات در طراحی مهندسیمجتبی صالحی 1 , سعید پارسا 2 * , صبا جودکی 3 , هوشنگ کولیوند 4
1 - گروه کامپیوتر، دانشگاه آزاد اسلامی، واحد بروجرد، بروجرد، ایران
2 -
3 - گروه کامپیوتر، دانشگاه آزاد اسلامی، واحد خرم آباد، خرم آباد، ایران
4 - School of computer science and mathematics, faculty of engineering and technology, liverpool john moores university, united kingdom
کلید واژه: آزمون نرم افزار, الگوریتم های متاهیوریستیک, بهینه سازی ازدحام ذرات, پوشش مسیر,
چکیده مقاله :
این مطالعه به بررسی بهبودهای الگوریتم‌های بهینه‌سازی ازدحام ذرات (PSO) برای تولید خودکار داده‌های آزمون نرم‌افزار می‌پردازد و بر پوشش مسیر در نرم افزارها تمرکز دارد. PSO به دلیل مقیاس‌پذیری و سادگی ارزشمند است و از طریق بهبودهای مختلف الگوریتمی برای رفع چالش‌هایی مانند گیر افتادن در بهینه محلی و ناکارآمدی همگرایی ارتقا یافته است. در این مقاله ده نسخه بهبود یافته اخیر PSO را در برنامه‌های معیار ارزیابی می‌کند و عملکرد آنها را بر اساس پوشش، زمان اجرا و نرخ موفقیت مقایسه می‌نماید. در میان این الگوریتم‌ها، الگوریتم A5 عملکرد برتری را نشان داده و در ایجاد توازن بین اکتشاف و بهره‌برداری، تنوع جمعیت و کارایی همگرایی به طور چشمگیری برتر عمل کرده است. نتایج تجربی، کارآمدی رویکردهای فراابتکاری را در تولید داده‌های آزمون در فضای جستجوی بزرگ نشان می دهد. همچنین الگوریتم A5 را به‌عنوان یک راه‌حل پیشرو جهت تولید داده آزمون در فرآیندهای آزمون نرم‌افزار معرفی می‌کند.
This study explores improvements in Particle Swarm Optimization (PSO) algorithms for automated software test data generation, focusing on path coverage in software systems. PSO, valued for its scalability and simplicity, has been enhanced through various algorithmic improvements to address challenges like local optima entrapment and convergence inefficiencies. The research evaluates ten recent PSO variants on benchmark programs, comparing their performance based on coverage, runtime, and success rates. Among these, the A5 algorithm demonstrated superior performance, excelling in exploration-exploitation balance, population diversity, and convergence efficiency. Experimental results affirm the efficacy of meta-heuristic approaches in generating test data across expansive search spaces, positioning A5 as a leading solution for test data generation in optimizing software testing processes.
[1] P. McMinn, Search‐based software test data generation: a survey, Software testing, Verification and reliability, 14 (2004) 105-156.
[2] M. Harman, P. McMinn, J.T. De Souza, S. Yoo, Search based software engineering: Techniques, taxonomy, tutorial, in: LASER Summer School on Software Engineering, (Springer, 2008), pp. 1-59.
[3] S. Tiwari, K. Mishra, A.K. Misra, Test case generation for modified code using a variant of particle swarm optimization (PSO) algorithm, in: 2013 10th International Conference on Information Technology: New Generations, (IEEE, 2013), pp. 363-368.
[4] M. Khari, A. Sinha, E. Verdu, R.G. Crespo, Performance analysis of six meta-heuristic algorithms over automated test suite generation for path coverage-based optimization, Soft Computing, 24 (2020) 9143-9160.
[5] G. Bhattacharjee, P. Pati, A novel approach for test path generation and prioritization of uml activity diagrams using tabu search algorithm, International Journal of Scientific & Engineering Research, 5 (2014) 1212-1217.
[6] C. Mao, L. Xiao, X. Yu, J. Chen, Adapting ant colony optimization to generate test data for software structural testing, Swarm and Evolutionary Computation, 20 (2015) 23-36.
[7] W. Jianfeng, W. Changan, J. Shouda, Test data generation algorithm of combinatorial testing based on differential evolution, in: 2013 Third International Conference on Instrumentation, Measurement, Computer, Communication and Control, (IEEE, 2013), pp. 544-548.
[8] D. Karaboga, An idea based on honey bee swarm for numerical optimization, in, (Technical report-tr06, Erciyes university, engineering faculty, computer …, 2005).
[9] X.-S. Yang, Nature-inspired metaheuristic algorithms, (Luniver press, 2010).
[10] X. Liang, S. Guo, M. Huang, X. Jiao, Combinatorial Test Case Suite Generation Based on Differential Evolution Algorithm, J. Softw., 9 (2014) 1479-1484.
[11] R. Malhotra, C. Anand, N. Jain, A. Mittal, Comparison of search based techniques for automated test data generation, International Journal of Computer Applications, 95 (2014).
[12] P.R. Srivatsava, B. Mallikarjun, X.-S. Yang, Optimal test sequence generation using firefly algorithm, Swarm and Evolutionary Computation, 8 (2013) 44-53.
[13] N. Jatana, B. Suri, Particle swarm and genetic algorithm applied to mutation testing for test data generation: a comparative evaluation, Journal of King Saud University-Computer and Information Sciences, 32 (2020) 514-521.
[14] R.R. Sahoo, M. Ray, PSO based test case generation for critical path using improved combined fitness function, Journal of King Saud University-Computer and Information Sciences, 32 (2020) 479-490.
[15] X.-W. Lv, S. Huang, Z.-W. Hui, H.-J. Ji, Test cases generation for multiple paths based on PSO algorithm with metamorphic relations, Iet Software, 12 (2018) 306-317.
[16] M.A. Saadatjoo, S.M. Babamir, Test-data generation directed by program path coverage through imperialist competitive algorithm, Science of Computer Programming, 184 (2019) 102304.
[17] A.S. Ghiduk, M.R. Girgis, E. Hassan, S. Aljahdali, Automatic PSO Based Path Generation Technique for Data Flow Coverage, INTELLIGENT AUTOMATION AND SOFT COMPUTING, 29 (2021) 147-164.
[18] R. Ferreira Vilela, J. Choma Neto, V.H. Santiago Costa Pinto, P.S. Lopes de Souza, S. do Rocio Senger de Souza, Bio‐inspired optimization to support the test data generation of concurrent software, Concurrency and Computation: Practice and Experience, 35 (2023) e7489.
[19] S.D. Semujju, H. Huang, F. Liu, Y. Xiang, Z. Hao, Search-Based Software Test Data Generation for Path Coverage Based on a Feedback-Directed Mechanism, Complex System Modeling and Simulation, 3 (2023) 12-31.
[20] M. Rajagopal, R. Sivasakthivel, K. Loganathan, L.E. Sarris, An Automated Path-Focused Test Case Generation with Dynamic Parameterization Using Adaptive Genetic Algorithm (AGA) for Structural Program Testing, Information, 14 (2023) 166.
[21] A. Damia, M. Esnaashari, M. Parvizimosaed, Software Testing using an Adaptive Genetic Algorithm, Journal of AI and Data Mining, 9 (2021) 465-474.
[22] A. Damia, M. Esnaashari, M. 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), (IEEE, 2021), pp. 282-286.
[23] M. Esnaashari, A.H. Damia, Automation of software test data generation using genetic algorithm and reinforcement learning, Expert Systems with Applications, 183 (2021) 115446.
[24] S. Jiang, J. Shi, Y. Zhang, H. Han, Automatic test data generation based on reduced adaptive particle swarm optimization algorithm, Neurocomputing, 158 (2015) 109-116.
[25] S. Varshney, M. Mehrotra, C. Saini, An Adaptive PSO-based Approach for Data Flow Coverage of a Program.
[26] X. Han, H. Lei, Y.-s. Wang, Multiple paths test data generation based on particle swarm optimisation, IET Software, 11 (2017) 41-47.
[27] C. Mao, X. Yu, J. Chen, Swarm intelligence-based test data generation for structural testing, in: 2012 IEEE/ACIS 11th International Conference on Computer and Information Science, (IEEE, 2012), pp. 623-628.
[28] Y. Duan, N. Chen, L. Chang, Y. Ni, S.S. Kumar, P. Zhang, CAPSO: Chaos adaptive particle swarm optimization algorithm, Ieee Access, 10 (2022) 29393-29405.
[29] M. Lin, Z. Wang, F. Wang, D. Chen, Improved simplified particle swarm optimization based on piecewise nonlinear acceleration coefficients and mean differential mutation strategy, IEEE Access, 8 (2020) 92842-92860.
[30] Z. Ma, X. Yuan, S. Han, D. Sun, Y. Ma, Improved chaotic particle swarm optimization algorithm with more symmetric distribution for numerical function optimization, Symmetry, 11 (2019) 876.
[31] Y. Zhang, X. Kong, A particle swarm optimization algorithm with empirical balance strategy, Chaos, Solitons & Fractals: X, 10 (2023) 100089.
[32] Y. Song, Y. Liu, H. Chen, W. Deng, A Multi-Strategy Adaptive Particle Swarm Optimization Algorithm for Solving Optimization Problem, Electronics, 12 (2023) 491.
[33] M. Zhao, H. Zhao, M. Zhao, Particle swarm optimization algorithm with adaptive two-population strategy, IEEE Access, (2023).
[34] L. Xu, B. Song, M. Cao, An improved particle swarm optimization algorithm with adaptive weighted delay velocity, Systems Science & Control Engineering, 9 (2021) 188-197.
[35] Z. Ahmad, J. Li, T. Mahmood, Adaptive Hyperparameter Fine-Tuning for Boosting the Robustness and Quality of the Particle Swarm Optimization Algorithm for Non-Linear RBF Neural Network Modelling and Its Applications, Mathematics, 11 (2023) 242.
[36] W. Liu, Z. Wang, N. Zeng, Y. Yuan, F.E. Alsaadi, X. Liu, A novel randomised particle swarm optimizer, International Journal of Machine Learning and Cybernetics, 12 (2021) 529-540.