Real-coded Bayesian Optimization Algorithm

Abstract

This chapter describes a real-coded (i.e., continuous) Estimation of Distribution Algorithm (EDA) that solves real-valued (i.e., numerical) optimization problems of bounded difficulty quickly, accurately, and reliably. This is the real-coded Bayesian Optimization Algorithm (rBOA). The objective is to bring the power of (discrete) BOA to bear upon the area of real-valued optimization. That is, the rBOA must properly decompose a problem and effectively perform Probabilistic Building-Block Crossover (PBBC) for real-valued multivariate data. In other words, a unique feature of rBOA is to learn complex dependencies of variables and make use of mixture models at the level of substructures. To begin with, a Bayesian factorization is performed. The resulting factorization that contains linkage information is then utilized for finding implicit subproblems (i.e., substructures). Mixture models are employed for independently fitting each of these substructures. Subsequently, an independent substructurewise sampling draws the offspring. Experimental studies show that the rBOA finds, with a sub-quadratic scale-up behavior for (additively) decomposable problems, a solution that is superior in quality to that found by advanced real-coded EDAs regardless of inherent problem characteristics. Moreover, comparable or better performance is achieved for nondecomposable problems. © Springer-Verlag Berlin/Heidelberg 2006.