Bayesian network structure learning using scatter search
Wei-Ting Yang, Karim Tamssaouet, Stéphane Dauzère‐Pérès · Knowledge-Based Systems · 2024
Learning the structure of Bayesian networks (BNs) from data is an NP-hard problem as the solution space grows super-exponentially with the number of nodes. Many algorithms have been developed to efficiently find the best structures, with score-based algorithms being those that use heuristics or metaheuristics to explore potential structures in the search space. This paper proposes a new score-based algorithm that relies on a well-known metaheuristic called scatter search, which, to the best of our knowledge, has not been used in learning BN structure. The core of scatter search is to maintain a reference set that stores both high-quality and diverse solutions, thereby continuously tracking and improving the high-quality solutions, while exploring different search directions indicated by the diverse solutions. By incorporating a distance metric in the learning process, the exploration can be more systematic than purely random, as is often the case in most existing algorithms. The effectiveness and efficiency of the proposed algorithm are evaluated through computational experiments. In addition to learning higher-score structures, the results show that scatter search provides a higher degree of robustness compared with benchmark algorithms.