MEDAL Report 2009001
Initial-Population Bias in the Univariate Estimation of Distribution Algorithm
Martin Pelikan and Kumara Sastry  (2009)

Abstract. This paper analyzes the effects of an initial-population bias on the performance of the univariate marginal distribution algorithm (UMDA). The analysis considers two test problems: (1) onemax and (2) noisy onemax. Theoretical models are provided and verified with experiments. Intuitively, biasing the initial population toward the global optimum should improve performance of UMDA, whereas biasing the initial population away from the global optimum should have the opposite effect. Both theoretical and experimental results confirm this intuition. Effects of mutation and sampling are also analyzed and the performance of UMDA is compared to that of the mutation-based hill climbing. While for deterministic onemax the hill climbing is shown to deal with the initial bias very well, for noisy onemax performance of the hill climbing is poor regardless of the bias.

Download PDF

Go back

Missouri Estimation of Distribution Algorithms Laboratory
Department of Mathematics and Computer Science
University of Missouri-St. Louis, St. Louis, MO


            Web design by Martin Pelikan