====== 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 =====

<WRAP box border right centeralign 440px>
{{:rudolph:hypervolume:hv.png?200|}}
{{:rudolph:hypervolume:hvemm3d.png?200|}}

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


==== Hypervolume ====

=== C/C++ ===

  * **[[http://iridia.ulb.ac.be/~manuel/hypervolume|C version]]** by Carlos Fonseca et al. ([[http://dx.doi.org/10.1109/CEC.2006.1688440|algorithm description]])
  * **[[http://ls11-www.cs.tu-dortmund.de/people/beume/publications/hoy.cpp|C++ version of HOY]]** by Nicola Beume
  * **[[http://image.diku.dk/shark/|Shark library]]** by Thomas Voß
  * Several C++ algorithms in the **[[https://esa.github.io/pagmo/|PaGMO library]]**

=== Python ===

  * **[[https://esa.github.io/pygmo/|PyGMO library]]**: Python wrapper of PaGMO
  * **{{:rudolph:hypervolume:hv_python.zip|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.
<code python>
# usage example:
from hv import HyperVolume
referencePoint = [2, 2, 2]
hyperVolume = HyperVolume(referencePoint)
front = [[1, 0, 1], [0, 1, 0]]
result = hyperVolume.compute(front)
</code>

=== R ===

  * **[[http://cran.r-project.org/web/packages/emoa/|R version]]** by Olaf Mersmann



==== Weighted Hypervolume ====
  * In [[http://dx.doi.org/10.1007/978-3-540-70928-2_64|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 **[[http://www.tik.ee.ethz.ch/sop/download/supplementary/weightedHypervolume/|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 ====
<WRAP box border right centeralign 440px>
{{:rudolph:hypervolume:ehc.png?200|}}
{{:rudolph:hypervolume:porto3d.jpg?200|}}

<WRAP justify>
The exclusive hypervolume contribution of each point in the same examples as above.
</WRAP>
</WRAP>

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 **[[http://image.diku.dk/shark/|Shark library]]** by Thomas Voß


=== MATLAB ===

  * **{{:rudolph:hypervolume:bbob-biobj-matlab-smsemoa-de.zip|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 ===

  * **[[http://jmetal.sourceforge.net/|JMetal version]]**  by Simon Wessing

=== Python ===

  * In the package **[[https://pypi.python.org/pypi/evoalgos/|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 =====

=== First Appearance of the Hypervolume ===

  * at this time simply as "the size of the space covered"
    * E. Zitzler and L. Thiele. [[http://dx.doi.org/10.1007/BFb0056872|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 ===
   * Performance Assessment Indicators comparison: Compatibility and Completeness: [[http://ieeexplore.ieee.org/document/1197687/| Zitzler, Thiele, Laumanns, Fonseca, Grunert da Fonseca (2003)]]

  * Lower Bound Runtime: $\Omega(n \log n)$
    * see [[http://dx.doi.org/10.1109/TEVC.2009.2015575|Nicola Beume, Carlos M. Fonseca, Manuel López-Ibáñez, Luís Paquete, Jan Vahrenhold, 2009]]

  * Worst Case Upper Bound Runtime: $O( n^{d/3} \log^{O(1)} n)$
    * see [[http://dx.doi.org/10.1109/FOCS.2013.51|Timothy Chan, 2013]]
 
  * Complexity of recursive algorithm: $O(n^{d-2} \cdot \log(n))$
      * see [[http://dx.doi.org/10.1109/CEC.2006.1688440|Fonseca et al., 2006]]
 
  * Fastest implemented algorithm in 4-D [[http://2012.cccg.ca/papers/paper70.pdf| Guerreiro, Fonseca, Emmerich 2012]]

  * Approximation
    * fast and precise approximation of 2-dimensional hypervolume, see [[https://hpi.de/friedrich/research/the-hypervolume-indicator.html|Tobias Friedrich's homepage]]

  * Runtime Analysis
    * of the $(\mu+1)$-SIBEA on two pseudo-boolean test functions, see D. Brockhoff, T. Friedrich, and F. Neumann. [[http://dx.doi.org/10.1007/978-3-540-87700-4_65|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 $\Theta(n \log n)$ in 2-D and 3-D, see [[http://www.springerlink.com/content/b581111m6550w082|Emmerich and Fonseca]].
    * Dynamic programming algorithm for 2-D subset selection in $O(n^3)$, see [[http://doi.acm.org/10.1145/1569901.1569980|Auger, Bader, Brockhoff and Zitzler, 2009]]. 
    * 2-D subset selection for hypervolume and epsilon-indicator: [[http://dx.doi.org/10.1145/2576768.2598276|Bringmann et al. 2014]]
    * Upper bounds for complexity of finding the minimal contributor for $d>3$: [[http://dx.doi.org/10.1162/EVCO_a_00012|Bringmann and Friedrich]].
    * Subset selection NP hardness for n>3, see [[http://www.jcdcgg.u-tokai.ac.jp/JCDCG3_abstracts.pdf| Rote, Buchin, Bringmann, Cabello, and Emmerich (extended abstract)]] 
    * Set-based Gradient of the hypervolume, see [[http://www.springerlink.com/content/q988g282q57m1325/|Emmerich, Deutz and Beume]] and for high dimensions see [[http://dx.doi.org/10.1007/978-3-319-01460-9_8|Emmerich and Deutz]]

  * Optimization Goal of (Weighted, Cone-based) Hypervolume
    * Optimal distribution of $\mu$ points maximizing the (weighted) hypervolume indicator, see [[http://dx.doi.org/10.1016/j.tcs.2011.03.012|Auger, Bader, Brockhoff and Zitzler, 2012]].
    * Reference point free weighted hypervolume indicators [[http://dx.doi.org/10.1016/j.protcy.2014.10.001|Emmmerich, Deutz and Yevseyeva]].   
    * Cone-based hypervolume indicator: efficient computation and $\mu$-point optimal distributions [[http://link.springer.com/chapter/10.1007%2F978-3-642-37140-0_12|Emmerich, Deutz, Shukla, and Kruisselbrink 2013]]

  * Expected Hypervolume Improvement in Efficient Global optimization
    * Exact computation and properties  [[http://ieeexplore.ieee.org/document/5949880| Emmerich, Deutz, Klinkenberg 2011]]
    * Faster Computation [[http://link.springer.com/chapter/10.1007/978-3-319-15892-1_5| Hupkens, Yang, Deutz, Emmerich 2015]]
 
=== Hypervolume-based Multiobjective Optimizers ===
  * Bounded Archiver using Lebesgue Measure [[http://ieeexplore.ieee.org/document/1299401/| Knowles, Corne, Fleischer 2003]]
  * SMS-EMOA
    * original conference publication [[http://link.springer.com/chapter/10.1007%2F978-3-540-31880-4_5| Emmerich, Beume, and Naujoks 2005]] 
    * extended journal publication, see [[http://dx.doi.org/10.1016/j.ejor.2006.08.008 |Nicola Beume, Boris Naujoks, Michael Emmerich, 2007]] 
    * efficient implementation with efficient incremental updates (O(log n) amortized time per iteration in 2-D and  O(n) in 3-D), see [[http://link.springer.com/chapter/10.1007%2F978-3-319-01128-8_11|Hupkens and Emmerich, 2013]]
    * Parallel SMS EMOA for Many Objective Optimization [[http://link.springer.com/chapter/10.1007%2F978-3-319-45823-6_53| Goméz, Coello Coello, and Alba]]

  * HypE
    * see Johannes Bader and Eckart Zitzler. [[http://dx.doi.org/10.1162/EVCO_a_00009|HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization]]. Evolutionary Computation, posted online since July 22, 2010
    * code available on the [[http://www.tik.ee.ethz.ch/sop/download/supplementary/hype/|PISA web page]]

  * MO-CMA-ES
    * see [[http://dx.doi.org/10.1162/evco.2007.15.1.1|Christian Igel, Nikolaus Hansen, Stefan Roth, 2007]]
    * code available within the [[http://image.diku.dk/shark/sphinx_pages/build/html/rest_sources/tutorials/algorithms/mocma.html|Shark library]]

  * POSEA - Portfolio-based Selection based on Hypervolume (POSEA)
      * Algorithm description and empirical performance assessment [[http://link.springer.com/chapter/10.1007%2F978-3-319-10762-2_66| Guerreiro, Yevseyeva, Emmerich, and Fonseca 2014]] 
      * Hypervolume based Sharpe Indicator, theoretical results [[http://link.springer.com/chapter/10.1007/978-3-319-45823-6_76|Fonseca and Guerreiro, 2016]]
 
  * Efficient Global Optimization
    * Early ideas on infill criteria based on hypervolume, see  [[http://link.springer.com/chapter/10.1007/978-3-642-15844-5_72]]
    * Efficient Multicritera Optimization with  extensive benchmark [[http://link.springer.com/article/10.1007/s10898-013-0118-2|Couckuyt, Deschrijver, and Dhaene 575]]
    * Efficient Multicritera Optimization, efficient implementation ($\Theta(n \log n)$) [[http://www.springer.com/gp/book/9783319299730| Emmerich, Yang, Wang, and Fonseca 2016]]

  * Hypervolume-based Newton's Method [[http://link.springer.com/chapter/10.1007%2F978-3-319-07494-8_2| Sosa Hernandéz, Schütze, and Emmerich (2014)]]
=== 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. [[http://doi.acm.org/10.1145/1712605.1712625|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

    * Docking Problems in Drug Discovery, in [[http://dx.doi.org/10.1007/978-3-642-34032-1_3|Sanchez{-}Faddeev, Emmerich Verbeek, Henry, Grimshaw, Spaink, van Vlijmen and Bender]]

    * Bioplant-Controller Design [[http://ieeexplore.ieee.org/document/7257122/| Yang, Gaida, Bäck, Emmerich]]

=== Further Reading ===
   * A review paper on the hypervolume indicator in multiobjective optimization [[http://www.sciencedirect.com/science/article/pii/S0304397511002428| Auger, Bader, Brockhoff and Zitzler 2012]]

    * Set-oriented and Indicator Based Optimization: Open Theoretical Problem Page (includes recent results and open questions on the hypervolume indicator and related measures), see [[http://simco.gforge.inria.fr/doku.php?id=openproblems| Emmerich, Naujoks, Brockhoff 2013-]]