Significance-based Estimation-of-Distribution Algorithms
This addresses a fundamental issue in randomized search heuristics for optimization, offering a novel solution with proven efficiency gains, though it is incremental relative to existing EDAs.
The paper tackled the problem of erratic model updates in estimation-of-distribution algorithms (EDAs) by proposing a significance-based compact genetic algorithm (sig-cGA) that uses a longer history of samples and statistically significant information, proving it optimizes benchmark functions OneMax, LeadingOnes, and BinVal in quasilinear time, a result not shown for other EDAs or evolutionary 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.