论文标题
逗号的选择有助于应对本地Optima吗
Does Comma Selection Help To Cope With Local Optima
论文作者
论文摘要
在进化计算中使用非精神主义的一种希望是，放弃当前最好的解决方案有助于离开本地Optima的能力。为了提高我们对这种机制的理解，我们对基本的基本的非私人进化算法（ea），$（μ，λ）$ ea进行了严格的运行时分析，并在最基本的基准测试函数上具有局部最佳的optimum，即跳跃函数。我们证明，对于参数的所有合理值和问题，$（μ，λ）$ 〜EA的预期运行时间除了较低的术语外，至少与其精英人士的预期运行时一样大，即$（μ+λ）$ 〜EA（为此，我们对此进行了第一次运行时间分析此比较）。因此，$（μ，λ）$ 〜E EA将本地Optima留给下等方面的能力并不会带来运行时的优势。 我们将其与上限进行补充，该界限对于参数的宽范围，与我们的下限相同。这是针对多模式问题的非专业算法的第一个运行时结果，该算法与较低的术语分开。
One hope when using non-elitism in evolutionary computation is that the ability to abandon the current-best solution aids leaving local optima. To improve our understanding of this mechanism, we perform a rigorous runtime analysis of a basic non-elitist evolutionary algorithm (EA), the $(μ,λ)$ EA, on the most basic benchmark function with a local optimum, the jump function. We prove that for all reasonable values of the parameters and the problem, the expected runtime of the $(μ,λ)$~EA is, apart from lower order terms, at least as large as the expected runtime of its elitist counterpart, the $(μ+λ)$~EA (for which we conduct the first runtime analysis on jump functions to allow this comparison). Consequently, the ability of the $(μ,λ)$~EA to leave local optima to inferior solutions does not lead to a runtime advantage. We complement this lower bound with an upper bound that, for broad ranges of the parameters, is identical to our lower bound apart from lower order terms. This is the first runtime result for a non-elitist algorithm on a multi-modal problem that is tight apart from lower order terms.
