Estimation-of-distribution algorithms (EDAs) are optimization algorithms that
learn a distribution on the search space from which good solutions can be
sampled easily. A key parameter of most EDAs is the sample size (population
size). If the population size is too small, the update of the probabilistic
model builds on few samples, leading to the undesired effect of genetic drift.
Too large population sizes avoid genetic drift, but slow down the process.
Building on a recent quantitative analysis of how the population size leads
to genetic drift, we design a smart-restart mechanism for EDAs. By stopping
runs when the risk for genetic drift is high, it automatically runs the EDA in
good parameter regimes.
Via a mathematical runtime analysis, we prove a general performance guarantee
for this smart-restart scheme. This in particular shows that in many situations
where the optimal (problem-specific) parameter values are known, the restart
scheme automatically finds these, leading to the asymptotically optimal
performance.
We also conduct an extensive experimental analysis. On four classic benchmark
problems, we clearly observe the critical influence of the population size on
the performance, and we find that the smart-restart scheme leads to a
performance close to the one obtainable with optimal parameter values. Our
results also show that previous theory-based suggestions for the optimal
population size can be far from the optimal ones, leading to a performance
clearly inferior to the one obtained via the smart-restart scheme. We also
conduct experiments with PBIL (cross-entropy algorithm) on two combinatorial
optimization problems from the literature, the max-cut problem and the
bipartition problem. Again, we observe that the smart-restart mechanism finds
much better values for the population size than those suggested in the
literature, leading to a much better performance.

通过量化分析和实验验证，我们设计了一种基于 “智能重启机制” 的 EDAs 算法，可以自动识别较好的参数，并且在许多情况下充分展示了其优异的性能表现。

从遗传漂变理解到用于分布估计算法的智能重启机制

From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms

Estimation-of-distribution algorithms (EDAs) are randomized search heuristics
that create a probabilistic model of the solution space, which is updated
iteratively, based on the quality of the solutions sampled according to the
model. As previous works show, this iteration-based perspective can lead to
erratic updates of the model, in particular, to bit-frequencies approaching a
random boundary value.
In order to overcome this problem, we propose a new EDA based on the classic
compact genetic algorithm (cGA) that takes into account a longer history of
samples and updates its model only with respect to information which it
classifies as statistically significant. We prove that this significance-based
compact genetic algorithm (sig-cGA) optimizes the commonly regarded benchmark
functions OneMax, LeadingOnes, and BinVal all in quasilinear time, a result
shown for no other EDA or evolutionary algorithm so far.
For the recently proposed scGA -- an EDA that tries to prevent erratic model
updates by imposing a bias to the uniformly distributed model -- we prove that
it optimizes OneMax only in a time exponential in its hypothetical population
size. Similarly, we show that the convex search algorithm cannot optimize
OneMax in polynomial time.

提出一种基于紧凑遗传算法的 EDA 方法，只更新经历考虑后的信息，证明了该方法可在近线性时间内优化 OneMax、LeadingOne 和 BinVal 等基准函数，对于其他 EDA 和进化算法还未有类似的结果。同时证明了其他两种算法无法在多项式时间内优化 OneMax。