Unbiased Black-Box Complexities of Jump Functions
We analyze the unbiased black-box complexity of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we show that when the jump size is $(1/2 - \varepsilon)n$, that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities $3$ and higher are of the same order as those for the simple \textsc{OneMax} function. Even for the extreme jump function, in which all but the two fitness values $n/2$ and $n$ are blanked out, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a $\Theta(n^{-1/2})$ fraction) is a plateau of constant fitness. To prove these results, we introduce new tools for the analysis of unbiased black-box complexities, for example, selecting the new parent individual not by comparing the fitnesses of the competing search points, but also by taking into account the (empirical) expected fitnesses of their offspring.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Pricing options on the cryptocurrency futures contracts
The cryptocurrency options market is notable for its high volatility and lower liquidity compared to traditional markets. These characteristics introduce significant challenges to traditional option pricing methodologies…
Black-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…
Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity
The JUMP$_k$ benchmark was the first problem for which crossover was proven to give a speed-up over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of $O(\text{poly}(n) + 4^k/p_c)$ …
DiversityEvolutionary AlgorithmsGeneral multilevel Monte Carlo methods for pricing discretely monitored Asian options
We describe general multilevel Monte Carlo methods that estimate the price of an Asian option monitored at $m$ fixed dates. Our approach yields unbiased estimators with standard deviation $O(\epsilon)$ in $O(m + (1/\epsi…
MONGOOSE: Path-wise Smooth Bayesian Optimisation via Meta-learning
In Bayesian optimisation, we often seek to minimise the black-box objective functions that arise in real-world physical systems. A primary contributor to the cost of evaluating such black-box objective functions is often…
Bayesian OptimisationMeta-Learning