A simplified run time analysis of the univariate marginal distribution algorithm on LeadingOnes
- With elementary means, we prove a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LEADINGONES benchmark function in the desirable regime with low genetic drift. If the population size is at least quasilinear, then, with high probability, the UMDA samples the optimum in a number of iterations that is linear in the problem size divided by the logarithm of the UMDA's selection rate. This improves over the previous guarantee, obtained by Dang and Lehre (2015) via the deep level-based population method, both in terms of the run time and by demonstrating further run time gains from small selection rates. Under similar assumptions, we prove a lower bound that matches our upper bound up to constant factors.
| Author details: | Benjamin DoerrORCiDGND, Martin Stefan KrejcaORCiDGND |
|---|---|
| DOI: | https://doi.org/10.1016/j.tcs.2020.11.028 |
| ISSN: | 0304-3975 |
| ISSN: | 1879-2294 |
| Title of parent work (English): | Theoretical computer science |
| Publisher: | Elsevier |
| Place of publishing: | Amsterdam |
| Publication type: | Article |
| Language: | English |
| Date of first publication: | 2021/01/06 |
| Publication year: | 2021 |
| Release date: | 2023/12/11 |
| Tag: | Estimation-of-distribution algorithm; Run time analysis; Theory |
| Volume: | 851 |
| Number of pages: | 8 |
| First page: | 121 |
| Last Page: | 128 |
| Funding institution: | Investissement d'avenir project, LabEx LMHFrench National Research Agency (ANR) [ANR-11-LABX-0056-LMH]; COSTEuropean Cooperation in Science and Technology (COST) [CA15140] |
| Organizational units: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
| DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Peer review: | Referiert |
