Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916696959221760 |
|---|---|
| author | Opris, Andre Lengler, Johannes Sudholt, Dirk |
| author_facet | Opris, Andre Lengler, Johannes Sudholt, Dirk |
| contents | The JUMP$_k$ benchmark was the first problem for which crossover was proven to give a speed-up over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of $O(\text{poly}(n) + 4^k/p_c)$ for the ($μ$+1) Genetic Algorithm ($(μ+1)$ GA), but only for unrealistically small crossover probabilities $p_c$. To this date, it remains an open problem to prove similar upper bounds for realistic $p_c$; the best known runtime bound, in terms of function evaluations, for $p_c = Ω(1)$ is $O((n/χ)^{k-1})$, $χ$ a positive constant. We provide a novel approach and analyse the evolution of the population diversity, measured as sum of pairwise Hamming distances, for a variant of the $(μ+1)$ GA on JUMP$_k$. The $(μ+1)$-$λ_c$-GA creates one offspring in each generation either by applying mutation to one parent or by applying crossover $λ_c$ times to the same two parents (followed by mutation), to amplify the probability of creating an accepted offspring in generations with crossover. We show that population diversity in the $(μ+1)$-$λ_c$-GA converges to an equilibrium of near-perfect diversity. This yields an improved time bound of $O(μn \log(μ) + 4^k)$ function evaluations for a range of $k$ under the mild assumptions $p_c = O(1/k)$ and $μ\in Ω(kn)$. For all constant $k$, the restriction is satisfied for some $p_c = Ω(1)$ and it implies that the expected runtime for all constant $k$ and an appropriate $μ= Θ(kn)$ is bounded by $O(n^2 \log n)$, irrespective of $k$. For larger $k$, the expected time of the $(μ+1)$-$λ_c$-GA is $Θ(4^k)$, which is tight for a large class of unbiased black-box algorithms and faster than the original $(μ+1)$ GA by a factor of $Ω(1/p_c)$. We also show that our analysis can be extended to other unitation functions such as JUMP$_{k, δ}$ and HURDLE. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07061 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity Opris, Andre Lengler, Johannes Sudholt, Dirk Neural and Evolutionary Computing 68Q25, 68Q87, 68W20, 68W40, 68W50 F.2.2; G.3 The JUMP$_k$ benchmark was the first problem for which crossover was proven to give a speed-up over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of $O(\text{poly}(n) + 4^k/p_c)$ for the ($μ$+1) Genetic Algorithm ($(μ+1)$ GA), but only for unrealistically small crossover probabilities $p_c$. To this date, it remains an open problem to prove similar upper bounds for realistic $p_c$; the best known runtime bound, in terms of function evaluations, for $p_c = Ω(1)$ is $O((n/χ)^{k-1})$, $χ$ a positive constant. We provide a novel approach and analyse the evolution of the population diversity, measured as sum of pairwise Hamming distances, for a variant of the $(μ+1)$ GA on JUMP$_k$. The $(μ+1)$-$λ_c$-GA creates one offspring in each generation either by applying mutation to one parent or by applying crossover $λ_c$ times to the same two parents (followed by mutation), to amplify the probability of creating an accepted offspring in generations with crossover. We show that population diversity in the $(μ+1)$-$λ_c$-GA converges to an equilibrium of near-perfect diversity. This yields an improved time bound of $O(μn \log(μ) + 4^k)$ function evaluations for a range of $k$ under the mild assumptions $p_c = O(1/k)$ and $μ\in Ω(kn)$. For all constant $k$, the restriction is satisfied for some $p_c = Ω(1)$ and it implies that the expected runtime for all constant $k$ and an appropriate $μ= Θ(kn)$ is bounded by $O(n^2 \log n)$, irrespective of $k$. For larger $k$, the expected time of the $(μ+1)$-$λ_c$-GA is $Θ(4^k)$, which is tight for a large class of unbiased black-box algorithms and faster than the original $(μ+1)$ GA by a factor of $Ω(1/p_c)$. We also show that our analysis can be extended to other unitation functions such as JUMP$_{k, δ}$ and HURDLE. |
| title | Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity |
| topic | Neural and Evolutionary Computing 68Q25, 68Q87, 68W20, 68W40, 68W50 F.2.2; G.3 |
| url | https://arxiv.org/abs/2404.07061 |