ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems

TLDR

The paper addresses multiobjective optimization problems where each solution evaluation is costly in time or money. The authors evaluate two algorithms on nine low‑dimensional real‑valued test functions with only 100–260 evaluations, and propose ParEGO, which initializes via design‑of‑experiments and iteratively updates a Gaussian process model of the landscape. NSGA‑II performs competitively against random search with limited evaluations, but ParEGO achieves markedly better results—especially in worst‑case scenarios—and overall shows promising performance for expensive or evaluation‑restricted multiobjective optimization.

Abstract

This paper concerns multiobjective optimization in scenarios where each solution evaluation is financially and/or temporally expensive. We make use of nine relatively low-dimensional, nonpathological, real-valued functions, such as arise in many applications, and assess the performance of two algorithms after just 100 and 250 (or 260) function evaluations. The results show that NSGA-II, a popular multiobjective evolutionary algorithm, performs well compared with random search, even within the restricted number of evaluations used. A significantly better performance (particularly, in the worst case) is, however, achieved on our test set by an algorithm proposed herein-ParEGO-which is an extension of the single-objective efficient global optimization (EGO) algorithm of Jones et al. ParEGO uses a design-of-experiments inspired initialization procedure and learns a Gaussian processes model of the search landscape, which is updated after every function evaluation. Overall, ParEGO exhibits a promising performance for multiobjective optimization problems where evaluations are expensive or otherwise restricted in number.