An extended jump functions benchmark for the analysis of randomized search heuristics

DOI10.1007/S00453-022-00977-1arXiv2105.03090WikidataQ114229328 ScholiaQ114229328MaRDI QIDQ6185933FDOQ6185933

Authors: Henry Bambury, Antoine Bultel, Benjamin Doerr 

Publication date: 9 January 2024

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Jump functions are the {most-studied} non-unimodal benchmark in the theory of randomized search heuristics, in particular, evolutionary algorithms (EAs). They have significantly improved our understanding of how EAs escape from local optima. However, their particular structure -- to leave the local optimum one can only jump directly to the global optimum -- raises the question of how representative such results are. For this reason, we propose an extended class $extsc{Jump}_{k,delta}$ of jump functions that contain a valley of low fitness of width $delta$ starting at distance $k$ from the global optimum. We prove that several previous results extend to this more general class: for all {$klefrac{n}^{1/3}lnn$} and $delta<k$, the optimal mutation rate for the $(1+1)$~EA is $fracdeltan$, and the fast $(1+1)$~EA runs faster than the classical $(1+1)$~EA by a factor super-exponential in $delta$. However, we also observe that some known results do not generalize: the randomized local search algorithm with stagnation detection, which is faster than the fast $(1+1)$~EA by a factor polynomial in $k$ on $extsc{Jump}_k$, is slower by a factor polynomial in $n$ on some $extsc{Jump}_{k,delta}$ instances. Computationally, the new class allows experiments with wider fitness valleys, especially when they lie further away from the global optimum.

Full work available at URL: https://arxiv.org/abs/2105.03090

zbMATH Keywords

theoryevolutionary computationbenchmarksruntime analysis

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• On the black-box complexity of example functions: the real jump function
• Title not available (Why is that?)
• Tight bounds on the optimization time of a randomized search heuristic on linear functions
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• When a genetic algorithm outperforms hill-climbing
• On the analysis of the \((1+1)\) evolutionary algorithm
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• Crossover can be constructive when computing unique input-output sequences
• Crossover can provably be useful in evolutionary computation
• Faster black-box algorithms through higher arity operators
• From black-box complexity to designing new genetic algorithms
• Memetic algorithms outperform evolutionary algorithms in multimodal optimisation
• Self-adjusting evolutionary algorithms for multimodal optimization
• Solving problems with unknown solution length at almost no extra cost
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• The interplay of population size and mutation probability in the \((1+\lambda )\) EA on OneMax
• Towards a runtime comparison of natural and artificial evolution
• Title not available (Why is that?)
• Static and self-adjusting mutation strengths for multi-valued decision variables
• More effective crossover operators for the all-pairs shortest path problem
• On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help
• Fast mutation in crossover-based algorithms
• On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms
• Stagnation detection with randomized local search
• The runtime of the compact genetic algorithm on jump functions
• The benefits and limitations of voting mechanisms in evolutionary optimisation
• Theory of evolutionary computation. Recent developments in discrete optimization
• When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms
• Stagnation detection meets fast mutation
• Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations

Cited In (1)

• Tight runtime bounds for static unary unbiased evolutionary algorithms on linear functions

This page was built for publication: An extended jump functions benchmark for the analysis of randomized search heuristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185933)