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

X X X X

X X X X

X X X X

X X X X
X X X X
X X X X

X X X X

X X X X

Fig. 6.7. Decomposition of the matrix representation into rows.

suggests the use of genetic algorithms for solving the problems. Following
the convention, we call the search population of each subproblem a species
population. Suppose there are n variables: there will be n different species
populations. Inside each population, we use a simple GA to search for the
optimal solution.
Although such a problem breakdown seems plausible, it is required that
the composite network must be acyclic. Obviously, illegal solutions could be
avoided only if each species population has the knowledge of others and works
cooperatively to prevent cycle formation. To realize this idea, we propose an
approach that uses the topological ordering of a graph as guidance. In the
following sections, we discuss our algorithm in detail.
A Feedback Mechanism. Noting that every legal network (i.e., an acyclic
graph) conforms to a topological ordering, it follows that we could use an
ordering as constraints for each species population to avoid cycle formation.
In particular, the possible parent set of a node, which defines the search space
of the corresponding species population, could only consist of nodes preceding
it in the given ordering. Consequently, a composite of the solutions from the
species populations will be acyclic (as it conforms to the given ordering).
Alternatively, it could be viewed as if we are to search the optimal network
for a given ordering.
Using this idea, we propose a feedback mechanism. Essentially, we use
the node ordering implied by the collaborative structure, , to produce con-

straints for each species population such that each candidate solution con-
forms to the ordering. Next, we update

S

with results from the species pop-
ulations and start another cycle. We show this idea in Fig. 6.8.
Nevertheless, there is a problem in the feedback mechanism, namely,

S

S
will conform to the same ordering for whatever update is made. Eventually,
this will drive the search process to return the optimal network for an initial
ordering, which is fine only if the ordering is optimal.
To tackle this problem, we therefore use

S only to approximate an or-

dering. In particular, every directed edge X is associated with a

certain degree of belief 7 that specifies the likelihood of finding the edge in the

→ Y in S

7 The value of the degree of belief is selected randomly from a uniform distribution
between 0.0and1.0.