Dynamic Bayesian Network Structure Learning with Improved Bacterial Foraging Optimization Algorithm

By Soham NandiReviewed by Susha Cheriyedath, M.Sc.Apr 16 2024

In an article published in the journal Nature, researchers focused on improving dynamic Bayesian network (DBN) structure learning by introducing an improved bacterial foraging optimization algorithm (IBFO-A) to solve issues of random step size, limited group communication, and balancing global and local searching.

The proposed IBFO-A-based DBN structure learning (IBFO-D) method combined dynamic K2 scoring, V-structure orientation, and elimination-dispersal strategies to enhance the efficiency and accuracy of DBN structure learning, showcasing good convergence, stability, and practicality in engineering applications. 

Background

DBNs are probabilistic graphical models that combine the structure of static Bayesian networks (BN) with time-related information, allowing for dynamic uncertainty inference and temporal data analysis. They have found wide applications in fields such as artificial intelligence (AI), machine learning (ML), and automatic control, as well as various engineering domains. However, the integration of time information into DBNs increases search space complexity, reduces the accuracy of structure learning, and makes it challenging to directly apply static BN learning methods.

Previous work on DBN structure learning included classical approaches such as the dynamic max–min hill climb (DMMHC) local search algorithm and heuristic greedy search (GS) algorithm, which were effective but limited in their efficiency and ability to escape local optima. Other studies applied metaheuristic algorithms like genetic algorithm (GA) and particle swarm optimization (PSO) to optimize DBN structure learning, achieving some success.

This paper addressed the limitations of previous approaches by proposing an IBFO-A for optimizing DBN structure learning. The IBFO-A algorithm enhanced optimization performance through chaotic mapping strategies, improved chemotactic activity, and multi-point crossover operators. Combined with a dynamic K2 scoring function and V-structure orientation rules, the new IBFO-D method aimed to increase search efficiency, accuracy, and stability in learning DBN structures from data, thereby filling gaps in previous work. 

Foundations of Bayesian Network Modeling

A BN is a probabilistic graphical model representing independent relationships among variables using a directed acyclic graph (DAG). In this context, the network structure and parameters were key for efficiently calculating joint probability distributions. Model selection and optimization involved evaluating different structures using a scoring function to find the best representation of the data.

DBNs extended BNs by incorporating temporal evolution patterns of variables, providing a closer approximation to complex dynamic data. They relied on assumptions like the Markov chain property and consistent transitional probabilities across time steps. DBNs consist of an initial network and a transitional network, which together allow for modeling time trajectory and unfolding probabilistic graphical models. By leveraging DBNs, researchers can optimize models and adapt them dynamically to changing environments, offering powerful reasoning tools for real-world decision-making. 

Optimization Methodology for IBFO-D Algorithm

The IBFO-D optimization algorithm incorporated intelligent swarm techniques for DBN structure learning. The process began with initializing the bacterial population using chaotic mapping to improve species diversity and search efficiency. Then, bacteria used chemotactic activities to explore the search space, adjusting their positions to find high-nutrient areas. During the chemotactic process, bacteria could flip and swim movements to investigate and improve their target fitness values. This movement guided bacteria toward high-nutrient regions and allowed them to avoid becoming stuck in local optima.

Reproductive activity enabled bacteria to maintain a high level of health and find the best network structures. The algorithm also included elimination-dispersal activity, which used adaptive mechanisms to escape local optima and explore new search paths. By updating the elimination-dispersal probability based on current progress and iteration number, the algorithm balanced exploration and exploitation.

To evaluate bacterial health, the algorithm employed a dynamic K2 scoring function that assessed each bacterium's performance based on the DBN's network structure. This scoring function helped determine the health of bacteria and guided the optimization process. Finally, the IBFO-D algorithm combined several stages, such as initialization, chemotactic activities, and reproductive processes, to create an efficient and robust approach to improving DBN structures. By incorporating swarm intelligence and adaptive mechanisms, IBFO-D provided a comprehensive method for optimizing DBN structures and maximizing the K2 score.

Performance Evaluation and Comparative Analysis of IBFO Algorithms

The experimental section of the research study focused on evaluating the optimization performance of the proposed IBFO-A and IBFO-D algorithms. The authors used a variety of benchmark functions and optimization problems to assess the algorithms' convergence speed, accuracy, and stability. Initially, the IBFO-A algorithm was tested against seven other optimization algorithms using 10 benchmark functions from CEC2005. These functions included multi-peak, single-peak, and fixed-dimensional multi-peak functions, providing a comprehensive assessment of the algorithms' global search abilities.

Results indicated that IBFO-A performed well, converging to optimal values in several benchmark functions and showing superior performance compared to other algorithms in certain tests. Subsequently, additional comparative experiments with IBFO-A, novel optimization algorithms, and other improved methods were conducted using the CEC2019 benchmark functions. The results demonstrated IBFO-A's strong performance across various types of benchmark functions, particularly in high-dimensional test functions and multi-modal, multi-objective optimization problems.

Moreover, the researchers evaluated the performance of IBFO-A in two real-world engineering optimization problems: tension/compression spring design and constrained truss optimization. These tests showed improved optimization capabilities of IBFO-A compared to the original BFO-A, suggesting its practical applications in engineering. For IBFO-D algorithm network learning performance, dynamic benchmark network experiments derived from well-known static BNs were used. IBFO-D demonstrated stable convergence within high fitness values for both temporal and non-temporal data, proving its efficiency in network learning.

Conclusion

In conclusion, the researchers introduced an IBFO-A for enhancing DBN structure learning. By incorporating chaotic mapping, chemotactic activity improvements, and elimination-dispersal strategies, IBFO-A improved optimization performance. The proposed IBFO-D algorithm, based on IBFO-A, achieved stable convergence, high accuracy, and efficiency in DBN structure learning for both temporal and non-temporal data.

Experimental evaluations confirmed the method's superior performance compared to traditional and other state-of-the-art algorithms. Future work may expand IBFO-D's application to higher-order and time-varying DBNs and integrate additional metaheuristic techniques for further improvements.