Module bayesian_network 

Bayesian-network model (BOA — Bayesian Optimization Algorithm) for binary search spaces.

Unlike the univariate binary models (super::univariate_bernoulli, super::compact_genetic) and the first-order chain of super::dependency_chain, this model learns an arbitrary-topology directed acyclic graph (DAG) over the binary genes, bounded to at most BayesianNetworkParams::max_parents parents per node. fit greedily constructs the network by adding the single edge with the highest score gain each round; sample performs ancestral sampling along a topological order, drawing each gene from its conditional probability table (CPT) given the already-sampled parent configuration.

The chain is built à la BOA (Pelikan, Goldberg & Cantú-Paz, 1999): starting from an edgeless network, the algorithm repeatedly scores every candidate edge u → v and commits the one with the largest strictly-positive gain, subject to the max_parents cap and an acyclicity check, until no profitable edge remains.

The fitness tensor is accepted by the ProbabilityModel interface but always ignored; the fit is unweighted (the MIMIC precedent).

Non-incremental fit

prev is consumed only as the not-bootstrap signal: when prev = Some(_) the whole network — structure and CPTs — is relearned from scratch from the current generation’s selected rows. Canonical BOA carries no cross-generation state, so the previous BayesianNetworkState is never read. The Some arm exists purely to distinguish the learning path from the params-only prior path.

Structure score: BIC

Edges are scored with the Bayesian Information Criterion (BIC). For a node v with sorted parent set Pa (q = |Pa|), let N(c, x) be the number of selected rows in which the parents take packed configuration c and gene v takes bit x ∈ {0, 1}, and N(c) = N(c, 0) + N(c, 1):

score(v, Pa) = Σ_c Σ_x  N(c, x) · ln( N(c, x) / N(c) )  −  (ln(n) / 2) · 2^q

The log-likelihood term rewards parents that make v more predictable; the −½·ln(n)·2^q complexity term penalises CPT size (2^q cells), which grows exponentially in the parent count. This penalty is the structural analogue of super::dependency_chain’s |r| < 2/√k significance filter: both suppress spurious dependencies that a univariate model would never pay for, here by requiring an edge’s likelihood improvement to outweigh the cost of doubling the child’s CPT. The score is computed on raw maximum-likelihood counts — never the Laplace-smoothed counts used for CPT estimation — so the penalty is the sole overfitting guard. Terms with N(c, x) = 0 contribute exactly 0 (the p·ln p → 0 limit), and configurations with N(c) = 0 contribute 0 likelihood while still counting toward the 2^q penalty. All scoring arithmetic is performed in f64.

Parent-configuration bit-packing

For a node v with parents[v] sorted ascending, a row’s parent configuration is packed as config = Σ_j bit(gene[parents[v][j]]) << j: parent j (in sorted order) contributes bit j. fit and sample use the identical packing, so the CPT index computed at sampling time matches the one used during estimation. See the cpt field.

Complexity

fit is O(D² · N · κ) per generation with gain caching: the first sweep scores all D² candidate edges (each an O(N·κ) counting pass), and after each accepted edge only the D entries sharing the affected child are rescored. It is fully host-side and sequential. sample is O(D) per drawn individual: one conditional Bernoulli draw per gene.

Binary gene convention

Genes are emitted as raw {0, 1} f32 values, so EdaParams::bounds clamps are a documented no-op (the PBIL / cGA precedent).

References

• Pelikan, Goldberg & Cantú-Paz (1999), BOA: The Bayesian optimization algorithm.

Structs

BayesianNetwork

Bayesian-network model for binary spaces (BOA).

BayesianNetworkParams

Per-run configuration for the BayesianNetwork model.

BayesianNetworkState

Fitted state for the BayesianNetwork model after one call to ProbabilityModel::fit.