28559 articles – 22057 references  [version française]

inria-00638989, version 1

## Hypervolume-based Multiobjective Optimization: Theoretical Foundations and Practical Implications

Anne Auger () 1, Johannes Bader a2, Dimo Brockhoff () 1, Eckart Zitzler a2

Theoretical Computer Science 425 (2011) 75-103

Abstract: In recent years, indicator-based evolutionary algorithms, allowing to implicitly incorporate user preferences into the search, have become widely used in practice to solve multiobjective optimization problems. When using this type of methods, the optimization goal changes from optimizing a set of objective functions simultaneously to the single-objective optimization goal of finding a set of $\mu$ points that maximizes the underlying indicator. Understanding the difference between these two optimization goals is fundamental when applying indicator-based algorithms in practice. On the one hand, a characterization of the inherent optimization goal of different indicators allows the user to choose the indicator that meets her preferences. On the other hand, knowledge about the sets of $\mu$ points with optimal indicator values---so-called optimal $\mu$-distributions---can be used in performance assessment whenever the indicator is used as a performance criterion. However, theoretical studies on indicator-based optimization are sparse. One of the most popular indicators is the weighted hypervolume indicator. It allows to guide the search towards user-defined objective space regions and at the same time has the property of being a refinement of the Pareto dominance relation with the result that maximizing the indicator results in Pareto-optimal solutions only. In previous work, we theoretically investigated the unweighted hypervolume indicator in terms of a characterization of optimal $\mu$-distributions and the influence of the hypervolume's reference point for general bi-objective optimization problems. In this paper, we generalize those results to the case of the weighted hypervolume indicator. In particular, we present general investigations for finite $\mu$, derive a limit result for $\mu$ going to infinity in terms of a density of points and derive lower bounds (possibly infinite) for placing the reference point to guarantee the Pareto front's extreme points in an optimal $\mu$-distribution. Furthermore, we state conditions about the slope of the front at the extremes such that there is no finite reference point that allows to include the extremes in an optimal $\mu$-distribution---contradicting previous belief that a reference point chosen just above the nadir point or the objective space boundary is sufficient for obtaining the extremes. However, for fronts where there exists a finite reference point allowing to obtain the extremes, we show that for $\mu$ to infinity, a reference point that is slightly worse in all objectives than the nadir point is a sufficient choice. Last, we apply the theoretical results to problems of the ZDT, DTLZ, and WFG test problem suites.

• a –  ETH Zurich
• 1:  TAO (INRIA Saclay - Ile de France)
• INRIA – CNRS : UMR8623 – Université Paris XI - Paris Sud
• 2:  Computer Engineering and Networks Laboratory (TIK)
• Swiss Federal Institute of Technology Zurich (ETH Zurich)
• Domain : Computer Science/Neural and Evolutionary Computing

• inria-00638989, version 1
• oai:hal.inria.fr:inria-00638989
• From:
• Submitted on: Monday, 7 November 2011 18:15:46
• Updated on: Saturday, 27 October 2012 14:17:25