Addressing sampling errors and diversity loss in UMDA

Estimation of distribution algorithms replace the typical crossover and mutation operators by constructing a probabilistic model and generating offspring according to this model. In previous studies, it has been shown that this generally leads to diversity loss due to sampling errors. In this paper, for the case of the simple Univariate Marginal Distribution Algorithm (UMDA), we propose and test several methods for counteracting diversity loss. The diversity loss can come in two phases: sampling from the probability model (offspring generation) and selection. We show that it is possible to completely remove the sampling error during offspring generation. Furthermore, we examine several plausible model construction variants which counteract diversity loss during selection and demonstrate that these update rules work better than the standard update on a variety of simple test problems. Copyright 2007 ACM.