Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Software and Systems Modeling
Published in: Software and Systems Modeling 2/2019

22-07-2017 | Regular Paper

SMTIBEA: a hybrid multi-objective optimization algorithm for configuring large constrained software product lines

Authors: Jianmei Guo, Jia Hui Liang, Kai Shi, Dingyu Yang, Jingsong Zhang, Krzysztof Czarnecki, Vijay Ganesh, Huiqun Yu

Published in: Software and Systems Modeling | Issue 2/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A key challenge to software product line engineering is to explore a huge space of various products and to find optimal or near-optimal solutions that satisfy all predefined constraints and balance multiple often competing objectives. To address this challenge, we propose a hybrid multi-objective optimization algorithm called SMTIBEA that combines the indicator-based evolutionary algorithm (IBEA) with the satisfiability modulo theories (SMT) solving. We evaluated the proposed algorithm on five large, constrained, real-world SPLs. Compared to the state-of-the-art, our approach significantly extends the expressiveness of constraints and simultaneously achieves a comparable performance. Furthermore, we investigate the performance influence of the SMT solving on two evolutionary operators of the IBEA.
previous article Assessing the impact of meta-model evolution: a measure and its automotive application
next article Formal modeling of biomedical signal acquisition systems: source of evidence for certification

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Apel, S., Batory, D.S., Kästner, C., Saake, G.: Feature-Oriented Software Product Lines—Concepts and Implementation. Springer, Berlin (2013)CrossRef
2.
Arcuri, A., Briand, L.C.: A practical guide for using statistical tests to assess randomized algorithms in software engineering. In: Proceedings of 33rd International Conference on Software Engineering (ICSE), pp. 1–10 (2011)
3.
Batory, D.: Feature models, grammars, and propositional formulas. In: Proceedings of 9th International Software Product Line Conference (SPLC), pp. 7–20 (2005)
4.
Benavides, D., Segura, S., Cortés, A.: Automated analysis of feature models 20 years later: a literature review. Inf. Syst. 35(6), 615–636 (2010)CrossRef
5.
Berger, T., She, S., Lotufo, R., Wasowski, A., Czarnecki, K.: A study of variability models and languages in the systems software domain. IEEE Trans. Softw. Eng. 39(12), 1611–1640 (2013)CrossRef
6.
Brockhoff, D., Friedrich, T., Neumann, F.: Analyzing hypervolume indicator based algorithms. In: Proceedings of 10th International Conference on Parallel Problem Solving from Nature (PPSN), pp. 651–660 (2008)
7.
Clements, P., Northrop, L.: Software Product Lines: Practices and Patterns. Addison-Wesley, Boston (2001)
8.
Czarnecki, K., Eisenecker, U.: Generative Programming: Methods, Tools, and Applications. Addison-Wesley, Boston (2000)
9.
de Moura, L., Bjørner, N.: Satisfiability modulo theories: introduction and applications. Commun. ACM 54(9), 69–77 (2011)CrossRef
10.
de Moura, L., Bjørner, N.: Z3: An Efficient SMT Solver. In: Proceedings of 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 337–340 (2008)
11.
Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)CrossRef
12.
Deb, K., Mohan, M., Mishra, S.: Towards a quick computation of well-spread Pareto-optimal solutions. In: Proceedings of Second International Conference on Evolutionary Multi-Criterion Optimization (EMO), pp. 222–236 (2003)
13.
Durillo, J.J., Nebro, A.J.: jMetal: a java framework for multi-objective optimization. Adv. Eng. Softw. 42, 760–771 (2011)CrossRef
14.
Durillo, J.J., Nebro, A.J., Alba, E.: The jMetal framework for multi-objective optimization: design and architecture. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC), pp. 4138–4325. Barcelona, Spain (2010)
15.
Eén, N., Sörensson, N.: Translating pseudo-boolean constraints into SAT. J. Satisf. Boolean Model. Comput. 2(1–4), 1–26 (2006)MATH
16.
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Natural Computing Series. Springer, Berlin (2003)CrossRefMATH
17.
Gavanelli, M.: An algorithm for multi-criteria optimization in CSPs. In: Proceedings of 15th European Conference on Artificial Intelligence (ECAI), pp. 136–140 (2002)
18.
Guo, J., Czarnecki, K., Apel, S., Siegmund, N., Wąsowski, A.: Variability-aware performance prediction: a statistical learning approach. In: Proceedings of 28th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 301–311 (2013)
19.
Guo, J., White, J., Wang, G., Li, J., Wang, Y.: A genetic algorithm for optimized feature selection with resource constraints in software product lines. J. Syst. Softw. 84(12), 2208–2221 (2011)CrossRef
20.
Guo, J., Zulkoski, E., Olaechea, R., Rayside, D., Czarnecki, K., Apel, S., Atlee, J.M.: Scaling exact multi-objective combinatorial optimization by parallelization. In: Proceedings of 29th ACM/IEEE International Conference on Automated Software Engineering (ASE), pp. 409–420 (2014)
21.
Harman, M.: The current state and future of search based software engineering. In: Proceedings of International Workshop on the Future of Software Engineering (FOSE), pp. 342–357 (2007)
22.
Harman, M., Jia, Y., Krinke, J., Langdon, W.B., Petke, J., Zhang, Y.: Search based software engineering for software product line engineering: a survey and directions for future work. In: Proceedings of 18th International Software Product Line Conference (SPLC), pp. 5–18 (2014)
23.
Harman, M., Jones, B.F.: Search-based software engineering. Inf. Softw. Technol. 43(14), 833–839 (2001)CrossRef
24.
Harman, M., Mansouri, S., Zhang, Y.: Search based software engineering: a comprehensive analysis and review of trends techniques and applications. Tech. rep., King’s College London TR-09-03 (2009)
25.
Hartert, R., Schaus., P.: A support-based algorithm for the bi-objective Pareto constraint. In: Proceedings of 28th AAAI Conference on Artificial Intelligence (AAAI), pp. 2674–2679 (2014)
26.
Henard, C., Papadakis, M., Harman, M., Traon, Y.L.: Combining multi-objective search and constraint solving for configuring large software product lines. In: Proceedings of 37th IEEE/ACM International Conference on Software Engineering (ICSE), pp. 517–528 (2015)
27.
Henard, C., Papadakis, M., Perrouin, G., Klein, J., Traon, Y.L.: Multi-objective test generation for software product lines. In: Proceedings of 17th International Software Product Line Conference (SPLC), pp. 62–71 (2013)
28.
Hierons, R.M., Li, M., Liu, X., Segura, S., Zheng, W.: SIP: optimal product selection from feature models using many-objective evolutionary optimization. ACM Trans. Softw. Eng. Methodol. 25(2), 17 (2016)CrossRef
29.
Ishibuchi, H., Masuda, H., Tanigaki, Y., Nojima, Y.: Modified distance calculation in generational distance and inverted generational distance. In: Proceedings of 8th International Conference on Evolutionary Multi-Criterion Optimization (EMO), pp. 110–125 (2015)
30.
Jackson, D.: Software Abstractions: Logic, Language, and Analysis. MIT, Cambridge (2006)
31.
Kang, K., Cohen, S., Hess, J., Novak, W., Peterson, A.: Feature-oriented domain analysis (FODA) feasibility study. Tech. rep., CMU SEI, SEI-90-TR-21 (1990)
32.
Knowles, J., Corne, D.: On metrics for comparing nondominated sets. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC), pp. 711–716 (2002)
33.
Lu, H., Yue, T., Ali, S., Zhang, L.: Nonconformity resolving recommendations for product line configuration. In: Proceedings of Ninth International Conference on Software Testing, Verification and Validation (ICST), pp. 57–68 (2016)
34.
35.
Marek, V., Truszczynski, M.: Stable models and an alternative logic programming paradigm. In: The Logic Programming Paradigm: A 25-year Perspective. Springer (1999)
36.
Mkaouer, W., Kessentini, M., Shaout, A., Koligheu, P., Bechikh, S., Deb, K., Ouni, A.: Many-objective software remodularization using NSGA-III. ACM Trans. Softw. Eng. Methodol. 24(3), 1–45 (2015)CrossRef
37.
Nadi, S., Berger, T., Kästner, C., Czarnecki, K.: Where do configuration constraints stem from? An extraction approach and an empirical study. IEEE Trans. Softw. Eng. 41(8), 820–841 (2015)CrossRef
38.
Olaechea, R., Rayside, D., Guo, J., Czarnecki, K.: Comparison of exact and approximate multi-objective optimization for software product lines. In: Proceedings of 18th International Software Product Line Conference (SPLC), pp. 92–101 (2014)
39.
Olaechea, R., Stewart, S., Czarnecki, K., Rayside, D.: Modeling and multi-objective optimization of quality attributes in variability-rich software. In: Proceedings of Fourth International Workshop on Nonfunctional System Properties in Domain Specific Modeling Languages (NFPinDSML), pp. 2:1–2:6 (2012)
40.
Passos, L.T., Berger, T., Novakovic, M., Czarnecki, K., Xiong, Y., Wasowski, A.: A study of non-boolean constraints in variability models of an embedded operating system. In: Proceedings of Third Workshop on Feature-Oriented Software Development (FOSD), pp. 9–16 (2011)
41.
Passos, L.T., Guo, J., Teixeira, L., Czarnecki, K., Wasowski, A., Borba, P.: Coevolution of variability models and related artifacts: a case study from the Linux kernel. In: Proceedings of 17th International Software Product Line Conference (SPLC), pp. 91–100 (2013)
42.
Passos, L.T., Teixeira, L., Dintzner, N., Apel, S., Wasowski, A., Czarnecki, K., Borba, P., Guo, J.: Coevolution of variability models and related software artifacts—a fresh look at evolution patterns in the Linux kernel. Empir. Softw. Eng. 21(4), 1744–1793 (2016)CrossRef
43.
Pohl, K., Bockle, G., van der Linden, F.: Software Product line Engineering: Foundations, Principles, and Techniques. Springer, Berlin (2005)CrossRefMATH
44.
Rayside, D., Estler, H.C., Jackson, D.: A guided improvement algorithm for exact, general purpose, many-objective combinatorial optimization. Tech. rep., MIT-CSAIL-TR-2009-033 (2009)
45.
Saadatpanah, P., Famelis, M., Gorzny, J., Robinson, N., Chechik, M., Salay, R.: Comparing the effectiveness of reasoning formalisms for partial models. In: Proceedings of the Workshop on Model-Driven Engineering, Verification and Validation (MoDeVVa), pp. 41–46 (2012)
46.
Sarkar, A., Guo, J., Siegmund, N., Apel, S., Czarnecki, K.: Cost-efficient sampling for performance prediction of configurable systems. In: Proceedings of 30th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 342–352 (2015)
47.
Sarro, F., Petrozziello, A., Harman, M.: Multi-objective software effort estimation. In: Proceedings of 38th International Conference on Software Engineering (ICSE), pp. 619–630 (2016)
48.
Sayyad, A., Ingram, J., Menzies, T., Ammar, H.: Scalable product line configuration: A straw to break the camel’s back. In: Proceedings of 28th International Conference on Automated Software Engineering (ASE), pp. 465–474 (2013)
49.
Sayyad, A., Menzies, T., Ammar, H.: On the value of user preferences in search-based software engineering: A case study in software product lines. In: Proceedings of 35th International Conference on Software Engineering (ICSE), pp. 492–501. IEEE (2013)
50.
Sayyad, A.S., Ingram, J., Menzies, T., Ammar, H.: Optimum feature selection in software product lines: let your model and values guide your search. In: Proceedings of 1st International Workshop on Combining Modelling and Search-Based Software Engineering (CMSBSE), pp. 22–27 (2013)
51.
Siegmund, N., Kolesnikov, S., Kästner, C., Apel, S., Batory, D., Rosenmüller, M., Saake, G.: Predicting performance via automated feature-interaction detection. In: Proceedings of 34th International Conference on Software Engineering (ICSE), pp. 167–177 (2012)
52.
Tsang, E.: Foundations of constraint satisfaction. Academic, (1993)
53.
Vargha, A., Delaney, H.D.: A critique and improvement of the CL common language effect size statistics of McGraw and Wong. J. Educ. Behav. Stat. 25(2), 101–132 (2000)
54.
White, J., Doughtery, B., Schmidt, D.C.: Filtered cartesian flattening: an approximation technique for optimally selecting features while adhering to resource constraints. In: Proceedings of First International Workshop on Analyses of Software Product Lines (ASPL), pp. 209–216 (2008)
55.
Wu, Z., Tang, J., Kwong, C.K., Chan, C.Y.: An optimization model for reuse scenario selection considering reliability and cost in software product line development. Int. J. Inf. Technol. Decis. Mak. 10(5), 811–841 (2011)CrossRefMATH
56.
Yen, G., He, Z.: Performance metric ensemble for multiobjective evolutionary algorithms. IEEE Trans. Evol. Comput. 18(1), 131–144 (2014)CrossRef
57.
Zhang, Y., Guo, J., Blais, E., Czarnecki, K.: Performance prediction of configurable software systems by Fourier learning. In: Proceedings of 30th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 365–373 (2015)
58.
Zitzler, E., Künzli, S.: Indicator-based selection in multiobjective search. In: Proceedings of 8th International Conference on Parallel Problem Solving from Nature (PPSN), pp. 832–842 (2004)
59.
Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Proceedings of the Conference on Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems (EUROGEN), pp. 95–100 (2001)
60.
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., da Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117–132 (2003)CrossRef
Metadata
Title
SMTIBEA: a hybrid multi-objective optimization algorithm for configuring large constrained software product lines
Authors
Jianmei Guo
Jia Hui Liang
Kai Shi
Dingyu Yang
Jingsong Zhang
Krzysztof Czarnecki
Vijay Ganesh
Huiqun Yu
Publication date
22-07-2017
Publisher
Springer Berlin Heidelberg
Published in
Software and Systems Modeling / Issue 2/2019
Print ISSN: 1619-1366
Electronic ISSN: 1619-1374
DOI
https://doi.org/10.1007/s10270-017-0610-0

Other articles of this Issue 2/2019

Software and Systems Modeling 2/2019 Go to the issue

Theme Section Paper

A method for testing and validating executable statechart models

Special Section Paper

Semi-automatic derivation of RESTful choreographies from business process choreographies

Regular Paper

FlexiSketch: a lightweight sketching and metamodeling approach for end-users

Special Section Paper

Model clone detection for rule-based model transformation languages

Editorial

Guest editorial to the special section on ECMFA and ICMT at STAF 2016

Special Section Paper

Consistency requirements in business process modeling: a thorough overview

Premium Partner

    Image Credits