research-article

Optimizing selection of competing features via feedback-directed evolutionary algorithms

Authors:

Jin Song DongAuthors Info & Claims

ISSTA 2015: Proceedings of the 2015 International Symposium on Software Testing and Analysis

Pages 246 - 256

https://doi.org/10.1145/2771783.2771808

Published: 13 July 2015 Publication History

Abstract

Software that support various groups of customers usually require complicated configurations to attain different functionalities. To model the configuration options, feature model is proposed to capture the commonalities and competing variabilities of the product variants in software family or Software Product Line (SPL). A key challenge for deriving a new product is to find a set of features that do not have inconsistencies or conflicts, yet optimize multiple objectives (e.g., minimizing cost and maximizing number of features), which are often competing with each other. Existing works have attempted to make use of evolutionary algorithms (EAs) to address this problem. In this work, we incorporated a novel feedback-directed mechanism into existing EAs. Our empirical results have shown that our method has improved noticeably over all unguided version of EAs on the optimal feature selection. In particular, for case studies in SPLOT and LVAT repositories, the feedback-directed Indicator-Based EA (IBEA) has increased the number of correct solutions found by 72.33% and 75%, compared to unguided IBEA. In addition, by leveraging a pre-computed solution, we have found 34 sound solutions for Linux X86, which contains 6888 features, in less than 40 seconds.

References

[1]

Linux Variability Analysis Tools (LVAT) Repository. https://code.google.com/p/linux-variability-analysistools/source/browse/?repo=formulas.

[2]

SAT4J – The boolean satisfaction and optimization library in Java. http://www.sat4j.org/.

[3]

A. Arcuri and L. C. Briand. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In ICSE, pages 1–10, 2011.

Digital Library

[4]

D. Benavides, P. T. Mart´ın-Arroyo, and A. R. Cortés. Automated reasoning on feature models. In CAiSE, pages 491–503, 2005.

Digital Library

[5]

T. Berger, S. She, R. Lotufo, K. Czarnecki, T. Berger, S. She, R. Lotufo, A. Wasowski, and K. Czarnecki. Variability modeling in the systems software domain. Technical report, University of Waterloo, 2012.

[6]

J. Bosch, G. Florijn, D. Greefhorst, J. Kuusela, J. H. Obbink, and K. Pohl. Variability issues in software product lines. In PFE, 2001.

Digital Library

[7]

E. M. Clarke, O. Grumberg, S. Jha, Y. Lu, and H. Veith. Counterexample-guided abstraction refinement. In CAV, pages 154–169, 2000.

Digital Library

[8]

P. Clements and L. Northrop. Software Product Lines: Practices and Patterns. Addison-Wesley Professional, 3rd edition, Aug. 2001.

[9]

K. Czarnecki and U. W. Eisenecker. Generative programming - methods, tools and applications. Addison-Wesley, 2000.

Digital Library

[10]

L. M. de Moura and N. Bjørner. Z3: an efficient SMT solver. In TACAS, pages 337–340, 2008.

Digital Library

[11]

K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-II. IEEE Trans. Evolutionary Computation, 6(2):182–197, 2002.

Digital Library

[12]

J. J. Durillo and A. J. Nebro. jmetal: A java framework for multi-objective optimization. Advances in Engineering Software, 42(10):760–771, 2011.

Digital Library

[13]

J. J. Durillo, A. J. Nebro, F. Luna, and E. Alba. On the effect of the steady-state selection scheme in multi-objective genetic algorithms. In EMO, pages 183–197, 2009.

Digital Library

[14]

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.

Digital Library

[15]

J. Guo, E. Zulkoski, R. Olaechea, D. Rayside, K. Czarnecki, S. Apel, and J. M. Atlee. Scaling exact multi-objective combinatorial optimization by parallelization. In ASE, 2014.

Digital Library

[16]

M. Harman. The current state and future of search based software engineering. In FOSE, pages 342–357, 2007.

Digital Library

[17]

M. Harman and B. F. Jones. Search-based software engineering. Information & Software Technology, 43(14):833––839, 2001.

[18]

I. Jacobson, M. L. Griss, and P. Jonsson. Software reuse - architecture, process and organization for business. Addison-Wesley-Longman, 1997.

Digital Library

