research-article

SIP: Optimal Product Selection from Feature Models Using Many-Objective Evolutionary Optimization

Authors:

Robert M. Hierons,

Wei ZhengAuthors Info & Claims

ACM Transactions on Software Engineering and Methodology (TOSEM), Volume 25, Issue 2

Article No.: 17, Pages 1 - 39

https://doi.org/10.1145/2897760

Published: 06 April 2016 Publication History

Abstract

A feature model specifies the sets of features that define valid products in a software product line. Recent work has considered the problem of choosing optimal products from a feature model based on a set of user preferences, with this being represented as a many-objective optimization problem. This problem has been found to be difficult for a purely search-based approach, leading to classical many-objective optimization algorithms being enhanced either by adding in a valid product as a seed or by introducing additional mutation and replacement operators that use an SAT solver. In this article, we instead enhance the search in two ways: by providing a novel representation and by optimizing first on the number of constraints that hold and only then on the other objectives. In the evaluation, we also used feature models with realistic attributes, in contrast to previous work that used randomly generated attribute values. The results of experiments were promising, with the proposed (SIP) method returning valid products with six published feature models and a randomly generated feature model with 10,000 features. For the model with 10,000 features, the search took only a few minutes.

References

[1]

Anne Auger, Johannes Bader, Dimo Brockhoff, and Eckart Zitzler. 2009. Theory of the hypervolume indicator: Optimal μ-distributions and the choice of the reference point. In Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA’09). 87--102.

Digital Library

[2]

Johannes Bader and Eckart Zitzler. 2011. HypE: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation 19, 1 (2011), 45--76.

Digital Library

[3]

Don Batory, David Benavides, and Antonio Ruiz-Cortés. 2006. Automated analysis of feature models: Challenges ahead. Communications of the ACM December (2006), 45--47.

Digital Library

[4]

David Benavides, Sergio Segura, and Antonio Ruiz-Cortés. 2010. Automated analysis of feature models 20 years later: A literature review. Information Systems 35, 6 (2010), 615--636.

Digital Library

[5]

David Benavides, Sergio Segura, Pablo Trinidad, and Antonio Ruiz-Cortés. 2007. FAMA: Tooling a framework for the automated analysis of feature models. In Proceedings of the 1st International Workshop on Variability Modelling of Software-Intensive Systems (VAMOS’07). 129--134.

[6]

David Benavides, Pablo Trinidad, and Antonio Ruiz-Cortés. 2005. Automated reasoning on feature models. In Advanced Information Systems Engineering. Lecture Notes in Computer Science, Vol. 3520. Springer, Berlin, 491--503.

Digital Library

[7]

Paul Clements and Linda Northrop. 2001. Software Product Lines: Practices and Patterns. Addison--Wesley.

Digital Library

[8]

Jonathas Cruz, Pedro Santos Neto, Ricardo Britto, Ricardo Rabelo, Werney Ayala, Thiago Soares, and Mauricio Mota. 2013. Toward a hybrid approach to generate software product line portfolios. In Proceedings of the 2013 IEEE Congress on Evolutionary Computation (CEC’13). 2229--2236.

[9]

Kalyanmoy Deb. 2001. Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley, New York.

Digital Library

[10]

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.

[11]

Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182--197.

Digital Library

[12]

Juan J. Durillo, Antonio J. Nebro, Francisco Luna, and Enrique Alba. 2009. On the effect of the steady-state selection scheme in multi-objective genetic algorithms. In Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization (EMO’09). Nantes, France, 183--197.

Digital Library

[13]

Naeem Esfahani, Sam Malek, and Kaveh Razavi. 2013. GuideArch: Guiding the exploration of architectural solution space under uncertainty. In Proceedings of the 2013 International Conference on Software Engineering (ICSE’13). IEEE Press, Piscataway, NJ, 43--52. http://dl.acm.org/citation.cfm?id=2486788.2486795

Digital Library

[14]

Tobias Friedrich, Christian Horoba, and Frank Neumann. 2009. Multiplicative approximations and the hypervolume indicator. In Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO’09). 571--578.

Digital Library

[15]

Jesús García-Galán, Pablo Trinidad, Omer F. Rana, and Antonio Ruiz-Cortés. 2016. Automated configuration support for infrastructure migration to the cloud. Future Generation Computer Systems 55 (2016), 200--212.

