DICE: A new family of bivariate estimation of distribution algorithms based on dichotomised multivariate gaussian distributions

Fergal Lane, R. Muhammad Atif Azad, Conor Ryan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationApplications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings
EditorsJ.Ignacio Hidalgo, Carlos Cotta, Ting Hu, Alberto Tonda, Paolo Burrelli, Matt Coler, Giovanni Iacca, Michael Kampouridis, Antonio M. Mora Garcia, Giovanni Squillero, Anthony Brabazon, Evert Haasdijk, Jacqueline Heinerman, Fabio D Andreagiovanni, Jaume Bacardit, Trung Thanh Nguyen, Sara Silva, Ernesto Tarantino, Anna I. Esparcia-Alcazar, Gerd Ascheid, Kyrre Glette, Stefano Cagnoni, Paul Kaufmann, Francisco Fernandez de Vega, Michalis Mavrovouniotis, Mengjie Zhang, Federico Divina, Kevin Sim, Neil Urquhart, Robert Schaefer
PublisherSpringer Verlag
Pages670-685
Number of pages16
ISBN (Print)9783319558486
DOIs
Publication statusPublished - 2017
Event20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017 - Amsterdam, Netherlands
Duration: 19 Apr 201721 Apr 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10199 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017
Country/TerritoryNetherlands
City Amsterdam
Period19/04/1721/04/17

Keywords

  • Combinatorial optimization
  • Dichotomised Gaussian models
  • EDAs

Fingerprint

Dive into the research topics of 'DICE: A new family of bivariate estimation of distribution algorithms based on dichotomised multivariate gaussian distributions'. Together they form a unique fingerprint.

Cite this