Directed Multiobjective Optimization Based on the Weighted Hypervolume Indicator

Dimo Brockhoff, Johannes Bader, Lothar Thiele, Eckart ZitzlerJournal of Multi-Criteria Decision Analysis 2013 · DOI

TL;DR

This paper introduces a novel approach to multiobjective optimization that allows users to guide the search towards their specific preferences. By extending the well-known hypervolume indicator with user-defined weights, they developed an algorithm (W-HypE) that efficiently navigates complex search spaces and demonstrably achieves better results aligned with user goals.

What Problem Does This Paper Address?

In multiobjective optimization, the goal is often to find a set of "Pareto-optimal" solutions, representing a trade-off between competing objectives. While algorithms like evolutionary algorithms are good at finding this set, they typically don't allow users to express which trade-offs they prefer. This paper addresses the challenge of incorporating user preferences directly into the optimization process. Traditional methods for this are often limited, especially in problems with more than two objectives. The authors aim to provide a flexible and efficient framework for "directed" optimization, where the search actively seeks solutions that align with user-defined priorities.

Methods

The core of the paper is the weighted hypervolume indicator. The standard hypervolume indicator measures the volume of the objective space dominated by a set of solutions. By introducing a weight function $w(z)$, the authors modify this measure to give more importance to certain regions of the objective space. This allows them to:

  • Formalize User Preferences: They develop a toolkit of weight functions that can represent various user preferences, such as stressing a particular objective, aiming for a specific "preference point," or focusing on a defined region.
  • Efficiently Compute Weighted Hypervolume: Calculating the exact weighted hypervolume can be computationally expensive, especially in high dimensions. The paper proposes using Monte Carlo sampling to efficiently estimate this value.
  • W-HypE Algorithm: They introduce a new algorithm, W-HypE, which leverages the weighted hypervolume indicator and Monte Carlo sampling. W-HypE is designed to be efficient and scalable to problems with many objectives. It uses an "improved heuristic set mutation" that prioritizes solutions contributing most to the weighted hypervolume.

Datasets

The paper evaluates its approach on standard benchmark problems:

  • ZDT problems: Specifically ZDT1 for bi-objective optimization.
  • DTLZ problems: DTLZ2 for bi-objective, 3-objective, and 7-objective scenarios.
  • 0/1 Knapsack Problem: A discrete domain problem.

No new benchmark datasets were introduced.

Key Insights and Ideas

  • Hypervolume as a Preference Tool: The hypervolume indicator, beyond just measuring quality, can be actively steered by user preferences through weighting. This is a powerful shift from simply finding a Pareto front to finding the desired part of a Pareto front.
  • Monte Carlo for Scalability: The use of Monte Carlo sampling is crucial for making weighted hypervolume calculations feasible for problems with many objectives, overcoming a significant computational bottleneck.
  • Toolkit for Preference Articulation: The proposed toolkit of weight functions and their composition methods provides a systematic way to translate diverse user preferences into a form that an optimization algorithm can understand.
  • Equivalence of Weighting and Transformation: A key theoretical result shows that transforming objective functions using monotonic desirability functions is equivalent to using a specific weighted hypervolume indicator. This bridges two different ways of incorporating preferences.

Key Results

  • Superior Performance with W-HypE: W-HypE consistently achieved higher normalized hypervolume values compared to reference algorithms (IBEA, NSGA-II, SPEA2) when optimizing for specific weight functions. This indicates that W-HypE successfully directs the search towards the user's intended regions.
  • Statistical Significance: Statistical tests (Scheirer-Ray-Hare, Conover-Inman) confirmed that the choice of weight function and algorithm had a significant impact on hypervolume values, and W-HypE's performance was statistically superior in most cases.
  • Efficiency: The Monte Carlo approach in W-HypE made it feasible to handle problems with up to 7 objectives, with runtimes reported in seconds per generation on a standard laptop.
  • Discrete Domain Applicability: The approach was successfully applied to the 0/1 knapsack problem, demonstrating its versatility beyond continuous optimization.

Limitations and Future Work

  • Interactive Optimization: The authors note that an adaptive optimization approach allowing for closer interaction with a decision maker is a promising future direction. This would enable continuous steering and refinement of the search.
  • Computational Cost: While Monte Carlo sampling improves efficiency, calculating the exact hypervolume remains computationally expensive, especially for very high dimensions or complex weight functions.
  • "Nice" Convergence: For some discrete problems (knapsack), the convergence to the Pareto front in low-weight regions was not as "nice" as in continuous cases, potentially due to a lower rate of creating dominated solutions.
  • General Superiority vs. Specificity: The paper emphasizes that the goal is to demonstrate the specificity of W-HypE in achieving user-defined preferences, rather than claiming general superiority over all other algorithms in all scenarios.

Summary updated

Abstract

ABSTRACT Recently, there has been a large interest in set‐based evolutionary algorithms for multi objective optimization. They are based on the definition of indicators that characterize the quality of the current population while being compliant with the concept of Pareto‐optimality. It has been shown that the hypervolume indicator, which measures the dominated volume in the objective space, enables the design of efficient search algorithms and, at the same time, opens up opportunities to express user preferences in the search by means of weight functions. The present paper contains the necessary theoretical foundations and corresponding algorithms to (i) select appropriate weight functions, to (ii) transform user preferences into weight functions and to (iii) efficiently evaluate the weighted hypervolume indicator through Monte Carlo sampling. The algorithm W‐HypE , which implements the previous concepts, is introduced, and the effectiveness of the search, directed towards the user's preferred solutions, is shown using an extensive set of experiments including the necessary statistical performance assessment. Copyright © 2013 John Wiley & Sons, Ltd.
BibTeX
@article{brockhoff2013directed,
  author = {Dimo Brockhoff and Johannes Bader and Lothar Thiele and Eckart Zitzler},
  title = {{Directed Multiobjective Optimization Based on the Weighted Hypervolume Indicator}},
  journal = {Journal of Multi-Criteria Decision Analysis},
  year = {2013},
  doi = {10.1002/mcda.1502},
}
Figure