### Table of Contents

# 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.

## Implementations

### Hypervolume

#### C/C++

**C version**by Carlos Fonseca et al. (algorithm description)**C++ version of HOY**by Nicola Beume**Shark library**by Thomas Voß- Several C++ algorithms in the
**PaGMO library**

#### 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)

#### R

**R version**by Olaf Mersmann

### Weighted Hypervolume

- In The Hypervolume Indicator Revisited: On the Design of Pareto-compliant Indicators Via Weighted Integration (E. Zitzler, D. Brockhoff, and L. Thiele. In S. Obayashi et al., editors,
*Conference on Evolutionary Multi-Criterion Optimization (EMO 2007)*, volume 4403 of LNCS, pages 862–876, Berlin, 2007. Springer), the so-called weighted hypervolume indicator has been introduced in order to incorporate specific user preferences into the search.

- 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 S-Metric Selection Evolutionary Multiobjective Optmization Algorithm uses the hypervolume indicator to compute the exclusive hypervolume contribution of solutions.

#### C/C++

- As part of the
**Shark library**by Thomas Voß

#### 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)

#### Java

**JMetal version**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

#### First Appearance of the Hypervolume

- at this time simply as “the size of the space covered”
- E. Zitzler and L. Thiele. Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study. In
*Conference on Parallel Problem Solving from Nature (PPSN V)*, volume 1498 of LNCS, pages 292–301, 1998

#### Hypervolume Theory

- Lower Bound Runtime:

- Worst Case Upper Bound Runtime:

- Complexity of recursive algorithm:

- Approximation
- fast and precise approximation of 2-dimensional hypervolume, see Tobias Friedrich's homepage

- 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

- Hypervolume-based Subset Selection and Differential Hypervolume
- Asymptotically optimal algorithm for computing all differential hypervolume contributions in 2-D and 3-D, see Emmerich and Fonseca.
- Dynamic programming algorithm for 2-D subset selection in , see Auger, Bader, Brockhoff and Zitzler, 2009.
- 2-D subset selection for hypervolume and epsilon-indicator: Bringmann et al. 2014
- Upper bounds for complexity of finding the minimal contributor for : Bringmann and Friedrich.
- Set-based Gradient of the hypervolume, see Emmerich, Deutz and Beume

- Optimization Goal of (Weighted) Hypervolume
- Optimal distribution of points maximizing the (weighted) hypervolume indicator, see Auger, Bader, Brockhoff and Zitzler, 2012.

#### Hypervolume-based Multiobjective Optimizers

- SMS-EMOA

- HypE
- see Johannes Bader and Eckart Zitzler. HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization. Evolutionary Computation, posted online since July 22, 2010
- code available on the PISA web page

- MO-CMA-ES
- code available within the Shark library

#### 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
- Hui Li, Giuliano Casale, and Tariq Ellahi. 2010. SLA-driven planning and optimization of enterprise applications. In
*Proceedings of the first joint WOSP/SIPEW international conference on Performance engineering (WOSP/SIPEW '10)*. ACM, New York, NY, USA, 117-128.

- 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