- Treffer 1 von 1
Lower bounds on the run time of the Univariate Marginal Distribution Algorithm on OneMax
- The Univariate Marginal Distribution Algorithm (UMDA) - a popular estimation-of-distribution algorithm - is studied from a run time perspective. On the classical OneMax benchmark function on bit strings of length n, a lower bound of Omega(lambda + mu root n + n logn), where mu and lambda are algorithm-specific parameters, on its expected run time is proved. This is the first direct lower bound on the run time of UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation-of-distribution algorithms in general.
Verfasserangaben: | Martin S. KrejcaORCiD, Carsten WittORCiD |
---|---|
DOI: | https://doi.org/10.1016/j.tcs.2018.06.004 |
ISSN: | 0304-3975 |
ISSN: | 1879-2294 |
Titel des übergeordneten Werks (Englisch): | Theoretical computer science : the journal of the EATCS |
Verlag: | Elsevier |
Verlagsort: | Amsterdam [u.a.] |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 06.09.2020 |
Erscheinungsjahr: | 2020 |
Datum der Freischaltung: | 17.04.2023 |
Freies Schlagwort / Tag: | estimation-of-distribution algorithm; lower bound; run time analysis |
Band: | 832 |
Seitenanzahl: | 23 |
Erste Seite: | 143 |
Letzte Seite: | 165 |
Fördernde Institution: | Danish Council for Independent ResearchDet Frie Forskningsrad (DFF); [DFF-FNU 4002-00542] |
Organisationseinheiten: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer Review: | Referiert |