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

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

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 algorithms heuristic optimization evolutionary algorithms randomized algorithms drift analysis direct search Markov-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

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