Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

A simplified run time analysis of the univariate marginal distribution algorithm on LeadingOnes

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
Read More Add to Saved list
  • Additional Information
    • Contributors:
      École polytechnique (X); Institut Polytechnique de Paris (IP Paris); Laboratoire d'informatique de l'École polytechnique Palaiseau (LIX); Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS); Hasso Plattner Institute Potsdam, Germany; ANR-11-LABX-0056,LMH,LabEx Mathématique Hadamard(2011)
    • Publication Information:
      CCSD
      Elsevier
    • Publication Date:
      2021
    • Collection:
      École Polytechnique, Université Paris-Saclay: HAL
    • Abstract:
      International audience ; 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.
    • Relation:
      info:eu-repo/semantics/altIdentifier/arxiv/2004.04978; ARXIV: 2004.04978
    • Accession Number:
      10.1016/J.TCS.2020.11.028
    • Online Access:
      https://hal.science/hal-04485607
      https://hal.science/hal-04485607v1/document
      https://hal.science/hal-04485607v1/file/2004.04978.pdf
      https://doi.org/10.1016/J.TCS.2020.11.028
    • Rights:
      info:eu-repo/semantics/OpenAccess
    • Accession Number:
      edsbas.4B70AAE2