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. ISSN 1865-9284 (In Press)

[img] Text
DICE Exploiting All Bivariate Dependencies in Binary and Multary.pdf - Accepted Version
Restricted to Repository staff only until 17 November 2018.

Download (1MB) | Request a copy

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 [19], 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 correlationbased 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
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
UoA Collections > UoA11: Computer Science and Informatics
Depositing User: $ Ian McDonald
Date Deposited: 06 Dec 2017 12:43
Last Modified: 06 Dec 2017 12:43
URI: http://www.open-access.bcu.ac.uk/id/eprint/5380

Actions (login required)

View Item View Item

Research

In this section...