[19]

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 CMU/SEI-90-TR-21, Carnegie Mellon University, November 1990.

[20]

Y. Li, T. H. Tan, and M. Chechik. Management of time requirements in component-based systems. In FM, pages 399–415, 2014.

Digital Library

[21]

M. Mendon¸ ca, T. T. Bartolomei, and D. D. Cowan. Decision-making coordination in collaborative product configuration. In SAC, pages 108–113, 2008.

Digital Library

[22]

M. Mendon¸ ca, M. Branco, and D. D. Cowan. S.P.L.O.T.: software product lines online tools. In OOPSLA Companion, pages 761–762, 2009.

Digital Library

[23]

A. J. Nebro, J. J. Durillo, F. Luna, B. Dorronsoro, and E. Alba. Mocell: A cellular genetic algorithm for multiobjective optimization. Int. J. Intell. Syst., 24(7):726–746, 2009.

Digital Library

[24]

C. Pacheco, S. K. Lahiri, M. D. Ernst, and T. Ball. Feedback-directed random test generation. In ICSE, pages 75–84. IEEE Computer Society, 2007.

Digital Library

[25]

R. Pohl, K. Lauenroth, and K. Pohl. A performance comparison of contemporary algorithmic approaches for automated analysis operations on feature models. In ASE, pages 313–322, 2011.

Digital Library

[26]

R. Pohl, V. Stricker, and K. Pohl. Measuring the structural complexity of feature models. In ASE, pages 454–464, 2013.

Digital Library

[27]

A. S. Sayyad, J. Ingram, T. Menzies, and H. Ammar. Optimum feature selection in software product lines: Let your model and valuesguide your search. In CMSBSE, pages 22–27, 2013.

Digital Library

[28]

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.

Digital Library

[29]

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, pages 492–501, 2013.

Digital Library

[30]

S. She, R. Lotufo, T. Berger, A. Wasowski, and K. Czarnecki. Reverse engineering feature models. In ICSE, pages 461–470, 2011.

Digital Library

[31]

M. Srinivas and L. M. Patnaik. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 24(4):656–667, 1994.

[32]

T. H. Tan, É. André, J. Sun, Y. Liu, J. S. Dong, and M. Chen. Dynamic synthesis of local time requirement for service composition. In ICSE, pages 542–551, 2013.

Digital Library

[33]

T. H. Tan, M. Chen, É. André, J. Sun, Y. Liu, and J. S. Dong. Automated runtime recovery for qos-based service composition. In WWW, pages 563–574, 2014.

Digital Library

[34]

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.

Digital Library

[35]

Y. Xue, Z. Xing, and S. Jarzabek. Understanding feature evolution in a family of product variants. In WCRE, pages 109–118, 2010.

Digital Library

[36]

E. Zitzler and S. Künzli. Indicator-based selection in multiobjective search. In PPSN, pages 832–842, 2004.

[37]

E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. Evolutionary Computation, 3(4):257–271, 1999.

Digital Library

Cited By

Li MChen TYao X(2022)How to Evaluate Solutions in Pareto-Based Search-Based Software Engineering: A Critical Review and Methodological GuidanceIEEE Transactions on Software Engineering10.1109/TSE.2020.303610848:5(1771-1799)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1109/TSE.2020.3036108
Xiang YYang XHuang HHuang ZLi M(2022)Sampling configurations from software product lines via probability-aware diversification and SAT solvingAutomated Software Engineering10.1007/s10515-022-00348-829:2Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10515-022-00348-8
Dorn JApel SSiegmund N(2020)Generating attributed variability models for transfer learningProceedings of the 14th International Working Conference on Variability Modelling of Software-Intensive Systems10.1145/3377024.3377040(1-8)Online publication date: 5-Feb-2020
https://dl.acm.org/doi/10.1145/3377024.3377040
Show More Cited By

Index Terms

Optimizing selection of competing features via feedback-directed evolutionary algorithms
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Requirements analysis

Recommendations

Use of the q-Gaussian mutation in evolutionary algorithms
Special issue on advances in computational intelligence and bioinformatics

This paper proposes the use of the q-Gaussian mutation with self-adaptation of the shape of the mutation distribution in evolutionary algorithms. The shape of the q-Gaussian mutation distribution is controlled by a real parameter q. In the proposed ...
Evolutionary Algorithms for Multi-Objective Optimization: Performance Assessments and Comparisons

