DICE: A New Family of Bivariate Estimation of Distribution Algorithms based on Dichotomised Multivariate Gaussian Distributions

A new family of Estimation of Distribution Algorithms (EDAs) for discrete search spaces is presented. The proposed algorithms, which we label DICE (Discrete Correlated Estimation of distribution algorithms) are based, like previous bivariate EDAs such as MIMIC and BMDA, on bivariate marginal distribution models. However, bivariate models previously used in similar discrete EDAs were only able to exploit an O(d) subset of all the O(d2) bivariate variable dependencies between d variables. We introduce, and utilize in DICE, a model based on dichotomised multivariate Gaussian distributions. These models are able to capture and make use of all O(d2) bivariate variable interactions in binary and multary search spaces. This paper tests the performances of these new EDA models and algorithms on a suite of challenging combinatorial optimization problems, and compares their performances to previously used discrete-space bivariate EDA models. EDAs utilizing these new dichotomised Gaussian (DG) models exhibit significantly superior optimization performances, with the performance gap becoming more marked with increasing dimensionality