论文标题
单变量的边际分布算法很好地应对欺骗和上学
The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis
论文作者
论文摘要
Lehre and Nguyen（Foga 2019）在最近的工作中表明，单变量的边际分布算法（UMDA）需要在父群体大小中的时间指数，以优化decteptiveledeadingblocks（DLB）问题。他们得出的结论是，单变量EDA在欺骗和上学方面遇到困难。 在这项工作中，我们表明，这种负面发现是由于不幸的umda参数选择引起的。当选择足够大以防止遗传漂移的人口大小时，UMDA用最多$λ（\ frac {n} {2} {2} + 2 e \ ln n n）$适应性评估来优化DLB问题。由于后代人口大小的订单$ n \ log n $的$λ$可以防止遗传漂移，因此UMDA可以通过$ O（n^2 \ log n）$ fitness评估解决DLB问题。相比之下，对于经典的进化算法而言，没有比$ o（n^3）$更好的运行时间保证（我们证明这对于$ {（1+1）} $ ea是紧密的，因此我们的结果表明，UMDA可以很好地应对欺骗和epistatis。 从更广泛的角度来看，我们的结果表明，与进化算法相比，UMDA可以更好地应对本地优点。以前仅因紧凑型遗传算法而闻名。加上Lehre和Nguyen的下限，我们的结果首次严格证明，在遗传漂移方面运行EDA会导致巨大的绩效损失。
In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceptiveLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most $λ(\frac{n}{2} + 2 e \ln n)$ fitness evaluations. Since an offspring population size $λ$ of order $n \log n$ can prevent genetic drift, the UMDA can solve the DLB problem with $O(n^2 \log n)$ fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than $O(n^3)$ is known (which we prove to be tight for the ${(1+1)}$ EA), so our result rather suggests that the UMDA can cope well with deception and epistatis. From a broader perspective, our result shows that the UMDA can cope better with local optima than evolutionary algorithms; such a result was previously known only for the compact genetic algorithm. Together with the lower bound of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.
