TY - GEN
T1 - DICE
T2 - 20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017
AU - Lane, Fergal
AU - Muhammad Atif Azad, R.
AU - Ryan, Conor
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - Combinatorial optimization
KW - Dichotomised Gaussian models
KW - EDAs
UR - http://www.scopus.com/inward/record.url?scp=85017526276&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-55849-3_43
DO - 10.1007/978-3-319-55849-3_43
M3 - Conference contribution
AN - SCOPUS:85017526276
SN - 9783319558486
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 670
EP - 685
BT - Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings
A2 - Hidalgo, J.Ignacio
A2 - Cotta, Carlos
A2 - Hu, Ting
A2 - Tonda, Alberto
A2 - Burrelli, Paolo
A2 - Coler, Matt
A2 - Iacca, Giovanni
A2 - Kampouridis, Michael
A2 - Mora Garcia, Antonio M.
A2 - Squillero, Giovanni
A2 - Brabazon, Anthony
A2 - Haasdijk, Evert
A2 - Heinerman, Jacqueline
A2 - D Andreagiovanni, Fabio
A2 - Bacardit, Jaume
A2 - Nguyen, Trung Thanh
A2 - Silva, Sara
A2 - Tarantino, Ernesto
A2 - Esparcia-Alcazar, Anna I.
A2 - Ascheid, Gerd
A2 - Glette, Kyrre
A2 - Cagnoni, Stefano
A2 - Kaufmann, Paul
A2 - de Vega, Francisco Fernandez
A2 - Mavrovouniotis, Michalis
A2 - Zhang, Mengjie
A2 - Divina, Federico
A2 - Sim, Kevin
A2 - Urquhart, Neil
A2 - Schaefer, Robert
PB - Springer Verlag
Y2 - 19 April 2017 through 21 April 2017
ER -