Balancing between time budgets and costs in surrogate-assisted evolutionary algorithms

For many real-world multi-objective optimisation problems, function evaluations are computationally expensive, resulting in a limited budget of function evaluations that can be performed in practice. To tackle such expensive problems, multi-objective surrogate-assisted evolutionary algorithms (SAEAs) have been introduced. Often, the performance of these EAs is measured after a fixed number of function evaluations (typically several hundreds) and complex surrogate models are found to be the best to use. However, when selecting an SAEA for a real-world problem, the surrogate building time, surrogate evaluation time, function evaluation time, and available optimisation time budget should be considered simultaneously. To gain insight into the performance of various surrogate models under different conditions, we evaluate an EA with and without four surrogate models (both complex and simple) for a range of optimisation time budgets and function evaluation times while considering the surrogate building and surrogate evaluation times. We use 55 bbob-biobj benchmark problems as well as a real-world problem where the fitness function involves a biomechanical simulation. Our results, on both types of problems, indicate that a larger hypervolume can be obtained with SAEAs when a function evaluation takes longer than 0.384 s (on the hardware we used). While we confirm that state-of-the-art complex surrogate models are mostly the best choice if up to several hundred function evaluations can be performed, we also observe that simple surrogate models can still outperform non-surrogate-assisted EAs if several thousand function evaluations can be performed.

• View at Publisher