Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax

DOI10.1145/3040718.3040724zbMath1365.68391OpenAlexW2605136245WikidataQ57200553 ScholiaQ57200553MaRDI QIDQ5738858

Carsten Witt, Martin S. Krejca

Publication date: 13 June 2017

Published in: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (Search for Journal in Brave)

Full work available at URL: https://backend.orbit.dtu.dk/ws/files/152318081/1_s2.0_S0304397518304122_main.pdf

zbMATH Keywords

lower boundestimation of distribution algorithmruntime analysis

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

The complex parameter landscape of the compact genetic algorithm ⋮ Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ A simplified run time analysis of the univariate marginal distribution algorithm on LeadingOnes ⋮ Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax ⋮ Level-based analysis of the univariate marginal distribution algorithm ⋮ On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization ⋮ The univariate marginal distribution algorithm copes well with deception and epistasis ⋮ Unbiasedness of estimation-of-distribution algorithms

This page was built for publication: Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax