A Clustering-Based Model-Building EA for Optimization Problems with Binary and Real-Valued Variables

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.