On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help

Abstract

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 $\mu /\lambda$ is extremely high, where $\mu$ and $\lambda$ are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of $\mu =\Omega (\log n)$ has an expected runtime of $e^{\Omega (\mu )}$ on the DLB problem assuming any selective pressure $\frac{\mu }{\lambda }\ge \frac{14}{1000}$, as opposed to the expected runtime of $\mathcal{O}(n\lambda \log \lambda +n^3)$ for the non-elitist $(\mu ,\lambda )\text{EA}$ with $\mu /\lambda \le 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.

arXiv commentTo appear in the 15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), Potsdam, Germany

References in corpus (3)

• Improved Runtime Bounds for the Univariate Marginal Distribution Algorithm via Anti-Concentration
• Runtime Analysis of the Univariate Marginal Distribution Algorithm under Low Selective Pressure and Prior Noise
• An Exponential Lower Bound for the Runtime of the cGA on Jump Functions

Cited by in corpus (7)

• Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms
• The Runtime of the Compact Genetic Algorithm on Jump Functions
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm
• How Well Does the Metropolis Algorithm Cope With Local Optima?
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
• A Fresh Look at Lamarckian Evolution and the Baldwin Effect