Level-Based Analysis of Genetic Algorithms and Other Search Processes
Level-Based Analysis of Genetic Algorithms and Other Search Processes
复制标题
DOI：
10.1101/084335
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Dogan Corus;D. Dang;A. Eremeev;P. Lehre
中科院分区：
文献类型：
--
作者：
Dogan Corus;D. Dang;A. Eremeev;P. Lehre
了解进化算法的时间复杂度如何依赖于其参数设置和适应度景观的特征是进化计算中的一个基本问题。大多数严格的结果是使用少数关键分析技术得出的，包括漂移分析。然而，由于这些技术很少毫不费力地适用于人口为基础的EA，大多数时间复杂度的结果涉及简化的EA，如（1 + 1）EA。本文介绍了基于水平的定理，一种新的技术，适合人口为基础的过程。它适用于任何非精英过程，其中弹簧独立于仅取决于当前人口的分布进行采样。在此分布的条件下，我们的技术提供了预期时间的上限，直到该过程达到目标状态。我们展示了几个伪布尔函数的技术，排序问题，并在组合优化的最优解的近似。该定理的条件通常可以直接验证，即使对于遗传算法和分布估计算法来说也是如此，这些算法被认为是非常不容易分析的。最后，我们证明了定理是近最优的过程考虑。给定定理需要的关于过程的信息，一个更严格的界限无法被证明。
Understanding how the time-complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous results were derived using a handful of key analytic techniques, including drift analysis. However, since few of these techniques apply effortlessly to population-based EAs, most time-complexity results concern simplified EAs, such as the (1 + 1) EA. This paper describes the level-based theorem, a new technique tailored to population-based processes. It applies to any non-elitist process where o spring are sampled independently from a distribution depending only on the current population. Given conditions on this distribution, our technique provides upper bounds on the expected time until the process reaches a target state. We demonstrate the technique on several pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combina-torial optimisation. The conditions of the theorem are often straightfor-ward to verify, even for Genetic Algorithms and Estimation of Distribution Algorithms which were considered highly non-trivial to analyse. Finally, we prove that the theorem is nearly optimal for the processes considered. Given the information the theorem requires about the process, a much tighter bound cannot be proved.