Information Technology Reference
In-Depth Information
genetic operators that prevent the generation of illegal graph structures. Inso-
far as genetic algorithms do not solve the closure problem [9], crossover and
mutation operators may generate invalid individuals. For this reason, a repair
operator must be executed in order to transform invalid structures into DAGs
[10].
Different evolutionary approaches codify BNs into an array of nodes that
can only be forward connected [11,12,13]. In order to preserve DAG properties,
crossover and mutation operators perform order permutations over this array
only. The system presented in [14] replaces the crossover operator with several
specific mutation operators that perform controlled mutations on the genome of
the individuals. The work described in [15] implements a restricted crossover op-
erator that reduces the search space but always produces valid offspring. In the
same way, the system in [16] reduces the search space by only allowing the gen-
eration of naive-Bayes classifiers, whose straightforward codification decreases
the complexity of the evolutionary procedure and avoids the need for preserving
DAG structures.
This paper presents the EvoBANE (Evolutionary Bayesian Networks) system,
a grammar-guided evolutionary system for automatically generating Bayesian
networks that solve classification problems. EvoBANE implements a context-free
grammar (CFG) generator and a fitness calculator module. The CFG generator
inputs the specifications of the application domain, as well as the features of
the solutions to be built. It then outputs the CFG that generates the language
codifying the solution space of all the valid BN structures (individuals) for those
specifications and features. The fitness calculator first calculates the conditional
probability tables of the individuals by means of a probabilistic estimator [17],
and then evaluates the individual's accuracy as an instance classifier. EvoBANE
is based on GGEAS technology [18] to initialize and evolve a population of BN
structures. Evolution is achieved by means of a general-purpose grammatical
crossover operator [19] that avoids the closure problem without including a repair
operator. This way, EvoBANE always generates valid individuals, preserving
the DAG properties without using constraints that prevent it from exploring the
whole solution space. The eciency of EvoBANE for building Bayesian classifiers
has been tested in two different application domains. A genetic algorithm with
a single-point crossover operator was run on the same problems, and the results
were compared.
2TheEoBANESyem
EvoBANE's structure is an extension of the modular design implemented in
GGEAS. It consists of two independent components: a grammar-guided genetic
programming (GGGP) core and an external layer. The GGGP core is common
to every GGEAS implementation and remains unchanged whatever the cho-
sen application domain. The external layer is composed, in this case, of two
special-purpose modules: the CFG generator and the fitness calculator, whose
implementation directly depends on the GGEAS application domain. EvoBANE
 
Search WWH ::




Custom Search