Investigating uncertainty propagation in surrogate-assisted evolutionary algorithms
Vanessa Volz, Günter Rudolph, Boris Naujoks · Proceedings of the Genetic and Evolutionary Computation Conference · 2017
Uncertainty propagation is a technique to incorporate individuals with uncertain fitness estimates in evolutionary algorithms. The Surrogate-Assisted Partial Order-Based Evolutionary Optimisation Algorithm (SAPEO) uses uncertainty propagation of fitness predictions from a Kriging model to reduce the number of function evaluations. The fitness predictions are ranked with partial orders and the corresponding individuals are only evaluated if they are indistinguishable otherwise or the risk of uncertainty propagation exceeds a steadily decreasing error tolerance threshold. In this paper, we investigate the effects of using uncertainty propagation according to SAPEO on single-objective problems. To this end, we present and apply different ways of measuring the deviations of SAPEO from the underlying CMA-ES. We benchmark the algorithms on the BBOB testbed to assess the effects of uncertainty propagation on their performance throughout the runtime of the algorithm on a variety of problems. Additionally, we examine thoroughly the differences per iteration between the evolution paths of SAPEO and CMA-ES based on a model for the rank-one update. The BBOB results suggest that the success of SAPEO generally improves the performance but depends heavily on function and dimension, which is supported by the analysis of the evolution paths.