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

DOI10.1016/J.TCS.2020.03.007MaRDI QIDQ1989355zbMATH OpenOpenAlexFDO

Authors Yuan Zhang, Xiaofeng Qin, Qinglian Ma, Satoru Hiwa, Tomoyuki Hiroyasu, Hiroshi Furutani, MingHao 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

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

Recommendations

• On the analysis of the \((1+1)\) evolutionary algorithm
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• On the analysis of a dynamic evolutionary algorithm
• (1+1) EA on Generalized Dynamic OneMax
• On some theoretical properties of \((1+1)\) evolutionary algorithms

Cites work

• scientific article; zbMATH DE number 6019547 (Why is no real title available?)
• scientific article; zbMATH DE number 3141621 (Why is no real title available?)
• scientific article; zbMATH DE number 3167451 (Why is no real title available?)
• scientific article; zbMATH DE number 3680816 (Why is no real title available?)
• scientific article; zbMATH DE number 3514781 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Analyzing randomized search heuristics: tools from probability theory
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• Drift analysis and average time complexity of evolutionary algorithms
• Extreme value theory. An introduction.
• On the analysis of the \((1+1)\) evolutionary algorithm
• Towards an analytic framework for analysing the computation time of evolutionary algorithms

Cited in

(1)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1989355)