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

1. Set t, the generation count, to 0.
2. Create an initial population, Pop(t) of m random DAGs (m is the population size).
3. Each DAG in the population is evaluated using the MDL metric.
4. While t is less than the maximum number of generations,
• each DAG in Pop(t) produces one offspring by performing a number of mutation
operations. If there are cycles, a randomly picked edge in each cycle is removed.
• the DAGs in Pop(t) and all new offspring are stored in the intermediate popu-
lation Pop (t). The size of Pop (t) is 2 × m.
• conduct a number of pairwise competitions over all DAGs in Pop (t). For each
G i in the population, q other individuals are selected. Then the fitness of G i
and the q individuals are compared. The score of G i is the number of individuals
(out of q) that have lower fitness than G i .
• select the m highest-score individuals from Pop (t) with ties broken randomly.
The individuals are stored in Pop(t + 1).
• increment t by 1.
5. Return the individual that has the lowest MDL metric in any generation of a run
as the output of the algorithm.

Fig. 6.5. The MDLEP algorithm.

Furthermore, there is no crossover operation in EP, and the only operation
is mutation. An outline of the MDLEP algorithm is given in Fig. 6.5.
In essence, MDLEP uses four mutation operators that include simple,
reversion, move, and knowledge-guided mutations. The simple mutation op-
erator randomly picks an edge and either adds the edge to (when it is absent)
or removes it from (when it is already present) the network. The reverse mu-
tation operator randomly picks an edge from the network and reverses its
direction. The move mutation operator modifies the parent set of a node by
replacing one of the parents with a nonparent. The knowledge-guided muta-
tion operator is similar to simple mutation except that an edge is selected with
certain guidance. Briefly, each edge, X Y ,isweightedbyevaluatingthe

MDL score of node Y having only X as its parent. These scores are computed
and stored at the beginning. When the knowledge-guided mutation operator
determines that an existing edge should be removed, it retrieves the stored
MDL scores of all edges in the network and those edges with higher scores are
deleted with higher probabilities. On the other hand, if the knowledge-guided
mutation operator decides to add an edge to the network, it gets the stored
MDL scores of the edges that are absent and those edges with lower scores
will have higher probabilities of being added.
In their experiments, they tested their algorithm with data sets generated
from two benchmark networks, ALARM and PRINTD. They compared their
algorithm with the GA approach using the MDL metric, and they found
that MDLEP performs better in many aspects. In general, those networks
generated from MDLEP have smaller structural differences (in comparison
with the original network) and smaller MDL scores. In addition, MDLEP is
also faster, as it requires fewer generations to converge and generates less
invalid structures.

→