The weights can be harmful: pareto search versus weighted search in multi-objective search-based software engineering

Tao Chen, Miqing Li

Research output: Contribution to journalArticlepeer-review

122 Downloads (Pure)

Abstract

In presence of multiple objectives to be optimized in Search-Based Software Engineering (SBSE), Pareto search has been commonly adopted. It searches for a good approximation of the problem’s Pareto-optimal solutions, from which the stakeholders choose the most preferred solution according to their preferences. However, when clear preferences of the stakeholders (e.g., a set of weights that reflect relative importance between objectives) are available prior to the search, weighted search is believed to be the first choice, since it simplifies the search via converting the original multi-objective problem into a single-objective one and enables the search to focus on what only the stakeholders are interested in.

This article questions such a “weighted search first” belief. We show that the weights can, in fact, be harmful to the search process even in the presence of clear preferences. Specifically, we conduct a large-scale empirical study that consists of 38 systems/projects from three representative SBSE problems, together with two types of search budget and nine sets of weights, leading to 604 cases of comparisons. Our key finding is that weighted search reaches a certain level of solution quality by consuming relatively less resources at the early stage of the search; however, Pareto search is significantly better than its weighted counterpart the majority of the time (up to 77% of the cases), as long as we allow a sufficient, but not unrealistic search budget. This is a beneficial result, as it discovers a potentially new “rule-of-thumb” for the SBSE community: Even when clear preferences are available, it is recommended to always consider Pareto search by default for multi-objective SBSE problems, provided that solution quality is more important. Weighted search, in contrast, should only be preferred when the resource/search budget is limited, especially for expensive SBSE problems. This, together with other findings and actionable suggestions in the article, allows us to codify pragmatic and comprehensive guidance on choosing weighted and Pareto search for SBSE under the circumstance that clear preferences are available. All code and data can be accessed at https://github.com/ideas-labo/pareto-vs-weight-for-sbse.
Original languageEnglish
Article number5
Pages (from-to)1–40
Number of pages40
JournalACM Transactions on Software Engineering and Methodology
Volume32
Issue number1
Early online date23 Apr 2022
DOIs
Publication statusPublished - Jan 2023

Keywords

  • Search-based software engineering
  • multi-objective optimization
  • pareto optimization
  • quality evaluation
  • quality indicator
  • user preference
  • configurable systems
  • adaptive systems
  • self-adaptive systems

Fingerprint

Dive into the research topics of 'The weights can be harmful: pareto search versus weighted search in multi-objective search-based software engineering'. Together they form a unique fingerprint.

Cite this