On the effectiveness of distributions estimated by probabilistic model building
Chung-Yao Chuang, Ying-ping Chen · 2008
Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms that capture the likely structure of promising solutions by explicitly building a probabilistic model and utilize the built model to guide the further search. It is presumed that EDAs can detect the structure of the problem by recognizing the regularities of the promising solutions. However, in certain situations, EDAs are unable to discover the entire structure of the problem because the set of promising solutions on which the model is built contains insufficient information regrading some parts of the problem and renders EDAs incapable of processing those parts accurately. In this work, we firstly propose a general concept that the estimated probabilistic models should be inspected to reveal the effective search directions. Based on that concept, we design a practical approach which utilizes a reserved set of solutions to examine the built model for the fragments that may be inconsistent with the actual problem structure. Furthermore, we provide an implementation of the designed approach on the extended compact genetic algorithm (ECGA) and conduct numerical experiments. The experimental results indicate that the proposed method can significantly assist ECGA to handle problems comprising building blocks of disparate scalings.