Probabilistic analysis of the (1+1)-evolutionary algorithm

Alois Panholzer; Hsien-Kuei Hwang; Nicolas Rolin; Tsung-Hsi Tsai; Wei-Mei Chen

arxiv: 1409.4955 · v1 · pith:UAUFKJS3new · submitted 2014-09-17 · 🧮 math.PR · cs.DS

Probabilistic analysis of the (1+1)-evolutionary algorithm

Hsien-Kuei Hwang , Alois Panholzer , Nicolas Rolin , Tsung-Hsi Tsai , Wei-Mei Chen This is my paper

classification 🧮 math.PR cs.DS

keywords algorithmanalysisevolutionaryapproximationsasymptoticapplicableapproachapproached

0 comments

read the original abstract

We give a detailed analysis of the cost used by the (1+1)-evolutionary algorithm. The problem has been approached in the evolutionary algorithm literature under various views, formulation and degree of rigor. Our asymptotic approximations for the mean and the variance represent the strongest of their kind. The approach we develop is also applicable to characterize the limit laws and is based on asymptotic resolution of the underlying recurrence. While most approximations have their simple formal nature, we elaborate on the delicate error analysis required for rigorous justifications.

This paper has not been read by Pith yet.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Sharp Bounds on the Runtime of the (1+1) EA via Drift Analysis and Analytic Combinatorial Tools
cs.NE 2019-06 conditional novelty 6.0

Drift analysis yields E(T) bounded between sum 1/Δ(k) minus c1 log n and sum 1/Δ(k) minus c2 log n, with the difference exactly (e/2) log n + O(1) for the (1+1) EA on OneMax from n/2 ones.