No Access

Mutation with Local Searching and Elite Inheritance Mechanism in Multi-Objective Optimization Algorithm: A Case Study in Software Product Line

Kai Shi

Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai, P. R. China

Shanghai Key Laboratory of Computer Software Evaluating and Testing, Shanghai, P. R. China

E-mail Address: BH4AWS@163.com

Search for more papers by this author

Huiqun Yu

Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai, P. R. China

E-mail Address: yhq@ecust.edu.cn

Search for more papers by this author

Guisheng Fan

Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai, P. R. China

E-mail Address: gsfan@ecust.edu.cn

Search for more papers by this author

Jianmei Guo

Alibaba Group, Hangzhou, P. R. China

E-mail Address: guojianmei@gmail.com

Search for more papers by this author

Liqiong Chen

Department of Computer Science and Information Engineering, Shanghai Institute of Technology, Shanghai, P. R. China

E-mail Address: lqchen@sit.edu.cn

Search for more papers by this author

Xingguang Yang

Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai, P. R. China

E-mail Address: xingguang2955@163.com

Search for more papers by this author

, and

Huaiying Sun

Department of Computer Science and Information Engineering, Shanghai Institute of Technology, Shanghai, P. R. China

E-mail Address: ecustshy@foxmail.com

Search for more papers by this author

https://doi.org/10.1142/S0218194019500426Cited by:2 (Source: Crossref)

Abstract

An effective method for addressing the configuration optimization problem (COP) in Software Product Lines (SPLs) is to deploy a multi-objective evolutionary algorithm, for example, the state-of-the-art SATIBEA. In this paper, an improved hybrid algorithm, called SATIBEA-LSSF, is proposed to further improve the algorithm performance of SATIBEA, which is composed of a multi-children generating strategy, an enhanced mutation strategy with local searching and an elite inheritance mechanism. Empirical results on the same case studies demonstrate that our algorithm significantly outperforms the state-of-the-art for four out of five SPLs on a quality Hypervolume indicator and the convergence speed. To verify the effectiveness and robustness of our algorithm, the parameter sensitivity analysis is discussed and three observations are reported in detail.

Keywords:

References

