Journal article · 2019 · Open access

Efficient computation of expected hypervolume improvement using box decomposition algorithms

Kaifeng Yang, Michael Emmerich, Andre H. Deutz, Thomas Bäck

Journal of Global Optimization, 75(1), 3–34 · Published 3 July 2019 · DOI 10.1007/s10898-019-00798-7

Open PDFView at the publisherCite this paper

In brief

“Efficient computation of expected hypervolume improvement using box decomposition algorithms” is a 2019 journal article by Kaifeng Yang and 3 co-authors, published in Journal of Global Optimization. OpenAlex counts 138 citations as of 19 November 2026. It is open access under a CC BY licence: the full text is free to read at Journal of Global Optimization.

Citations
138
Most cited in
2026 (27)
Field-weighted impact
8.75
References
48
Authors
4

Abstract

In the field of multi-objective optimization algorithms, multi-objective Bayesian Global Optimization (MOBGO) is an important branch, in addition to evolutionary multi-objective optimization algorithms. MOBGO utilizes Gaussian Process models learned from previous objective function evaluations to decide the next evaluation site by maximizing or minimizing an infill criterion. A commonly used criterion in MOBGO is the Expected Hypervolume Improvement (EHVI), which shows a good performance on a wide range of problems, with respect to exploration and exploitation. However, so far, it has been a challenge to calculate exact EHVI values efficiently. This paper proposes an efficient algorithm for the exact calculation of the EHVI for in a generic case. This efficient algorithm is based on partitioning the integration volume into a set of axis-parallel slices. Theoretically, the upper bound time complexities can be improved from previously $$O (n^2)$$ and $$O(n^3)$$ , for two- and three-objective problems respectively, to $$\varTheta (n\log n)$$ , which is asymptotically optimal. This article generalizes the scheme in higher dimensional cases by utilizing a new hyperbox decomposition technique, which is proposed by Dächert et al. (Eur J Oper Res 260(3):841–855, 2017). It also utilizes a generalization of the multilayered integration scheme that scales linearly in the number of hyperboxes of the decomposition. The speed comparison shows that the proposed algorithm in this paper significantly reduces computation time. Finally, this decomposition technique is applied in the calculation of the Probability of Improvement (PoI).

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Yang, K., Emmerich, M., Deutz, A. H., & Bäck, T. (2019). Efficient computation of expected hypervolume improvement using box decomposition algorithms. Journal of Global Optimization, 75(1), 3–34. https://doi.org/10.1007/s10898-019-00798-7

MLA 9

Yang, Kaifeng, et al. “Efficient computation of expected hypervolume improvement using box decomposition algorithms.” Journal of Global Optimization, vol. 75, no. 1, 2019, pp. 3–34. https://doi.org/10.1007/s10898-019-00798-7.

Chicago

Yang, Kaifeng, Michael Emmerich, Andre H. Deutz, and Thomas Bäck. 2019. “Efficient computation of expected hypervolume improvement using box decomposition algorithms.” Journal of Global Optimization 75 (1): 3–34. https://doi.org/10.1007/s10898-019-00798-7.

Harvard

Yang, K. et al. (2019) ‘Efficient computation of expected hypervolume improvement using box decomposition algorithms’, Journal of Global Optimization, 75(1), pp. 3–34. doi:10.1007/s10898-019-00798-7.

IEEE

K. Yang, M. Emmerich, A. H. Deutz, and T. Bäck, “Efficient computation of expected hypervolume improvement using box decomposition algorithms,” Journal of Global Optimization, vol. 75, no. 1, pp. 3–34, 2019, doi: 10.1007/s10898-019-00798-7.

BibTeX

@article{yang2019efficient,
  title     = {{Efficient computation of expected hypervolume improvement using box decomposition algorithms}},
  author    = {Yang, Kaifeng and Emmerich, Michael and Deutz, Andre H. and Bäck, Thomas},
  journal   = {Journal of Global Optimization},
  year      = {2019},
  volume    = {75},
  number    = {1},
  pages     = {3--34},
  doi       = {10.1007/s10898-019-00798-7},
  url       = {https://doi.org/10.1007/s10898-019-00798-7}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
201911
202099
20211313
20222323
20232323
20241818
20252424
20262727

Its field-weighted citation impact is 8.75: it has been cited 8.75 times as often as the average work of the same field, type and year (1.00 is the world average).

Topic and keywords

Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Multi-Objective Optimization Algorithms

  • expected hypervolume improvement
  • infill criterion
  • Gaussian processes
  • probability of improvement
  • multi-objective optimization
  • computational complexity

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Yang, K., Emmerich, M., Deutz, A. H., & Bäck, T. (2019). Efficient computation of expected hypervolume improvement using box decomposition algorithms. Journal of Global Optimization, 75(1), 3–34. https://doi.org/10.1007/s10898-019-00798-7

How many times has this paper been cited?

138 times, according to OpenAlex on 19 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at Journal of Global Optimization: sign in and open the PDF from this page.

Who wrote this paper?

Kaifeng Yang, Michael Emmerich, Andre H. Deutz, Thomas Bäck.

What is the DOI of this paper?

10.1007/s10898-019-00798-7, permanently at https://doi.org/10.1007/s10898-019-00798-7. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 19 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.