Hardest Monotone Functions for Evolutionary Algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908429015056384 |
|---|---|
| author | Kaufmann, Marc Larcher, Maxime Lengler, Johannes Sieberling, Oliver |
| author_facet | Kaufmann, Marc Larcher, Maxime Lengler, Johannes Sieberling, Oliver |
| contents | In this paper we revisit the question how hard it can be for the $(1+1)$ Evolutionary Algorithm to optimize monotone pseudo-Boolean functions. By introducing a more pessimistic stochastic process, the partially-ordered evolutionary algorithm (PO-EA) model, Jansen first proved a runtime bound of $O(n^{3/2})$. More recently, Lengler, Martinsson and Steger improved this upper bound to $O(n \log^2 n)$ by an entropy compression argument. In this work, we analyze monotone functions that may adversarially vary at each step of the optimization, so-called dynamic monotone functions. We introduce the function Switching Dynamic BinVal (SDBV) and prove, using a combinatorial argument, that for the $(1+1)$-EA with any mutation rate $p \in [0,1]$, SDBV is drift minimizing within the class of dynamic monotone functions. We further show that the $(1+1)$-EA optimizes SDBV in $Θ(n^{3/2})$ generations. Therefore, our construction provides the first explicit example which realizes the pessimism of the \poea model. Our simulations demonstrate matching runtimes for both the static and the self-adjusting $(1,λ)$-EA and $(1+λ)$-EA. Moreover, devising an example for fixed dimension, we illustrate that drift minimization does not equal maximal runtime beyond asymptotic analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_07438 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hardest Monotone Functions for Evolutionary Algorithms Kaufmann, Marc Larcher, Maxime Lengler, Johannes Sieberling, Oliver Neural and Evolutionary Computing Probability 68W50 In this paper we revisit the question how hard it can be for the $(1+1)$ Evolutionary Algorithm to optimize monotone pseudo-Boolean functions. By introducing a more pessimistic stochastic process, the partially-ordered evolutionary algorithm (PO-EA) model, Jansen first proved a runtime bound of $O(n^{3/2})$. More recently, Lengler, Martinsson and Steger improved this upper bound to $O(n \log^2 n)$ by an entropy compression argument. In this work, we analyze monotone functions that may adversarially vary at each step of the optimization, so-called dynamic monotone functions. We introduce the function Switching Dynamic BinVal (SDBV) and prove, using a combinatorial argument, that for the $(1+1)$-EA with any mutation rate $p \in [0,1]$, SDBV is drift minimizing within the class of dynamic monotone functions. We further show that the $(1+1)$-EA optimizes SDBV in $Θ(n^{3/2})$ generations. Therefore, our construction provides the first explicit example which realizes the pessimism of the \poea model. Our simulations demonstrate matching runtimes for both the static and the self-adjusting $(1,λ)$-EA and $(1+λ)$-EA. Moreover, devising an example for fixed dimension, we illustrate that drift minimization does not equal maximal runtime beyond asymptotic analysis. |
| title | Hardest Monotone Functions for Evolutionary Algorithms |
| topic | Neural and Evolutionary Computing Probability 68W50 |
| url | https://arxiv.org/abs/2311.07438 |