Parallel Genetic Algorithm with Mutual Information and Parent Set Structure for Bayesian Network Structure Learning

Zuowei He

doi:10.1109/tevc.2026.3730953

Parallel Genetic Algorithm with Mutual Information and Parent Set Structure for Bayesian Network Structure Learning

2026-09-07

0

PRE

AI

Carlos A. Coello Coello

DOI：10.1109/tevc.2026.3730953

Original

Original request for help

Save

Abstract

En 中文

The task of Bayesian network structure learning (BNSL) is widely recognized as an NP-hard problem. Genetic algorithms (GA) have shown significant efficacy in addressing combinatorial optimization problems, including those related to BNSL. However, when dealing with large-scale datasets and high-dimensional networks, existing GA-based BNSL methods often encounter extensive time consumption and involve numerous redundant calculations. To address these issues, this paper proposes a full-process parallel GA for BNSL with mutual information and parent set structure (PGA-MIPS), which is driven by a general parallel distributed framework implemented on Apache Spark. A strategy with parent set structure decomposition and memorization is designed to avoid redundant calculations in fitness evaluation. The proposed GA uses customized crossover and mutation operators, based on the parent set structure and mutual information to preserve advantageous substructures and simultaneously increase population diversity. The experimental results on eight Bayesian networks show that PGA-MIPS outperforms the compared algorithms in terms of both consistency and structural Hamming distance with the shortest runtime in most cases.

Keywords:

Bayesian network

parallel structure learning

genetic algorithm

mutual information

memorization

Parallel Genetic Algorithm with Mutual Information and Parent Set Structure for Bayesian Network Structure Learning

Abstract

Journal

Organization

Cited Papers