Abstract
We propose a novel clustering-based model-building evolutionary
algorithm to tackle optimization problems that
have both binary and real-valued variables. The search
space is clustered every generation using a distance metric
that considers binary and real-valued variables jointly
in order to capture and exploit dependencies between variables
of different types. After clustering, linkage learning
takes place within each cluster to capture and exploit dependencies
between variables of the same type. We compare
this with a model-building approach that only considers dependencies
between variables of the same type. Additionally,
since many real-world problems have constraints, we
examine the use of different well-known approaches to handling
constraints: constraint domination, dynamic penalty
and global competitive ranking. We experimentally analyze
the performance of the proposed algorithms on various unconstrained
problems as well as a selection of well-known
MINLP benchmark problems that all have constraints, and
compare our results with the Mixed-Integer Evolution Strategy
(MIES). We find that our approach to clustering that is
aimed at the processing of dependencies between binary and
real-valued variables can significantly improve performance
in terms of required population size and function evaluations
when solving problems that exhibit properties such as multiple
optima, strong mixed dependencies and constraints.
algorithm to tackle optimization problems that
have both binary and real-valued variables. The search
space is clustered every generation using a distance metric
that considers binary and real-valued variables jointly
in order to capture and exploit dependencies between variables
of different types. After clustering, linkage learning
takes place within each cluster to capture and exploit dependencies
between variables of the same type. We compare
this with a model-building approach that only considers dependencies
between variables of the same type. Additionally,
since many real-world problems have constraints, we
examine the use of different well-known approaches to handling
constraints: constraint domination, dynamic penalty
and global competitive ranking. We experimentally analyze
the performance of the proposed algorithms on various unconstrained
problems as well as a selection of well-known
MINLP benchmark problems that all have constraints, and
compare our results with the Mixed-Integer Evolution Strategy
(MIES). We find that our approach to clustering that is
aimed at the processing of dependencies between binary and
real-valued variables can significantly improve performance
in terms of required population size and function evaluations
when solving problems that exhibit properties such as multiple
optima, strong mixed dependencies and constraints.
Original language | English |
---|---|
Title of host publication | Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, July 11-15, 2015 |
Editors | Juan Luis Jiménez Laredo, Sara Silva, Anna Isabel Esparcia-Alcázar |
Publisher | Association for Computing Machinery |
Pages | 911-918 |
Number of pages | 8 |
ISBN (Print) | 978-1-4503-3472-3 |
DOIs | |
Publication status | Published - 2015 |