Abstract 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 $${\mathcal {O}}\left( n\lambda \log \lambda +n^2\right)$$ O n λ log λ + n 2 under an offspring population size $$\lambda =\Omega (\log n)$$ λ = Ω ( log n ) and a parent population size $$\mu \le \lambda /(e(1+\delta ))$$ μ ≤ λ / ( e ( 1 + δ ) ) for any constant $$\delta >0$$ δ > 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 \ge \lambda /(e(1+\delta ))$$ μ ≥ λ / ( e ( 1 + δ ) ) . In case of the PBIL, an expected runtime of $${\mathcal {O}}(n^{2+c})$$ O ( n 2 + c ) holds for some constant $$c \in (0,1)$$ c ∈ ( 0 , 1 ) (Wu, Kolonko and Möhring, IEEE TEVC 2017). Despite being a generalisation of the UMDA, this upper bound is significantly asymptotically looser than the upper bound of $${\mathcal {O}}\left( n^2\right)$$ O n 2 of the UMDA for $$\lambda =\Omega (\log n)\cap {\mathcal {O}}\left( n/\log n\right)$$ λ = Ω ( log n ) ∩ O n / log n . Furthermore, the required population size is very large, i.e., $$\lambda =\Omega (n^{1+c})$$ λ = Ω ( n 1 + c ) . Our contributions are then threefold: (1) we show that the UMDA with $$\mu =\Omega (\log n)$$ μ = Ω ( log n ) and $$\lambda \le \mu e^{1-\varepsilon }/(1+\delta )$$ λ ≤ μ e 1 - ε / ( 1 + δ ) for any constants $$\varepsilon \in (0,1)$$ ε ∈ ( 0 , <

We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the Univariate Marginal Distribution Algorithm (UMDA) in the presence of epistasis and deception. We show that simple Evolutionary Algorithms (EAs) outperform the UMDA unless the selective pressure µ/λ is extremely high, where µ and λ are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of µ = Ω (log n) has an expected runtime of eΩ(µ) on the DLB problem assuming any selective pressure [EQUATION], as opposed to the expected runtime of O (nλ log λ + n3) for the non-elitist (µ, λ) EA with µ/λ ≤ 1/e. These results illustrate inherent limitations of univariate EDAs against deception and epistasis, which are common characteristics of real-world problems. In contrast, empirical evidence reveals the efficiency of the bi-variate MIMIC algorithm on the DLB problem. Our results suggest that one should consider EDAs with more complex probabilistic models when optimising problems with some degree of epistasis and deception.

We perform a rigorous runtime analysis for the Univariate Marginal Distribution Algorithm on the LeadingOnes function, a well-known benchmark function in the theory community of evolutionary computation with a high correlation between decision variables. For a problem instance of size n, the currently best known upper bound on the expected runtime is O (nλ log λ + n2) (Dang and Lehre, GECCO 2015), while a lower bound necessary to understand how the algorithm copes with variable dependencies is still missing. Motivated by this, we show that the algorithm requires a eΩ(µ) runtime with high probability and in expectation if the selective pressure is low; otherwise, we obtain a lower bound of [MATH HERE] on the expected runtime. Furthermore, we for the first time consider the algorithm on the function under a prior noise model and obtain an O(n2) expected runtime for the optimal parameter settings. In the end, our theoretical results are accompanied by empirical findings, not only matching with rigorous analyses but also providing new insights into the behaviour of the algorithm.

Estimation of Distribution Algorithms (EDAs) are stochastic heuristics that search for optimal solutions by learning and sampling from probabilistic models. Despite their popularity in real-world applications, there is little rigorous understanding of their performance. Even for the Univariate Marginal Distribution Algorithm (UMDA)—a simple population-based EDA assuming independence between decision variables—the optimisation time on the linear problem OneMax was until recently undetermined. The incomplete theoretical understanding of EDAs is mainly due to the lack of appropriate analytical tools. We show that the recently developed level-based theorem for non-elitist populations combined with anti-concentration results yield upper bounds on the expected optimisation time of the UMDA. This approach results in the bound $$\mathcal {O}\left( n\lambda \log \lambda +n^2\right) $$ on the LeadingOnes and BinVal problems for population sizes $$\lambda >\mu =\varOmega (\log n)$$ , where $$\mu $$ and $$\lambda $$ are parameters of the algorithm. We also prove that the UMDA with population sizes $$\mu \in \mathcal {O}\left( \sqrt{n}\right) \cap \varOmega (\log n)$$ optimises OneMax in expected time $$\mathcal {O}\left( \lambda n\right) $$ , and for larger population sizes $$\mu =\varOmega (\sqrt{n}\log n)$$ , in expected time $$\mathcal {O}\left( \lambda \sqrt{n}\right) $$ . The facility and generality of our arguments suggest that this is a promising approach to derive bounds on the expected optimisation time of EDAs.

Memetic algorithms are popular hybrid search heuristics that integrate local search into the search process of an evolutionary algorithm in order to combine the advantages of rapid exploitation and global optimisation. However, these algorithms are not well understood and the field is lacking a solid theoretical foundation that explains when and why memetic algorithms are effective.

Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that ED As may improve optimisation performance on epistatic fitness landscapes by learning variable interactions.