Jul, 2019
关于单变量边缘分布算法对欺骗的局限性及双变量 EDAs 的帮助
On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help
Per Kristian Lehre, Phan Trung Hai Nguyen
TL;DR我们引入了一个名为欺骗性领先块（DLB）的新基准问题，通过它来严格研究单变量边际分布算法（UMDA）在存在遗传上下文和欺骗的情况下的运行时间。我们展示了简单的进化算法（EA）优于 UMDA，除非选择压力 $\mu/\lambda$ 极高，其中 $\mu$ 和 $\lambda$ 分别为父代和子代种群大小，并说明 UMDA 在父代种群大小为 $\mu=Ω(\log n)$ 的情况下，预期将具有 $e^{Ω(\mu)}$ 的 DLB 问题运行时间，假设选择压力 $\frac {\mu}{\lambda} \geq \frac {14}{1000}$，而非精英 $(\mu,\lambda)~\text {EA}$ 的预期运行时间为 $\mathcal {O}(n\lambda\log \lambda+n^3)$ 且 $\mu/\lambda\leq 1/e$。这些结果说明了单变量 EDA 在面对现实世界问题中的欺骗和遗传上下文的固有限制。相比之下，实证证据揭示了双变量 MIMIC 算法在 DLB 问题上的效率。我们的结果表明，当优化问题具有一定程度的遗传上下文和欺骗性时，应考虑具有更复杂概率模型的 EDA。