Rafael Olaechea
Jianmei Guo
ABSTRACT
Software product lines (SPLs) allow stakeholders to manage product variants in a systematical way and derive variants by selecting features. Finding a desirable variant is often difficult, due to the huge configuration space and usually conflicting objectives (e.g., lower cost and higher performance). This scenario can be characterized as a multi-objective optimization problem applied to SPLs. We address the problem using an exact and an approximate algorithm and compare their accuracy, time consumption, scalability, parameter setting requirements on five case studies with increasing complexity. Our empirical results show that (1) it is feasible to use exact techniques for small SPL multi-objective optimization problems, and (2) approximate methods can be used for large problems but require substantial effort to find the best parameter setting for acceptable approximation which can be ameliorated with known good parameter ranges. Finally, we discuss the tradeoff between accuracy and time consumption when using exact and approximate techniques for SPL multi-objective optimization and guide stakeholders to choose one or the other in practice.
- A. Arcuri and L. Briand. A hitchhiker's guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification & Reliability, 2012.Google Scholar
- A. Arcuri and G. Fraser. On parameter tuning in search based software engineering. In Proc. SSBSE, 2011. Google ScholarDigital Library
- D. Benavides, P. Trinidad, and A. Ruiz-Cortés. Automated reasoning on feature models. In Proc. CAiSE. Springer, 2005. Google ScholarDigital Library
- T. Berger, R. Rublack, D. Nair, J. M. Atlee, M. Becker, K. Czarnecki, and A. Wąsowski. A survey of variability modeling in industrial practice. In Proc. VaMoS, 2013. Google ScholarDigital Library
- P. C. Clements and L. Northrop. Software Product Lines: Practices and Patterns. Addison-Wesley, 2001. Google ScholarDigital Library
- L. de Moura and N. Bjørner. Z3: An efficient SMT solver. In Proc. TACAS. Springer, 2008. Google ScholarDigital Library
- K. Deb. Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, 2001. Google ScholarDigital Library
- J. J. Durillo and A. J. Nebro. jMetal: A Java framework for multi-objective optimization. Advances in Engineering Software, 42:760--771, 2011. Google ScholarDigital Library
- A. E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. SpringerVerlag, 2003. Google ScholarDigital Library
- N. Esfahani, S. Malek, and K. Razavi. Guidearch: guiding the exploration of architectural solution space under uncertainty. In Proc. ICSE, 2013. Google ScholarDigital Library
- F. Ferrucci, M. Harman, J. Ren, and F. Sarro. Not going to take this anymore: multi-objective overtime planning for software engineering projects. In Proc. ICSE, 2013. Google ScholarDigital Library
- J. Guo, J. White, G. Wang, J. Li, and Y. Wang. A genetic algorithm for optimized feature selection with resource constraints in software product lines. Journal of Systems and Software, 84(12):2208--2221, 2011. Google ScholarDigital Library
- J. Guo, K. Czarnecki, S. Apel, N. Siegmund, and A. Wasowski. Variability-aware performance prediction: A statistical learning approach. In ASE, 2013.Google ScholarDigital Library
- D. Hadka and P. Reed. Diagnostic assessment of search controls and failure modes in many-objective evolutionary optimization. Evol. Comput., 20(3):423--452, 2012. Google ScholarDigital Library
- M. Harman. The current state and future of search based software engineering. In Proc. FoSE, 2007. Google ScholarDigital Library
- C. Henard, M. Papadakis, G. Perrouin, J. Klein, and Y. L. Traon. Multi-objective test generation for software product lines. In Proc. SPLC. ACM, 2013. Google ScholarDigital Library
- J. H. Hollande. Adaptation in Natural and Artificial Systems. Univ. of Michigan Press, 1975. Google ScholarDigital Library
- F. Hutter, H. H. Hoos, K. Leyton-Brown, and T. Stutzle. Paramils an automatic algorithm configuration framework. JAIR, 36:267--306, October 2009. Google ScholarDigital Library
- M. F. Johansen, O. Haugen, and F. Fleurey. Properties of realistic feature models make combinatorial testing of product lines feasible. In Proc. MODELS, 2011. Google ScholarDigital Library
- M. F. Johansen, O. Haugen, and F. Fleurey. An algorithm for generating t-wise covering arrays from large feature models. In Proc. SPLC. ACM, 2012. Google ScholarDigital Library
- K. C. Kang, S. G. Cohen, J. A. Hess, W. E. Novak, and A. S. Peterson. Feature-Oriented Domain Analysis (FODA) feasibility study. Technical report, Software Engineering Institute - CMU, 1990.Google Scholar
- A. S. Karatas, H. Oguztuzun, and A. H. Dogru. Mapping extended feature models to constraint logic programming over finite domains. In Proc. SPLC, 2010. Google ScholarDigital Library
- J. Knowles. Local-search and Hybrid Evolutionary Algorithms for Pareto Optimization. PhD thesis, University of Reading, Reading, U.K., 2002.Google Scholar
- S. Q. Lau. Domain analysis of e-commerce systems using feature-based model templates. Master's thesis, University of Waterloo, 2006.Google Scholar
- M. Mendonça, T. T. Bartolomei, and D. Cowan. Decision-making coordination in collaborative product configuration. In Proc. SAC. ACM, 2008. Google ScholarDigital Library
- R. Olaechea, S. Stewart, K. Czarnecki, and D. Rayside. Modelling and Optimization of Quality Attributes in Variability-Rich Software. In NFPinDSML Workshop at MODELS Conference, 2012. Google ScholarDigital Library
- D. Rayside, H.-Christian. Estler, and D. Jackson. A Guided Improvement Algorithm for Exact, General Purpose, Many-Objective Combinatorial Optimization. Technical Report MIT-CSAIL-TR-2009-033, MIT CSAIL, 2009.Google Scholar
- P. Saadatpanah, M. Famelis, J. Gorzny, N. Robinson, M. Chechik, and R. Salay. Comparing the effectiveness of reasoning formalisms for partial models. In Proc. MoDeVVa. ACM, 2012. Google ScholarDigital Library
- A. Saltelli, M. Ratto, T. Andres, F. Campolongo, J. Cariboni, D. Gatelli, M. Saisana, and S. Tarantola. Global Sensitivity Analysis: The Primer. Wiley, 2008.Google Scholar
- A. S. Sayyad, J. Ingram, T. Menzies, and H. Ammar. Scalable product line configuration: A straw to break the camel's back. In ASE, 2013.Google ScholarDigital Library
- A. S. Sayyad, T. Menzies, and H. Ammar. On the value of user preferences in search-based software engineering: A case study in software product lines. In ICSE, 2013. Google ScholarDigital Library
- N. Siegmund, M. Rosenmuller, M. Kuhlemann, C. Kastner, S. Apel, and G. Saake. Spl conqueror: Toward optimization of non-functional properties in software product lines. Software Quality, 1(3):1--31, 2011.Google Scholar
- W. Simmons. A Framework for Decision Support in Systems Architecting. PhD thesis, Aeronautics & Astronautics, Massachusetts Institute of Technology, 2008.Google Scholar
- R. Steuer. Multiple Criteria Optimization: Theory, Computations, and Application. Wiley, 1986.Google Scholar
- D. A. Van Veldhuizen. Multiobjective evolutionary algorithms: classifications, analyses, and new innovations. PhD thesis, Air Force Institute of Technology, 1999. Google ScholarDigital Library
- J. White, B. Dougherty, and D. C. Schmidt. Selecting highly optimal architectural feature sets with filtered cartesian flattening. Journal of Systems and Software, 82(8):1268--1284, 2009. Google ScholarDigital Library
- S. Yoo and M. Harman. Pareto efficient multi-objective test case selection. In Proc. ISSTA. ACM, 2007. Google ScholarDigital Library
- S. Yoo and M. Harman. Using hybrid algorithm for pareto efficient multi-objective test suite minimisation. J. Syst. Softw., 83(4):689--701, Apr. 2010. Google ScholarDigital Library
- E. Zitzler. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. PhD thesis, ETH Zurich, 1999.Google Scholar
- E. Zitzler and S. Künzli. Indicator-based selection in multiobjective search. In Proc. PPSN. Springer, 2004.Google Scholar
- E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto evolutionary algorithm. IEEE Transactions on Evolutionary Computation, 3(4):257--271, 1999. Google ScholarDigital Library
Index Terms
- Comparison of exact and approximate multi-objective optimization for software product lines
Recommendations
Multi-objective test generation for software product lines
SPLC '13: Proceedings of the 17th International Software Product Line ConferenceSoftware Products Lines (SPLs) are families of products sharing common assets representing code or functionalities of a software product. These assets are represented as features, usually organized into Feature Models (FMs) from which the user can ...
Multi-objective Optimal Test Suite Computation for Software Product Line Pairwise Testing
ICSM '13: Proceedings of the 2013 IEEE International Conference on Software MaintenanceSoftware Product Lines (SPLs) are families of related software products, which usually provide a large number of feature combinations, a fact that poses a unique set of challenges for software testing. Recently, many SPL testing approaches have been ...
Multi-objective optimization
The optimal solution is selected by a higher-performing product with a lower price.The distribution of the Pareto front is always an increasing or decreasing trend.A quantitative method for evaluating Pareto non-inferior solutions is proposed. Based on ...
Comments