Evaluating the performance of NSGA-II and NSGA-III on Product Line Architecture Design
Resumo
Product Line Architecture (PLA) design can be modeled as an optimization problem to be solved with search-based algorithms. PLA design optimization has successfully been done using the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) in scenarios involving up to three objectives, which involve software metrics for properties such as feature modularization, PLA extensibility, and cohesion. As many of these properties may be desired in a PLA at the same time, more than three objectives might need to be optimized simultaneously. The Non-Dominated Sorting Genetic Algorithm III (NSGA-III) was designed to solve problems impacted by more than three objectives, named many-objective problems, so it might suit this need. However, NSGA-III has not yet been applied in the context of PLA design. In this sense, this study aims to compare the performance of NSGA-II and NSGA-III for PLA design to uncover which algorithm best fits this problem. To accomplish this goal, we implemented a specialized version of NSGA-III and then ran experiments using both algorithms to optimize eight PLAs with three, four, and five objectives. We evaluate the algorithms’ performance via quality indicators commonly used in search-based software engineering. The empirical results point out that: (i) NSGA-III had a slightly better performance than NSGA-II when optimizing four or five objectives in the context of our study; (ii) NSGA-II was the best or the algorithms tied when the PLA given as input is easier to optimize due to reduced solution space.
Palavras-chave:
product-line architecture, search-based software engineering, multiobjective evolutionary algorithm
Referências
Sven Apel and Dirk Beyer. 2011. Feature cohesion in software product lines: an exploratory study. In Proc. of the ICSE’11 (Waikiki, Honolulu, HI, USA). New York, USA, 421–430.
Andrea Arcuri and Lionel Briand. 2011. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In Proceedings of the 33rd international conference on software engineering. 1–10.
Andrea Arcuri and Lionel Briand. 2014. A hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability 24, 3 (2014), 219–250.
Carlos Vinicius Bindewald, Willian M Freire, Aline M M Miotto Amaral, and Thelma Elita Colanzi. 2019. Towards the support of user preferences in searchbased product line architecture design: an exploratory study. In Proceedings of the XXXIII Brazilian Symposium on Software Engineering (SBES). 387–396. DOI: 10.1145/3350768.3351993
Luiz Carvalho, Alessandro Garcia, Thelma Elita Colanzi, Wesley K. G. Assunção, Juliana Alves Pereira, Baldoino Fonseca, Márcio Ribeiro, Maria Julia de Lima, and Carlos Lucena. 2020. On the Performance and Adoption of Search-Based Microservice Identification with toMicroservices. In 2020 IEEE International Conference on Software Maintenance and Evolution (ICSME). 569–580. DOI: 10.1109/ICSME46990.2020.00060
Soo Ho Chang, Hyun Jung La, and Soo Dong Kim. 2006. Key Issues and Metrics for Evaluating Product Line Architectures. In Proc. of the 18th Int. Conf. on Softw. Engineering & Knowledge Engineering (SEKE) (San Francisco, CA, USA). 212–219.
Thelma Elita Colanzi, Wesley K.G. Assunção, Silvia R. Vergilio, Paulo Roberto Farah, and Giovani Guizzo. 2020. The Symposium on Search-Based Software Engineering: Past, Present and Future. Information and Software Technology 127 (2020), 106372. DOI: 10.1016/j.infsof.2020.106372
Thelma Elita Colanzi and Silvia Regina Vergilio. 2016. A feature-driven crossover operator for multi-objective and evolutionary optimization of product line architectures. Journal of Systems and Software 121 (2016), 126–143. DOI: 10.1016/j.jss.2016.02.026
Thelma Elita Colanzi, Silvia Regina Vergilio, Itana Gimenes, and Willian Nalepa Oizumi. 2014. A search-based approach for software product line design. In Proceedings of the 18th International Software Product Line Conference (SPLC), Vol. 1. 237–241. DOI: 10.1145/2648511.2648537
Indraneel Das and J. E. Dennis. 1998. Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM J. on Optimization 8, 3 (mar 1998), 631–657. DOI: 10.1137/S1052623496307510
Kalyanmoy Deb and Himanshu Jain. 2012. Handling many-objective problems using an improved NSGA-II procedure. In 2012 IEEE Congress on Evolutionary Computation. 1–8. DOI: 10.1109/CEC.2012.6256519
Kalyanmoy Deb and Himanshu Jain. 2014. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE Transactions on Evolutionary Computation 18, 4 (2014), 577–601.
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6 (2002), 182–197. DOI: 10.1109/4235.996017
Juan J. Durillo and Antonio J. Nebro. 2011. jMetal: A Java framework for multiobjective optimization. Advances in Engineering Software 42, 10 (2011), 760–771. DOI: 10.1016/j.advengsoft.2011.05.014
Willian Freire, Cláudia Rosa, Aline Amaral, and Thelma Colanzi. 2022. Validating an Interactive Ranking Operator for NSGA-II to Support the Optimization of Software Engineering Problems. In Proceedings of the XXXVI Brazilian Symposium on Software Engineering (SBES). 337–346.
Willian Marques Freire, Mamoru Massago, Arthur Cattaneo Zavadski, Aline M M Miotto Amaral, and Thelma Elita Colanzi. 2020. OPLA-Tool v2.0: a Tool for Product Line Architecture Design Optimization. In 34th Brazilian Symposium on Software Engineering (SBES). DOI: 10.1145/3422392.3422498
Mark Harman, Yue Jia, Jens Krinke, William B Langdon, Justyna Petke, and Yuanyuan Zhang. 2014. Search based software engineering for software product line engineering: a survey and directions for future work. In Proceedings of the 18th International Software Product Line Conference-Volume 1. 5–18.
Mark Harman and Bryan F Jones. 2001. Search-based software engineering. Information and software Technology 43, 14 (2001), 833–839.
Mark Harman, S Afshin Mansouri, and Yuanyuan Zhang. 2009. Search based software engineering: A comprehensive analysis and review of trends techniques and applications. Department of Computer Science, King’s College London, Tech. Rep. TR-09-03 (2009), 23.
Hisao Ishibuchi, Ryo Imada, Yu Setoguchi, and Yusuke Nojima. 2016. Performance comparison of NSGA-II and NSGA-III on various many-objective test problems. In 2016 IEEE Congress on Evolutionary Computation (CEC). 3045–3052. DOI: 10.1109/CEC.2016.7744174
Muhammad Abid Jamil, Ahmad Alhindi, Muhammad Arif, Mohamed K Nour, Normi Sham Awang Abubakar, and Tareq Fahad Aljabri. 2019. Multiobjective Evolutionary Algorithms NSGA-II and NSGA-III for Software Product Lines Testing Optimization. In 2019 IEEE 6th International Conference on Engineering Technologies and Applied Sciences (ICETAS). 1–5. DOI: 10.1109/ICETAS48360.2019.9117500
Miqing Li and Xin Yao. 2019. Quality Evaluation of Solution Sets in Multiobjective Optimisation: A Survey. Comput. Surveys 52 (03 2019), 1–38. DOI: 10.1145/3300148
F. v. d. Linden, F. Schmid, and E. Rommes. 2007. Software Product Lines in Action - The Best Industrial Practice in Product Line Engineering. Springer.
Mohamed Wiem Mkaouer, Marouane Kessentini, Slim Bechikh, Kalyanmoy Deb, and Mel Ó Cinnéide. 2014. High dimensional search-based software engineering: finding tradeoffs among 15 objectives for automating software refactoring using NSGA-III. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (Vancouver, BC, Canada) (GECCO ’14). Association for Computing Machinery, New York, NY, USA, 1263–1270. DOI: 10.1145/2576768.2598366
Klaus Pohl, Günter Böckle, and van Der Linden Frank J. 2005. Software product line engineering: foundations, principles and techniques (1 ed.). Springer Science & Business Media.
Aurora Ramírez, José Raúl Romero, and Sebastián Ventura. 2016. A comparative study of many-objective evolutionary algorithms for the discovery of software architectures. Empirical Software Engineering 21 (2016), 2546–2600.
SEI. 2009. Software Engineering Institute - The Arcade Game Maker Pedagogical Product Line. [link]. Accessed in 2023 April.
Diego Fernandes Silva, Luiz Fernando Okada, Wesley K. G. Assunção, and Thelma Elita Colanzi. 2022. Intensifying the search-based optimization of product line architectures with crossover operators. Empirical Software Engineering 27 (2022), 166. DOI: 10.1007/s10664-022-10198-3
Yenisei Delgado Verdecia, Thelma Elita Colanzi, Silvia Regina Vergilio, and Marcelo C Benitez Santos. 2017. An Enhanced Evaluation Model for Search-based Product Line Architecture Design.. In CIbSE. 155–168.
T. Young. 2005. Using AspectJ to Build a Software Product Line for Mobile Devices. Master’s thesis. University of British Columbia.
Milan Zeleny and James L Cochrane. 1973. Multiple criteria decision making. University of South Carolina Press.
Eckart Zitzler, Lothar Thiele, Marco Laumanns, Carlos M Fonseca, and Viviane Grunert Da Fonseca. 2003. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation 7 (2003), 117–132.
Andrea Arcuri and Lionel Briand. 2011. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In Proceedings of the 33rd international conference on software engineering. 1–10.
Andrea Arcuri and Lionel Briand. 2014. A hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability 24, 3 (2014), 219–250.
Carlos Vinicius Bindewald, Willian M Freire, Aline M M Miotto Amaral, and Thelma Elita Colanzi. 2019. Towards the support of user preferences in searchbased product line architecture design: an exploratory study. In Proceedings of the XXXIII Brazilian Symposium on Software Engineering (SBES). 387–396. DOI: 10.1145/3350768.3351993
Luiz Carvalho, Alessandro Garcia, Thelma Elita Colanzi, Wesley K. G. Assunção, Juliana Alves Pereira, Baldoino Fonseca, Márcio Ribeiro, Maria Julia de Lima, and Carlos Lucena. 2020. On the Performance and Adoption of Search-Based Microservice Identification with toMicroservices. In 2020 IEEE International Conference on Software Maintenance and Evolution (ICSME). 569–580. DOI: 10.1109/ICSME46990.2020.00060
Soo Ho Chang, Hyun Jung La, and Soo Dong Kim. 2006. Key Issues and Metrics for Evaluating Product Line Architectures. In Proc. of the 18th Int. Conf. on Softw. Engineering & Knowledge Engineering (SEKE) (San Francisco, CA, USA). 212–219.
Thelma Elita Colanzi, Wesley K.G. Assunção, Silvia R. Vergilio, Paulo Roberto Farah, and Giovani Guizzo. 2020. The Symposium on Search-Based Software Engineering: Past, Present and Future. Information and Software Technology 127 (2020), 106372. DOI: 10.1016/j.infsof.2020.106372
Thelma Elita Colanzi and Silvia Regina Vergilio. 2016. A feature-driven crossover operator for multi-objective and evolutionary optimization of product line architectures. Journal of Systems and Software 121 (2016), 126–143. DOI: 10.1016/j.jss.2016.02.026
Thelma Elita Colanzi, Silvia Regina Vergilio, Itana Gimenes, and Willian Nalepa Oizumi. 2014. A search-based approach for software product line design. In Proceedings of the 18th International Software Product Line Conference (SPLC), Vol. 1. 237–241. DOI: 10.1145/2648511.2648537
Indraneel Das and J. E. Dennis. 1998. Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM J. on Optimization 8, 3 (mar 1998), 631–657. DOI: 10.1137/S1052623496307510
Kalyanmoy Deb and Himanshu Jain. 2012. Handling many-objective problems using an improved NSGA-II procedure. In 2012 IEEE Congress on Evolutionary Computation. 1–8. DOI: 10.1109/CEC.2012.6256519
Kalyanmoy Deb and Himanshu Jain. 2014. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE Transactions on Evolutionary Computation 18, 4 (2014), 577–601.
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6 (2002), 182–197. DOI: 10.1109/4235.996017
Juan J. Durillo and Antonio J. Nebro. 2011. jMetal: A Java framework for multiobjective optimization. Advances in Engineering Software 42, 10 (2011), 760–771. DOI: 10.1016/j.advengsoft.2011.05.014
Willian Freire, Cláudia Rosa, Aline Amaral, and Thelma Colanzi. 2022. Validating an Interactive Ranking Operator for NSGA-II to Support the Optimization of Software Engineering Problems. In Proceedings of the XXXVI Brazilian Symposium on Software Engineering (SBES). 337–346.
Willian Marques Freire, Mamoru Massago, Arthur Cattaneo Zavadski, Aline M M Miotto Amaral, and Thelma Elita Colanzi. 2020. OPLA-Tool v2.0: a Tool for Product Line Architecture Design Optimization. In 34th Brazilian Symposium on Software Engineering (SBES). DOI: 10.1145/3422392.3422498
Mark Harman, Yue Jia, Jens Krinke, William B Langdon, Justyna Petke, and Yuanyuan Zhang. 2014. Search based software engineering for software product line engineering: a survey and directions for future work. In Proceedings of the 18th International Software Product Line Conference-Volume 1. 5–18.
Mark Harman and Bryan F Jones. 2001. Search-based software engineering. Information and software Technology 43, 14 (2001), 833–839.
Mark Harman, S Afshin Mansouri, and Yuanyuan Zhang. 2009. Search based software engineering: A comprehensive analysis and review of trends techniques and applications. Department of Computer Science, King’s College London, Tech. Rep. TR-09-03 (2009), 23.
Hisao Ishibuchi, Ryo Imada, Yu Setoguchi, and Yusuke Nojima. 2016. Performance comparison of NSGA-II and NSGA-III on various many-objective test problems. In 2016 IEEE Congress on Evolutionary Computation (CEC). 3045–3052. DOI: 10.1109/CEC.2016.7744174
Muhammad Abid Jamil, Ahmad Alhindi, Muhammad Arif, Mohamed K Nour, Normi Sham Awang Abubakar, and Tareq Fahad Aljabri. 2019. Multiobjective Evolutionary Algorithms NSGA-II and NSGA-III for Software Product Lines Testing Optimization. In 2019 IEEE 6th International Conference on Engineering Technologies and Applied Sciences (ICETAS). 1–5. DOI: 10.1109/ICETAS48360.2019.9117500
Miqing Li and Xin Yao. 2019. Quality Evaluation of Solution Sets in Multiobjective Optimisation: A Survey. Comput. Surveys 52 (03 2019), 1–38. DOI: 10.1145/3300148
F. v. d. Linden, F. Schmid, and E. Rommes. 2007. Software Product Lines in Action - The Best Industrial Practice in Product Line Engineering. Springer.
Mohamed Wiem Mkaouer, Marouane Kessentini, Slim Bechikh, Kalyanmoy Deb, and Mel Ó Cinnéide. 2014. High dimensional search-based software engineering: finding tradeoffs among 15 objectives for automating software refactoring using NSGA-III. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (Vancouver, BC, Canada) (GECCO ’14). Association for Computing Machinery, New York, NY, USA, 1263–1270. DOI: 10.1145/2576768.2598366
Klaus Pohl, Günter Böckle, and van Der Linden Frank J. 2005. Software product line engineering: foundations, principles and techniques (1 ed.). Springer Science & Business Media.
Aurora Ramírez, José Raúl Romero, and Sebastián Ventura. 2016. A comparative study of many-objective evolutionary algorithms for the discovery of software architectures. Empirical Software Engineering 21 (2016), 2546–2600.
SEI. 2009. Software Engineering Institute - The Arcade Game Maker Pedagogical Product Line. [link]. Accessed in 2023 April.
Diego Fernandes Silva, Luiz Fernando Okada, Wesley K. G. Assunção, and Thelma Elita Colanzi. 2022. Intensifying the search-based optimization of product line architectures with crossover operators. Empirical Software Engineering 27 (2022), 166. DOI: 10.1007/s10664-022-10198-3
Yenisei Delgado Verdecia, Thelma Elita Colanzi, Silvia Regina Vergilio, and Marcelo C Benitez Santos. 2017. An Enhanced Evaluation Model for Search-based Product Line Architecture Design.. In CIbSE. 155–168.
T. Young. 2005. Using AspectJ to Build a Software Product Line for Mobile Devices. Master’s thesis. University of British Columbia.
Milan Zeleny and James L Cochrane. 1973. Multiple criteria decision making. University of South Carolina Press.
Eckart Zitzler, Lothar Thiele, Marco Laumanns, Carlos M Fonseca, and Viviane Grunert Da Fonseca. 2003. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation 7 (2003), 117–132.
Publicado
30/09/2024
Como Citar
WOLSCHICK, Lucas; GONÇALVES, Paulo Cesar; CHOMA NETO, João; FREIRE, Willian Marques; AMARAL, Aline Maria Malachini Miotto; COLANZI, Thelma Elita.
Evaluating the performance of NSGA-II and NSGA-III on Product Line Architecture Design. In: SIMPÓSIO BRASILEIRO DE COMPONENTES, ARQUITETURAS E REUTILIZAÇÃO DE SOFTWARE (SBCARS), 18. , 2024, Curitiba/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 11-20.
DOI: https://doi.org/10.5753/sbcars.2024.3830.
