Surrogate Model Assisted Evolutionary Algorithms: Performance Bound and Incremental Gaussian Process Model Updates

The performance of surrogate model assisted algorithms for black-box optimization is impacted by two factors: algorithmic design choices on how to use the surrogate model, and the ability of the model to accurately represent the true objective function. In an effort to better understand the potential of surrogate model assisted algorithms, we propose to decouple those factors by studying the performance of the algorithms assuming perfect models. As a result, we obtain a natural performance bound that algorithms that use real models can be compared against, and that also provides an indication of the goodness of those models. We employ that performance bound in order to analytically evaluate a surrogate model assisted (1 + 1)-ES. Using the same bound, we also investigate the potential of performing incremental updates of Gaussian process surrogate models in an attempt to reduce algorithm internal computational costs and find that significant savings can be achieved at the cost of a small deterioration of model accuracy.