Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax

DOI10.1007/S00453-018-0463-0zbMath1414.68107arXiv1704.00026OpenAlexW3101350160WikidataQ57200540 ScholiaQ57200540MaRDI QIDQ1725646

Carsten Witt

Publication date: 14 February 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.00026

zbMATH Keywords

running time analysisrandomized search heuristicsUMDAestimation-of-distribution algorithms

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 (8)

Does comma selection help to cope with local optima? ⋮ The complex parameter landscape of the compact genetic algorithm ⋮ How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys ⋮ A simplified run time analysis of the univariate marginal distribution algorithm on LeadingOnes ⋮ On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization ⋮ The runtime of the compact genetic algorithm on jump functions ⋮ Working principles of binary differential evolution ⋮ The univariate marginal distribution algorithm copes well with deception and epistasis

Cites Work

• Unnamed Item
• A rigorous analysis of the compact genetic algorithm for linear functions
• Improved time complexity analysis of the simple genetic algorithm
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift
• The Benefit of Recombination in Noisy Evolutionary Search
• Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links
• Mean, Median and Mode in Binomial Distributions
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• A Sharp Uniform Bound for the Distribution of Sums of Bernoulli Trials
• On the Number of Successes in Independent Trials
• Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax

This page was built for publication: Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax