Using Cooperative Coevolution for Data Mining of Bayesian Networks - Advanced Techniques in Knowledge Discovery and Data Mining - page 167

A

A
B
C
D
A node ordering

D B

constraints updates

Evolving

C

the collaborative structure

Fig. 6.8. The feedback mechanism.

optimal structure. If our degree of belief is less than a fixed threshold, the
belief factor, it casts doubt on the correctness of the edge. Hence, we allow
the presence of Y in X's possible parent set, which is otherwise forbidden.
As a result, a new

could exhibit an ordering that is different from the orig-
inal. However, the drawback is that we should watch out for possible cycles
formation.
Initialization. In the beginning, the chromosomes in the species populations
are randomly initialized. After the populations are initialized, we assemble

S

S
using the best individual from each population. Note that in this way, S will
probably contain cycle(s). Next, for each node N i in the network, we create
anewnetwork S that copies S (i.e., its S except that N i is a root node in

S as a
reference, we produce constraints on the species population of node N i such
that we assure each candidate solution, when substituted to

S is repaired for cycles. Using parent set is empty). Then the network

S , will create a

network that is still acyclic.
Searching Inside the Species Populations. For every species population,
the search space is equivalent to the possible parent set of the correspond-
ing node. As mentioned earlier, the possible parent set of a node is subject
to different changes during the course of searching. Consequently, the cor-
responding search process of the node faces both permanent and temporary
constraints. For the permanent constraints, we refer to the reduction of the
possible parent set due to the result from CI test. For the temporary con-
straints, we refer to the changes due to the aforementioned ordering implied
by

. As a result of these constraints, the length of the bit-string and the
mapping (i.e., which bit corresponds to which parent) are varying. 8
With the varying bit-string representation, a simple GA with crossover
and mutation is used to create a new population. However, instead of using

S

8 In the special case when the sizeofapossibleparentsetofanodeistoosmall,
it would clearly be unwise to search for the optimal combination using genetic
operators. Hence, for such cases, we simply list all the possibilities with the
entire population, and we inhibit any genetic operation to be performed on the
population.