On updating probabilistic graphical models in Bayesian Optimisation Algorithm

The Bayesian Optimisation Algorithm (BOA) is an Estimation of Distribution Algorithm (EDA) that uses a Bayesian network as probabilistic graphical model (PGM). During the evolutionary process, determining the optimal Bayesian network structure by a given solution sample is an NP-hard problem resulting in a very time-consuming process. However, we show in this paper that significant changes in PGM structure do not occur so frequently, and can be particularly sparse at the end of evolution. A statistical study of BOA is thus presented to characterise a pattern of PGM adjustments that can be used as a guide to reduce the frequency of PGM updates. This is accomplished by proposing a new BOA-based optimisation approach (FBOA) whose PGM is not updated at each iteration. This new approach avoids the computational burden usually found in the standard BOA. Inspired by fitness landscape analysis concepts, we perform an investigation in the search space of an NK-landscape optimisation problem and compare the performances of both algorithms by using the correlation between the landscape ruggedness of the problem and the expected runtime of the algorithms. The experiments show that FBOA presents competitive results with significant saving of computational time.