Fixed-Parameter Tractability of the (1+1) Evolutionary Algorithm on Random Planted Vertex Covers
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_ | 1866913501770940416 |
|---|---|
| author | Kearney, Jack Neumann, Frank Sutton, Andrew M. |
| author_facet | Kearney, Jack Neumann, Frank Sutton, Andrew M. |
| contents | We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every $O(n \log n)$ steps will find a cover at least as small as the planted cover in polynomial time for sufficiently dense random graphs $p > 0.71$. For superlogarithmic planted covers, we prove that the (1+1) EA finds a solution in fixed-parameter tractable time in expectation.
We complement these theoretical investigations with a number of computational experiments that highlight the interplay between planted cover size, graph density and runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_10144 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fixed-Parameter Tractability of the (1+1) Evolutionary Algorithm on Random Planted Vertex Covers Kearney, Jack Neumann, Frank Sutton, Andrew M. Neural and Evolutionary Computing We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every $O(n \log n)$ steps will find a cover at least as small as the planted cover in polynomial time for sufficiently dense random graphs $p > 0.71$. For superlogarithmic planted covers, we prove that the (1+1) EA finds a solution in fixed-parameter tractable time in expectation. We complement these theoretical investigations with a number of computational experiments that highlight the interplay between planted cover size, graph density and runtime. |
| title | Fixed-Parameter Tractability of the (1+1) Evolutionary Algorithm on Random Planted Vertex Covers |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2409.10144 |