Digital Library

[16]

Jianmei Guo, Jules White, Guangxin Wang, Jian Li, and Yinglin Wang. 2011. A genetic algorithm for optimized feature selection with resource constraints in software product lines. Journal of Systems and Software 84, 12 (2011), 2208--2221.

Digital Library

[17]

Jianmei Guo, Edward Zulkoski, Rafael Olaechea, Derek Rayside, Krzysztof Czarnecki, Sven Apel, and Joanne M. Atlee. 2014. Scaling exact multi-objective combinatorial optimization by parallelization. In Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering (ASE’14). ACM, New York, NY, 409--420.

Digital Library

[18]

David Hadka and Patrick Reed. 2012. Diagnostic assessment of search controls and failure modes in many-objective evolutionary optimization. Evolutionary Computation 20, 3 (2012), 423--452.

Digital Library

[19]

Mark Harman, Yue Jia, Jens Krinke, Bill 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 (SPLC’14). ACM, New York, NY, 5--18.

Digital Library

[20]

Christopher Henard, Mike Papdakis, Mark Harman, and Yves Le Traon. 2015. Combining multi-objective search and constraint solving for configuring large software product lines. In Proceedings of the 2015 International Conference on Software Engineering (ICSE’15). IEEE Press.

Digital Library

[21]

Peter Hofman, Tobias Stenzel, Thomas Pohley, Michael Kircher, and Andreas Bermann. 2012. Domain specific feature modeling for software product lines. In Proceedings of the 16th International Software Product Line Conference - Volume 1 (SPLC’12). ACM, New York, NY, 229--238.

Digital Library

[22]

Hisao Ishibuchi, Naoya Akedo, and Yusuke Nojima. 2015. Behavior of multi-objective evolutionary algorithms on many-objective knapsack problems. IEEE Transactions on Evolutionary Computation 19, 2 (2015), 264--283.

Digital Library

[23]

Hisao Ishibuchi, Noritaka Tsukamoto, and Yusuke Nojima. 2008. Evolutionary many-objective optimization: A short review. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC’08). 2419--2426.

[24]

Kyo C. Kang, Sholom Cohen, James Hess, William Novak, and Spencer Peterson. 1990. Feature--Oriented Domain Analysis (FODA) Feasibility Study. Technical Report CMU/SEI-90-TR-21. SEI.

[25]

Ahmet Serkan Karatas, Halit Oguztüzün, and Ali Dogru. 2013. From extended feature models to constraint logic programming. Science of Computer Programming 78, 12 (2013), 2295--2312. Special Section on International Software Product Line Conference 2010 and Fundamentals of Software Engineering (selected papers of {FSEN} 2011).

[26]

Sean Quan Lau. 2006. Domain Analysis of E-Commerce Systems Using Feature-Based Model Templates. Master’s thesis. University of Waterloo, Waterloo.

[27]

Bingdong Li, Jinlong Li, Ke Tang, and Xin Yao. 2014. An improved two archive algorithm for many-objective optimization. In IEEE Congress on Evolutionary Computation (CEC’14). IEEE, 2869--2876.

[28]

Jian Li, Xijuan Liu, Yinglin Wang, and Jianmei Guo. 2012. Formalizing feature selection problem in software product lines using 0-1 programming. In Practical Applications of Intelligent Systems, Yinglin Wang and Tianrui Li (Eds.). Advances in Intelligent and Soft Computing, Vol. 124. Springer, Berlin, 459--465.

[29]

Miqing Li, Shengxiang Yang, and Xiaohui Liu. 2014a. Shift-based density estimation for Pareto-based algorithms in many-objective optimization. IEEE Transactions on Evolutionary Computation 18, 3 (2014), 348--365.

[30]

Miqing Li, Shengxiang Yang, and Xiaohui Liu. 2014b. A test problem for visual investigation of high-dimensional multi-objective search. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC’14). 2140--2147.

[31]

Miqing Li, Shengxiang Yang, Xiaohui Liu, and Ruimin Shen. 2013. A comparative study on evolutionary algorithms for many-objective optimization. In Proceedings of the 7th International Conference on Evolutionary Multi-Criterion Optimization (EMO’13). 261--275.

