Pareto Search vs Weighted Search in Multi-objective SBSE
T. Chen and M. Li. The weights can be harmful: Pareto search versus weighted search in multi-objective search-based software engineering. ACM Transactions on Software Engineering and Methodology. 2022.
T. Chen and M. Li. The weights can be harmful: Pareto search versus weighted search in multi-objective search-based software engineering. ACM Transactions on Software Engineering and Methodology. 2022.
Brief:
Brief:
In multi-objective SBSE, when clear preferences (e.g., a set of weights which reflect relative importance between objectives) of the decision-maker 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 enable the search to focus on what is only interested in.
In multi-objective SBSE, when clear preferences (e.g., a set of weights which reflect relative importance between objectives) of the decision-maker 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 enable the search to focus on what is only interested in.
This paper 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. We found that Pareto search is significantly better than its weighted counterpart at the majority of the time (up to 77% of the cases).
This paper 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. We found that Pareto search is significantly better than its weighted counterpart at the majority of the time (up to 77% of the cases).
Illustration:
Illustration:
Illustration of Pareto search and weighted search in a bi-objective minimisation scenario, where the curve represents the Pareto front. For weighted search, the weight vector is (0.5, 0.5) and the population seeks to converge into one point on the Pareto front.
Illustration of Pareto search and weighted search in a bi-objective minimisation scenario, where the curve represents the Pareto front. For weighted search, the weight vector is (0.5, 0.5) and the population seeks to converge into one point on the Pareto front.
Results:
Results:
Three representative problem instances where weighted search performs worse than Pareto search
Three representative problem instances where weighted search performs worse than Pareto search
The left (a) and the middle (b) are situations that the solution obtained by weighted search is dominated by that obtained by Pareto search; the right (c) is the situation wherein a non-dominated solution has been obtained by weighted search, but it is not the solution the decision maker wants (i.e., not the weight (0.7, 03) corresponding to).