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 \textsc{LeadingOnes} and \textsc{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$.%

本研究提出了将经典的伪布尔基准转化为置换集基准的一般方法，分析了置换基础 $(1+1)$EA 在 LeadingOnes 和 Jump 基准的模拟上的运行时间，旨在研究置换问题。