DICE: Exploiting All Bivariate Dependencies in Binary and Multary Search Spaces

Lane, Fergal and Azad, R. Muhammad Atif and Ryan, Conor (2017) DICE: Exploiting All Bivariate Dependencies in Binary and Multary Search Spaces. Memetic Computing, 10. pp. 245-255. ISSN 1865-9284

[img]
Preview
Text
DICE Exploiting All Bivariate Dependencies in Binary and Multary.pdf - Accepted Version

Download (1MB)

Abstract

Although some of the earliest Estimation of Distribution Algorithms (EDAs) utilized bivariate marginal distribution models, up to now, all discrete bivariate EDAs had one serious limitation: they were constrained to exploiting only a limited O(d) subset out of all possible O(d2) bivariate dependencies. As a first we present a family of discrete bivariate EDAs that can learn and exploit all O(d2) dependencies between variables, and yet have the same run-time complexity as their more limited counterparts. This family of algorithms, which we label DICE (DIscrete Correlated Estimation of distribution algorithms), is rigorously based on sound statistical principles, and particularly on a modelling technique from statistical physics: dichotomised multivariate Gaussian distributions. Initially (Lane et al. in European Conference on the Applications of Evolutionary Computation, Springer, 1999), DICE was trialled on a suite of combinatorial optimization problems over binary search spaces. Our proposed dichotomised Gaussian (DG) model in DICE significantly outperformed existing discrete bivariate EDAs; crucially, the performance gap increasingly widened as dimensionality of the problems increased. In this comprehensive treatment, we generalise DICE by successfully extending it to multary search spaces that also allow for categorical variables. Because correlation is not wholly meaningful for categorical variables, interactions between such variables cannot be fully modelled by correlation-based approaches such as in the original formulation of DICE. Therefore, here we extend our original DG model to deal with such situations. We test DICE on a challenging test suite of combinatorial optimization problems, which are defined mostly on multary search spaces. While the two versions of DICE outperform each other on different problem instances, they both outperform all the state-of-the-art bivariate EDAs on almost all of the problem instances. This further illustrates that these innovative DICE methods constitute a significant step change in the domain of discrete bivariate EDAs.

Item Type: Article
Identification Number: https://doi.org/10.1007/s12293-017-0246-1
Date: 19 December 2017
Uncontrolled Keywords: Dichotomised Gaussian models, Bivariate, Estimation of Distribution Algorithms, Combinatorial Optimization
Subjects: G400 Computer Science
Divisions: Faculty of Computing, Engineering and the Built Environment
Faculty of Computing, Engineering and the Built Environment > School of Computing and Digital Technology
Faculty of Computing, Engineering and the Built Environment > School of Computing and Digital Technology > Enterprise Systems
REF UoA Output Collections > REF2021 UoA11: Computer Science and Informatics
Depositing User: Ian Mcdonald
Date Deposited: 06 Dec 2017 12:43
Last Modified: 15 May 2020 05:30
URI: http://www.open-access.bcu.ac.uk/id/eprint/5380

Actions (login required)

View Item View Item

Research

In this section...