1. S. Apel, D. S. Batory, C. Kästner and G. Saake , Feature-Oriented Software Product Lines — Concepts and Implementation (Springer Verleg, Berlin, 2016). Google Scholar
2. A. Arcuri and L. C. Briand , A practical guide for using statistical tests to assess randomized algorithms in software engineering, in Proc. 33th Int. Conf. Software Engineering, 2011, pp. 1–10. Google Scholar
3. A. Arcuri and G. Fraser , Parameter tuning or default values? An empirical investigation in search-based software engineering, Empir. Softw. Eng. 18(3) (2013) 594–623. Web of Science, Google Scholar
4. D. Benavides, S. Segura and A. R. Cortés , Automated analysis of feature models 20 years later: A literature review, Inf. Syst. 35(6) (2010) 615–636. Web of Science, Google Scholar
5. T. Berger, R. Rublack, D. Nair, J. M. Atlee, M. Becker, K. Czarnecki and A. Wasowski , A survey of variability modeling in industrial practice, in Proc. 7th Int. Conf. Variability Modelling of Software-Intensive Systems, 2013, pp. 7:1–7:8. Google Scholar
6. J. Brest and M. S. Maucec , Population size reduction for the differential evolution algorithm, Appl. Intell. 29(3) (2008) 228–247. Web of Science, Google Scholar
7. D. Brockhoff, T. Friedrich and F. Neumann , Analyzing hypervolume indicator based algorithms, in Proc. 10th Int. Conf. Parallel Problem Solving from Nature, 2008, pp. 651–660. Google Scholar
8. P. Clements and L. Northrop , Software Product Lines: Practices and Patterns (Addison-Wesley, 2001). Google Scholar
9. K. Deb, M. Mohan and S. Mishra , Towards a quick computation of well-spread pareto-optimal solutions, in Proc. 2nd Int. Conf. Evolutionary Multi-Criterion Optimization, 2003, pp. 222–236. Google Scholar
10. J. J. Durillo and A. J. Nebro , jMetal: A Java framework for multi-objective optimization, Adv. Eng. Softw. 42(10) (2011) 760–771. Web of Science, Google Scholar
11. J. J. Durillo, A. J. Nebro and E. Alba , The jMetal framework for multi-objective optimization: Design and architecture, in Proc. IEEE Congress on Evolutionary Computation, 2010, pp. 4138–4325. Google Scholar
12. N. Eén and N. Sörensson , An extensible SAT-solver, in Proc. 6th Int. Conf. Theory and Applications of Satisfiability Testing, 2003, pp. 502–518. Google Scholar
13. W. Gong, Z. Cai and C. X. Ling , DE/BBO: A hybrid differential evolution with biogeography-based optimization for global numerical optimization, Soft Comput. 15(4) (2010) 645–665. Web of Science, Google Scholar
14. J. Guo, J. H. Liang, K. Shi, D. Yang, J. Zhang, K. Czarnecki, V. Ganesh and H. Yu , SMTIBEA: A hybrid multi-objective optimization algorithm for configuring large constrained software product lines, Softw. Syst. Model. 18(2) (2019) 1447–1466. Web of Science, Google Scholar
15. J. Guo and K. Shi , To preserve or not to preserve invalid solutions in search-based software engineering: A case study in software product lines, in Proc. 40th IEEE/ACM Int. Conf. Software Engineering, 2018, pp. 12–22. Google Scholar
16. 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, J. Syst. Softw. 84(12) (2011) 2208–2221. Web of Science, Google Scholar
17. 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 Proc. 29th ACM/IEEE Int. Conf. Automated Software Engineering, 2014, pp. 409–420. Google Scholar
18. M. Harman , The current state and future of search based software engineering, in Proc. Int. Conf. Software Engineering (ISCE), Workshop on the Future of Software Engineering, 2007, pp. 342–357. Google Scholar
19. 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, in Proc. 18th Int. Software Product Line Conf., 2014, pp. 1:5–1:18. Google Scholar
20. M. Harman and B. F. Jones , Search based software engineering, Inf. Softw. Technol. 43(14) (2001) 833–839. Web of Science, Google Scholar
21. M. Harman, S. Mansouri and Y. Zhang, Search based software engineering: A comprehensive analysis and review of trends techniques and applications, Technical report, King’s College London TR-09-03, 2009. Google Scholar
22. C. Henard, M. Papadakis, M. Harman and Y. L. Traon , Combining multi-objective search and constraint solving for configuring large software product lines, in Proc. 37th IEEE/ACM Int. Conf. Software Engineering, 2015, pp. 517–528. Google Scholar
23. C. Henard, M. Papadakis, G. Perrouin, J. Klein and Y. L. Traon , Multi-objective test generation for software product lines, in Proc. 17th Int. Software Product Line Conf., 2013, pp. 62–71. Google Scholar
24. R. M. Hierons, M. Li, X. Liu, S. Segura and W. Zheng , SIP: Optimal product selection from feature models using many-objective evolutionary optimization, ACM Trans. Softw. Eng. Methodol. 25(2) (2016) 17. Web of Science, Google Scholar
25. H. Ishibuchi, H. Masuda, Y. Tanigaki and Y. Nojima , Modified distance calculation in generational distance and inverted generational distance, in Proc. 8th Int. Conf. Evolutionary Multi-Criterion Optimization, 2015, pp. 110–125. Google Scholar
26. K. Kang, S. Cohen, J. Hess, W. Novak and A. Peterson, Feature-Oriented Domain Analysis (FODA) Feasibility Study, Technical report, CMU SEI, SEI-90-TR-21, 1990. Google Scholar
27. J. Knowles and D. Corne , On metrics for comparing nondominated sets, in Proc. 2th Evolutionary Computation, 2002, pp. 711–716. Google Scholar
28. X. Lian and L. Zhang , An evolutionary methodology for optimized feature selection in software product lines, in Proc. 26th Int. Conf. Software Engineering and Knowledge Engineering, 2014, pp. 63–66. Google Scholar
29. X. Lian and L. Zhang , Optimized feature selection towards functional and non-functional requirements in software product lines, in Proc. 22nd IEEE Int. Conf. Software Analysis, Evolution, and Reengineering, 2015, pp. 191–200. Google Scholar
30. M. R. Lohokare, Bijaya K. Panigrahi, Shyam S. Pattnaik, S. Devi and A. Mohapatra , Neighborhood search-driven accelerated biogeography-based optimization for optimal load dispatch, IEEE Trans. Systems Man Cybernetics Part C 42(5) (2012) 641–652. Google Scholar
31. H. Lu, T. Yue, S. Ali and L. Zhang , Nonconformity resolving recommendations for product line configuration, in Proc. IEEE Int. Conf. Software Testing, Verification and Validation, 2016, pp. 57–68. Google Scholar
32. LVAT. Linux Variabiltiy Analysis Tools, 2016. Google Scholar
33. A. Metzger and K. Pohl , Software product line engineering and variability management: Achievements and challenges, in Proc. on Future of Software Engineering, 2014, pp. 70–84. Google Scholar
34. W. Mkaouer, M. Kessentini, A. Shaout, P. Koligheu, S. Bechikh, K. Deb and A. Ouni , Many-objective software remodularization using NSGA-III, ACM Trans. Softw. Eng. Methodol. 24(3) (2015) 1–45. Web of Science, Google Scholar
35. M. Noorian, E. Bagheri and W. Du , Toward automated quality-centric product line configuration using intentional variability, J. Softw. Evol. Process 29(9) (2017) e1870. Web of Science, Google Scholar
36. E. Nudelman, A. Devkar, Y. Shoham, K. Leyton-Brown and H. Hoos , SATzilla: An algorithm portfolio for SAT, in Proc. 7th Int. Conf. Theory and Applications of Satisfiability Testing, 2004, pp. 13–14. Google Scholar
37. R. Olaechea, D. Rayside, J. Guo and K. Czarnecki , Comparison of exact and approximate multi-objective optimization for software product lines, in Proc. 18th Int. Software Product Line Conf., 2014, pp. 92–101. Google Scholar
38. G. G. Pascual, R. E. Lopez-Herrejon, M. Pinto, L. Fuentes and A. Egyed , Applying multiobjective evolutionary algorithms to dynamic software product lines for reconfiguring mobile applications, J. Syst. Softw. 103 (2015) 392–411. Web of Science, Google Scholar
39. K. Pohl, G. Bockle and F. v. d. Linden , Software Product Line Engineering: Foundations, Principles, and Techniques (Springer, 2005). Google Scholar
40. T. Saber, D. Brevet, G. Botterweck and A. Ventresque , Is seeding a good strategy in multi-objective feature selection when feature models evolve? Inf. Softw. Technol. 95 (2018) 266–280. Web of Science, Google Scholar
41. F. Sarro, A. Petrozziello and M. Harman , Multi-objective software effort estimation, in Proc. 38th Int. Conf. Software Engineering, 2016, pp. 619–630. Google Scholar
42. A. Sayyad, J. Ingram, T. Menzies and H. Ammar , Scalable product line configuration: A straw to break the camel’s back, in Proc. 28th IEEE/ACM Int. Conf. Automated Software Engineering, 2013, pp. 465–474. Google Scholar
43. A. S. Sayyad, J. Ingram, T. Menzies and H. Ammar , Optimum feature selection in software product lines: Let your model and values guide your search, in Proc. 1st Int. Workshop on Combining Modelling and Search-Based Software Engineering, 2013, pp. 22–27. Google Scholar
44. 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 Proc. 35th Int. Conf. Software Engineering, 2013, pp. 492–501. Google Scholar
45. A. Schaerf , Local search techniques for constrained portfolio selection problems, CoRR, cs.CE/0104017, 2001. Google Scholar
46. K. Shi , Combining evolutionary algorithms with constraint solving for configuration optimization, in Proc. IEEE Int. Conf. Software Maintenance and Evolution, 2017, pp. 665–669. Google Scholar
47. D. Simon, M. G. H. Omran and M. Clerc , Linearized biogeography-based optimization with re-initialization and local search, Inf. Sci. 267 (2014) 140–157. Web of Science, Google Scholar
48. K. C. Tan, T. H. Lee and E. F. Khor , Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization, IEEE Trans. Evol. Comput. 5(6) (2001) 565–588. Web of Science, Google Scholar
49. T. H. Tan, Y. Xue, M. Chen, J. Sun, Y. Liu and J. S. Dong , Optimizing selection of competing features via feedback-directed evolutionary algorithms, in Proc. Int. Symp. Software Testing and Analysis, 2015, pp. 246–256. Google Scholar
50. A. Vargha and H. D. Delaney , A critique and improvement of the “CL” common language effect size statistics of McGraw and Wong, J. Educ. Behav. Stat. 25(2) (2000) 101–132. Web of Science, Google Scholar
51. J. White, B. Doughtery and D. C. Schmidt , Filtered cartesian flattening: An approximation technique for optimally selecting features while adhering to resource constraints, in Proc. 12th Int. Conf. Software Product Lines SPLC, Second Volume (Workshops), 2008, pp. 209–216. Google Scholar
52. Z. Wu, J. Tang, C. K. Kwong and C.-Y. Chan , An optimization model for reuse scenario selection considering reliability and cost in software product line development, Int. J. Inf. Technol. Decis. Making 10(5) (2011) 811–841. Link, Web of Science, Google Scholar
53. X. Lian, L. Zhang, J. Jiang and W. Goss , An approach for optimized feature selection in large-scale software product lines, J. Syst. Softw. 137 (2018) 636–651. Web of Science, Google Scholar
54. Y. Xue, J. Zhong, T. H. Tan, Y. Liu, W. Cai, M. Chen and J. Sun , IBED: Combining IBEA and DE for optimal feature selection in software product line engineering, Appl. Soft Comput. 49 (2016) 1215–1231. Web of Science, Google Scholar
55. G. G. Yen and Z. He , Performance metric ensemble for multiobjective evolutionary algorithms, IEEE Trans. Evol. Comput. 18(1) (2014) 131–144. Web of Science, Google Scholar
56. S. Yoo and M. Harman , Pareto efficient multi-objective test case selection, in Proc. ACM/SIGSOFT Int. Symp. Software Testing and Analysis, 2007, pp. 140–150. Google Scholar
57. E. Zitzler and S. Künzli , Indicator-based selection in multiobjective search, in Proc. 8th Int. Conf. Parallel Problem Solving from Nature, 2004, pp. 832–842. Google Scholar
58. E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca and V. G. da Fonseca , Performance assessment of multiobjective optimizers: An analysis and review, IEEE Trans. Evol. Comput. 7(2) (2003) 117–132. Web of Science, Google Scholar