Abstract: Using a limit theorem describing the maximum of independent identically distributed random variables (hereinafter r.v.). in terms of Gumbel distribution, we obtain two claims about the runtime of the $(1+(\lambda,\lambda))~GA_{\mu},$ which is a modification of the $(1+(\lambda,\lambda))~GA$ from (Doerr, Doerr, Ebel, 2015). The modification consists in starting the $(1+(\lambda,\lambda))~GA$ from a best individual out of $\mu=n/\ln n$ randomly sampled individuals. The population size $\lambda=\omega(1)$ is deterministic. In the case of \onemax fitness, limit theorems give us asymptotic distribution of fitness increment in the stage of mutation and crossover of the $(1+(\lambda,\lambda))~GA_{\mu}$, which leads to~$o(n\sqrt{\ln n})$ bound on the expected runtime, given suitable parameters settings. In the case when the fitness is given by \onemax with random disturbances of order $\sqrt{n\ln n}$ (a ``frozen noise''), using limit theorems, we show that with probability tending to~1, the runtime of the $(1+(\lambda,\lambda))~GA_{\mu}$ is at most~$n\sqrt{\ln n}$ as $n\to \infty$, if the disturbance probability at each point is $\rho2^{-n}$, $\rho=O(n^{\beta})$, $\beta \in(0,1)$.

Cite: Eremeev A. , Topchii V.
Application of Limit Theorems to Runtime Analysis of the (1 + (λ, λ)) Genetic Algorithm
In compilation GECCO '25 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion. – Publisher: Association for Computing Machinery, NY, United States., 2025. – C.975-978. – ISBN 979-8-4007-1464-1. DOI: 10.1145/3712255.3726625

Dates:

Published print:	Aug 11, 2025
Published online:	Aug 11, 2025

Identifiers: No identifiers

Citing: Пока нет цитирований

Altmetrics: