Hypervolume

This page presents a collection of links and papers related to the hypervolume quality indicator, a measure often used to assess the performance of multi-objective evolutionary algorithms. It is also used directly inside EAs to provide a selection pressure rewarding convergence as well as objective-space diversity of the candidate solutions. Hypervolume has the drawback that it takes exponential time in the number of dimensions to compute. For this reason, there is an active community developing faster algorithms (in theory and in practice) for this important problem.

(Contributors: Simon Wessing, Boris Naujoks, Michael Emmerich (Leiden U.), Günter Rudolph and Nicola Beume)

Implementations

Examples of the dominated hypervolume in two and three dimensions. The left figure shows a minimization case whereas the right one shows maximization.

Hypervolume

Python

• PyGMO library: Python wrapper of PaGMO
• Python version by Simon Wessing is a reimplementation of the code by Fonseca et al. (Variant 3, Version 1.2) in pure Python. Some small modifications have been applied to obtain more performance on the Python interpreter.
# usage example:
from hv import HyperVolume
referencePoint = [2, 2, 2]
hyperVolume = HyperVolume(referencePoint)
front = [[1, 0, 1], [0, 1, 0]]
result = hyperVolume.compute(front)

Weighted Hypervolume

• The C version implementations of three different bi-objective hypervolume based indicators mentioned in the above paper which incorporate the following preferences: (i) focus on extreme points, (ii) focus on the extremes of the second objective plus one additional extreme point for the first objective, (iii) focus on a given reference point

SMS-EMOA

The exclusive hypervolume contribution of each point in the same examples as above.

The S-Metric Selection Evolutionary Multiobjective Optmization Algorithm uses the hypervolume indicator to compute the exclusive hypervolume contribution of solutions.

MATLAB

• MATLAB version by Fabian Kretzschmar and Tobias Wagner (Last Update on March 7, 2016: Implemented Online Convergence Detection according to Wagner, T.; Trautmann, H.: Online Convergence Detection for Evolutionary Multi-Objective Algorithms Revisited. In: Proceedings of the 2010 IEEE Congress on Evolutionary Computation (IEEE CEC 2010), 18.7.-23.7. 2010, Barcelona, Spain, G. Fogel, H. Ishibuchi (Hrsg.), ISBN 978-1-4244-6910-8, S. 3554-3561)

Python

• In the package evoalgos by Simon Wessing

Hypervolume-based Measures

• Gradient of Hypervolume
• Hypervolume contribution
• S-metric-based Expected Improvement (SExI)
• Online Convergence Detection (OCD-Classic and OCD-HV)

Literature

Hypervolume Theory

• Lower Bound Runtime:
• Worst Case Upper Bound Runtime:
• Complexity of recursive algorithm:
• Runtime Analysis
• of the -SIBEA on two pseudo-boolean test functions, see D. Brockhoff, T. Friedrich, and F. Neumann. Analyzing Hypervolume Indicator Based Algorithms. In G. Rudolph et al., editors, Conference on Parallel Problem Solving From Nature (PPSN X), volume 5199 of LNCS, pages 651–660. Springer, 2008

Selected Applications

• Water Distribution Network Design
• Edgar Reehuis, Johannes Kruisselbrink, Andre Deutz, Thomas Baeck, Michael Emmerich, Multiobjective optimization of water distribution networks using SMS-EMOA, EUROGEN 2011, C. Poloni, D. Quagliarella, J. Periaux, N. Gauger and K. Giannakoglou (Eds.), CIRA, Capua, Italy 2011, pages 269-279
• Grid Computing
• Kuijl, A. v. d., Emmerich, M. T. M. and Li, H. (2010), A robust multi-objective resource allocation scheme incorporating uncertainty and service differentiation. Concurrency and Computation: Practice and Experience, 22: 314–328. doi: 10.1002/cpe.1481
• Software Architecture Design
• Rui Li, R. Etemaadi, Michael T. M. Emmerich, and Michel R. V. Chaudron. An Evolutionary Multiobjective Optimization Approach to Component-Based Software Architecture Design. IEEE Conference on Evolutionary Computation, New Orleans, June 5-8, 2011.
• Molecular Control
• J.W. Klinkenberg, T.M. Emmerich, A.H. Deutz, O.M. Shir, T. Baeck: A reduced-cost SMS-EMOA using kriging, self-adaptation, and parallelization In M. Ehrgott et al.: Conference on Multicriteria Decision Making 2008, January 2008, Auckland, NZ , Lecture Notes on Economy and Mathematical Systems, 2009 Springer
• Planning Software
• Airfoil Optimization
• Boris Naujoks, Nicola Beume, and Michael Emmerich. Metamodel-Assisted SMS EMOA Applied to Airfoil Optimization Tasks. In R. Schilling, W. Haase, J. Periaux, and H. Baier, editors, Proceedings EUROGEN'05 (CD-ROM). FLM, TU Munich, 2005
• Set-oriented and Indicator Based Optimization: Open Theoretical Problem Page (includes recent results and open questions on the hypervolume indicator and related measures), see Emmerich, Naujoks, Brockhoff 2013-

Last modified: 2020-06-29 19:09 by Günter Rudolph