TY - GEN
T1 - Computing 3-D expected hypervolume improvement and related integrals in asymptotically optimal time
AU - Yang, Kaifeng
AU - Emmerich, Michael
AU - Deutz, André
AU - Fonseca, Carlos M.
N1 - Funding Information:
Kaifeng Yang acknowledges financial support from the China Scholarship Council (CSC), CSC No. 201306370037. Carlos M. Fonseca was supported by national funds through the Portuguese Foundation for Science and Technology (FCT), and by the European Regional Development Fund (FEDER) through COMPETE 2020 – Operational Program for Competitiveness and Internationalization (POCI).
Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - Efficient global optimization
KW - Expected hypervolume improvement
KW - Probability of improvement
KW - Surrogate-assisted multi-criterion optimization
KW - Time complexity
UR - https://www.scopus.com/pages/publications/85014255506
U2 - 10.1007/978-3-319-54157-0_46
DO - 10.1007/978-3-319-54157-0_46
M3 - Conference contribution
AN - SCOPUS:85014255506
SN - 9783319541563
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 685
EP - 700
BT - Evolutionary Multi-Criterion Optimization - 9th International Conference, EMO 2017, Proceedings
A2 - Schütze, Oliver
A2 - Rudolph, Gunter
A2 - Klamroth, Kathrin
A2 - Jin, Yaochu
A2 - Trautmann, Heike
A2 - Grimme, Christian
A2 - Wiecek, Margaret
PB - Springer-Verlag Italia Srl
T2 - 9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017
Y2 - 19 March 2017 through 22 March 2017
ER -