论文标题
通过对称参数对进化算法的运行时分析
Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments
论文作者
论文摘要
我们使用基于小组动作的基本论点来证明，由Sutton和Witt（GECCO 2019）分析的无选择的稳态遗传算法（GECCO 2019）的预期数量为$ω（2^n / \ sqrt n）$迭代，以找到任何特定的目标搜索点。此界限对所有人口尺寸$μ$都是有效的。我们的结果改善了$ω（\ exp（n^{Δ/2}）））$对人口尺寸$μ= o（n^{1/2-Δ}）$，$ 0 <Δ<1/2 $有效。
We use an elementary argument building on group actions to prove that the selection-free steady state genetic algorithm analyzed by Sutton and Witt (GECCO 2019) takes an expected number of $Ω(2^n / \sqrt n)$ iterations to find any particular target search point. This bound is valid for all population sizes $μ$. Our result improves over the previous lower bound of $Ω(\exp(n^{δ/2}))$ valid for population sizes $μ= O(n^{1/2 - δ})$, $0 < δ< 1/2$.
