Sharp bounds for genetic drift in estimation of distribution algorithms (Hot-off-the-press track at GECCO 2020)
B Doerr, W Zheng - Proceedings of the 2020 Genetic and Evolutionary …, 2020 - dl.acm.org
B Doerr, W Zheng
Proceedings of the 2020 Genetic and Evolutionary Computation Conference …, 2020•dl.acm.orgEstimation of distribution algorithms (EDAs) are a successful branch of evolutionary
algorithms (EAs) that evolve a probabilistic model instead of a population. Analogous to
genetic drift in EAs, EDAs also encounter the phenomenon that the random sampling in the
model update can move the sampling frequencies to boundary values not justified by the
fitness. This can result in a considerable performance loss. This work gives the first tight
quantification of this effect for three EDAs and one ant colony optimizer, namely for the …
algorithms (EAs) that evolve a probabilistic model instead of a population. Analogous to
genetic drift in EAs, EDAs also encounter the phenomenon that the random sampling in the
model update can move the sampling frequencies to boundary values not justified by the
fitness. This can result in a considerable performance loss. This work gives the first tight
quantification of this effect for three EDAs and one ant colony optimizer, namely for the …
Estimation of distribution algorithms (EDAs) are a successful branch of evolutionary algorithms (EAs) that evolve a probabilistic model instead of a population. Analogous to genetic drift in EAs, EDAs also encounter the phenomenon that the random sampling in the model update can move the sampling frequencies to boundary values not justified by the fitness. This can result in a considerable performance loss.
This work gives the first tight quantification of this effect for three EDAs and one ant colony optimizer, namely for the univariate marginal distribution algorithm, the compact genetic algorithm, population-based incremental learning, and the max-min ant system with iteration-best update. Our results allow to choose the parameters of these algorithms in such a way that within a desired runtime, no sampling frequency approaches the boundary values without a clear indication from the objective function.
This paper for the Hot-off-the-Press track at GECCO 2020 summarizes the work "Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms" by B. Doerr and W. Zheng, which has been accepted for publication in the IEEE Transactions on Evolutionary Computation [5].