| Autor: |
Kearney, Jack, Neumann, Frank, Sutton, Andrew M. |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2023) |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1145/3594805.3607134 |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