Evolutionary techniques for multi-objective (MO) optimization are currently gaining significant attention from researchers in various fields due to their effectiveness and robustness in searching for a set of trade-off solutions. Unlike conventional methods ...
Genetic diversity as an objective in multi-objective evolutionary algorithms

A key feature of an efficient and reliable multi-objective evolutionary algorithm is the ability to maintain genetic diversity within a population of solutions. In this paper, we present a new diversity-preserving mechanism, the Genetic Diversity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2015: Proceedings of the 2015 International Symposium on Software Testing and Analysis

July 2015

447 pages

ISBN:9781450336208

DOI:10.1145/2771783

General Chair:
Michal Young
University of Oregon, USA
,
Program Chair:
Tao Xie
University of Illinois at Urbana-Champaign, USA

Copyright © 2015 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]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '15

Sponsor:

SIGSOFT

ISSTA '15: International Symposium on Software Testing and Analysis

July 13 - 17, 2015

MD, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
313
Total Downloads

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

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li MChen TYao X(2022)How to Evaluate Solutions in Pareto-Based Search-Based Software Engineering: A Critical Review and Methodological GuidanceIEEE Transactions on Software Engineering10.1109/TSE.2020.303610848:5(1771-1799)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1109/TSE.2020.3036108
Xiang YYang XHuang HHuang ZLi M(2022)Sampling configurations from software product lines via probability-aware diversification and SAT solvingAutomated Software Engineering10.1007/s10515-022-00348-829:2Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10515-022-00348-8
Dorn JApel SSiegmund N(2020)Generating attributed variability models for transfer learningProceedings of the 14th International Working Conference on Variability Modelling of Software-Intensive Systems10.1145/3377024.3377040(1-8)Online publication date: 5-Feb-2020
https://dl.acm.org/doi/10.1145/3377024.3377040
Xiang YYang XZhou YHuang H(2020)Enhancing Decomposition-Based Algorithms by Estimation of Distribution for Constrained Optimal Software Product SelectionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2019.292241924:2(245-259)Online publication date: Apr-2020
https://doi.org/10.1109/TEVC.2019.2922419
Trujillo-Tzanahua GJuárez-Martínez UAguilar-Lasserre ACortés-Verdín MAzzaro-Pantel C(2020)Multiple software product lines to configure applications of internet of thingsIET Software10.1049/iet-sen.2019.003214:2(165-175)Online publication date: Apr-2020
https://doi.org/10.1049/iet-sen.2019.0032
Shi KYu HFan GGuo JChen LYang XSun H(2019)Mutation with Local Searching and Elite Inheritance Mechanism in Multi-Objective Optimization Algorithm: A Case Study in Software Product LineInternational Journal of Software Engineering and Knowledge Engineering10.1142/S021819401950042629:09(1347-1378)Online publication date: 10-Oct-2019
https://doi.org/10.1142/S0218194019500426
Xue YLi MShepperd MLauria SLiu X(2019)A novel aggregation-based dominance for Pareto-based evolutionary algorithms to configure software product linesNeurocomputing10.1016/j.neucom.2019.06.075364:C(32-48)Online publication date: 28-Oct-2019
https://dl.acm.org/doi/10.1016/j.neucom.2019.06.075
Xiang YYang XZhou YZheng ZLi MHuang H(2019)Going deeper with optimal software products selection using many-objective optimization and satisfiability solversEmpirical Software Engineering10.1007/s10664-019-09761-2Online publication date: 30-Aug-2019
https://doi.org/10.1007/s10664-019-09761-2
Pereira JSchulze SFigueiredo ESaake G(2018)N-dimensional tensor factorization for self-configuration of software product lines at runtimeProceedings of the 22nd International Systems and Software Product Line Conference - Volume 110.1145/3233027.3233039(87-97)Online publication date: 10-Sep-2018
https://dl.acm.org/doi/10.1145/3233027.3233039
Xue YLi YChaudron MCrnkovic IChechik MHarman M(2018)Multi-objective integer programming approaches for solving optimal feature selection problemProceedings of the 40th International Conference on Software Engineering10.1145/3180155.3180257(1231-1242)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3180155.3180257
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents