Fitness levels with tail bounds for the analysis of randomized search heuristics

DOI10.1016/J.IPL.2013.09.013MaRDI QIDQ2350596zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Carsten Witt

Publication date 25 June 2015

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.09.013

zbMATH Keywords

randomized algorithmsrandomized search heuristicsrunning time analysistail boundsfitness-level method

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Recommendations

• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• Concentrated hitting times of randomized search heuristics with variable drift
• The use of tail inequalities on the probable computational time of randomized search heuristics
• Tight bounds on the optimization time of a randomized search heuristic on linear functions

Cites work

• scientific article; zbMATH DE number 1754585 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (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.
• Analyzing randomized search heuristics: tools from probability theory
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• The use of tail inequalities on the probable computational time of randomized search heuristics

Cited in

(14)

• Fixed-target runtime analysis
• Lower bounds from fitness levels made easy
• Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions
• Analyzing randomized search heuristics: tools from probability theory
• The use of tail inequalities on the probable computational time of randomized search heuristics
• Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
• Analysis of speedups in parallel evolutionary algorithms and \((1 + \lambda)\) EAs for combinatorial optimization
• Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm
• MMAS versus population-based EA on a family of dynamic fitness functions
• The impact of random initialization on the runtime of randomized search heuristics
• A theoretical investigation of termination criteria for evolutionary algorithms
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• Concentrated hitting times of randomized search heuristics with variable drift
• Fourier analysis meets runtime analysis: precise runtimes on plateaus

This page was built for publication: Fitness levels with tail bounds 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 Q2350596)