Trust Your Neighbours: Handling Noise in Multi-Objective Optimisation Using kNN-Averaging

The non-deterministic nature of modern systems such as cyber-physical systems (e.g. due to sensor noise) and multi-process/multi-agent systems (e.g. due to timing differences), poses a significant challenge in the field of multi-objective optimisation (MOO). Those systems may produce different objective values on every evaluation of the objective function, in which case the effectiveness of classical MOO algorithms can no longer be guaranteed. It has indeed been observed that they are prone to producing results that are either not optimal or not feasible. An obvious, yet naive, solution is to approximate the true fitness of a solution by sampling the objective function multiple times. However, this leads to significantly more evaluations of the objective function, which may not be acceptable, e.g. if the fitness function is expensive to compute. To tackle this issue, we propose kNN-averaging, an MOO algorithm that approximates the true fitness of solutions based on a k-nearest neighbours (kNN) regression scheme. We experimentally compare kNN-averaging to two resampling-based methods, a Gaussian process-based spectral sampling approach, and the default, uncorrected baseline, on 40 benchmark problems and one real-world case study.