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\nunivariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes\nbenchmark function in the desirable regime with low genetic drift. If the\npopulation size is at least quasilinear, then, with high probability, the UMDA\nsamples the optimum within a number of iterations that is linear in the problem\nsize divided by the logarithm of the UMDA's selection rate. This improves over\nthe previous guarantee, obtained by Dang and Lehre (2015) via the deep\nlevel-based population method, both in terms of the run time and by\ndemonstrating further run time gains from small selection rates. With similar\narguments as in our upper-bound analysis, we also obtain the first lower bound\nfor this problem. Under similar assumptions, we prove that a bound that matches\nour upper bound up to constant factors holds with high probability.\n