On resampling vs. adjusting probabilistic graphical models in estimation of distribution algorithms
This work addresses efficiency issues for researchers and practitioners using estimation of distribution algorithms, but it is incremental as it builds on existing BOA methods.
The paper tackles the computational burden of the Bayesian Optimization Algorithm (BOA) by showing that probabilistic graphical model (PGM) structure changes are infrequent, especially late in evolution, and proposes a new approach (FBOA) that reduces update frequency. The results demonstrate that FBOA achieves competitive performance on an NK-landscape problem while significantly saving computational time, with concrete runtime savings reported.
The Bayesian Optimisation Algorithm (BOA) is an Estimation of Distribution Algorithm (EDA) that uses a Bayesian network as probabilistic graphical model (PGM). Determining the optimal Bayesian network structure given a solution sample is an NP-hard problem. This step should be completed at each iteration of BOA, resulting in a very time-consuming process. For this reason most implementations use greedy estimation algorithms such as K2. 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 during the evolutionary process. 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. The results compare the performances of both algorithms on an NK-landscape optimisation problem using the correlation between the ruggedness and the expected runtime over enumerated instances. The experiments show that FBOA presents competitive results while significantly saving computational time.