Markov chain analysis of evolutionary algorithms on OneMax function -- from coupon collector's problem to (1 + 1) EA

DOI10.1016/j.tcs.2020.03.007zbMath1433.68653OpenAlexW3011708793MaRDI QIDQ1989355

Satoru Hiwa, Tomoyuki Hiroyasu, Qinglian Ma, Xiaofeng Qin, Hiroshi Furutani, Yuan Zhang, Ming-Hao Zhao

Publication date: 21 April 2020

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

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

zbMATH Keywords

evolutionary algorithmcoupon collector's problemGumbel functionOneMax problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Statistics of extreme values; tail inference (62G32) Combinatorial probability (60C05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• Towards an analytic framework for analysing the computation time of evolutionary algorithms
• On the analysis of the \((1+1)\) evolutionary algorithm
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: Markov chain analysis of evolutionary algorithms on OneMax function -- from coupon collector's problem to (1 + 1) EA