Linkage problem, distribution estimation, and Bayesian networks

fpelikandegcantupazgilligalgeuiucedu In this paper an algorithm based on the concepts of genetic algorithms that uses an estimation of the joint distribution of promising solutions in order to generate new candidate solutions is proposed The algorithm is settled into the context of evolutionary computation and the algorithms based on the estimation of distributions The proposed algorithm is called the Bayesian optimization algorithm BOA To estimate the distribution of promising solutions the techniques for modeling multivariate data by Bayesian networks are used The proposed algorithm identies reproduces and mixes building blocks up to a specied order It is independent of the ordering of the variables in strings representing the solutions Moreover prior information about the problem can be incorporated into the algorithm However the prior information is not essential The rst experiments were done with additively decomposable problems with nonoverlapping building blocks The proposed algorithm is able to solve all tested problems in linear or close to linear time with respect to the problem size without the use of any prior knowledge about the problem Keywords Linkage problem estimation of distribution algorithm modeling data learning Bayesian networks evolu tionary computatio