论文标题
基于跨界的算法的快速突变
Fast Mutation in Crossover-based Algorithms
论文作者
论文摘要
在Doerr，Le，Makhmara和Nguyen（Gecco 2017）中提出的重尾突变算子，称为\ Emph {fast fast突变}同意以前使用的语言，到目前为止，仅在基于突变的算法中才有优势。在那里，它可以缓解算法设计人员找到最佳突变率，然后获得接近最佳突变率的性能。 在使用突变率的重尾选择基于交叉的算法的第一个运行时分析中，我们显示出更强的影响。对于$（1+（λ，λ））$遗传算法优化OneMAX基准功能，我们表明，使用重尾突变率可以实现线性运行时。这是比任何静态突变率可以获得的渐近速度，并且在渐近上等同于$（1+（1+（1+（λ，λ））$遗传算法的参数选择的自我调整版本）。这一结果是通过一项经验研究补充的，该研究表明了快速突变对随机令人满意的Max-3 Sat实例的有效性。
The heavy-tailed mutation operator proposed in Doerr, Le, Makhmara, and Nguyen (GECCO 2017), called \emph{fast mutation} to agree with the previously used language, so far was proven to be advantageous only in mutation-based algorithms. There, it can relieve the algorithm designer from finding the optimal mutation rate and nevertheless obtain a performance close to the one that the optimal mutation rate gives. In this first runtime analysis of a crossover-based algorithm using a heavy-tailed choice of the mutation rate, we show an even stronger impact. For the $(1+(λ,λ))$ genetic algorithm optimizing the OneMax benchmark function, we show that with a heavy-tailed mutation rate a linear runtime can be achieved. This is asymptotically faster than what can be obtained with any static mutation rate, and is asymptotically equivalent to the runtime of the self-adjusting version of the parameters choice of the $(1+(λ,λ))$ genetic algorithm. This result is complemented by an empirical study which shows the effectiveness of the fast mutation also on random satisfiable Max-3SAT instances.
