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

DOI10.1016/J.IPL.2013.09.013zbMATH Open1329.68281DBLPjournals/ipl/Witt14OpenAlexW2083026540WikidataQ57200587 ScholiaQ57200587MaRDI QIDQ2350596FDOQ2350596

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

Recommendations

• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• Concentrated hitting times of randomized search heuristics with variable drift
• Analyzing randomized search heuristics via stochastic domination
• 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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• The use of tail inequalities on the probable computational time of randomized search heuristics
• Title not available (Why is that?)

Cited In (13)

• 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
• Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
• Fourier analysis meets runtime analysis: precise runtimes on plateaus
• MMAS versus population-based EA on a family of dynamic fitness functions
• The impact of random initialization on the runtime of randomized search heuristics
• Fixed-target runtime analysis
• Lower bounds from fitness levels made easy
• Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• A theoretical investigation of termination criteria for evolutionary algorithms
• Analyzing randomized search heuristics via stochastic domination
• Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift

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)