To Reevaluate or Not: A Theoretical Study of NSGA-II Under Noise

Multi-objective evolutionary algorithms (MOEAs) are widely used to optimize problems with multiple objectives. In real-world applications, however, solution evaluations may be corrupted by noise, for example, when using a simulator. A straightforward response is to reevaluate solutions. This raises a key question: is it more beneficial to reevaluate solutions in every generation, or retain their initial noisy fitness values throughout the search? We investigate this question theoretically for NSGA-II, one of the most widely used MOEAs. On the common benchmark LOTZ under one-bit prior noise, we show that under noise levels of $\omega (\sqrt{\log n/n})$ and $O(1/\log n)$, retaining initial fitness values yields polynomial expected runtime, whereas reevaluation requires superpolynomial expected runtime, with all other algorithm settings unchanged. The proven detrimental effect of reevaluation echoes known results for simple MOEAs. Further, we construct a new benchmark PairedCOCZ and prove that for noise levels below but sufficiently close to one, reevaluation is helpful: it leads to polynomial expected runtime, compared with at least exponential expected runtime without reevaluation. These results not only provide theoretical comparison of evaluation strategies for practical MOEAs under noise for the first time, but also challenge the prevailing belief that reevaluation is always detrimental. We complement the theory with empirical studies.