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

DOI10.1007/S00453-022-00977-1MaRDI QIDQ6185933zbMATH OpenWikidataFDO

Authors Henry Bambury, Antoine Bultel, Benjamin Doerr

Publication date 9 January 2024

Published in Algorithmica (Search for Journal in Brave)

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)

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.

Cites work

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

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)