Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift

DOI10.1007/978-3-319-13075-0_54zbMath1342.68309OpenAlexW2287495828WikidataQ57200586 ScholiaQ57200586MaRDI QIDQ2942670

Carsten Witt, Per Kristian Lehre

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13075-0_54

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (14)

The interplay of population size and mutation probability in the \((1+\lambda )\) EA on OneMax ⋮ Tail bounds on hitting times of randomized search heuristics using variable drift analysis ⋮ Concentration of first hitting times under additive drift ⋮ Linear multi-objective drift analysis ⋮ Runtime analysis for self-adaptive mutation rates ⋮ Lower bounds from fitness levels made easy ⋮ The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate ⋮ Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax ⋮ On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization ⋮ Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint ⋮ The impact of a sparse migration topology on the runtime of island models in dynamic optimization ⋮ Optimal mutation rates for the \((1+\lambda)\) EA on OneMax through asymptotically tight drift analysis ⋮ First-hitting times under drift ⋮ Phase transition of the 3-majority dynamics with uniform communication noise

Cites Work

• Unnamed Item
• Unnamed Item
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• Simplified drift analysis for proving lower bounds in evolutionary computation
• The cycle structure of random permutations
• On the analysis of the \((1+1)\) evolutionary algorithm
• Erratum to: ``Drift analysis and average time complexity of evolutionary algorithms
• Adaptive drift analysis
• Multiplicative drift analysis
• Fitness levels with tail bounds for the analysis of randomized search heuristics
• Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Probabilistic recurrence relations
• The time complexity of maximum matching by simulated annealing
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• Optimizing expected path lengths with ant colony optimization using fitness proportional update
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis

This page was built for publication: Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift