The Runtime of Random Local Search on the Generalized Needle Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908587939332096 |
|---|---|
| author | Doerr, Benjamin Kelley, Andrew James |
| author_facet | Doerr, Benjamin Kelley, Andrew James |
| contents | In their recent work, C. Doerr and Krejca (Transactions on Evolutionary Computation, 2023) proved upper bounds on the expected runtime of the randomized local search heuristic on generalized Needle functions. Based on these upper bounds, they deduce in a not fully rigorous manner a drastic influence of the needle radius $k$ on the runtime.
In this short article, we add the missing lower bound necessary to determine the influence of parameter $k$ on the runtime. To this aim, we derive an exact description of the expected runtime, which also significantly improves the upper bound given by C. Doerr and Krejca. We also describe asymptotic estimates of the expected runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_08153 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Runtime of Random Local Search on the Generalized Needle Problem Doerr, Benjamin Kelley, Andrew James Neural and Evolutionary Computing Artificial Intelligence Data Structures and Algorithms In their recent work, C. Doerr and Krejca (Transactions on Evolutionary Computation, 2023) proved upper bounds on the expected runtime of the randomized local search heuristic on generalized Needle functions. Based on these upper bounds, they deduce in a not fully rigorous manner a drastic influence of the needle radius $k$ on the runtime. In this short article, we add the missing lower bound necessary to determine the influence of parameter $k$ on the runtime. To this aim, we derive an exact description of the expected runtime, which also significantly improves the upper bound given by C. Doerr and Krejca. We also describe asymptotic estimates of the expected runtime. |
| title | The Runtime of Random Local Search on the Generalized Needle Problem |
| topic | Neural and Evolutionary Computing Artificial Intelligence Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.08153 |