[32]

Roberto E. Lopez-Herrejon, Lukas Linsbauer, and Alexander Egyed. 2015. A systematic mapping study of search-based software engineering for software product lines. Information and Software Technology 61 (2015), 33--51.

Digital Library

[33]

Shinsuke Matsumoto, Yasutaka Kamei, Akito Monden, Ken-ichi Matsumoto, and Masahide Nakamura. 2010. An analysis of developer metrics for fault prediction. In Proceedings of the 6th International Conference on Predictive Models in Software Engineering (PROMISE’10). ACM, 18.

Digital Library

[34]

Yoshihiro Matsumoto. 2007. A guide for management and financial controls of product lines. In Proceedings of the 11th International Software Product Line Conference. 162--170.

Digital Library

[35]

Marcilio Mendonca, Thiago Tonelli Bartolomei, and Donald Cowan. 2008. Decision-making coordination in collaborative product configuration. In Proceedings of the 2008 ACM Symposium on Applied Computing (SAC’08). ACM, New York, NY, 108--113.

Digital Library

[36]

Marcilio Mendonca, Moises Branco, and Donald Cowan. 2009. S.P.L.O.T.: Software product lines online tools. In Companion to the 24th ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA’09). ACM, 761--762.

Digital Library

[37]

Johannes Muller. 2011. Value-based portfolio optimization for software product lines. In Proceedings of the 2011 15th International Software Product Line Conference (SPLC’11). 15--24.

Digital Library

[38]

Rafael Olaechea, Derek Rayside, Jianmei Guo, and Krzysztof Czarnecki. 2014. Comparison of exact and approximate multi-objective optimization for software product lines. In Proceedings of the 18th International Software Product Line Conference - Volume 1 (SPLC’14). ACM, New York, NY, 92--101.

Digital Library

[39]

Abdel Salam Sayyad. 2014. Evolutionary Search Techniques with Strong Heuristics for Multi-Objective Feature Selection in Software Product Lines. Ph.D. Dissertation. West Virginia University.

[40]

Abdel Salam Sayyad, Katerina Goseva-Popstojanova, Tim Menzies, and Hany Ammar. 2013a. On parameter tuning in search based software engineering: A replicated empirical study. In Proceedings of the 2013 3rd International Workshop on Replication in Empirical Software Engineering Research (RESER’13). IEEE Computer Society, Washington, DC, 84--90.

Digital Library

[41]

Abdel Salam Sayyad, Joseph Ingram, Tim Menzies, and Hany Ammar. 2013b. Optimum feature selection in software product lines: Let your model and values guide your search. In Proceedings of the 2013 1st International Workshop on Combining Modelling and Search-Based Software Engineering (CMSBSE’13). 22--27.

Digital Library

[42]

Abdel Salam Sayyad, Joseph Ingram, Tim Menzies, and Hany Ammar. 2013c. Scalable product line configuration: A straw to break the camel’s back. In Proceedings of the 2013 IEEE/ACM 28th International Conference on Automated Software Engineering (ASE’13). 465--474.

Digital Library

[43]

Abdel Salam Sayyad, Tim Menzies, and Hany Ammar. 2013d. On the value of user preferences in search-based software engineering: A case study in software product lines. In Proceedings of the 2013 International Conference on Software Engineering (ICSE’13). IEEE Press, 492--501.

Digital Library

[44]

David C. Sharp. 1998. Reducing avionics software cost through component based product line development. In Proceedings of the 17th Digital Avionics Systems Conference. IEEE.

[45]

Norbert Siegmund, Marko Rosenmüller, Martin Kuhlemann, Christian Kästner, Sven Apel, and Gunter Saake. 2012. SPL conqueror: Toward optimization of non-functional properties in software product lines. Software Quality Journal 20, 3--4 (2012), 487--517.

Digital Library

[46]

Ana B. Sánchez, Sergio Segura, José A. Parejo, and Antonio Ruiz-Cortés. 2015. Variability testing in the wild: The drupal case study. Software & Systems Modeling (2015), 1--22.

[47]

