TL;DR
This paper surveys methods for incorporating partial user preferences into evolutionary multiobjective optimization (EMO). Instead of finding the entire Pareto front, these methods aim to focus the search on the user's most relevant solutions, leading to a more efficient and targeted approximation. This is crucial because in many real-world applications, users only need a single optimal solution and have some initial idea of what they prefer.
What Problem Does This Paper Address?
Evolutionary multiobjective optimization (EMO) typically aims to find a comprehensive set of non-dominated solutions that approximate the entire Pareto optimal front. The underlying assumption is that without any user input, all Pareto optimal solutions are equally valid. However, in practical scenarios, decision-makers (DMs) usually have a specific goal in mind and are interested in a single solution. Presenting them with the entire Pareto front can be overwhelming and inefficient, especially when they have some initial, albeit incomplete, preferences. This paper addresses the challenge of how to effectively integrate these "partial" user preferences into the EMO process to guide the search towards more relevant areas of the Pareto front, thereby improving efficiency and user satisfaction.
Methods
The paper categorizes and surveys various approaches for incorporating partial user preferences into EMO. These methods can be broadly classified based on the type of information requested from the DM:
- A priori approaches: These methods aggregate multiple objectives into a single objective before the optimization process begins. This allows the use of standard single-objective evolutionary algorithms. Examples include linear combinations or lexicographic ordering of objectives.
- A posteriori approaches: These are the most common EMO methods, where a set of non-dominated solutions is generated first, and the DM then selects their preferred solution from this set. Prominent examples include NSGA-II and SPEA-II.
- Interactive approaches: These methods interleave the optimization process with progressive elicitation of user preferences.
- Intermediate approaches (the focus of the paper): These approaches fall between a priori and a posteriori methods. They integrate partial user preferences during the optimization process to bias the search towards relevant regions of the Pareto front. The paper discusses several techniques within this category:
- Scaling: Adjusting the importance of objectives based on user preferences, influencing the distribution of solutions.
- Constraints: Incorporating user-defined limits on objective values.
- Reference Points: Using aspiration levels or target values to guide the search.
- Trade-off Information: Allowing users to specify acceptable trade-offs between objectives.
- Weighted Performance Measures: Using metrics that incorporate user preferences to evaluate solutions.
- Marginal Contribution: Evaluating solutions based on their contribution to a performance measure, such as hypervolume, with preferences influencing the weighting.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Partial preferences are valuable: Even vague or incomplete user preferences can significantly improve the efficiency and relevance of EMO by focusing the search.
- Beyond the entire Pareto front: The goal of EMO can shift from finding the entire Pareto front to finding a small, relevant subset of solutions that is highly likely to contain the DM's preferred solution.
- Three key advantages of incorporating preferences:
- Focus: Avoids overwhelming the DM with too many (potentially irrelevant) alternatives.
- Speed: Accelerates convergence by directing computational effort towards promising regions.
- Gradient: Restores a useful "fitness gradient" in high-dimensional objective spaces where Pareto dominance becomes less effective.
- Bridging MCDM and EMO: Combining classical Multi-Criteria Decision Making (MCDM) techniques for preference handling with EMO's ability to generate multiple solutions offers significant promise.
- Flexibility in preference elicitation: Different methods cater to different types of user knowledge, from simple constraints to complex trade-off specifications.
Key Results
The paper does not present specific quantitative results from experiments but rather surveys and categorizes existing approaches. The key "results" are the insights into the effectiveness and variety of methods for incorporating partial user preferences. The paper demonstrates that by using partial preferences, EMO can achieve:
- Biased Pareto-front Approximation: Instead of a uniform distribution, the approximation is concentrated in areas deemed more relevant by the user.
- Reduced Computational Effort: By focusing the search, algorithms can find preferred solutions more quickly.
- Improved User Experience: DMs are presented with a more manageable and relevant set of solutions.
Limitations and Future Work
- Application Dependency: The most appropriate method for incorporating preferences depends heavily on the specific application, the shape of the Pareto front (convex/concave), and the DM's comfort level with providing certain types of information.
- Complexity of Preference Specification: While many methods exist, specifying preferences in a "sensible manner" can still be challenging for the DM.
- Extending to Higher Dimensions: Some methods, like guided dominance, become difficult to extend to more than two objectives.
- Future Work: The paper suggests that many of these ideas can be combined and used in an interactive manner, which is the focus of the subsequent chapter. The potential for combining reference point-based approaches with marginal contribution methods is highlighted.
Summary updated