Computing 3-D expected hypervolume improvement and related integrals in asymptotically optimal time

Kaifeng Yang, Michael Emmerich, André Deutz, Carlos M. Fonseca

Research output: Chapter in Book/Report/Conference proceedingsConference contributionpeer-review

29 Citations (Scopus)

Abstract

The Expected Hypervolume Improvement (EHVI) is a frequently used infill criterion in surrogate-assisted multi-criterion optimization. It needs to be frequently called during the execution of such algorithms. Despite recent advances in improving computational efficiency, its running time for three or more objectives has remained in O(nd) for d ≥ 3, where d is the number of objective functions and n is the size of the incumbent Pareto-front approximation. This paper proposes a new integration scheme, which makes it possible to compute the EHVI in Θ(n log n) optimal time for the important three-objective case (d = 3). The new scheme allows for a generalization to higher dimensions and for computing the Probability of Improvement (PoI) integral efficiently. It is shown, both theoretically and empirically, that the hidden constant in the asymptotic notation is small. Empirical speed comparisons were designed between the C++ implementations of the new algorithm (which will be in the public domain) and those recently published by competitors, on randomly-generated non-dominated fronts of size 10, 100, and 1000. The experiments include the analysis of batch computations, in which only the parameters of the probability distribution change but the incumbent Pareto-front approximation stays the same. Experimental results show that the new algorithm is always faster than the other algorithms, sometimes over 104 times faster.

Original languageEnglish
Title of host publicationEvolutionary Multi-Criterion Optimization - 9th International Conference, EMO 2017, Proceedings
EditorsOliver Schütze, Gunter Rudolph, Kathrin Klamroth, Yaochu Jin, Heike Trautmann, Christian Grimme, Margaret Wiecek
PublisherSpringer-Verlag Italia Srl
Pages685-700
Number of pages16
ISBN (Print)9783319541563
DOIs
Publication statusPublished - 2017
Event9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017 - Munster, Germany
Duration: 19 Mar 201722 Mar 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10173 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017
Country/TerritoryGermany
CityMunster
Period19.03.201722.03.2017

Keywords

  • Efficient global optimization
  • Expected hypervolume improvement
  • Probability of improvement
  • Surrogate-assisted multi-criterion optimization
  • Time complexity

Fingerprint

Dive into the research topics of 'Computing 3-D expected hypervolume improvement and related integrals in asymptotically optimal time'. Together they form a unique fingerprint.

Cite this