论文标题
基于置换的进化算法的运行时分析
Runtime Analysis for Permutation-based Evolutionary Algorithms
论文作者
论文摘要
尽管在过去25年中，对进化算法的理论分析（EAS）在伪树状优化问题方面取得了重大进展，但仅在EAS求解基于置换的问题方面存在零星的理论结果。 为了克服缺乏基于置换的基准问题，我们提出了一种将经典的伪树立基准测试转换为定义在排列集定义的基准的一般方法。然后，我们对Scharnow，Tinnefeld和Wegener（2004）提出的基于置换的$（1+1）$ ea进行了严格的运行时分析，对前导者和跳跃基准的类似物。后者表明，与位串不同的是，不仅锤距离决定将排列$σ$变为另一个$τ$，而且还确定了$στ^{ - 1} $的精确循环结构有多困难。因此，我们还考虑了更对称的争夺突变算子。我们观察到，它不仅会导致更简单的证据，而且还可以将跳跃功能的运行时减少奇数跳跃大小的$θ（n）$。最后，我们表明，与位串联案例一样，在跳跃尺寸$ m $的跳跃功能上，加快订单$ m^{θ（m）} $的重型版本会导致订单$ m^{θ（m）} $。简短的经验分析证实了这些发现，但也揭示了诸如空隙突变率之类的较小实施细节可以产生重要的不同。
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 $σ$ into another one $τ$, but also the precise cycle structure of $στ^{-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 $Θ(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^{Θ(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.
