Grammar-Guided Evolutionary Construction of Bayesian Networks - Foundations on Natural and Artificial Computation - page 62

Language's specifications {n, l, p, c}

External layer

CFG generator

CFG

GGGP core

Initialization

Selection Crossover Replacement

Fitness calculator

Fig. 1. Components and execution flow of EvoBANE

adopts the GGGP core and builds its own external layer modules in order to
compose a system that automatically generates Bayesian networks that solve
classification problems.
Figure 1 displays the execution flow of EvoBANE over the different compo-
nents of its architecture. The CFG generator receives the specifications of the
language that defines the solution space and outputs the context-free grammar
that generates that language. This grammar is used by the GGGP core to ini-
tialize a population of BN structures. They are first evaluated by the fitness cal-
culator module and then reinserted into the GGGP core for selection, crossover
and replacement. The following sections explain both external modules in detail.

2.1 The CFG Generator

A context-free grammar is defined as a 4-tuple G Σ T =

Ø, where Σ N is the alphabet of non-terminal symbols, Σ T is the alphabet of
terminal symbols,

=( Σ N ,Σ T ,S,P ) /Σ N ∩

is the set of production rules written
in Backus-Naur form. The CFG generator in EvoBANE automatically builds
grammars of this kind whose production rules generate individuals that codify
valid BN structures. For this purpose, the CFG generator needs four input pa-
rameters:

S is the axiom and P

n , the number of nodes of the networks to be codified; l ,thenumberof

layers in which those nodes are distributed ;p , the maximum permitted number

of input connections per node and c , the maximum permitted number of input

connections for the class node.
The number of nodes n is extracted from the application domain and

equals the number of feature variables observed for classifying an instance set.
The class node that contains the possible classes in which instances are classified
is counted as an extra node. Consequently, the total number of nodes is n

∈ N

+1 .

Nodes are distributed throughout a list of n ,

and the class node alone is stored in the last layer. A layer is an array that
contains a set of nodes arranged in a fixed order. Layers can be reordered to
generate different BN structures, but the position of the nodes within a layer
must be unchanged. Nodes arranged in layers are forward connected to each

l layers, where l ∈ N , 1 ≤ l ≤