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

other (even within the same layer). No backward connections are allowed in
order to preserve DAG properties. Connections between nodes represent their
conditional dependencies. Every node has a limited number of input connections
p ,where p

∈ N , 0 ≤ p ≤ n − 1 , except for the class node whose limit equals c ,so

that c n .

Grammars generated by the CFG generator are named after the four param-
eters

∈ N , 1 ≤ c ≤

in the form G nlpc . These four parameters vest the CFG gen-
erator of EvoBANE with the flexibility to modify the search space of a problem
depending on its complexity (given by the value of n ), allowing the evolutionary
system to find the simplest BN structure that best solves that problem. Insofar
as the value of n is fixed, the lower the value of l , p and c is, the smaller the
combinatorial explosion generated from reordering and connecting the nodes will
be. Notice that a grammar created with l

n , l , p and c

n , generates
the language of all the valid BN structures for a given n . On the other hand,
a grammar with l

= n , p = n − 1 and c =

= n , p =0 (complete conditional independence), and c = n

generates the language of all the valid naive-Bayes structures for a given n .

a)

G 3323 =( ∑ N , ∑ T , S, P)
∑ N = { S, ORDER, CONNECTIONS, CLASS }
∑ T = {0, 1, n 0 ,n 1 ,n 2 ,:}
P = {

S::= ORDER CONNECTIONS : CLASS
ORDER::= n 0 n 1 n 2 |n 0 n 2 n 1 |n 1 n 0 n 2 |n 1 n 2 n 0 |n 2 n 0 n 1 |n 2 n 1 n 0
CONNECTIONS::= 1:11 | 1:10 | 1:01 | 1:00 | 0:11 | 0:10 | 0:01 | 0:00
CLASS::= 111 | 110 | 101 | 100 | 011 | 010 | 001

}

b)
Genotype:

n 1 n 0 n 2 1:01:111

Sentence:

S

Phenotype:

n 1 n 0 n 2

ORDER CONNECTIONS : CLASS

n 1 n 0 n 2 1:01 111

class

Fig. 2. a) Sample grammar G 3323 automatically generated by the CFG generator. b)
Sample individual that belongs to the language generated by G 3323 .

Figure 2.a shows the sample grammar G 3323 generated by the CFG generator
for the values n . Every individual generated by the

grammar is composed of three parts: ORDER, CONNECTIONS and CLASS.
The first part references to the order in which the layers of nodes are arranged.
Insofar as the number of nodes and layers is the same in this example

=3 ,l =3 ,p =2 and c =3

,
every layer contains only one node. The second part refers to the list of input
connections of the n nodes in the individual, and the last part represents the
input connections of the class node. The set of terminal symbols stores one
symbol per node (except for the class node), a divider token “:” and numbers “1”
and “0”, which codify the presence or absence of a connection, respectively.
The first of the production rules displays the sequence of the three components
of an individual. The second production rule determines an ordered list of nodes

( n = l )