## 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(n^{d}) 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 10^{4} times faster.

Original language | English |
---|---|

Title of host publication | Evolutionary Multi-Criterion Optimization - 9th International Conference, EMO 2017, Proceedings |

Editors | Oliver Schütze, Gunter Rudolph, Kathrin Klamroth, Yaochu Jin, Heike Trautmann, Christian Grimme, Margaret Wiecek |

Publisher | Springer-Verlag Italia Srl |

Pages | 685-700 |

Number of pages | 16 |

ISBN (Print) | 9783319541563 |

DOIs | |

Publication status | Published - 2017 |

Event | 9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017 - Munster, Germany Duration: 19 Mar 2017 → 22 Mar 2017 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10173 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017 |
---|---|

Country/Territory | Germany |

City | Munster |

Period | 19.03.2017 → 22.03.2017 |

## Keywords

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