Abstract
Unlike using the sequence-based representation for a chromosome in previous genetic algorithms for Bayesian structure learning, we proposed a matrix representation-based genetic algorithm. Since a good chromosome representation helps us to develop efficient genetic operators that maintain a functional link between parents and their offspring, we represent a chromosome as a matrix that is a general and intuitive data structure for a directed acyclic graph (DAG), Bayesian network structure. This matrix-based genetic algorithm enables us to develop genetic operators more efficient for structuring Bayesian network: a probability matrix and a transpose-based mutation operator to inherit a structure with the correct edge direction and enhance the diversity of the offspring. To show the outstanding performance of the proposed method, we analyzed the performance between two well-known genetic algorithms and the proposed method using two Bayesian network scoring measures.
Introduction
Learning the structure of a Bayesian Network (BN)—essentially a map of how different variables influence one another—is a notoriously difficult "NP-hard" problem. A BN is represented as a Directed Acyclic Graph (DAG). Traditional algorithms like K2 are efficient but require a pre-defined ordering of variables, which is rarely available in real-world scenarios.
Genetic Algorithms (GAs) are well-suited for searching these massive spaces without prior knowledge. However, they typically represent the network as a flat sequence of numbers. This "sequence-based" approach is unintuitive for graphs; it makes it difficult for the algorithm to maintain functional links between parents and offspring during "crossover" (breeding) and often fails to explore the search space effectively, leading to sub-optimal networks with edges pointing in the wrong direction.
Methodology: Matrix-Based Representation
The proposed approach utilizes a Matrix-Based Genetic Algorithm. Instead of a sequence, each "chromosome" is an $n \times n$ connectivity matrix where a '1' at a specific cell indicates a directed edge between two variables.
Two novel operators distinguish this method:
- Probability Matrix ($P$): Instead of standard two-parent crossover, the algorithm selects a group of $t$ parents and creates a probability matrix. Each cell in this matrix represents the frequency of a specific edge appearing across all selected parents. Offspring are then generated based on these probabilities. This allows a single child to inherit structural "wisdom" from many parents simultaneously, exponentially increasing the diversity of potential offspring.
- Transpose-Based Mutation: A significant challenge in BN learning is "reverse edges"—where the algorithm correctly identifies a link between variables A and B but points the arrow the wrong way. Because these reversed edges often have similar statistical scores to correct ones, they are difficult to eliminate. The authors introduced a mutation that transposes the matrix, effectively flipping edge directions to evaluate if a superior structure emerges.
Experimental Evaluation
The algorithm was evaluated on three classic Bayesian Network benchmarks:
- Asia: A small network (8 variables) representing medical knowledge about lung diseases.
- Car-start: A medium-sized network (18 variables) for diagnosing why a car won't start.
- ALARM: A large, complex network (37 variables) used for monitoring patients in intensive care.
The researchers generated 10,000 data samples for each benchmark to test how accurately the algorithm could reconstruct the original "ground truth" structures.
Key Results
The proposed method was compared against two established GA approaches (Larranaga et al. and Ross et al.) using the Bayesian score and the Bayesian Information Criterion (BIC).
- Superior Accuracy: The matrix-based GA consistently achieved scores closer to the ground truth across all datasets.
- Edge Counting: On the Asia dataset, the proposed method found significantly more "correct edges" and fewer "reverse" or "wrong" edges than its competitors.
- Efficiency: In the Car-start dataset, the algorithm's score slightly exceeded the theoretical optimal score, demonstrating high efficiency in navigating the search space.
Conclusion and Future Work
By using a matrix representation, the GA operates in a data structure that mirrors the actual problem, making genetic operators more structurally meaningful. The probability matrix approach helps avoid local optima, while the transpose mutation addresses the "likelihood equivalence" problem of edge directionality.
While the algorithm excels on small and medium datasets, the search space for very large networks like ALARM remains a challenge. Future work will focus on developing "divide-and-conquer" strategies—breaking large datasets into smaller sub-problems—to allow the matrix-based GA to scale effectively to high-dimensional data.
Summary updated