Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
Benjamin Doerr, Andrew James Kelley · Proceedings of the Genetic and Evolutionary Computation Conference · 2023
We propose a new method based on discrete Fourier analysis to analyze the time evolutionary algorithms spend on plateaus. This immediately gives a concise proof of the classic estimate of the expected runtime of the (1 + 1) evolutionary algorithm on the Needle problem due to Garnier, Kallel, and Schoenauer (1999).