Runtime Analyses of the Population-Based Univariate Estimation of Distribution Algorithms on LeadingOnes

摘要

We perform rigorous runtime analyses for the univariate marginal distribution algorithm (UMDA) and the population-based incremental learning (PBIL) Algorithm on LeadingOnes. For the UMDA, the currently known expected runtime on the function is O(n lambda log lambda + n(2)) under an offspring population size lambda = Omega(log n) and a parent population size mu = lambda/(e(1 + delta)) for any constant delta 0 (Dang and Lehre, GECCO 2015). There is no lower bound on the expected runtime under the same parameter settings. It also remains unknown whether the algorithm can still optimise the LeadingOnes function within a polynomial runtime when mu = lambda/(e(1+delta)). In case of the PBIL, an expected runtime of O(n(2+c)) holds for some constant c is an element of(0,1) (Wu, Kolonko and Mohring, IEEE TEVC 2017). Despite being a generalisation of the UMDA, this upper bound is significantly asymptotically looser than the upper bound of O(n(2) of the UMDA for lambda=Omega(log n) boolean AND O. Furthermore, the required population size is very large, i.e., lambda=Omega(n(1+c)). Our contributions are then threefold: (1) we show that the UMDA with mu=Omega(log n) and lambda = mu e(1-epsilon)/(1+delta) for any constants epsilon is an element of(0,1) and 0 delta = e(1-epsilon)-1 requires an expected runtime of e(Omega(mu)) on LEADINGONES, (2) an upper bound of O(n lambda log lambda + n(2)) is shown for the PBIL, which improves the current bound O(n(2+c)) by a significant factor of Theta(n(c)), and (3) we for the first time consider the two algorithms on the LeadingOnes function in a noisy environment and obtain an expected runtime of O(n(2)) for appropriate parameter settings. Our results emphasise that despite the independence assumption in the probabilistic models, the UMDA and the PBIL with fine-tuned parameter choices can still cope very well with variable interactions.