Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded

DOI10.1007/s00453-010-9396-yzbMath1211.68382OpenAlexW2080956517MaRDI QIDQ633837

Jens Jägersküpper

Publication date: 30 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9396-y

zbMATH Keywords

genetic algorithmsheuristic optimizationevolutionary algorithmsrandomized algorithmsdrift analysisdirect searchMarkov-Chain analysis

Mathematics Subject Classification ID

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

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 ⋮ Drift Analysis and Evolutionary Algorithms Revisited ⋮ Runtime analysis for self-adaptive mutation rates ⋮ Adaptive drift analysis ⋮ Runtime analysis for permutation-based evolutionary algorithms ⋮ Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances ⋮ Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint ⋮ Markov chain analysis of evolutionary algorithms on OneMax function -- from coupon collector's problem to (1 + 1) EA ⋮ Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions

Cites Work

• Unnamed Item
• Unnamed Item
• On the analysis of the \((1+1)\) evolutionary algorithm
• Erratum to: ``Drift analysis and average time complexity of evolutionary algorithms
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Algorithmic analysis of a basic evolutionary algorithm for continuous optimization
• On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded