تحلیل مقایسه ای بهبودهای اخیر الگوریتم بهینه سازی ازدحام ذرات در تولید خودکار داده های آزمون نرم افزار
محورهای موضوعی : مجله فناوری اطلاعات در طراحی مهندسیمجتبی صالحی 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.
|
Information Technology in Engineering Design https://sanad.iau.ir/journal/ited | |
Comparative Analysis of the Latest Improvements of Particle Swarm Optimization Algorithms on Automated Software Test Data Generation
Mojtaba Salehi(1) Saeed Parsa(2) * Saba Joudaki(3) Hoshang Kolivand(4) (1) Department of Computer Engineering, Bo. C., Islamic Azad University, Borujerd, Iran (2) Department of Computer Engineering, Tehran Branch, Iran University of Science and Technology, Tehran, Iran* (3) Department of Computer Engineering, Khor.C., Islamic Azad University, Khorramabad, Iran (4) School of Computer Science and Maths, Liverpool John Moores University, L3 3AF, Liverpool, UK
(Date received: 1403/09/08 Date accepted: 1404/02/27)
| |
Abstract This study examines enhancements to Particle Swarm Optimization (PSO) algorithms for generating automated software test data, with a focus 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 (EBPSO) 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. Keywords: Test data generation, meta-heuristic algorithms, particle swarm optimization, path coverage
Corresponding author:* Saeed Parsa Address: Department of Computer Engineering, Tehran Branch, Iran University of Science and Technology, Tehran, Iran
Email: parsa@iust.ac.ir | |
1- Introduction
Although random testing is a low-cost approach to software testing, it struggles to address complex constraints and achieve comprehensive structural coverage. Search-based software testing (SBST) utilizes optimization techniques to generate test data, thereby efficiently overcoming these limitations. SBST leverages meta-heuristic algorithms, which excel at navigating large search spaces without assumptions about problem characteristics. Foundational studies by McMinn [1] and Harman et al. [2] highlighted the effectiveness of meta-heuristic approaches, including Particle Swarm Optimization (PSO) [3], Hill Climbing (HC) [4], Tabu Search (TS) [5], Ant Colony Optimization (ACO) [6], Differential Evolution (DE) [7], Artificial Bee Colony (ABC) [8], and Firefly Algorithm (FA) [9].
Significant advancements in these algorithms have enhanced their adaptability and performance. Liang et al. [10] introduced a DE algorithm with a one-test-at-a-time strategy, achieving notable improvements in solution quality through parameter optimization. Malhotra et al. [11] demonstrated that ABC outperformed ACO and GA in test data generation due to its efficient parallelism and neighborhood production mechanism. Similarly, Srivatsava et al. [12] employed the FA to optimize test paths, demonstrating its ability to minimize test efforts through features like guidance matrices and cyclomatic complexity-based traversal.
Inspired by swarm intelligence, PSO has emerged as a leading method for generating test data. PSO optimizes candidate solutions for improved coverage and efficiency by iteratively updating the positions and velocities of particles. Tiwari et al. [3] applied a PSO variant to regression testing, achieving superior path coverage. Jatana et al. [13] compared PSO with GA in mutation testing, finding that PSO offered faster convergence and smaller test suites. Sahoo et al. [14] introduced an Improved Combined Fitness function with Adaptive PSO (APSO), showcasing its ability to enhance critical path coverage.
This paper investigates the performance of ten advanced PSO variants in automated test data generation. Among these, Algorithm A5 emerged as the most effective, utilizing innovative solution-updating strategies that adapt to search space conditions. By balancing exploration and exploitation, Algorithm A5 mitigates the entrapment in local optima, enhances population diversity, and leverages collective intelligence to navigate the search space efficiently.
The rest of this paper is structured as follows: Section 2 reviews related work on SBST and PSO applications. Section 3 outlines the theoretical background supporting the proposed approach. Section 4 introduces the improved PSO algorithms, details the experimental setup, and presents a comparative analysis of their performance. Finally, Section 5 summarizes the findings, emphasizing the superiority of Algorithm A5, and discusses potential directions for future research.
2- Related Work
Test data generation is a critical challenge in software testing, with random testing often failing under complex constraints. Search-based software testing (SBST) employs meta-heuristic algorithms, such as Particle Swarm Optimization (PSO) [3], Hill Climbing [4], and Differential Evolution (DE) [7], to address these issues by efficiently navigating large search spaces without assumptions about problem characteristics [1, 2]. Liang et al. [10] improved DE with a one-test-at-a-time strategy, while Malhotra et al. [11] showed ABC's superiority in path coverage due to its robust parallelism. Srivatsava et al. [12] optimized test paths using the Firefly Algorithm (FA), and Lv et al. [15] proposed a metamorphic relations-based approach as an alternative to PSO despite its reliance on domain expertise.
PSO has demonstrated notable success in testing, with Tiwari et al. [3] applying it to regression testing and Sahoo [14] enhancing it with a fitness function to achieve 100% path coverage. Saadatjoo [16] and Ghiduk [17] demonstrated the potential of evolutionary and PSO-based methods for optimizing test data generation. Recent efforts, including Damia's adaptive PSO [21, 22] and Esnaashari's hybrid memetic algorithm [23], have addressed the limitations of PSO, such as entrapment in local optima and convergence issues. Researchers such as Semujju [19] and Rajagopal [20] have developed adaptive and hybrid approaches, enhancing efficiency in challenging testing scenarios.
These studies affirm the versatility of PSO and its variants in tackling diverse software testing challenges, with continuous innovations improving adaptability, efficiency, and coverage.
3- Background
This section describes the theoretical background being used in our proposed approach. This section introduces the basic concepts of software testing, path testing, and fitness functions, which will help us understand the test data generation based on the PSO algorithm.
3-1- Control Flow Graph
The control flow graph was constructed using source code. Source code is taken as input, and the instrumented code is generated [1]. After that, instrumented code is parsed and stored, line by line, in the adjacency list. CFG for a program 𝑃 is a directed graph 𝐺 = (𝑁, 𝐸) consisting of N as a set of nodes and E as a set of edges. A node represents a statement or a basic block of statements [2]. An edge represents the flow of control between nodes. CFG is generated using software such as Visustin or the pycfg or staticfg library in the Python programming language, and then extracts the paths of this graph from the desired graph. An example of the flow graph with the resulting program from Visustin output is shown in Fig.1.
Figure 1: Corresponding CFG sample method, b: a sample source code c: instrumented method
3-2- Initial Population
The initial population of particles in the PSO algorithm can be considered the initial test data set. Each particle (or test data set) is initialized with a random set of values within the defined bounds of the search space [3]. The data structure considered here for PSO-improved algorithms is a matrix structure, where the number of matrix columns equals the product of the number of program variables and their paths [4]. Suppose there are m execution paths, 3-3- Fitness Function The fitness function is a crucial component of search algorithms used to assess the quality of various solutions. The solution (test data) needs to be provided as input to the program under test, which is then executed, and its path coverage is measured. If the number of paths of the program under test is denoted as NP and the number of paths covered by the PSO algorithm is denoted as TP, in all implementation algorithms, the fitness of each solution (i) is calculated using Eq. (1): 
to 
, to be covered by n test data, 
to 
. Each test data, 
, is a vector (
,
..., 
), of m elements where each element is an input variable.
| (1) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Algorithm. Simple PSO ŒInput: (1) the program under test P, and The variable (a1, a2, a3, …., an) is the variable list of P ; (2) structural coverage criterion target path ; (3) algorithm parameter of PSO. n, w, c1, c2, and Vmax; (4) the maximum evolution generation max_gen. ŒOutput: test data set TS satisfying the target path. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
01 encode input list variable into a m-dimension position vector; 02 instrument program P for gathering structural coverage information; 03 initialize the velocity vector ŒTest Suite Generation 04 while(Max_iteration) 06 for each particle i in the population with size n 07 for each dimension ( 08 Calculate the current velocity of particle i in dimension d; 09 if 10 adjust it within the boundary; 11 endif 12 calculate the current position 13 endfor 14 decode vector 15 execute the program with the test case tci and collect the coverage information to calculate the fitness f (Xi) ; 16 if 17 pbesti = Xi 18 endif 19 if gbest=Xi 20 endif 21 end for 22 end while 23 return TS = (tci ) ; Figure 2: Algorithm simple Pso
We must encode the input list (a1, a2, a3,…, an) into an m-dimensional position vector at the initialization stage. Path coverage is a criterion commonly applied in structural methods of test data generation. To calculate the fitness value of each particle (test case), we should instrument the program under test P to gather the coverage information about construct elements. On the other hand, some random values are utilized to initialize the velocity vector V_i^dand position vector X_i^d. In the algorithm body, the procedure between lines 07 and 14 is used to determine the current position X_i^d of particle i at different dimensions d. In line 14, each particle vector Xi in the population is decoded into a test case. Then, the fitness of each test case f (Xi) is evaluated. Based on the fitness value of each particle (test case), the personal best position, pbesti, and the global best position, best, can be updated (lines 16-20). The termination condition in line 05 controls the whole particle evolution process. For the testing problem, the termination condition can be the following two cases: (1) all construct elements have been covered, or (2) the maximum evolution generation max_gen is reached
3-4-2- Improved PSO Algorithms This section compares the ten most recent improved versions introduced by the particle swarm optimization algorithm for automatic test data generation. Particle swarm optimization (PSO) has been widely applied in various optimization fields due to its ease of implementation and high efficiency. However, it suffers from limitations, such as slow and premature convergence, when solving high-dimensional optimization problems. This paper attempts to address these critical issues. A1 to A10 are, respectively, different versions of PSO-improved algorithms. In research A1 [6], writers propose a novel PSO algorithm called Chaos Adaptive Particle Swarm Optimization (CAPSO), which adaptively adjusts the inertia weight parameter w and acceleration coefficients c1, c2, and introduces a controlling factor γ based on chaos theory to adaptively adjust the range of chaotic search. A2 is the standard particle swarm algorithm. In A3 [7], a new method of parameter adjustment, known as piecewise nonlinear acceleration coefficients, is introduced to the simplified particle swarm optimization algorithm (SPSO). An improved algorithm, referred to as piecewise-nonlinear-acceleration-coefficients-based SPSO (P-SPSO), is then proposed. Then, a mean differential mutation strategy is developed for the update mechanism of P-SPSO, and another improved algorithm named mean-differential-mutation-strategy embedded P-SPSO (MP-SPSO) is proposed. A4 [8] introduced appropriate improvements to PSO and proposed a novel chaotic PSO variant with arc tangent acceleration coefficient (CPSO-AT). A5 [31] presents a new particle swarm optimization (EBPSO) algorithm. Firstly, based on an adaptive adjustment mechanism, the algorithm can select a more effective strategy from two search equations to balance exploration and exploitation abilities. Secondly, to utilize the information from individual historical optimal solutions and the optimal solution of the current population, a weight is introduced to adjust their influence in the search equation. Thirdly, by introducing population diversity, a dynamic equation for adjusting the algorithm's searchability is proposed. Finally, to avoid falling into a local optimum and to explore potential locations, a dynamic random search mechanism is proposed, which utilizes information from the current optimal solution. In A6 [9], a constraint factor is introduced to control the velocity weight and reduce blindness in the search process. A dual-update (DU) strategy is based on new speed and position update strategies that are designed. Research A7 [10] proposed a PSO algorithm with an adaptive two-population strategy (PSO-ATPS), which adaptively divides a population into two groups representing excellent and ordinary populations. Inspired by animal hunting behavior, a new velocity–position update method is proposed for the general population. A velocity update formulation with decreasing inertia weights based on logistic chaotic mapping is applied to the excellent population. In A8 [11], an improved particle swarm optimization (PSO) with adaptive weighted delay velocity (PSO-AWDV) is proposed. A new scheme blending weighted delay velocity is first presented for a new PSO with a weighted delay velocity (PSO-WDV) algorithm. Then, to adaptively update the velocity inertia weight, an adaptive PSO-AWDV algorithm is developed based on the evolutionary state of the particle swarm evaluated via a new estimation method. In A9 [12], a hybrid HPSO-SSM algorithm is developed in which three significant improvements are made to the original PSO: First, a logistic map sequence is used to adjust the inertial weight 𝜔, which provides sufficient variety and facilitates the avoidance of optimal solutions throughout the selection process. Second, a significantly improved update equation for creating the next-generation position is proposed, which can more effectively integrate exploration and exploitation. Third, a spiral-shaped mechanism (SSM) is coupled to the original PSO as a local search strategy for the known optimum solution. In A10 [13], a novel randomized particle swarm optimizer (RPSO) is proposed. The Gaussian white noise with adjustable intensity is utilized to randomly perturb the acceleration coefficients to explore the problem space more thoroughly.
4- Experiments and results This study conducted two distinct experiments employing ten advanced Particle Swarm Optimization (PSO) algorithms (A1 through A10) to address five benchmark software problems. The first experiment focused on a comparative analysis of the meta-heuristics discussed in the paper, utilizing predetermined control parameter values. This comparison assessed the algorithms' performance based on the coverage metric and included a runtime analysis, emphasizing the importance of time efficiency in algorithm selection. Given that the fitness function directs the algorithms within the search space, the effectiveness of these functions was evaluated against the path coverage criterion. The second experiment conducted a comparative analysis of the success rates of algorithms derived from the first experiment, providing deeper insights into their performance and effectiveness. 4-1- Experimental setup An architecture based on actual value execution was used for the experiments. It consisted of a program analyzer, a path selector, and a test data generator. A program analyzer is provided with source code and generates a suitable representation (e.g., a control flow graph, a data dependence graph, or a program dependence graph) for subsequent analysis. Following the generation of test paths by the path selector, the test data generator generates path information for the specified test paths. The path selector utilizes this path information to regenerate the paths until a coverage criterion is met. The study utilized five benchmark problems, which comprised the following: triangle, quadratic equation, Max-Min number, leap year, and Fibonacci of marks. Triangle: The program checks whether a triangle can be formed using the given sides. If a triangle is formed, the program classifies the type of triangle as isosceles, equilateral, or scalene. Quadratic Equation: The program checks whether three input scans form a quadratic equation. If a quadratic equation is formed, then the roots of the equation are found. Max-Min: The program finds the largest and smallest numbers among input numbers. Leap: The program checks whether a given year is a leap year. Fibonacci: A Fibonacci program is a program that generates the Fibonacci sequence. The Fibonacci sequence is a series of numbers where each is the sum of the two preceding ones, starting from 0 to 1. In all of the problems, solutions were encoded using integer representation. Experiments were conducted on a platform equipped with an Intel(R) Core(TM) i7-6820HQ CPU at 2.70 GHz and 16 GB of RAM. All code fragments of the problems in Table 1 were implemented using the Python programming language.
Table 1: Properties of the benchmark problems used in the experiments
4-2- Experiment 1: Comparison of Improved PSO Algorithms The decision for the termination criteria is based on whether at least one test datum has traversed the target path or if the number of evolution iterations has reached the preset value. In either case, the evolution process will stop. Table 2 compares the results based on the coverage, evaluation, and time(s) criteria. Regarding the mean evaluations for the Quadratic Equation program, A5 generates path-oriented data more efficiently than other algorithms, and A4 has the worst mean evaluations among all algorithms. Regarding the search time for each approach, the mean A5 has the least search time, while A7 has the worst time. Regarding the mean coverage for the Quadratic Equation program, A3, A5, and A9 have achieved 100% coverage, while A10 has the lowest coverage. It shows that the paper performs best in this test code sample. Regarding the mean evaluations for the triangle classifier program, the paper for generating path-oriented data has the lowest evaluations compared to other Algorithms, and A2 has the worst mean evaluations among all algorithms. Regarding the mean coverage for the triangle classifier program, A3, A5, and A9 have reached 100% coverage. And A2 has the worst coverage. It shows that the paper performs best in this test code sample. Regarding the mean evaluations for the Leap program, A4 for generating path-oriented data has the lowest mean evaluations compared to other Algorithms, and A7 has the worst mean evaluations among all algorithms. Regarding the search time for each approach, the mean A2 has the least search time, while A8 has the worst time. Regarding the mean coverage for the Leap program, A1, with a coverage of 0.94, is the best, and A7 has the worst coverage. It shows that the paper performs best in this test code sample. Regarding the mean evaluations for the Max-Min program, A3 generates path-oriented data more efficiently than other algorithms, and A8 has the worst mean evaluations among all algorithms. For the search time of each approach, the mean A3 has the least search time, while A9 has the worst time. In terms of the mean coverage for the Max-Min program, A2, A3, A5, A6, A8, and A9 have reached 100% coverage. And A4 and A7 have the worst coverage. It shows that the paper performs best in this test code sample. Regarding the mean evaluations for the Fibonacci program, A5 yields the lowest results among other algorithms for generating path-oriented data, and A3 has the worst mean evaluations among all algorithms. Regarding the search time for each approach, the mean A3 and A5 have the shortest search times, while A8 has the longest time. Regarding the mean coverage for the Fibonacci program, A5 with 100% coverage is the most effective, while A10 has the worst coverage. It shows that the paper performs best in this test code sample. The experiments were repeated for the search space bounded by the range [-100, 100] to observe the algorithms' behavior in a constrained search space. We reported the mean and standard deviation in the first line, the median, and the rank of each algorithm in the second line of each cell. The number of evaluations and CPU times (in seconds) required to achieve maximum coverage were also reported in Table 2. The results produced by the algorithms were different versions of the PSO algorithm, ranging from A1 to A10, which were used, respectively. For a better understanding of Table 2, its structure is further explained in Figure 3.
Figure 3: Structure of Table 2 Table 2: The results of the algorithms designed using a fitness function. Mean ∓ standard deviation are reported. Median values are given in parentheses, and ranks are presented next to the median.
4-3- Experiment 2: comparison of success rate criteria The next criterion for evaluating the efficiency of algorithms is the success rate. The success rate is calculated based on Eq. 4.
مقالات مرتبط
حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات دانشگاه آزاد اسلامی است. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
