Analysis of runtime of optimization algorithms for noisy functions over discrete codomains

DOI10.1016/j.tcs.2015.04.008zbMath1338.90259OpenAlexW2144246951MaRDI QIDQ888426

Olivier Teytaud, Sandra Astete-Morales, Youhei Akimoto

Publication date: 30 October 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.04.008

zbMATH Keywords

discrete optimizationadditive noiseruntime analysis

Mathematics Subject Classification ID

Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (6)

Analysis of noisy evolutionary optimization when sampling fails ⋮ Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial ⋮ The voting algorithm is robust to various noise models ⋮ Exponential upper bounds for the runtime of randomized search heuristics ⋮ Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise ⋮ Sorting by swaps with noisy comparisons

Cites Work

• Unnamed Item
• Simplified drift analysis for proving lower bounds in evolutionary computation
• Log-linear convergence and divergence of the scale-invariant \((1+1)\)-ES in noisy environments
• On the analysis of the \((1+1)\) evolutionary algorithm
• A derivative based surrogate model for approximating and optimizing the output of an expensive computer simulation
• Upper and lower bounds for randomized search heuristics in black-box optimization
• Stochastic Approximation of Minima with Improved Asymptotic Speed

This page was built for publication: Analysis of runtime of optimization algorithms for noisy functions over discrete codomains