A novel aggregation-based dominance for Pareto-based evolutionary algorithms to configure software product lines

In software engineering, optimal feature selection for software product lines (SPLs) is an important and complicated task, involving simultaneous optimization of multiple competing objectives in large but highly constrained search spaces. A feature model is the standard representation of features of all possible products as well as the relationships among them for an SPL. Recently, various multi-objective evolutionary algorithms have been used to search for valid product configurations. However, the issue of the balance between correctness and diversity of solutions obtained in a reasonable time has been found very challenging for these algorithms. To tackle this problem, this paper proposes a novel aggregation-based dominance (ADO) for Pareto-based evolutionary algorithms to direct the search for high-quality solutions. Our method was tested on two widely used Pareto-based evolutionary algorithms: NSGA-II and SPEA2+SDE and validated on nine different SPLs with up to 10,000 features and two real-world SPLs with up to 7 objectives. Our experiments have shown the effectiveness and efficiency of both ADO-based NSGA-II and SPEA2+SDE: (1) Both algorithms could generate 100% valid solutions for all feature models. (2) The performance of both algorithms was improved as measured by the hypervolume metric in 7/9 and 8/9 feature models. (3) Even for the largest tested feature model with 10,000 features, it required under 40 s on a standard desktop to find 100% valid solutions in a single run of both algorithms.