S. Klikovits, C. Ho Thanh, A. Cetinkaya, P. Arcaini: Trust your neighbours: Handling noise in multi-objective optimisation using kNN-averaging, in Applied Soft Computing, Volume 146, October 2023, Doi: 10.1016/j.asoc.2023.110631
Multi-objective optimisation (MOO) is a popular approach for finding solutions to many types of complex problems with large search spaces and conflicting search objectives. In the past, MOO algorithms have been shown to reliably produce good optimisation results. With the rise of cyber–physical systems, however, emerges the new challenge of non-deterministic system executions, caused by e.g. imperfect sensor readings or synchronisation in multi-process/multi-agent system architectures. These systems produce varying output on each execution, causing the algorithms’ observations to be noisy. Naturally, MOO algorithms favour the fittest solutions, which may have been measured with great inaccuracy. The end results are therefore not trustworthy. In this paper, we propose kNN-averaging, a new method to address this issue by identifying the k-nearest neighbours (kNN) of a solution, and using their weighted average as an estimate for its true fitness. Our experiments demonstrate the viability of kNN-averaging on 40 synthetic benchmark problems and on a real-world case study system. In the process, we compare kNN-averaging to the noisy baseline as well as two resampling-based methods and one spectral sampling approach on a range of algorithm settings. The results show that kNN-averaging approximates the fitness of solutions more accurately than the noisy baseline, leading to more trustworthy results.