Runtime Analysis of the (μ + 1) EA on Simple Pseudo-Boolean Functions
本文首次严格分析了(μ + 1)进化算法在伪布尔函数上的期望运行时间和成功概率，发现对于简单函数该算法不优于(1 + 1)进化算法，但适度增加种群大小可显著降低复杂函数的运行时间。
Although Evolutionary Algorithms (EAs) have been successfully applied to optimization in discrete search spaces, theoretical developments remain weak, in particular for population-based EAs. This paper presents a first rigorous analysis of the (μ + 1) EA on pseudo-Boolean functions. Using three well-known example functions fromthe analysis of the (1 + 1) EA, we derive bounds on the expected runtime and success probability. For two of these functions, upper and lower bounds on the expected runtime are tight, and on all three functions, the (μ + 1) EA is never more efficient than the (1 + 1) EA. Moreover, all lower bounds growwith μ. On a more complicated function, however, a small increase of μ provably decreases the expected runtime drastically. This paper develops a newproof technique that bounds the runtime of the (μ + 1) EA. It investigates the stochastic process for creating family trees of individuals; the depth of these trees is bounded. Thereby, the progress of the population towards the optimum is captured. This new technique is general enough to be applied to other population-based EAs.