论文标题
紧凑的遗传算法在悬崖功能上挣扎
The Compact Genetic Algorithm Struggles on Cliff Functions
论文作者
论文摘要
紧凑型遗传算法（CGA）是分布算法的非精明主义估计，该算法已证明能够处理难以通过精英算法难以解决的困难多模式适应性景观。在本文中，我们研究了CGA关于最近已显示的悬崖功能，非精美的进化算法和人工免疫系统在预期的多项式时间内优化了它。我们指出，CGA在解决悬崖功能时面临主要困难，并在悬崖周围进行实验和理论上的动态。我们的实验结果表明，CGA需要满足更新强度$ k $的所有值的指数时间。从理论上讲，在明智的假设下，在悬崖的位置进行采样时，会出现负面漂移。实验进一步表明，$ k $有一个相变，其中预期优化时间从$ n^{θ（n）} $下降到$ 2^{θ（n）} $。
The compact genetic algorithm (cGA) is an non-elitist estimation of distribution algorithm which has shown to be able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. In this paper, we investigate the cGA on the CLIFF function for which it has been shown recently that non-elitist evolutionary algorithms and artificial immune systems optimize it in expected polynomial time. We point out that the cGA faces major difficulties when solving the CLIFF function and investigate its dynamics both experimentally and theoretically around the cliff. Our experimental results indicate that the cGA requires exponential time for all values of the update strength $K$. We show theoretically that, under sensible assumptions, there is a negative drift when sampling around the location of the cliff. Experiments further suggest that there is a phase transition for $K$ where the expected optimization time drops from $n^{Θ(n)}$ to $2^{Θ(n)}$.
