  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).
  We also use this method to analyze the runtime of the $(1+1)$ evolutionary
algorithm on a new benchmark consisting of $n/\ell$ plateaus of effective size
$2^\ell-1$ which have to be optimized sequentially in a LeadingOnes fashion.
  Using our new method, we determine the precise expected runtime both for
static and fitness-dependent mutation rates. We also determine the
asymptotically optimal static and fitness-dependent mutation rates. For $\ell =
o(n)$, the optimal static mutation rate is approximately $1.59/n$. The optimal
fitness dependent mutation rate, when the first $k$ fitness-relevant bits have
been found, is asymptotically $1/(k+1)$. These results, so far only proven for
the single-instance problem LeadingOnes, thus hold for a much broader class of
problems. We expect similar extensions to be true for other important results
on LeadingOnes. We are also optimistic that our Fourier analysis approach can
be applied to other plateau problems as well.
