Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal
We study the $(μ+1)$ EA on the Binary Value function BinVal. We show that it needs at most $O(μ\log μ\cdot n \log n)$ function evaluations to find the optimum when $μ= o(n/\log n)$. This substantially improves upon the recent upper bound of $O(μ^5 n \log(n/μ^4))$ by Krejca, Neumann and Witt. Our results hold for several mutation operators including standard bit mutation. In particular, our bound implies that the $(μ+1)$ EA is at most a factor $O(\log μ\cdot \log n)$ slower on BinVal than on OneMax.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function
We study evolutionary algorithms in a dynamic setting, where for each generation a different fitness function is chosen, and selection is performed with respect to the current fitness function. Specifically, we consider …
Evolutionary AlgorithmsLevel-Based Analysis of the Population-Based Incremental Learning Algorithm
The Population-Based Incremental Learning (PBIL) algorithm uses a convex combination of the current model and the empirical model to construct the next model, which is then sampled to generate offspring. The Univariate M…
Incremental LearningHardest Monotone Functions for Evolutionary Algorithms
The study of hardest and easiest fitness landscapes is an active area of research. Recently, Kaufmann, Larcher, Lengler and Zou conjectured that for the self-adjusting $(1,\lambda)$-EA, Adversarial Dynamic BinVal (ADBV) …
Evolutionary AlgorithmsBlack-Box Complexity of the Binary Value Function
The binary value function, or BinVal, has appeared in several studies in theory of evolutionary computation as one of the extreme examples of linear pseudo-Boolean functions. Its unbiased black-box complexity was previou…
Anytime Analysis on BinVal: Adaptive Parameters Help
While most theoretical run time analyses of discrete randomized search heuristics provide bounds on the expected number of evaluations to find the global optimum, we consider the anytime performance of evolutionary and e…