An Improved Genetic Algorithm for Multi-Objective Test Suite Optimization in Agile Software Development
Article Sidebar
Main Article Content
Abstract
Regression testing in agile development requires selecting a compact, fault-effective subset of test cases from a growing suite within strict sprint time constraints. This challenge is a multi-objective combinatorial optimization problem requiring simultaneous maximization of fault detection rate (FDR), minimization of execution cost, and maintenance of code coverage breadth. Standard single-objective approaches sacrifice one dimension, while NSGA-II ignores structural dependency relationships among test modules.
This paper proposes IGA-MO (Improved Genetic Algorithm for Multi-Objective optimization), extending NSGA-II with three innovations: (1) a semantic-aware crossover that builds a dependency graph from Jaccard similarity of McCabe-Halstead metric vectors and exchanges connected component blocks; (2) an adaptive mutation mechanism driven by Hamming distance diversity monitoring; and (3) a bounded elite archive with crowding-distance truncation. A complete Algorithm 1 pseudocode and full equation explanations are provided.
Experiments use the NASA CM1 dataset from the PROMISE Repository — 498 real C-language software modules from NASA satellite flight software with 49 NASA-verified defects (9.8%) and 21 McCabe and Halstead metrics. Over 10 independent runs, IGA-MO achieves a mean FDR of 63.1% (±18.4%) with 60.5% suite reduction, significantly outperforming random selection (Wilcoxon W=50.0, p=0.0098). All results are fully measured on real NASA data.
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
[1] J. Sayyad Shirabad and T. J. Menzies, "The PROMISE Repository of Software Engineering Databases," University of Ottawa, Canada, 2005. [Online]: http://promise.site.uottawa.ca/SERepository
[2] T. J. McCabe, "A complexity measure," IEEE Trans. Softw. Eng., vol. SE-2, no. 4, pp. 308–320, 1976, doi: 10.1109/TSE.1976.233837.
[3] M. H. Halstead, Elements of Software Science. New York, NY: Elsevier, 1977.
[4] M. Harman and B. F. Jones, "Search-based software engineering," Inf. Softw. Technol., vol. 43, pp. 833–839, 2001, doi: 10.1016/S0950-5849(01)00189-6.
[5] P. McMinn, "Search-based software test data generation: A survey," Softw. Test. Verif. Reliab., vol. 14, pp. 105–156, 2004, doi: 10.1002/stvr.294.
[6] S. Yoo and M. Harman, "Regression testing minimisation, selection and prioritisation: A survey," Softw. Test. Verif. Reliab., vol. 22, pp. 67–120, 2012, doi: 10.1002/stvr.430.
[7] Z. Li, M. Harman, and R. M. Hierons, "Search algorithms for regression test case prioritization," IEEE Trans. Softw. Eng., vol. 33, pp. 225–237, 2007, doi: 10.1109/TSE.2007.38.
[8] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Trans. Evol. Comput., vol. 6, pp. 182–197, 2002, doi: 10.1109/4235.996017.
[9] M. G. Epitropakis, S. Yoo, M. Harman, and E. K. Burke, "Empirical evaluation of Pareto efficient multi-objective regression test case prioritisation," in Proc. ACM ISSTA, 2015, pp. 234–245, doi: 10.1145/2771783.2771788.
[10] M. A. Noor, H. B. Z. Abidin, and A. A. A. Ghani, "A modified SPEA2 for multi-objective test case prioritization," J. Softw. Evol. Process, vol. 32, 2020, doi: 10.1002/smr.2223.
[11] E. Zitzler, M. Laumanns, and L. Thiele, "SPEA2: Improving the strength Pareto evolutionary algorithm," TIK Rep. 103, ETH Zurich, 2001.
[12] T. Menzies, J. Greenwald, and A. Frank, "Data mining static code attributes to learn defect predictors," IEEE Trans. Softw. Eng., vol. 33, pp. 2–13, 2007, doi: 10.1109/TSE.2007.256941.
[13] S. Lessmann, B. Baesens, C. Mues, and S. Pietsch, "Benchmarking classification models for software defect prediction," IEEE Trans. Softw. Eng., vol. 34, pp. 485–496, 2008, doi: 10.1109/TSE.2008.35.
[14] S. Elbaum, A. G. Malishevsky, and G. Rothermel, "Test case prioritization: A family of empirical studies," IEEE Trans. Softw. Eng., vol. 28, pp. 159–182, 2002, doi: 10.1109/32.988497.
[15] M. Srinivas and L. M. Patnaik, "Adaptive probabilities of crossover and mutation in genetic algorithms," IEEE Trans. Syst. Man Cybern., vol. 24, pp. 656–667, 1994, doi: 10.1109/21.286385.
[16] A. Marchetto and P. Tonella, "Search-based testing of Ajax web applications," in Proc. SSBSE, 2009, pp. 3–12, doi: 10.1109/SSBSE.2009.7.
[17] R. Sagarna and S. M. Yuen, "Parallel search for test data generation," in Proc. IEEE CEC, 2010, pp. 1–8, doi: 10.1109/CEC.2010.5586095.
[18] F. Wilcoxon, "Individual comparisons by ranking methods," Biom. Bull., vol. 1, pp. 80–83, 1945, doi: 10.2307/3001968.
[19] R. Just, D. Jalali, and M. D. Ernst, "Defects4J: A database of existing faults," in Proc. ACM ISSTA, 2014, pp. 437–440, doi: 10.1145/2610384.2628055.
[20] N. Gupta, A. Sharma, and M. K. Pachariya, "Multi-objective test suite optimization," J. King Saud Univ. Comput. Inf. Sci., 2020, doi: 10.1016/j.jksuci.2020.01.009.