Tian Huat Tan, Yinxing Xue, Manman Chen, Jun Sun, Yang Liu, and Jin Song Dong. 2015. Optimizing selection of competing features via feedback-directed evolutionary algorithms. In Proceedings of the 2015 International Symposium on Software Testing and Analysis (ISSTA’15). ACM, New York, NY, 246--256.

Digital Library

[48]

Thomas Thüm, Don Batory, and Christian Kastner. 2009. Reasoning about edits to feature models. In Proceedings of the 31st International Conference on Software Engineering (ICSE’09). IEEE Computer Society, Washington, DC, 254--264.

Digital Library

[49]

Thomas Thüm, Christian Kästner, Fabian Benduhn, Jens Meinicke, Gunter Saake, and Thomas Leich. 2014. FeatureIDE: An extensible framework for feature-oriented software development. Science of Computer Programming 79 (2014), 70--85. Experimental Software and Toolkits (EST 4): A special issue of the Workshop on Academic Software Development Tools and Techniques (WASDeTT-3 2010).

Digital Library

[50]

Pablo Trinidad, David Benavides, Antonio Ruiz-Cortés, Sergio Segura, and Alberto Jimenez. 2008. FAMA framework. In 12th Software Product Lines Conference (SPLC’08). 359.

Digital Library

[51]

Tobias Wagner, Nicola Beume, and Boris Naujoks. 2007. Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization (EMO’07). 742--756.

Digital Library

[52]

Ying-lin Wang and Jin-wei Pang. 2014. Ant colony optimization for feature selection in software product lines. Journal of Shanghai Jiaotong University (Science) 19, 1 (2014), 50--58.

[53]

Jules White, Brian Dougherty, and Douglas C. Schmidt. 2009. Selecting highly optimal architectural feature sets with filtered cartesian flattening. Journal of Systems and Software 82, 8 (Aug. 2009), 1268--1284.

Digital Library

[54]

Jules White, Brian Doughtery, and Douglas C. Schmidt. 2008. Filtered cartesian flattening: An approximation technique for optimally selecting features while adhering to resource constraints. In Proceedings of the 12th International Conference on Software Product Lines, (SPLC’08) Second Volume (Workshops). 209--216.

[55]

Shengxiang Yang, Miqing Li, Xiaohui Liu, and Jinhua Zheng. 2013. A grid-based evolutionary algorithm for many-objective optimization. IEEE Transactions on Evolutionary Computation 17, 5 (2013), 721--736.

Digital Library

[56]

Shin Yoo and Mark Harman. 2012. Regression testing minimization, selection and prioritization: A survey. Software Testing, Verification and Reliability 22, 2 (2012), 67--120.

[57]

Qingfu Zhang and Hui Li. 2007. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation 11, 6 (2007), 712--731.

Digital Library

[58]

Eckart Zitzler and Simon Künzli. 2004. Indicator-based selection in multiobjective search. In Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN’04). 832--842.

[59]

Eckart Zitzler, Marco Laumanns, and Lothar Thiele. 2002. SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization. In Evolutionary Methods for Design, Optimisation and Control. 95--100.

[60]

Eckart Zitzler and Lothar Thiele. 1999. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation 3, 4 (1999), 257--271.

Digital Library

Cited By

Zhang GLi LSu ZYue FChen YLi MYao X(2024)On Estimating the Feasible Solution Space of Multi-objective Testing Resource AllocationACM Transactions on Software Engineering and Methodology10.1145/365444433:6(1-41)Online publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1145/3654444
Chen PChen TLi M(2024)MMO: Meta Multi-Objectivization for Software Configuration TuningIEEE Transactions on Software Engineering10.1109/TSE.2024.338891050:6(1478-1504)Online publication date: Jun-2024
https://doi.org/10.1109/TSE.2024.3388910
Li GWang ZSun JZhang Q(2024)Objective Extraction for Simplifying Many-Objective Solution SetsIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2023.33014018:1(337-349)Online publication date: Feb-2024
https://doi.org/10.1109/TETCI.2023.3301401
Show More Cited By

Index Terms

SIP: Optimal Product Selection from Feature Models Using Many-Objective Evolutionary Optimization
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
2. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Reusability
        Software product lines

Recommendations

Discovering special product features for improving the process of product selection in E-commerce environment
ICEC '09: Proceedings of the 11th International Conference on Electronic Commerce

