Tail bounds on hitting times of randomized search heuristics using variable drift analysis

DOI10.1017/S0963548320000565OpenAlexW3097043185MaRDI QIDQ5886098

Carsten Witt, Per Kristian Lehre

Publication date: 30 March 2023

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548320000565

Mathematics Subject Classification ID

Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (10)

On easiest functions for mutation operators in bio-inspired optimisation ⋮ On the Diameter of Hyperbolic Random Graphs ⋮ MMAS versus population-based EA on a family of dynamic fitness functions ⋮ Fixed-target runtime analysis ⋮ Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift ⋮ Runtime Analysis of a Co-Evolutionary Algorithm ⋮ Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem ⋮ How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys ⋮ On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization ⋮ How to escape local optima in black box optimisation: when non-elitism outperforms elitism

Cites Work

• Unnamed Item
• Unnamed Item
• Concentration of first hitting times under additive drift
• Asymptotically tight steady-state queue length bounds implied by drift conditions
• 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
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• 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
• Optimal mutation rates for the \((1+\lambda)\) EA on OneMax through asymptotically tight drift analysis
• Adaptive drift analysis
• Multiplicative drift analysis
• Optimal parameter choices via precise black-box analysis
• First-hitting times under drift
• Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift
• Drift Analysis and Evolutionary Algorithms Revisited
• 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
• COMPUTING CALL ADMISSION CAPACITIES IN LINEAR NETWORKS
• Theory of Evolutionary Computation
• Optimizing expected path lengths with ant colony optimization using fitness proportional update

This page was built for publication: Tail bounds on hitting times of randomized search heuristics using variable drift analysis