A practical guide to select quality indicators for assessing pareto-based search algorithms in search-based software engineering

ABSTRACT

Many software engineering problems are multi-objective in nature, which has been largely recognized by the Search-based Software Engineering (SBSE) community. In this regard, Pareto-based search algorithms, e.g., Non-dominated Sorting Genetic Algorithm II, have already shown good performance for solving multi-objective optimization problems. These algorithms produce Pareto fronts, where each Pareto front consists of a set of non-dominated solutions. Eventually, a user selects one or more of the solutions from a Pareto front for their specific problems. A key challenge of applying Pareto-based search algorithms is to select appropriate quality indicators, e.g., hypervolume, to assess the quality of Pareto fronts. Based on the results of an extended literature review, we found that the current literature and practice in SBSE lacks a practical guide for selecting quality indicators despite a large number of published SBSE works. In this direction, the paper presents a practical guide for the SBSE community to select quality indicators for assessing Pareto-based search algorithms in different software engineering contexts. The practical guide is derived from the following complementary theoretical and empirical methods: 1) key theoretical foundations of quality indicators; 2) evidence from an extended literature review; and 3) evidence collected from an extensive experiment that was conducted to evaluate eight quality indicators from four different categories with six Pareto-based search algorithms using three real industrial problems from two diverse domains.

References

1. M. Harman, S. A. Mansouri and Y. Zhang, "Search Based Software Engineering: A Comprehensive Analysis and Review of Trends Techniques and Applications", Technical Report TR-09-03, Department of Computer Science, King College London, 2009.
2. M. Harman, "Making the Case for MORTO: Multi Objective Regression Test Optimization", Proc. of the IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops, pp. 111--114, 2011.
3. S. Ali, L. C. Briand, H. Hemmati, and R. K Panesar-Walawege, "A Systematic Review of the Application and Empirical Investigation of Search-Based Test Case Generation," IEEE Transactions on Software Engineering 36 (6), pp. 742--762, 2010.
4. S. Yoo, and M. Harman, "Pareto Efficient Multi-Objective Test Case Selection," Proc. of International Symposium on Software testing and analysis (ISSTA), pp. 140--150, 2007.{
5. Y. Zhang, A. Finkelstein and M. Harman, "Search Based Requirements Optimization: Existing Work and Challenges," Requirements Engineering: Foundation for Software Quality, pp. 88--94, 2008.
6. S. Wang, S. Ali and A. Gotlieb, "Cost-effective test suite minimization in product lines using search techniques", Journal of Systems and Software, vol (103), 370--391, 2015.
7. C. Henard, M. Papadakis, M. Harman, and Y. L. Traon, "Combining Multi-Objective Search and Constraint Solving for Configuring Large Software Product Lines", Proc. of the 37th International Conference on Software Engineering (ICSE), 2015.
8. S. Wang, S. Ali, T. Yue and M. Liaaen, 'UPMOA: An improved search algorithm to support user-preference multi-objective optimization", Proc. of International Symposium on Software Reliability Engineering, pp. 393--404, 2015.
9. J. J. Durillo, A. J. Nebro, "jMetal: A Java framework for multi-objective optimization," Advances in Engineering Software 42, pp. 760--771. 2011.
10. S. Wang, S. Ali and A. Gotlieb, and M. Liaaen, "A Systematic Test Case Selection Methodology for Product Lines: Results and Insights From an Industrial Case Study", Empirical Software Engineering Journal, pp. 1--37, 2014.
11. Y. Li, T. Yue, S. Ali, K. Nie and L. Zhang, "Zen-ReqOptimizer: A Search-based Approach for Requirements Assignment Optimization", Empirical Software Engineering Journal, 2016.
12. A. S. Sayyad, T. Menzies, H. Ammar, "On the value of user preferences in search-based software engineering: a case study in software product lines", Proc. of the International Conference of Software Engineering (ICSE), 492--501, 2013.
13. A. S. Sayyad, H. Ammar, "Pareto-Optimal Search-Based Software Engineering (POSBSE): A literature Survey", Proc. of 2nd International Workshop on Realizing Artificial Intelligence Synergies in Software Engineering, 21--27, 2013.
14. Y. Zhang and M. Harman and A. Mansouri, "The SBSE Repository: A repository and analysis of authors and research articles on Search Based Software Engineering", CREST Centre, UCL.
15. S. Wang, D. Buchmann, S, Ali, A. Gotlieb, D. Pradhan and M. Liaaen, "Multi-objective test prioritization in software product line testing: an industrial case study", Proc. of the 18th International Software Product Line Conference, pp. 32--41, 2014.
16. S. Wang, S. Ali and A. Gotlieb, "Minimizing Test Suites in Software Product Lines Using Weighted-based Genetic Algorithms", Proc. of the Genetic and Evolutionary Computation Conference (GECCO), pp. 1493--1500, 2013.
17. J. Brownlee, "Clever Algorithms: Nature-Inspired Programming Recipes," ISBN: 978-1-4467-8506-5, 2011.
18. K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II," IEEE Trans on Evolutionary Computation, 6(2), pp. 182--197, 2002.
19. A. J. Nebro, J. J. Durillo, F. Luna, B. Dorronsoro and E. Alba, "Design Issues in a Multiobjective Cellular Genetic Algorithm," Evolutionary Multi-Criterion Optimization, pp. 126--140, 2007.
20. E. Zitzler, M. Laumanns, and L. Thiele, "SPEA2: Improving the Strength Pareto Evolutionary Algorithm," Proc. of the EUROGEN 2001-Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems", pp. 95--100, 2001.
21. J. D. Knowles and D. W. Corne, "Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy," Evolutionary Computation 8(2), 149--172, 2000.
22. A. J. Nebro, J. J. Durillo, J. Garcia-Nieto, C. A. Coello Coello, F. Luna, and E. Alba, "SMPSO: A new PSO-based Metaheuristic for Multi-objective Optimization," Proc. of the Symposium on Computational Intelligence in Multicriteria Decision-Making (MCDM), pp. 66--73, 2009.
23. J. J. Durillo, A. J. Nebro, F. Luna, and E. Alba, "Solving Three-objective Optimization Problems using a New Hybrid Cellular Genetic Algorithm," Parallel Problem solving from nature-PPSN X. Lecture notes in computer science (5199), pp. 661--670, 2008.
24. S. Wang, S. Ali, T. Yue, Ø. Bakkeli, M. Liaaen, "Enhancing Test Case Prioritization in an Industrial Setting with Resource Awareness and Multi-Objective Search", Proc. of the 38^th International Conference on Software Engineering, 2016.
25. T., Yue, and S., Ali, "Applying Search Algorithms for Optimizing Stakeholders Familiarity and Balancing Workload in Requirements Assignment", Proc. of ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 1295--1302, 2014.
26. J. Knowles, L. Thiele, and E. Zitzler, "A Tutorial on the Performance Assessment of Stochastic Multiobjective Optimizers," Computer Engineering and Networks Laboratory (TIK), ETH Zurich, TIK Report 214, Feb. 2006.
27. K., Deb, "Multi-objective optimization using evolutionary algorithms," John Wiley & Sons; 2001.
28. E., Zitzler, L., Thiele, "Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach," IEEE Trans Evol Comput; 3(4), 257--71, 1999.
29. D. A., Van Veldhuizen, G. B., Lamont, "Multiobjective evolutionary algorithm research: A history and analysis, Tech. Rep. TR-98-03, Dept. Elec. Comput. Eng., Graduate School of Eng., Air Force Inst.Technol., Wright-Patterson, AFB, OH; 1998.
30. T. Yue, S. Ali and B. Selic, "Cyber-physical system product line engineering: comprehensive domain analysis and experience report", Proc. of International Conference on Software Product Line, pp. 338--347, 2015.
31. L. Briand, D. Falessi, S. Nejati, M. Sabetzadeh, and T. Yue, "Research-based innovation: A tale of three projects in model-driven engineering," Proc. of ACM/IEEE 15th International Conference on Model Driven Engineering Languages and Systems (MODELS), pp. 793--809, 2012.
32. J. L. Cochrane and M. Zeleny, "Multiple Criteria Decision Making," University of South Carolina Press, 1973.
33. C. M., Fonseca, P. J., Flemming, "Multiobjective optimization and multiple constraint handling with evolutionary algorithms-part ii: application example," IEEE Trans System, Man, Cybern 28 (1), pp. 38--47, 1998.
34. M., Tanaka, H., Watanabe, Y., Furukawa, T., Tanino, "GA-based decision support system for multicriteria optimization," Proc. of the IEEE international conference on systems, man, and cybernetics, vol. 2, pp. 1556--1561, 1995.
35. A. J. Nebro, F. Luna, E. Alba, B. Dorronsoro, J. J. Durillo and A. Beham, "AbYSS: Adapting Scatter Search to Multiobjective Optimization," IEEE Trans Evol Comput 12(4), pp. 439--457., 2008.
36. A. Zhou, Y. Jin, Q. Zhang, B. Sendhoff and E. Tsang, "Combining model-based and genetics-based offspring generation for multi-objective optimization using a convergence criterion, Proc. of IEEE Congress on evolutionary computation (CEC), pp. 3234--3241. 2006.
37. W. K. G. Assunção, T. E. Colanzi, A. T. R. Pozo and S. R. Vergilio, "Establishing Integration Test Orders of Classes with Several Coupling Measures," Proc. of GECCO, Dublin, Ireland, pp. 1867--1874. 2011.
38. J. T. de Souza, C. L. Maia, F. G. de Freitas and D. P. Coutinho, "The human competitiveness of search based software engineering," Proc. of SSBSE, pp. 143--152, 2010.
39. M. Li, S. Yang and X. Liu, "Diversity comparison of Pareto front approximations in many-objective optimization", IEEE Trans Cybern, 44(12), pp. 2568--2584, 2014.
40. J. M. Chaves-González and M. A. Pérez-Toledano, "Differential Evolution with Pareto Tournament for the Multi-objective Next Release Problem", Applied Mathematics and Computation, vol. 252, pp. 1--13, 2015.
41. Amarjeet and J. K. Chhabra, "An Empirical Study of the Sensitivity of Quality Indicator for Software Module Clustering", Proc. of 7th International Conference on Contemporary Computing (IC3 '14), pp. 206--211, 2014.
42. W. K. G. Assunção, T. E. Colanzi, S. R. Vergilio and A. Pozo, "A multi-objective optimization approach for the integration and test order problem", Information Sciences, Vol. 267, pp. 119--139, 2014.
43. G. Guizzo, T. E. Colanzi and S. R. Vergilio, "A Pattern-Driven Mutation Operator for Search-Based Product Line Architecture Design", Proc. of the 6th International Symposium on Search-Based Software Engineering (SSBSE), pp. 77--91, 2014.
44. M. Harman, Y. Jia, J. Krinke W. B. Langdon, J. Petke and Y. Zhang, "Search Based Software Engineering for Software Product Line Engineering: A Survey and Directions for Future Work", Proc. of the 18th International Software Product Line Conference (SPLC), pp. 5--18, 2014.
45. V. Hrubá, B. Křena, Z. Letko, H. Pluháčková and T. Vojnar, "Multi-objective Genetic Optimization for Noise-Based Testing of Concurrent Software", Proc. of the 6th International Symposium on Search-Based Software Engineering (SSBSE), pp. 107--122, 2014.
46. M. R. Karim and G. Ruhe, "Bi-Objective Genetic Search for Release Planning in Support of Themes", Proc. of the 6th International Symposium on Search-Based Software Engineering (SSBSE), pp. 123--137, 2014.
47. L. Li, M. Harman, E. Letier and Y. Zhang, "Robust Next Release Problem: Handling Uncertainty During Optimization", Proc. of the Conference on Genetic and Evolutionary Computation (GECCO), pp. 1247--1254, 2014.
48. R. E. Lopez-Herrejon, J. Ferrer, F. Chicano, A. Egyed and E. Alba, "Comparative Analysis of Classical Multi-Objective Evolutionary Algorithms and Seeding Strategies for Pairwise Testing of Software Product Lines", Proc. of IEEE Congress on Evolutionary Computation (CEC), pp. 387--396, 2014.
49. F. Luna, D. L. González-Álvarez, F. Chicano and M. A. Vega-Rodríguez, "The Software Project Scheduling Problem: A Scalability Analysis of Multi-objective Metaheuristics", Applied Soft Computing, Vol. 15, pp. 136--148, 2014.
50. M. W. Mkaouer, M. Kessentini, S., Bechikh, K., Deb and M.Ó. Cinnéide, "High Dimensional Search-based Software Engineering: Finding Tradeoffs among 15 Objectives for Automating Software Refactoring using NSGA-III", Proc. of the Conference on Genetic and Evolutionary Computation (GECCO), pp. 1263--1270, 2014.
51. M. W. Mkaouer, M. Kessentini, S. Bechikh, and M.Ó. Cinnéide, "A Robust Multi-objective Approach for Software Refactoring under Uncertainty", Proc. of the 6th International Symposium on Search-Based Software Engineering (SSBSE), pp. 168--183, 2014.
52. S. Nejati and L. C. Briand, "Identifying Optimal Trade-offs between CPU Time Usage and Temporal Constraints using Search", Proc. of the International Symposium on Software Testing and Analysis (ISSTA), pp. 251--261, 2014.
53. A. Ramrez, J. R. Romero and S. Ventura, "On the Performance of Multiple Objective Evolutionary Algorithms for Software Architecture Discovery", Proc. of Conference on Genetic and Evolutionary Computation (GECCO), pp. 1287--1294, 2014.
54. L. S. de Souza, R. B. C. Prudencio and F. A. Barros, "A Comparison Study of Binary Multi-Objective Particle Swarm Optimization Approaches for Test Case Selection", Proc. of the IEEE Congress on Evolutionary Computation (CEC), pp. 2164--2171, 2014.
55. A. Sureka, "Requirements Prioritization and Next-Release Problem under Non-Additive Value Conditions", Proc. of the 23rd Australian Software Engineering Conference (ASWEC), pp. 120--123, 2014.
56. W. K. G. Assunção, T. E. Colanzi, S. R. Vergilio and A. Pozo, "On the Application of the Multi-Evolutionary and Coupling-Based Approach with Different Aspect-Class Integration Testing Strategies", Proc. of the 5th International Symposium on Search-Based Software Engineering (SSBSE), pp. 19--33, 2013.
57. M. Bozkurt, "Cost-aware Pareto Optimal Test Suite Minimisation for Service-centric Systems", Proc. of the Conference on Genetic and Evolutionary Computation (GECCO), pp. 1429--1436, 2013.
58. L. C. Briand, Y. Labiche and K. Chen, "A Multi-Objective Genetic Algorithm to Rank State-Based Test Cases", Proc. of the 5th International Symposium on Search-Based Software Engineering (SSBSE), pp. 66--80, 2013.
59. M. W. Mkaouer, M. Kessentini, S. Bechikh and D. R. Tauritz, "Preference-based Multi-Objective Software Modelling", Proc. of 1st International Workshop on Combining Modelling and Search-Based Software Engineering (CMSBSE '13), pp. 61--66, 2013.
60. A. Ouni, M. Kessentini, H. Sahraoui and M. S. Hamdi, "The Use of Development History in Software Refactoring using A Multi-objective Evolutionary Algorithm", Proc. of Conference on Genetic and Evolutionary Computation (GECCO), pp. 1461--1468, 2013.
61. A. Arcuri, and L. C. Briand, "A Practical Guide for Using Statistical Tests to Assess Randomized Algorithms in Software Engineering," Proc. of International Conference on Software Engineering (ICSE), pp. 21--28, 2011.
62. M. O. Barros and A. C. Dias-Neto, "Threats to Validity in Search-based Software Engineering Empirical Studies", UNIRIO - Universidade Federal do Estado do Rio de Janeiro0006/2011, 2011.
63. D. J. Sheskin, "Handbook of Parametric and Nonparametric Statistical Procedures", 2003.
64. M. Kendall, "A New Measure of Rank Correlation". Biometrika 30 (1-2): 81--89, 1938.
65. E. Zizler, J. Knowles and L. Thiele, "Quality Assessment of Pareto Set Approximations," Multiobjective Optimization Lecture Notes in Computer Science, pp. 373--404, 2008.

Index Terms

• Software and its engineering

  • Software creation and management

    • Search-based software engineering