In the E-commerce environment, a customer faces several difficulties for selecting the product. The technology like recommendation system is being developed to improve the performance of product selection. In this paper, we have investigated the problem ...
Preference for Abstract Diagrams and Sentiments Applied in a Product Selection
Abstract
Searching and buying items from online shops has become common these days. Although recommender systems have supported consumers to find products online, it is challenging to select suitable products, such as clothes and smartphone cases, which ...
Product selection, machine time allocation, and scheduling decisions for manufacturing perishable products subject to a deadline

We are concerned about the following problem: a manufacturer owns a certain amount of perishable raw material which can be produced into different types of products. He must, however, finish the manufacturing process before a deadline (which represents, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology

ACM Transactions on Software Engineering and Methodology Volume 25, Issue 2

May 2016

328 pages

ISSN:1049-331X

EISSN:1557-7392

DOI:10.1145/2913009

Editor:
David S. Rosenblum
National University of Singapore, Singapore

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 April 2016

Accepted: 01 January 2016

Revised: 01 November 2015

Received: 01 July 2015

Published in TOSEM Volume 25, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

Product selection

Qualifiers

Research-article
Research
Refereed

Funding Sources

European Commission (FEDER) and Spanish Government under CICYT
Andalusian Government

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

84
Total Citations
View Citations
638
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang GLi LSu ZYue FChen YLi MYao X(2024)On Estimating the Feasible Solution Space of Multi-objective Testing Resource AllocationACM Transactions on Software Engineering and Methodology10.1145/365444433:6(1-41)Online publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1145/3654444
Chen PChen TLi M(2024)MMO: Meta Multi-Objectivization for Software Configuration TuningIEEE Transactions on Software Engineering10.1109/TSE.2024.338891050:6(1478-1504)Online publication date: Jun-2024
https://doi.org/10.1109/TSE.2024.3388910
Li GWang ZSun JZhang Q(2024)Objective Extraction for Simplifying Many-Objective Solution SetsIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2023.33014018:1(337-349)Online publication date: Feb-2024
https://doi.org/10.1109/TETCI.2023.3301401
Huang HHao Z(2024)Application of multiobjective optimization intelligence algorithmsIntelligent Algorithms10.1016/B978-0-443-21758-6.00004-8(143-195)Online publication date: 2024
https://doi.org/10.1016/B978-0-443-21758-6.00004-8
Song YFang X(2023)An Improved Strength Pareto Evolutionary Algorithm 2 with Adaptive Crossover Operator for Bi-Objective Distributed Unmanned Aerial Vehicle DeliveryMathematics10.3390/math1115332711:15(3327)Online publication date: 28-Jul-2023
https://doi.org/10.3390/math11153327
Jamil MNour MAlotaibi SHussain MHussaini SNaseer A(2023)Adaptive Test Suits Generation for Self-Adaptive Systems Using SPEA2 AlgorithmApplied Sciences10.3390/app13201132413:20(11324)Online publication date: 15-Oct-2023
https://doi.org/10.3390/app132011324
Jhaveri SKrone-Martins ALopes CStorm THirschfeld R(2023)Cloning and Beyond: A Quantum Solution to Duplicate CodeProceedings of the 2023 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3622758.3622889(32-49)Online publication date: 18-Oct-2023
https://dl.acm.org/doi/10.1145/3622758.3622889
Guégain ETaherkordi AQuinton C(2023)ICO: A Platform for Optimizing Highly Configurable Systems2023 38th IEEE/ACM International Conference on Automated Software Engineering Workshops (ASEW)10.1109/ASEW60602.2023.00013(62-67)Online publication date: 11-Sep-2023
https://doi.org/10.1109/ASEW60602.2023.00013
Li YBian YZhang ZZhao SLiu Y(2023)CTHPIET Software10.1049/sfw2.1213417:4(496-508)Online publication date: 27-Jun-2023
https://dl.acm.org/doi/10.1049/sfw2.12134
Antonio Parejo JSánchez A(2023)Cloud Development and DeploymentOptimising the Software Development Process with Artificial Intelligence10.1007/978-981-19-9948-2_6(155-176)Online publication date: 20-Jul-2023
https://doi.org/10.1007/978-981-19-9948-2_6
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents