Evolutionary algorithms (EAs) are general-purpose optimisers that come with several parameters like the sizes of parent and offspring populations or the mutation rate. It is well known that the performance of EAs may depend drastically on these parameters. Recent theoretical studies have shown that self-adjusting parameter control mechanisms that tune parameters during the algorithm run can provably outperform the best static parameters in EAs on discrete problems. However, the majority of these studies concerned elitist EAs and we do not have a clear answer on whether the same mechanisms can be applied for non-elitist EAs. We study one of the best-known parameter control mechanisms, the one-fifth success rule, to control the offspring population size $\lambda$ in the non-elitist $(1,\lambda)$ EA. It is known that the $(1,\lambda)$ EA has a sharp threshold with respect to the choice of $\lambda$ where the expected runtime on the benchmark function OneMax changes from polynomial to exponential time. Hence, it is not clear whether parameter control mechanisms are able to find and maintain suitable values of $\lambda$. For OneMax we show that the answer crucially depends on the success rate $s$ (i.e. a one-$(s+1)$-th success rule). We prove that, if the success rate is appropriately small, the self-adjusting $(1,\lambda)$ EA optimises OneMax in $O(n)$ expected generations and $O(n \log n)$ expected evaluations, the best possible runtime for any unary unbiased black-box algorithm. A small success rate is crucial: we also show that if the success rate is too large, the algorithm has an exponential runtime on OneMax and other functions with similar characteristics.
翻译:进化算法(EAs) 是通用的优化算法(EAs), 这些算法包含一些参数, 比如父母和后代的大小或者变异率。 众所周知, EAs的性能可能在很大程度上取决于这些参数。 最近的理论研究显示, 在算法运行期间调用参数的自我调整参数控制机制, 可以明显地超过EAs在离散问题上的最佳静态参数。 然而, 这些研究大多涉及精英EAs, 我们对于是否对非精英EA应用同样的机制。 我们研究的是最著名的参数控制机制之一, 即五分之一的成功规则, 以控制非精英 $(1,\ lambda) 中的后代 $\ 。 众所周知, 美元( 1,\ lambda) EA 在选择 $\ labdd 时, 也有一个尖锐的门槛, 也就是我们预期的运行时间是从多货币到指数的Oax。 因此, 我们不清楚参数控制机制是否正确决定了美元的成功率。