Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms: Why Success Rates Matter.

摘要: Recent theoretical studies have shown that self-adjusting mechanisms can provably outperform the best static parameters in evolutionary algorithms on discrete problems. However, majority of these concerned elitist and we do not a clear answer whether same be applied for non-elitist algorithms. We study one best-known parameter control mechanisms, one-fifth success rule, to offspring population size $\lambda$ ${(1 , \lambda)}$ EA. It is known EA has sharp threshold with respect choice where runtime OneMax changes from polynomial exponential time. Hence, it are able find maintain suitable values $\lambda$. show crucially depends rate $s$ (i.,e. one-$(s+1)$-th rule). We prove that, if appropriately small, optimises $O(n)$ expected generations $O(n \log n)$ evaluations. A small crucial: also too large, algorithm an OneMax.