Evolutionary Search Techniques with Strong Heuristics for Multi-Objective Feature Selection in Software Product Lines

Software design is a process of trading off competing objectives. If the user objective space is rich, then we should use optimizers that can fully exploit that richness. For example, this study configures software product lines (expressed as feature models) using various search-based software engineering methods. Our main result is that as we increase the number of optimization objectives, the methods in widespread use (e.g. NSGA-II, SPEA2) perform much worse than IBEA (Indicator-Based Evolutionary Algorithm). IBEA works best since it makes most use of user preference knowledge. Hence it does better on the standard measures (hypervolume and spread) but it also generates far more products with 0 violations of domain constraints. We also present significant improvements to IBEA's performance by employing three strong heuristic techniques that we call PUSH, PULL, and seeding. The PUSH technique forces the evolutionary search to respect certain rules and dependencies defined by the feature models, while the PULL technique gives higher weight to constraint satisfaction as an optimization objective and thus achieves a higher percentage of fully-compliant configurations within shorter runtimes. The seeding technique helps in guiding very large feature models to correct configurations very early in the optimization process. Our conclusion is that the methods we apply in search-based software engineering need to be carefully chosen, particularly when studying complex decision spaces with many optimization objectives. Also, we conclude that search methods must be customized to fit the problem at hand. Specifically, the evolutionary search must respect domain constraints.

Name thesis:degree_name

PhD

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Lane Department of Computer Science and Electrical Engineering

Year dc:date.available

2014

Author dc:creator

• Sayyad, Abdel Salam

Contributors dc:contributor

• Hany Ammar
• Tim Menzies
• Ali Mili
• Mario Perhinschi
• Ramana Reddy

• Computer engineering
• Artificial intelligence
• Computer science

Identifier

https://researchrepository.wvu.edu/etd/303

OAI identifier oai:identifier

oai:researchrepository.wvu.edu:etd-1306