论文标题
$（1+（λ，λ））$用于排列的遗传算法
The $(1+(λ,λ))$ Genetic Algorithm for Permutations
论文作者
论文摘要
$（1+（λ，λ））$遗传算法是进化算法的一个明亮示例，它是根据理论发现的见解而开发的。该算法使用交叉，并且在诸如onemax之类的简单问题上，它也被证明渐近地优于所有基于突变的进化算法。随后，对此进行了许多其他问题的研究，但所有这些都是伪树生。 我们旨在通过提出$（1+（λ，λ））$遗传算法对基于置换的问题的改编来改善这种情况。需要这样的适应，因为在某些关键方面，置换与钻头字符串明显不同，例如可能的突变数量及其相互依赖。我们还介绍了该算法对基于排列的问题的第一个运行时分析，该问题称为HAM，其属性类似于OneMax的属性。在此问题上，对于问题尺寸$ n $而言，基于简单的基于突变的算法的运行时间为$θ（n^2 \ log n）$，$（1+（1+（λ，λ））$遗传算法可在$ O（n^2）$ fitness查询中找到最佳。我们通过实验增强了这种分析，这表明该算法在实践中也很快。
The $(1+(λ,λ))$ genetic algorithm is a bright example of an evolutionary algorithm which was developed based on the insights from theoretical findings. This algorithm uses crossover, and it was shown to asymptotically outperform all mutation-based evolutionary algorithms even on simple problems like OneMax. Subsequently it was studied on a number of other problems, but all of these were pseudo-Boolean. We aim at improving this situation by proposing an adaptation of the $(1+(λ,λ))$ genetic algorithm to permutation-based problems. Such an adaptation is required, because permutations are noticeably different from bit strings in some key aspects, such as the number of possible mutations and their mutual dependence. We also present the first runtime analysis of this algorithm on a permutation-based problem called Ham whose properties resemble those of OneMax. On this problem, where the simple mutation-based algorithms have the running time of $Θ(n^2 \log n)$ for problem size $n$, the $(1+(λ,λ))$ genetic algorithm finds the optimum in $O(n^2)$ fitness queries. We augment this analysis with experiments, which show that this algorithm is also fast in practice.
