On the black-box complexity of example functions: the real jump function

DOI10.1145/2725494.2725507MaRDI QIDQ2981879zbMATH OpenOpenAlexFDO

Authors Thomas Jansen

Publication date 10 May 2017

Published in Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2725494.2725507

zbMATH Keywords

\((1+1)\) EAblack-box complexityjump functionruntime analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Upper and lower bounds on unrestricted black-box complexity of \(\textsc{Jump}_{n,\ell} \)
• Black-box complexity for bounding the performance of randomized search heuristics
• Black-box search by unbiased variation
• Ranking-based black-box complexity
• Black-box complexities of combinatorial problems

Cites work

• Absorption time of the Moran process
• Approximating fixation probabilities in the generalized Moran process
• scientific article; zbMATH DE number 3148873 (Why is no real title available?)
• On the fixation probability of superstars

Cited in

(12)

• Black-box complexities of combinatorial problems
• Black-box search by unbiased variation
• A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions
• Black-box complexity: advantages of memory usage
• How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys
• Black-box complexity for bounding the performance of randomized search heuristics
• From black-box complexity to designing new genetic algorithms
• scientific article; zbMATH DE number 7561499 (Why is no real title available?)
• Upper and lower bounds on unrestricted black-box complexity of \(\textsc{Jump}_{n,\ell} \)
• Black-box search by elimination of fitness functions
• An extended jump functions benchmark for the analysis of randomized search heuristics
• Fourier analysis meets runtime analysis: precise runtimes on plateaus

This page was built for publication: On the black-box complexity of example functions: the real jump function

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