  While the theoretical analysis of evolutionary algorithms (EAs) has made
significant progress for pseudo-Boolean optimization problems in the last 25
years, only sporadic theoretical results exist on how EAs solve
permutation-based problems.
  To overcome the lack of permutation-based benchmark problems, we propose a
general way to transfer the classic pseudo-Boolean benchmarks into benchmarks
defined on sets of permutations. We then conduct a rigorous runtime analysis of
the permutation-based $(1+1)$ EA proposed by Scharnow, Tinnefeld, and Wegener
(2004) on the analogues of the LeadingOnes and Jump benchmarks. The latter
shows that, different from bit-strings, it is not only the Hamming distance
that determines how difficult it is to mutate a permutation $\sigma$ into
another one $\tau$, but also the precise cycle structure of $\sigma \tau^{-1}$.
For this reason, we also regard the more symmetric scramble mutation operator.
We observe that it not only leads to simpler proofs, but also reduces the
runtime on jump functions with odd jump size by a factor of $\Theta(n)$.
Finally, we show that a heavy-tailed version of the scramble operator, as in
the bit-string case, leads to a speed-up of order $m^{\Theta(m)}$ on jump
functions with jump size $m$. A short empirical analysis confirms these
findings, but also reveals that small implementation details like the rate of
void mutations can make an important difference.
