Probabilistic model building GP with Belief propagation

Estimation of distribution algorithms (EDAs) which deal with tree structures as GP are called as probabilistic model building GPs (PMBGPs), and they show better search performance than GP in many problems. A problem of prototype tree-based method, a type of PMBGPs, is that samplings do not always generate the most probable solution, which is the individual with the highest probability and reflects a learned distribution most. This problem wastes a part of learning and increases the number of evaluations to get an optimum solution. In order to overcome this difficulty, this paper proposes a hybrid approach using Belief propagation (BP) in sampling process. BP is an inference algorithm on graphical models and can generate the most probable solution. By applying our approach to benchmark tests, we show that the proposed method is more effective than PLS alone.